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

1. Trong bài toán tìm kiếm tuần tự, nếu phần tử cần tìm nằm ở cuối danh sách, số phép so sánh ít nhất cần thực hiện là bao nhiêu?

A. 1 phép so sánh.

B. N phép so sánh, với N là độ dài danh sách.

C. N-1 phép so sánh, với N là độ dài danh sách.

D. Phụ thuộc vào giá trị của phần tử cần tìm.

2. Nếu bạn cần tìm kiếm một phần tử trong một tập dữ liệu rất lớn mà việc sắp xếp trước là khả thi, thuật toán nào sau đây thường được ưu tiên nhất về hiệu suất?

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

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

C. Tìm kiếm nhảy.

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

3. Điểm yếu lớn nhất của tìm kiếm tuần tự là gì?

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

B. Độ phức tạp thời gian cao đối với danh sách lớn.

C. Cần nhiều bộ nhớ hơn các thuật toán khác.

D. Khó cài đặt.

4. Nếu danh sách có 16 phần tử được sắp xếp, số lần so sánh tối đa cho tìm kiếm nhị phân là bao nhiêu?

A. 4 lần

B. 5 lần

C. 8 lần

D. 16 lần

5. Trong 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, bước tiếp theo sẽ tìm kiếm ở đâu?

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

B. Nửa cuối của danh sách.

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

D. Phần tử ngay trước phần tử ở giữa.

6. Trong tìm kiếm nhị phân, nếu phần tử cần tìm nhỏ hơn phần tử ở giữa, bước tiếp theo sẽ tìm kiếm ở đâu?

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

B. Nửa cuối của danh sách.

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

D. Phần tử ngay sau phần tử ở giữa.

7. Khi phần tử cần tìm không có trong danh sách đã sắp xếp, tìm kiếm nhị phân sẽ kết thúc như thế nào?

A. Trả về phần tử lớn nhất nhỏ hơn phần tử cần tìm.

B. Trả về phần tử nhỏ nhất lớn hơn phần tử cần tìm.

C. Trả về chỉ số mà phần tử đó nên được chèn vào để duy trì thứ tự.

D. Trả về một giá trị chỉ thị không tìm thấy (ví dụ: -1).

8. Khi tìm kiếm một phần tử trong danh sách rỗng bằng thuật toán tìm kiếm tuần tự, kết quả sẽ là gì?

A. Trả về phần tử đầu tiên của danh sách.

B. Trả về một lỗi hoặc chỉ số không hợp lệ (ví dụ: -1).

C. Thực hiện 1 phép so sánh và trả về kết quả không tìm thấy.

D. Chương trình bị treo.

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

A. Danh sách liên kết đơn chưa sắp xếp.

B. Cây tìm kiếm nhị phân.

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

D. Hash Table.

10. Độ phức tạp thời gian của thuật toán tìm kiếm Exponentiation Search kết hợp với tìm kiếm nhị phân là bao nhiêu, với N là kích thước của danh sách?

A. O(n)

B. O(log n)

C. O(log i), với i là vị trí của phần tử cần tìm.

D. O(n log n)

11. Điều kiện tiên quyết để áp dụng thuật toán tìm kiếm nhị phân là gì?

A. Danh sách phải được sắp xếp theo thứ tự giảm dần.

B. Danh sách phải được sắp xếp theo thứ tự tăng dần hoặc giảm dần.

C. Danh sách phải có kích thước là lũy thừa của 2.

D. Các phần tử trong danh sách phải là duy nhất.

12. Độ phức tạp thời gian của thuật toán tìm kiếm tuần tự (linear search) là gì?

A. O(log n)

B. O(n)

C. O(n log n)

D. O(n^2)

13. Ư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 tuần tự là gì?

A. Tìm kiếm được trên danh sách chưa sắp xếp.

B. Tốc độ tìm kiếm nhanh hơn đáng kể trên danh sách lớn.

