[Chân trời] Trắc nghiệm Tin học 7 bài 13 Thuật toán tìm kiếm

1. Khi phần tử cần tìm nằm ở vị trí trung tâm của danh sách đã sắp xếp, đó là trường hợp gì đối với tìm kiếm nhị phân?

A. Trường hợp xấu nhất.

B. Trường hợp tốt nhất.

C. Trường hợp trung bình.

D. Không có trường hợp cụ thể.

2. Trong thuật toán tìm kiếm nhị phân (binary search), điều kiện tiên quyết để áp dụng là gì?

A. Dữ liệu phải được lưu trữ dưới dạng cây.

B. Dữ liệu phải được sắp xếp theo một thứ tự nhất định.

C. Dữ liệu phải có cấu trúc dạng danh sách liên kết.

D. Dữ liệu phải được mã hóa trước.

3. Nếu bạn đang tìm kiếm một giá trị trong một danh sách rất nhỏ (ví dụ: dưới 10 phần tử), thuật toán nào có thể hiệu quả hơn tìm kiếm nhị phân, xem xét cả chi phí sắp xếp?

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

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

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

D. Tìm kiếm theo bảng băm.

4. Đâu là một kỹ thuật để xử lý xung đột băm trong bảng băm?

A. Tăng kích thước mảng băm một cách không giới hạn.

B. Sử dụng tìm kiếm tuần tự trên toàn bộ mảng.

C. Chuỗi liên kết (chaining) hoặc dò tìm mở (open addressing).

D. Chỉ cho phép một khóa duy nhất cho mỗi giá trị.

5. Thuật toán tìm kiếm nào thường được sử dụng để tìm kiếm một từ trong từ điển Anh-Việt đã được sắp xếp theo thứ tự ABC?

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

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

C. Tìm kiếm theo cây.

D. Tìm kiếm theo chuỗi ký tự.

6. Đâu là ứng dụng phổ biến của thuật toán tìm kiếm tuần tự trong đời sống số?

A. Tìm kiếm tên bài hát trong danh sách nhạc đã sắp xếp theo nghệ sĩ.

B. Tìm kiếm một mục cụ thể trong menu cài đặt của điện thoại.

C. Tìm kiếm một trang web trên Google.

D. Tìm kiếm người dùng theo tên trong danh bạ điện thoại đã sắp xếp.

7. Nếu bạn có một danh sách gồm 1000 phần tử đã được sắp xếp và muốn tìm một phần tử cụ thể, thuật toán tìm kiếm nhị phân sẽ có xu hướng thực hiện bao nhiêu phép so sánh trong trường hợp xấu nhất?

A. Khoảng 1000 phép so sánh.

B. Khoảng 500 phép so sánh.

C. Khoảng 10 phép so sánh.

D. Khoảng 100 phép so sánh.

8. Nếu một phần tử không tồn tại trong danh sách đã sắp xếp khi sử dụng tìm kiếm nhị phân, thuật toán sẽ kết thúc như thế nào?

A. Trả về vị trí của phần tử gần nhất.

B. Tiếp tục tìm kiếm cho đến hết danh sách.

C. Thông báo rằng phần tử không tìm thấy khi phạm vi tìm kiếm bị thu hẹp về không.

D. Trả về một giá trị mặc định.

9. Giả sử bạn có một tệp văn bản rất lớn chứa danh sách các từ. Nếu bạn muốn tìm tất cả các vị trí xuất hiện của một từ khóa cụ thể, thuật toán nào phù hợp nhất?

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

B. Tìm kiếm tuần tự (linear scan).

C. Tìm kiếm theo mẫu (pattern matching algorithms như KMP).

D. Tìm kiếm theo cây (tree search).

10. Ưu điểm chính của việc sử dụng tìm kiếm nhị phân so với tìm kiếm tuần tự trên tập dữ liệu lớn đã sắp xếp là gì?

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

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

C. Hiệu quả hơn về mặt thời gian xử lý.

D. Có thể tìm kiếm trên dữ liệu không sắp xếp.

11. Điểm khác biệt cơ bản giữa tìm kiếm tuần tự và tìm kiếm nhị phân nằm ở yếu tố nào?

A. Cách thức lưu trữ dữ liệu.

B. Yêu cầu về thứ tự sắp xếp của dữ liệu.

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

D. Tốc độ xử lý trên mọi loại dữ liệu.

12. Thuật toán tìm kiếm nào có độ phức tạp thời gian trung bình là O(1) nếu dữ liệu được phân bổ đều?

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

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

