[Cánh diều] Trắc nghiệm Tin học 11 KHMT bài 7 Lập trình giải bài toán tìm kiếm

1. Nếu một danh sách có 1024 phần tử, ước tính số lần so sánh tối đa cần thiết để tìm một phần tử bằng tìm kiếm nhị phân là bao nhiêu?

A. 10 (vì 2^10 = 1024).

B. 1024.

C. Khoảng 512.

D. Không thể xác định.

2. Trong Python, hàm nào sau đây thường được sử dụng để tìm kiếm một phần tử trong danh sách (list) theo cách đơn giản nhất?

A. Sử dụng toán tử `in` hoặc phương thức `.index()`.

B. Sử dụng hàm `sort()`.

C. Sử dụng hàm `append()`.

D. Sử dụng hàm `len()`.

3. Trong lập trình, khái niệm trường hợp xấu nhất (worst-case scenario) khi nói về thuật toán tìm kiếm đề cập đến điều gì?

A. Số phép toán hoặc thời gian cần thiết để hoàn thành thuật toán trong điều kiện kém thuận lợi nhất.

B. Số phép toán hoặc thời gian cần thiết để hoàn thành thuật toán trong điều kiện thuận lợi nhất.

C. Số phép toán hoặc thời gian trung bình để hoàn thành thuật toán.

D. Số phép toán hoặc thời gian cần thiết để tìm thấy phần tử đầu tiên.

4. Khi so sánh tìm kiếm tuyến tính và tìm kiếm nhị phân, yếu tố nào là khác biệt quan trọng nhất về mặt hiệu suất trên dữ liệu lớn?

A. Khả năng xử lý dữ liệu không sắp xếp (tuyến tính làm được, nhị phân không).

B. Tốc độ thực thi trên tập dữ liệu lớn (nhị phân nhanh hơn).

C. Yêu cầu về bộ nhớ (cả hai đều tương tự).

D. Độ phức tạp trong việc cài đặt (tuyến tính đơn giản hơn).

5. Một nhà khoa học dữ liệu đang làm việc với một tập dữ liệu lớn chứa thông tin về hàng triệu giao dịch. Họ cần tìm tất cả các giao dịch có giá trị lớn hơn một ngưỡng nhất định. Phương pháp tìm kiếm nào có khả năng hiệu quả nhất cho tác vụ này, nếu dữ liệu có thể được sắp xếp?

A. Tìm kiếm nhị phân sau khi đã sắp xếp dữ liệu theo giá trị giao dịch.

B. Tìm kiếm tuyến tính trên dữ liệu chưa sắp xếp.

C. Sử dụng hàm băm (hashing) để nhóm các giao dịch.

D. Thuật toán sắp xếp nổi bọt (bubble sort) để tìm các giao dịch lớn.

6. Khi áp dụng tìm kiếm nhị phân, nếu phần tử cần tìm nhỏ hơn phần tử ở giữa, thì bước tiếp theo là gì?

A. Tiếp tục tìm kiếm trong nửa bên trái của danh sách.

B. Tiếp tục tìm kiếm trong nửa bên phải của danh sách.

C. So sánh với phần tử đầu tiên của danh sách.

D. Dừng tìm kiếm vì phần tử không tồn tại.

7. Xét một danh sách các chuỗi chưa được sắp xếp: [apple, banana, cherry, date, fig]. Nếu tìm kiếm chuỗi cherry bằng thuật toán tìm kiếm tuyến tính, trung bình sẽ cần thực hiện bao nhiêu phép so sánh?

A. Khoảng 3 phép so sánh (vì cherry ở vị trí thứ 3).

B. 5 phép so sánh (vì có 5 phần tử).

C. 1 phép so sánh (nếu may mắn tìm thấy ngay).

D. Số phép so sánh không thể xác định trước.

8. Xét một danh sách được sắp xếp tăng dần các số nguyên: [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]. Nếu sử dụng thuật toán tìm kiếm nhị phân để tìm số 23, bước đầu tiên sẽ là so sánh 23 với phần tử nào trong danh sách?

A. Phần tử ở giữa danh sách (ví dụ: 16).

B. Phần tử đầu tiên trong danh sách (ví dụ: 2).

C. Phần tử cuối cùng trong danh sách (ví dụ: 91).