C. Yêu cầu ít bộ nhớ hơn.

D. Dễ cài đặt hơn.

14. Độ phức tạp thời gian của thuật toán tìm kiếm nhị phân (binary search) là gì?

A. O(log n)

B. O(n)

C. O(n log n)

D. O(n^2)

15. Thuật toán tìm kiếm Exponentiation Search (hay Exponential Search) phù hợp với trường hợp nào?

A. Tìm kiếm trong một dải giới hạn.

B. Tìm kiếm trong một danh sách có kích thước không xác định hoặc rất lớn.

C. Tìm kiếm trên dữ liệu không sắp xếp.

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

16. Trong thuật toán tìm kiếm nhị phân đệ quy, trường hợp cơ sở (base case) là gì?

A. Khi phần tử được tìm thấy.

B. Khi chỉ số bắt đầu lớn hơn chỉ số kết thúc.

C. Khi phần tử giữa bằng phần tử cần tìm.

D. Khi danh sách chỉ còn 1 phần tử.

17. Trong tìm kiếm nhị phân, sau mỗi bước so sánh, không gian tìm kiếm được thu hẹp như thế nào?

A. Bỏ đi một nửa các phần tử ở đầu danh sách.

B. Bỏ đi một nửa các phần tử ở cuối danh sách.

C. Bỏ đi một nửa không gian tìm kiếm không chứa phần tử cần tìm.

D. Bỏ đi toàn bộ các phần tử đã so sánh.

18. Độ phức tạp thời gian trung bình của tìm kiếm nội suy trên dữ liệu phân bố đều là bao nhiêu?

A. O(log n)

B. O(n)

C. O(log(log n))

D. O(n log n)

19. Thuật toán tìm kiếm nội suy (Interpolation Search) hoạt động tốt nhất trên loại dữ liệu nào?

A. Dữ liệu phân bố đều.

B. Dữ liệu phân bố theo hàm mũ.

C. Dữ liệu có giá trị trùng lặp nhiều.

D. Dữ liệu ngẫu nhiên.

20. Tìm kiếm nhảy (Jump Search) hoạt động bằng cách nào?

A. So sánh tuần tự từng phần tử.

B. Chia danh sách thành các khối và nhảy qua các khối.

C. Chia danh sách thành hai nửa và tìm kiếm đệ quy.

D. Dự đoán vị trí dựa trên giá trị.

21. Kích thước khối tối ưu cho tìm kiếm nhảy thường được chọn như thế nào để đạt hiệu quả tốt nhất?

A. Bằng N/2, với N là độ dài danh sách.

B. Bằng căn bậc hai của N (sqrt(N)).

C. Bằng log(N).

D. Bằng 1.

22. So với tìm kiếm nhị phân, tìm kiếm nội suy có thể nhanh hơn trong trường hợp nào?

A. Khi danh sách rất nhỏ.

B. Khi các phần tử trong danh sách có giá trị gần nhau.

C. Khi danh sách được sắp xếp và các phần tử phân bố đều.

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

23. Khi thực hiện tìm kiếm tuần tự trên một danh sách, nếu phần tử cần tìm là phần tử đầu tiên, số phép so sánh cần là bao nhiêu?

A. 0 phép so sánh.

B. 1 phép so sánh.

C. N phép so sánh, với N là độ dài danh sách.

D. Phụ thuộc vào vị trí của phần tử.

24. Độ phức tạp thời gian của tìm kiếm nhảy trên danh sách được sắp xếp là bao nhiêu?

A. O(n)

B. O(log n)

C. O(sqrt(n))

D. O(n log n)

25. Khi nào thuật toán tìm kiếm tuần tự là lựa chọn tốt nhất?

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

B. Khi danh sách nhỏ hoặc không chắc chắn về việc phần tử có tồn tại.

C. Khi cần tối ưu hóa tốc độ tìm kiếm.

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