C. Tìm kiếm theo bảng băm (hash table lookup).

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

13. Đâu là một hạn chế của việc sử dụng bảng băm (hash table) cho mục đích tìm kiếm?

A. Không thể tìm kiếm nhanh chóng.

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

C. Các xung đột băm (hash collisions) có thể làm giảm hiệu suất.

D. Chỉ phù hợp với dữ liệu có kích thước nhỏ.

14. Trong tìm kiếm nhị phân, tại mỗi bước, chúng ta so sánh phần tử cần tìm với phần tử nào?

A. Phần tử đầu tiên của danh sách hiện tại.

B. Phần tử cuối cùng của danh sách hiện tại.

C. Phần tử nằm ở giữa của danh sách hiện tại.

D. Phần tử ngẫu nhiên trong danh sách hiện tại.

15. Khi sử 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, chúng ta sẽ tiếp tục tìm kiếm ở đâu?

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

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

C. Cuối danh sách.

D. Đầu danh sách.

16. Trong thuật 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, đây được coi là trường hợp:

A. Tốt nhất.

B. Trung bình.

C. Xấu nhất.

D. Ngoại lệ.

17. So với tìm kiếm nhị phân, tìm kiếm tuần tự có ưu điểm gì?

A. Luôn nhanh hơn.

B. Không yêu cầu dữ liệu phải được sắp xếp.

C. Có thể tìm kiếm trên mọi loại cấu trúc dữ liệu.

D. Độ phức tạp thời gian luôn là O(1).

18. Nếu một bảng băm có tỷ lệ tải (load factor) cao, điều này có thể dẫn đến:

A. Tăng tốc độ tìm kiếm.

B. Giảm số lượng xung đột băm.

C. Giảm hiệu suất tìm kiếm do nhiều xung đột hơn.

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

19. Thuật toán tìm kiếm tuần tự (linear search) thường được áp dụng hiệu quả nhất cho loại cấu trúc dữ liệu nào sau đây?

A. Danh sách được sắp xếp theo thứ tự tăng dần.

B. Danh sách không được sắp xếp hoặc có kích thước nhỏ.

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

D. Mảng băm (hash table).

20. Khi nào thì việc sử dụng thuật toán tìm kiếm tuần tự là hợp lý, mặc dù nó có thể chậm hơn tìm kiếm nhị phân?

A. Khi danh sách dữ liệu có hàng triệu phần tử và đã sắp xếp.

B. Khi danh sách dữ liệu có kích thước rất lớn và không thể sắp xếp.

C. Khi danh sách dữ liệu có kích thước nhỏ hoặc không được sắp xếp.

D. Khi cần đảm bảo tốc độ tìm kiếm nhanh nhất có thể.

21. Thuật toán tìm kiếm tuần tự có thể được mô tả như một quá trình:

A. Ngẫu nhiên hóa.

B. So sánh từng đôi.

C. Chia để trị.

D. Băm và tra cứu.

22. Nếu bạn cần tìm một phần tử trong một tập dữ liệu rất lớn và bạn có thể thực hiện việc sắp xếp trước, bạn nên ưu tiên thuật toán nào?

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

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

C. Tìm kiếm theo bảng băm.

D. Tìm kiếm ngẫu nhiên.

23. Thuật toán tìm kiếm nhị phân hoạt động dựa trên nguyên tắc nào của việc xử lý dữ liệu?

A. Tuyến tính (Linear processing).

B. Chia để trị (Divide and conquer).

C. Duyệt theo chiều rộng (Breadth-first traversal).

D. Duyệt theo chiều sâu (Depth-first traversal).

24. Trong trường hợp nào sau đây, việc sử dụng tìm kiếm tuần tự là lựa chọn duy nhất có thể?

A. Tìm kiếm trong danh sách đã sắp xếp theo thứ tự giảm dần.

B. Tìm kiếm trong danh sách không có thứ tự hoặc không thể sắp xếp.

C. Tìm kiếm trong danh sách liên kết được sắp xếp.

D. Tìm kiếm trong mảng được sắp xếp theo thứ tự tăng dần.

25. Trong bối cảnh khoa học máy tính, thuật toán tìm kiếm được phân loại chủ yếu dựa trên tiêu chí nào?

A. Ngôn ngữ lập trình sử dụng.

B. Cấu trúc dữ liệu mà nó hoạt động trên đó và hiệu quả.

C. Tốc độ xử lý của CPU.

D. Giao diện người dùng của chương trình.