Trắc nghiệm Kết nối Tin học 11 KHMT bài 19 Bài toán tìm kiếm

1. Giả sử bạn có một danh sách các số nguyên đã sắp xếp và bạn muốn tìm một số cụ thể. Bạn nên ưu tiên sử dụng thuật toán nào để đạt hiệu suất tốt nhất?

A. Tìm kiếm tuần tự

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

C. Duyệt qua từng phần tử theo thứ tự ngược lại

D. Sử dụng băm (hashing)

2. Tìm kiếm nhị phân trên một mảng có 1000 phần tử. Nếu phần tử cần tìm nằm ở vị trí cuối cùng, số lần so sánh tối đa sẽ là bao nhiêu?

A. Khoảng 10

B. Khoảng 500

C. 1000

D. log 1000

3. Độ phức tạp thời gian của thuật toán tìm kiếm nhị phân trong trường hợp xấu nhất là bao nhiêu, với n là số phần tử trong danh sách?

A. O(1)

B. O(log n)

C. O(n)

D. O(n^2)

4. Đâu là nhược điểm chính của tìm kiếm tuần tự khi xử lý tập dữ liệu lớn?

A. Yêu cầu danh sách phải được sắp xếp.

B. Tốn nhiều bộ nhớ để lưu trữ.

C. Tốc độ tìm kiếm chậm, đặc biệt với dữ liệu lớn.

D. Không thể tìm thấy phần tử nếu nó không tồn tại.

5. Độ phức tạp thời gian (time complexity) của thuật toán tìm kiếm tuần tự trong trường hợp xấu nhất là bao nhiêu, với n là số phần tử trong danh sách?

A. O(1)

B. O(log n)

C. O(n)

D. O(n log n)

6. Đâu là một hạn chế của việc sử dụng cây tìm kiếm nhị phân cân bằng (balanced binary search tree) cho bài toán tìm kiếm?

A. Độ phức tạp tìm kiếm trung bình cao.

B. Yêu cầu dữ liệu phải được sắp xếp trước.

C. Phức tạp hơn trong việc triển khai so với tìm kiếm tuần tự.

D. Tốn nhiều bộ nhớ hơn mảng.

7. Khi nào thì tìm kiếm nhị phân có thể tốn nhiều thời gian hơn tìm kiếm tuần tự?

A. Khi danh sách rất lớn và đã sắp xếp.

B. Khi phần tử cần tìm nằm ở vị trí đầu tiên của danh sách đã sắp xếp.

C. Khi danh sách nhỏ và cần thực hiện tìm kiếm một lần duy nhất.

D. Khi danh sách không được sắp xếp.

8. Khi nào tìm kiếm tuần tự có thể là lựa chọn tốt hơn tìm kiếm nhị phân?

A. Khi danh sách rất lớn và đã sắp xếp.

B. Khi danh sách rất nhỏ hoặc không có thứ tự.

C. Khi cần tìm kiếm nhiều lần trên cùng một danh sách.

D. Khi bộ nhớ là yếu tố hạn chế nghiêm ngặt.

9. Yếu tố nào sau đây không ảnh hưởng đến hiệu suất của tìm kiếm tuần tự?

A. Vị trí của phần tử cần tìm.

B. Số lượng phần tử trong danh sách.

C. Tính sắp xếp của danh sách.

D. Tốc độ của CPU.

10. Thuật toán tìm kiếm nhị phân có thể được mô tả là một thuật toán chia để trị (divide and conquer) vì lý do gì?

A. Nó chia nhỏ bài toán thành các bài toán con giống nhau cho đến khi đạt kích thước đủ nhỏ để giải quyết trực tiếp.

B. Nó luôn tìm phần tử ở giữa trước.

C. Nó cần dữ liệu được sắp xếp để hoạt động.

D. Nó chỉ hoạt động trên các mảng.

11. Trong trường hợp dữ liệu phân bố không đều và không thể sắp xếp, phương pháp tìm kiếm nào thường được cân nhắc sử dụng?

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

B. Tìm kiếm tuần tự

C. Sử dụng bảng băm (Hash Table)

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

12. Khi nào thì việc xây dựng một bảng băm (hash table) để thực hiện tìm kiếm có thể là phương pháp hiệu quả nhất?

A. Khi dữ liệu cần tìm kiếm có thứ tự.

B. Khi cần thực hiện nhiều thao tác tìm kiếm trên một tập dữ liệu tĩnh.