D. Bất kỳ phần tử nào ngẫu nhiên trong danh sách.

9. Phân tích sự khác biệt cơ bản nhất giữa tìm kiếm nhị phân và tìm kiếm nội suy (Interpolation Search) khi áp dụng trên dữ liệu có phân phối đều:

A. Tìm kiếm nội suy ước tính vị trí dựa trên giá trị phần tử, trong khi tìm kiếm nhị phân chỉ chia đôi phạm vi.

B. Tìm kiếm nhị phân hiệu quả hơn trên mọi loại dữ liệu đã sắp xếp.

C. Tìm kiếm nội suy yêu cầu dữ liệu phải có phân phối chuẩn.

D. Tìm kiếm nhị phân không cần dữ liệu sắp xếp.

10. Khi một thuật toán tìm kiếm trả về một chỉ số (index) hợp lệ, điều đó có nghĩa là gì?

A. Phần tử cần tìm đã được tìm thấy tại vị trí đó trong tập hợp dữ liệu.

B. Phần tử cần tìm không tồn tại trong tập hợp dữ liệu.

C. Tập hợp dữ liệu đã được sắp xếp.

D. Thuật toán đã hoàn thành mà không tìm thấy phần tử.

11. Phát biểu nào sau đây là SAI về thuật toán tìm kiếm trong cấu trúc dữ liệu dạng cây tìm kiếm nhị phân (Binary Search Tree - BST)?

A. Việc tìm kiếm có thể thực hiện bằng cách so sánh phần tử cần tìm với nút hiện tại và đi theo nhánh trái hoặc phải tương ứng.

B. Độ phức tạp thời gian trung bình của tìm kiếm trên BST cân bằng là O(log N).

C. BST yêu cầu dữ liệu phải được sắp xếp trước khi xây dựng cây.

D. Nếu BST bị mất cân bằng nghiêm trọng (biến thành danh sách liên kết), độ phức tạp tìm kiếm có thể trở thành O(N).

12. Một lập trình viên đang xem xét lại mã nguồn và thấy một vòng lặp duyệt qua từng phần tử của một mảng để kiểm tra một điều kiện. Điều này mô tả hành vi của thuật toán nào?

A. Tìm kiếm tuyến tính.

B. Tìm kiếm nhị phân.

C. Sắp xếp chọn (Selection Sort).

D. Tìm kiếm nội suy.

13. Nếu một hàm tìm kiếm trả về một giá trị đặc biệt (ví dụ: -1 hoặc `None`), điều này thường biểu thị điều gì?

A. Phần tử cần tìm không có trong tập hợp dữ liệu.

B. Phần tử cần tìm nằm ở vị trí đầu tiên.

C. Tập hợp dữ liệu trống.

D. Đã xảy ra lỗi trong quá trình tìm kiếm.

14. Trong các thuật toán tìm kiếm được học, thuật toán nào có khả năng xử lý hiệu quả nhất với một tập dữ liệu rất lớn và đã được sắp xếp mà không cần biết trước vị trí của phần tử cần tìm?

A. Tìm kiếm nhị phân.

B. Tìm kiếm tuyến tính.

C. Tìm kiếm nhảy (Jump Search).

D. Tìm kiếm đệ quy.

15. Thuật toán tìm kiếm nhị phân yêu cầu điều kiện tiên quyết nào để hoạt động chính xác?

A. Danh sách dữ liệu phải được sắp xếp theo một thứ tự nhất định (tăng hoặc giảm).

B. Danh sách dữ liệu phải có kích thước là lũy thừa của 2.

C. Danh sách dữ liệu phải chứa các phần tử duy nhất, không trùng lặp.

D. Danh sách dữ liệu phải được lưu trữ dưới dạng cấu trúc cây.

16. Phát biểu nào sau đây mô tả đúng về độ phức tạp thời gian (time complexity) của thuật toán tìm kiếm nhị phân trên một mảng gồm N phần tử đã sắp xếp?

A. O(log N).

B. O(N).

C. O(N^2).

D. O(1).

17. Phát biểu nào sau đây mô tả đúng vai trò của index (chỉ số) trong một mảng hoặc danh sách khi thực hiện tìm kiếm?

A. Chỉ số là một số nguyên xác định vị trí của một phần tử cụ thể trong cấu trúc dữ liệu, giúp truy cập trực tiếp hoặc xác định phạm vi tìm kiếm.

