1. Trong tìm kiếm nhị phân, tại sao việc xác định "phần tử ở giữa" lại quan trọng?
A. Nó giúp bỏ qua một nửa phạm vi tìm kiếm không cần thiết.
B. Nó đảm bảo thuật toán luôn kết thúc.
C. Nó tăng số lượng phép so sánh.
D. Nó là phần tử duy nhất cần so sánh.
2. Trong tìm kiếm nhị phân, nếu phạm vi tìm kiếm còn lại chỉ có một phần tử, và phần tử đó không phải là phần tử cần tìm, điều này có ý nghĩa gì?
A. Phần tử cần tìm nằm ở vị trí đó.
B. Phần tử cần tìm đã được tìm thấy ở bước trước.
C. Phần tử cần tìm không có trong danh sách.
D. Cần thực hiện thêm một phép so sánh nữa.
3. Việc "sắp xếp" danh sách trước khi tìm kiếm nhị phân là một bước tiền xử lý, có ý nghĩa gì?
A. Giúp tìm kiếm tuần tự nhanh hơn.
B. Cho phép thuật toán nhị phân chia đôi phạm vi tìm kiếm một cách hiệu quả.
C. Tăng cường bảo mật cho dữ liệu.
D. Giảm dung lượng bộ nhớ cần thiết.
4. Độ phức tạp thời gian 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?
A. O(1)
B. O(log N)
C. O(N)
D. O(N^2)
5. Khi thực hiện tìm kiếm tuần tự trên một danh sách, các phần tử được kiểm tra theo thứ tự nào?
A. Ngẫu nhiên.
B. Từ cuối về đầu.
C. Theo thứ tự xuất hiện trong danh sách.
D. Dựa trên giá trị của phần tử.
6. Ư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. Có thể áp dụng trên danh sách không được sắp xếp.
B. Tốc độ tìm kiếm nhanh hơn đáng kể khi danh sách lớn.
C. Dễ dàng cài đặt hơn.
D. Sử dụng ít bộ nhớ hơn.
7. Giả sử bạn có một danh sách rất lớn các số nguyên và bạn cần thường xuyên tìm kiếm các số này. Việc sắp xếp danh sách một lần trước khi thực hiện các thao tác tìm kiếm sẽ mang lại lợi ích gì?
A. Giúp tìm kiếm tuần tự nhanh hơn.
B. Cho phép sử dụng tìm kiếm nhị phân hiệu quả.
C. Làm giảm số lượng phần tử cần lưu trữ.
D. Tăng tốc độ ghi dữ liệu.
8. Tìm kiếm nhị phân có thể được coi là một dạng của chiến lược "chia để trị" không?
A. Không, nó là một thuật toán tuyến tính.
B. Có, vì nó chia nhỏ bài toán thành các bài toán con nhỏ hơn.
C. Không, nó chỉ hiệu quả trên các mảng có kích thước cố định.
D. Có, nhưng chỉ khi danh sách được sắp xếp theo thứ tự giảm dần.
9. 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, phạm vi tìm kiếm tiếp theo sẽ là:
A. Nửa đầu của danh sách (trước phần tử giữa).
B. Nửa cuối của danh sách (sau phần tử giữa).
C. Toàn bộ danh sách.
D. Chỉ phần tử ở giữa.
10. Trong tìm kiếm tuần tự, nếu phần tử cần tìm xuất hiện nhiều lần trong danh sách, thuật toán sẽ trả về vị trí nào?
A. Vị trí của lần xuất hiện đầu tiên.
B. Vị trí của lần xuất hiện cuối cùng.
C. Vị trí ngẫu nhiên trong số các lần xuất hiện.
D. Thông báo rằng có nhiều lần xuất hiện.
11. Thuật toán tìm kiếm nào phù hợp nhất để tìm một từ trong một cuốn từ điển được sắp xếp theo thứ tự bảng chữ cái?
A. Tìm kiếm tuần tự.
B. Tìm kiếm nhị phân.
C. Tìm kiếm đồ thị.
D. Tìm kiếm băm.
12. Khi nào tìm kiếm tuần tự có thể hiệu quả 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 nhỏ hoặc không được sắp xếp.
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ớ có hạn.
13. Điểm khác biệt cơ bản nhất giữa tìm kiếm tuần tự và tìm kiếm nhị phân nằm ở đâu?
A. Yêu cầu về sắp xếp của dữ liệu.
B. Số lượng phép so sánh tối đa.
C. Cách thức truy cập các phần tử.
D. Khả năng tìm kiếm trên dữ liệu không có cấu trúc.
14. Nếu bạn đang làm việc với một tập dữ liệu rất lớn và cần tìm kiếm một giá trị cụ thể, việc nào sau đây KHÔNG nên làm nếu bạn muốn tối ưu hóa tốc độ tìm kiếm?
A. Sắp xếp danh sách và sử dụng tìm kiếm nhị phân.
B. Duy trì danh sách ở dạng không sắp xếp và dùng tìm kiếm tuần tự.
C. Sử dụng cấu trúc dữ liệu phù hợp khác nếu có.
D. Chia nhỏ danh sách thành các phần nhỏ hơn.
15. Trong tìm kiếm nhị phân, nếu phần tử cần tìm bằng với phần tử ở giữa, thuật toán sẽ làm gì tiếp theo?
A. Tiếp tục tìm kiếm ở nửa đầu.
B. Tiếp tục tìm kiếm ở nửa cuối.
C. Dừng lại và trả về vị trí của phần tử.
D. So sánh với phần tử tiếp theo.
16. Khái niệm "phạm vi tìm kiếm" (search space) trong bài toán tìm kiếm đề cập đến:
A. Số lần so sánh.
B. Tập hợp tất cả các phần tử có thể chứa phần tử cần tìm.
C. Kích thước của danh sách.
D. Tốc độ thực thi của thuật toán.
17. Nếu danh sách cần tìm kiếm rất lớn và đã được sắp xếp, thuật toán nào thường được ưu tiên sử dụng hơn?
A. Tìm kiếm tuần tự.
B. Tìm kiếm nhị phân.
C. Tìm kiếm nội suy.
D. Tìm kiếm nhảy.
18. Trong tìm kiếm tuần tự, nếu phần tử cần tìm nằm ở vị trí đầu tiên của danh sách, số phép so sánh là bao nhiêu?
A. N (với N là số phần tử)
B. 1
C. N/2
D. 0
19. Trong thuật toán 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, phạm vi tìm kiếm tiếp theo sẽ là:
A. Nửa đầu của danh sách (trước phần tử giữa).
B. Nửa cuối của danh sách (sau phần tử giữa).
C. Toàn bộ danh sách.
D. Chỉ phần tử ở giữa.
20. Độ 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?
A. O(1)
B. O(log N)
C. O(N)
D. O(N log N)
21. Trong bài toán tìm kiếm tuần tự, nếu danh sách cần tìm kiếm có N phần tử và phần tử cần tìm nằm ở vị trí cuối cùng, số phép so sánh tối đa cần thực hiện là bao nhiêu?
22. Cho danh sách đã sắp xếp: [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]. Khi tìm kiếm phần tử 23 bằng thuật toán tìm kiếm nhị phân, phép so sánh đầu tiên sẽ so sánh với phần tử nào?
23. Khi một thuật toán tìm kiếm tuần tự không tìm thấy phần tử cần tìm trong danh sách, nó sẽ thực hiện bao nhiêu phép so sánh?
A. 0
B. 1
C. N (với N là số phần tử)
D. N/2
24. Yếu tố nào sau đây không phải là một "điều kiện tiên quyết" cho tìm kiếm nhị phân?
A. Danh sách phải có các phần tử duy nhất.
B. Danh sách phải được sắp xếp.
C. Danh sách phải có thể truy cập theo chỉ số.
D. Danh sách phải có độ dài lớn hơn 0.
25. Đ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.
C. Danh sách không được có phần tử trùng lặp.
D. Danh sách phải có số lượng phần tử là lũy thừa của 2.
