1. Nếu một thuật toán tìm kiếm nhị phân hoạt động trên một danh sách có 16 phần tử, số lần so sánh tối đa để tìm thấy một phần tử là bao nhiêu?
2. Trong bài toán tìm kiếm, khi nào thuật toán tìm kiếm tuần tự (linear search) cho kết quả nhanh nhất?
A. Khi phần tử cần tìm nằm ở cuối danh sách.
B. Khi phần tử cần tìm nằm ở đầu danh sách hoặc danh sách rỗng.
C. Khi danh sách được sắp xếp theo thứ tự giảm dần.
D. Khi danh sách có kích thước rất lớn và phần tử cần tìm nằm ở giữa.
3. Trong thuật toán tìm kiếm tuần tự, nếu phần tử cần tìm không có trong danh sách, thuật toán sẽ thực hiện bao nhiêu phép so sánh?
A. Số phép so sánh bằng 0.
B. Số phép so sánh bằng n/2.
C. Số phép so sánh bằng n.
D. Số phép so sánh phụ thuộc vào vị trí của phần tử cuối cùng.
4. Độ phức tạp thời gian của thuật toán tìm kiếm tuần tự trên một danh sách có n phần tử là bao nhiêu trong trường hợp xấu nhất?
A. O(1)
B. O(log n)
C. O(n)
D. O(n^2)
5. Thuật toán tìm kiếm nhị phân (binary search) có thể áp dụng cho loại danh sách nào?
A. Danh sách không có thứ tự.
B. Danh sách được sắp xếp theo thứ tự bất kỳ.
C. Danh sách được sắp xếp theo thứ tự tăng hoặc giảm dần.
D. Danh sách có các phần tử trùng lặp.
6. Giả sử bạn có một danh sách lớn các số nguyên đã sắp xếp. Bạn muốn tìm kiếm một giá trị cụ thể. Phương pháp nào sau đây là hiệu quả nhất?
A. Duyệt qua từng phần tử một từ đầu đến cuối.
B. Chia đôi danh sách và kiểm tra phần tử ở giữa.
C. Sử dụng hàm băm để xác định vị trí.
D. Sắp xếp lại danh sách theo thứ tự ngược lại rồi tìm kiếm.
7. Đâu là một ví dụ về cấu trúc dữ liệu có thể được sử dụng để thực hiện tìm kiếm hiệu quả khi dữ liệu thay đổi thường xuyên?
A. Mảng tĩnh (static array).
B. Danh sách liên kết (linked list).
C. Cây tìm kiếm nhị phân cân bằng (balanced binary search tree).
D. Ngăn xếp (stack).
8. Nếu một thuật toán tìm kiếm có độ phức tạp thời gian O(n^2), điều này có nghĩa là gì khi kích thước đầu vào tăng gấp đôi?
A. Thời gian thực thi tăng gấp đôi.
B. Thời gian thực thi tăng gấp bốn lần.
C. Thời gian thực thi tăng gấp đôi logarit.
D. Thời gian thực thi không thay đổi.
9. Khi tìm kiếm một phần tử trong danh sách 100 phần tử đã sắp xếp bằng thuật toán tìm kiếm nhị phân, số lần so sánh tối đa có thể xảy ra là bao nhiêu?
10. Khi nào thì việc sử dụng tìm kiếm nhị phân không khả thi?
A. Khi danh sách quá lớn.
B. Khi danh sách chứa các phần tử trùng lặp.
C. Khi danh sách chưa được sắp xếp.
D. Khi cần tìm kiếm nhiều lần trên danh sách.
11. Khi nào thì việc sử dụng tìm kiếm tuần tự là hợp lý và có thể hiệu quả hơn tìm kiếm nhị phân?
A. Khi danh sách rất lớn và phần tử cần tìm chắc chắn ở cuối.
B. Khi danh sách chưa được sắp xếp và việc sắp xếp tốn nhiều thời gian.
C. Khi cần tìm kiếm nhiều lần trên cùng một danh sách.
D. Khi danh sách có ít phần tử.
12. Nếu bạn muốn tìm kiếm một chuỗi ký tự trong một văn bản lớn, phương pháp nào sau đây là một dạng của bài toán tìm kiếm?
A. Đếm số lần xuất hiện của mỗi từ.
B. Tìm kiếm một chuỗi con (substring search).
C. Đổi tất cả ký tự sang chữ hoa.
D. Sắp xếp các từ theo thứ tự bảng chữ cái.
13. 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 là gì?
A. Tìm kiếm trong nửa bên phải của danh sách.
B. Tìm kiếm trong nửa bên trái của danh sách.
C. So sánh với phần tử tiếp theo.
D. Bắt đầu lại từ đầu danh sách.
14. Nếu bạn đang tìm kiếm một phần tử trong một danh sách rất lớn chưa được sắp xếp, phương pháp nào sau đây là hợp lý nhất?
A. Thực hiện tìm kiếm nhị phân.
B. Thực hiện tìm kiếm tuần tự.
C. Sắp xếp danh sách rồi thực hiện tìm kiếm nhị phân.
D. Sử dụng cấu trúc dữ liệu dạng cây.
15. Điểm yếu chính của thuật toán tìm kiếm tuần tự so với tìm kiếm nhị phân là gì?
A. Tìm kiếm tuần tự yêu cầu danh sách phải được sắp xếp.
B. Tìm kiếm tuần tự chậm hơn đáng kể trên danh sách lớn.
C. Tìm kiếm tuần tự không thể xử lý các phần tử trùng lặp.
D. Tìm kiếm tuần tự tiêu tốn nhiều bộ nhớ hơn.
16. Thuật toán tìm kiếm nào hiệu quả nhất để tìm kiếm trong một mảng đã sắp xếp với kích thước rất lớn?
A. Tìm kiếm tuần tự.
B. Tìm kiếm nhị phân.
C. Tìm kiếm tuyến tính.
D. Tìm kiếm ngẫu nhiên.
17. Trong ngữ cảnh của bài toán tìm kiếm, thuật ngữ "phạm vi tìm kiếm" (search space) thường đề cập đến:
A. Số lần so sánh cần thực hiện.
B. Tổng số phần tử trong tập dữ liệu.
C. Tập hợp các vị trí hoặc giá trị có thể chứa phần tử cần tìm.
D. Độ phức tạp thời gian của thuật toán.
18. Độ phức tạp thời gian của việc tìm kiếm một phần tử trong một danh sách liên kết không có thứ tự là bao nhiêu?
A. O(1)
B. O(log n)
C. O(n)
D. O(n log n)
19. Thuật toán tìm kiếm nào sau đây có độ phức tạp thời gian trung bình là O(log n)?
A. Tìm kiếm tuần tự.
B. Tìm kiếm nhị phân.
C. Tìm kiếm theo chiều rộng (BFS) trên cây.
D. Tìm kiếm theo chiều sâu (DFS) trên cây.
20. Đâu là một ứng dụng thực tế của thuật toán tìm kiếm tuần tự?
A. Tìm kiếm tên trong danh bạ điện thoại đã sắp xếp.
B. Tìm kiếm một từ trong từ điển đã sắp xếp.
C. Tìm kiếm một mục trong danh sách các mục vừa được thêm vào.
D. Tìm kiếm giá trị lớn nhất trong một mảng đã sắp xếp.
21. Trong bài toán tìm kiếm, "độ phức tạp thời gian" đo lường điều gì?
A. Lượng bộ nhớ mà thuật toán sử dụng.
B. Số lượng phép toán mà thuật toán thực hiện.
C. Thời gian thực thi của thuật toán dưới dạng hàm của kích thước đầu vào.
D. Khả năng của thuật toán trong việc tìm đúng phần tử.
22. Đâu là yêu cầu tiên quyết để áp dụng thuật toán 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ó kích thước là lũy thừa của 2.
D. Danh sách phải được lưu trữ dưới dạng cây.
23. Đâu là một ví dụ về "trường hợp xấu nhất" (worst-case scenario) cho thuật toán tìm kiếm tuần tự trên một danh sách có n phần tử?
A. Phần tử cần tìm nằm ở đầu danh sách.
B. Phần tử cần tìm không có trong danh sách.
C. Phần tử cần tìm nằm ở giữa danh sách.
D. Danh sách có kích thước n/2.
24. Khi so sánh hiệu quả giữa tìm kiếm tuần tự và tìm kiếm nhị phân trên danh sách có 1000 phần tử, phát biểu nào sau đây là đúng?
A. Tìm kiếm tuần tự luôn nhanh hơn.
B. Tìm kiếm nhị phân yêu cầu danh sách phải được sắp xếp, nhưng nhanh hơn nhiều.
C. Cả hai có hiệu quả như nhau.
D. Tìm kiếm tuần tự tốn ít bộ nhớ hơn.
25. Tìm kiếm nhị phân hoạt động dựa trên nguyên tắc chia để trị. Bước "chia" trong thuật toán này là gì?
A. So sánh phần tử cần tìm với phần tử đầu tiên.
B. Chia danh sách thành hai nửa.
C. Kiểm tra xem phần tử có tồn tại hay không.
D. Xác định vị trí của phần tử ở giữa.