B. Chỉ số là giá trị của phần tử được tìm thấy.

C. Chỉ số chỉ được sử dụng trong tìm kiếm nhị phân.

D. Chỉ số là tên của thuật toán tìm kiếm.

18. Trong trường hợp tìm kiếm một phần tử không tồn tại trong một danh sách lớn được sắp xếp, thuật toán tìm kiếm nhị phân sẽ thực hiện bao nhiêu bước so với tìm kiếm tuyến tính?

A. Ít bước hơn nhiều.

B. Nhiều bước hơn.

C. Số bước tương đương.

D. Không thể thực hiện được.

19. Trong lập trình, bài toán tìm kiếm thường đề cập đến việc tìm kiếm một phần tử cụ thể trong một tập hợp dữ liệu. Phát biểu nào sau đây mô tả đúng nhất mục tiêu chính của bài toán tìm kiếm?

A. Xác định vị trí của phần tử cần tìm hoặc xác nhận sự tồn tại của nó trong tập hợp dữ liệu.

B. Sắp xếp lại toàn bộ tập hợp dữ liệu theo một thứ tự nhất định.

C. Thực hiện các phép tính toán học trên tất cả các phần tử của tập hợp dữ liệu.

D. Thêm một phần tử mới vào tập hợp dữ liệu.

20. Trong Python, phương thức `.count()` của danh sách (list) được sử dụng để làm gì?

A. Đếm số lần xuất hiện của một phần tử cụ thể trong danh sách.

B. Tìm vị trí đầu tiên của một phần tử.

C. Kiểm tra xem một phần tử có tồn tại trong danh sách hay không.

D. Xóa tất cả các phần tử trùng lặp khỏi danh sách.

21. Thuật toán tìm kiếm tuyến tính (hay tìm kiếm tuần tự) hoạt động như thế nào?

A. So sánh phần tử cần tìm với từng phần tử trong danh sách từ đầu đến cuối cho đến khi tìm thấy hoặc hết danh sách.

B. Chia đôi danh sách và so sánh với phần tử ở giữa.

C. Chia danh sách thành các nhóm nhỏ và tìm kiếm trong nhóm chứa phần tử có khả năng.

D. Sử dụng cấu trúc dữ liệu cây để tìm kiếm hiệu quả.

22. Khi nào thì việc sử dụng thuật toán tìm kiếm tuyến tính là hợp lý, mặc dù nó không hiệu quả bằng tìm kiếm nhị phân?

A. Khi danh sách dữ liệu nhỏ hoặc không được sắp xếp.

B. Khi cần tìm kiếm phần tử ở vị trí đầu tiên.

C. Khi danh sách dữ liệu có kích thước rất lớn và được sắp xếp.

D. Khi hiệu suất thời gian xử lý là yếu tố quan trọng nhất.

23. Xét một danh sách không sắp xếp. Nếu bạn muốn tìm phần tử lớn nhất, phương pháp nào là hiệu quả nhất?

A. Duyệt qua toàn bộ danh sách, giữ lại giá trị lớn nhất tìm được cho đến thời điểm đó.

B. Sử dụng tìm kiếm nhị phân.

C. Chỉ xem xét phần tử đầu tiên và cuối cùng của danh sách.

D. Sử dụng thuật toán sắp xếp tăng dần rồi lấy phần tử cuối.

24. Một ứng dụng cần tìm kiếm nhanh chóng các thông tin hồ sơ dựa trên mã số duy nhất. Nếu mã số này được sử dụng làm khóa trong một bảng băm (hash table), thì thời gian tìm kiếm trung bình sẽ là bao nhiêu?

A. O(1) (hằng số).

B. O(log N).

C. O(N).

D. O(N^2).

25. Đâu là ưu điểm chính của thuật toán tìm kiếm nhị phân so với tìm kiếm tuyến tính khi áp dụng trên một danh sách lớn đã được sắp xếp?

A. Hiệu quả hơn về thời gian xử lý (nhanh hơn).

B. Đơn giản hơn trong việc cài đặt.

C. Không yêu cầu danh sách phải được sắp xếp.

D. Có thể tìm kiếm trên các cấu trúc dữ liệu không có thứ tự.