C. Khi dữ liệu có phân bố rất ngẫu nhiên và không thể sắp xếp.

D. Khi bộ nhớ là yếu tố hạn chế chính.

13. Trong bài toán tìm kiếm tuần tự, nếu phần tử cần tìm nằm ở vị trí cuối cùng của danh sách, số lần so sánh tối đa xảy ra là bao nhiêu?

A. n

B. n/2

C. 1

D. log n

14. Nếu một danh sách có 16 phần tử và sử dụng tìm kiếm nhị phân, số lần so sánh tối đa để tìm thấy một phần tử là bao nhiêu?

A. 4

B. 8

C. 16

D. log 16

15. Nếu một danh sách gồm N phần tử, việc tìm kiếm một phần tử bằng tìm kiếm tuần tự có thể yêu cầu bao nhiêu thao tác so sánh trong trường hợp xấu nhất?

A. 1

B. N/2

C. N

D. log N

16. Cấu trúc dữ liệu nào sau đây không phù hợp để áp dụng thuật toán tìm kiếm nhị phân một cách trực tiếp và hiệu quả?

A. Mảng (Array)

B. Danh sách liên kết đơn

C. Danh sách liên kết đôi

D. Bảng băm (Hash Table)

17. Trong bài toán tìm kiếm, độ phức tạp không gian (space complexity) của thuật toán tìm kiếm tuần tự thường là bao nhiêu?

A. O(1)

B. O(n)

C. O(log n)

D. O(n^2)

18. Thuật toán tìm kiếm nhị phân có thể được áp dụng trực tiếp cho cấu trúc dữ liệu nào sau đây?

A. Danh sách liên kết không sắp xếp

B. Mảng đã sắp xếp

C. Cây nhị phân không cân bằng

D. Đồ thị có hướng

19. Đâu là một ví dụ về cấu trúc dữ liệu cho phép tìm kiếm với độ phức tạp thời gian trung bình O(1)?

A. Mảng đã sắp xếp

B. Cây tìm kiếm nhị phân cân bằng

C. Bảng băm (Hash Table)

D. Danh sách liên kết

20. Trong các thuật toán tìm kiếm, khái niệm trường hợp tốt nhất (best case) đề cập đến tình huống nào?

A. Thời gian tìm kiếm nhanh nhất có thể.

B. Số lần so sánh ít nhất có thể.

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

D. Tất cả các lựa chọn trên.

21. Trong tìm kiếm nhị phân, khi so sánh phần tử cần tìm với phần tử ở giữa danh sách, nếu phần tử cần tìm nhỏ hơn, ta sẽ tiếp tục tìm kiếm ở đâu?

A. Nửa đầu của danh sách.

B. Nửa sau của danh sách.

C. Toàn bộ danh sách.

D. Bỏ qua bước này và so sánh với phần tử kế tiếp.

22. Khi tìm kiếm một phần tử trong danh sách đã sắp xếp, thuật toán nào thường hiệu quả hơn về mặt tốc độ đối với tập dữ liệu lớn?

A. Tìm kiếm tuần tự

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

C. Tìm kiếm trên cây nhị phân

D. Tìm kiếm theo lớp

23. 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 đối với danh sách được tìm kiếm?

A. Danh sách phải được sắp xếp tăng dần.

B. Danh sách phải được sắp xếp giảm dần.

C. Danh sách phải có các phần tử phân biệt.

D. Danh sách phải là danh sách liên kết.

24. Khi sử dụng tìm kiếm nhị phân, nếu phần tử cần tìm lớn hơn phần tử ở giữa, ta sẽ tiếp tục tìm kiếm ở đâu?

A. Nửa đầu của danh sách.

B. Nửa sau của danh sách.

C. Toàn bộ danh sách.

D. Kiểm tra lại điều kiện đầu vào.

25. Thuật toán tìm kiếm Interpolation Search (Tìm kiếm nội suy) thường hoạt động hiệu quả hơn tìm kiếm nhị phân trong trường hợp nào?

A. Khi các phần tử trong danh sách phân bố ngẫu nhiên.

B. Khi các phần tử trong danh sách phân bố đều hoặc gần đều.

C. Khi danh sách quá lớn không thể lưu trong bộ nhớ.

D. Khi cần tìm kiếm một phần tử có khả năng xuất hiện ở đầu danh sách.