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

1. Thuật toán tìm kiếm tuần tự có độ phức tạp thời gian là O(n). Điều này có nghĩa là gì?

A. Số phép toán tăng theo logarit của kích thước dữ liệu.

B. Số phép toán tăng theo bình phương của kích thước dữ liệu.

C. Số phép toán tăng tỷ lệ thuận với kích thước dữ liệu.

D. Số phép toán gần như không đổi.

2. Thuật toán tìm kiếm nào thường được dùng để tìm kiếm trong cơ sở dữ liệu lớn, nơi dữ liệu được lưu trữ trên đĩa?

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

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

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

D. Tìm kiếm theo cây B (B-Tree).

3. Một tập dữ liệu có 1000 phần tử. Trung bình, thuật toán tìm kiếm tuần tự sẽ cần thực hiện bao nhiêu phép so sánh để tìm thấy một phần tử?

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

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

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

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

4. Khi tìm kiếm một phần tử trong tập dữ liệu, mục tiêu chính của bất kỳ thuật toán tìm kiếm hiệu quả nào là gì?

A. Giảm thiểu số lượng bộ nhớ sử dụng.

B. Tăng tốc độ tìm kiếm bằng cách giảm số phép so sánh hoặc truy cập.

C. Đảm bảo dữ liệu luôn được sắp xếp.

D. Ngăn chặn việc truy cập vào các phần tử không liên quan.

5. Để đảm bảo tìm kiếm hiệu quả trên cây tìm kiếm nhị phân (độ phức tạp O(log n) trong mọi trường hợp), người ta thường sử dụng các loại cây cân bằng như:

A. Cây đỏ đen (Red-Black Tree) hoặc cây AVL.

B. Cây B (B-Tree).

C. Cây chỉ mục (Index Tree).

D. Cây phủ quyết (Decision Tree).

6. Phát biểu nào sau đây là ĐÚNG về mối quan hệ giữa cấu trúc dữ liệu và thuật toán tìm kiếm?

A. Cấu trúc dữ liệu không ảnh hưởng đến hiệu quả của thuật toán tìm kiếm.

B. Cấu trúc dữ liệu có tổ chức (ví dụ: sắp xếp) thường cho phép sử dụng các thuật toán tìm kiếm hiệu quả hơn.

C. Các thuật toán tìm kiếm chỉ hoạt động trên dữ liệu không có tổ chức.

D. Chỉ có tìm kiếm tuần tự mới phù hợp với mọi cấu trúc dữ liệu.

7. Khi tìm kiếm một phần tử trong một danh sách không có thứ tự, thuật toán nào sau đây là hiệu quả nhất về mặt khái niệm, mặc dù có thể không phải là nhanh nhất trong mọi trường hợp?

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

B. Tìm kiếm tuyến tính (tuần tự)

C. Tìm kiếm theo băm (hashing)

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

8. Trong bài toán tìm kiếm, độ phức tạp thời gian (time complexity) của một thuật toán đo lường điều gì?

A. Lượng bộ nhớ cần thiết để lưu trữ dữ liệu.

B. Số lượng phép toán hoặc bước mà thuật toán thực hiện theo kích thước đầu vào.

C. Mức độ chính xác của kết quả tìm kiếm.

D. Thời gian thực thi trên một máy tính cụ thể.

9. Cây B (B-Tree) có đặc điểm gì giúp nó hiệu quả khi làm việc với dữ liệu trên đĩa?

A. Mỗi nút chỉ chứa một khóa.

B. Mỗi nút có thể chứa nhiều khóa và nhiều con.

C. Luôn luôn cân bằng hoàn hảo.

D. Tất cả các nút lá đều ở cùng một cấp độ.

10. Trong tìm kiếm nhị phân, nếu phần tử cần tìm nhỏ hơn phần tử ở vị trí giữa, chúng ta sẽ tiếp tục tìm kiếm ở đâu?

A. Nửa bên phải của danh sách.

B. Nửa bên trái của danh sách.

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

D. Bỏ qua bước này và chuyển sang phần tử tiếp theo.

11. Trong thuật toán tìm kiếm nhị phân, nếu phần tử cần tìm bằng với phần tử ở vị trí giữa, hành động tiếp theo là gì?

A. Tiếp tục tìm kiếm ở nửa bên trái.

B. Tiếp tục tìm kiếm ở nửa bên phải.

C. Thuật toán kết thúc và trả về vị trí của phần tử đó.

D. So sánh với phần tử kế tiếp.

12. Một tập dữ liệu có 1024 phần tử đã được sắp xếp. Trung bình, thuật toán tìm kiếm nhị phân sẽ cần thực hiện bao nhiêu phép so sánh để tìm thấy một phần tử?

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

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

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

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

13. Trong bài toán tìm kiếm, dữ liệu cần tìm kiếm được tổ chức theo một trật tự nhất định để tối ưu hóa hiệu quả. Phương pháp nào sau đây KHÔNG dựa trên nguyên tắc dữ liệu có thứ tự?

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

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

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

D. Tìm kiếm theo khoảng cách

14. Thuật toán tìm kiếm tuần tự có nhược điểm chính là gì khi so sánh với các thuật toán tìm kiếm trên dữ liệu có thứ tự?

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

B. Tốc độ tìm kiếm chậm trên tập dữ liệu lớn.

C. Không thể tìm thấy tất cả các phần tử.

D. Phức tạp trong việc cài đặt.

15. Thuật toán tìm kiếm nhị phân có ưu điểm vượt trội về tốc độ so với tìm kiếm tuần tự khi xử lý tập dữ liệu lớn. Ưu điểm này đến từ cơ chế hoạt động nào?

A. Duyệt qua từng phần tử một cách tuần tự.

B. Loại bỏ một nửa phạm vi tìm kiếm ở mỗi bước.

C. Sử dụng cấu trúc dữ liệu dạng cây để lưu trữ.

D. Phân bổ ngẫu nhiên vị trí phần tử.

16. Khi một xung đột băm xảy ra trong phương pháp tìm kiếm theo băm, các kỹ thuật xử lý phổ biến bao gồm:

A. Phân chia dữ liệu thành các nhóm nhỏ hơn.

B. Sử dụng cây nhị phân để lưu trữ các phần tử xung đột.

C. Tìm kiếm tuần tự trong một chuỗi hoặc sử dụng bảng băm khác.

D. Sắp xếp lại toàn bộ bảng băm.

17. Một nhược điểm tiềm ẩn của tìm kiếm theo băm là gì?

A. Tốc độ tìm kiếm chậm.

B. Yêu cầu sắp xếp dữ liệu trước.

C. Xảy ra xung đột băm (hash collisions).

D. Khó khăn trong việc xóa phần tử.

18. Khi nào thì tìm kiếm tuần tự trở nên hiệu quả hơn hoặc tương đương với tìm kiếm nhị phân?

A. Khi tập dữ liệu rất lớn và đã được sắp xếp.

B. Khi tập dữ liệu 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 tập dữ liệu.

D. Khi sử dụng bộ nhớ ngoài.

19. Trong trường hợp xấu nhất, độ phức tạp thời gian của tìm kiếm trên cây tìm kiếm nhị phân có thể trở thành bao nhiêu?

A. O(log n)

B. O(n)

C. O(n^2)

D. O(1)

20. Phát biểu nào sau đây mô tả đúng nhất khái niệm thuật toán tìm kiếm?

A. Là một quy trình để sắp xếp dữ liệu.

B. Là một tập hợp các bước để xác định vị trí một phần tử cụ thể trong tập dữ liệu.

C. Là một phương pháp để xóa bỏ các phần tử trùng lặp.

D. Là một cách để tính toán giá trị trung bình của dữ liệu.

21. Khi nào việc tiền xử lý (ví dụ: sắp xếp) dữ liệu là cần thiết và hợp lý cho bài toán tìm kiếm?

A. Khi chỉ thực hiện tìm kiếm một lần trên tập dữ liệu nhỏ.

B. Khi thực hiện nhiều lượt tìm kiếm trên cùng một tập dữ liệu lớn.

C. Khi dữ liệu không có thứ tự và không bao giờ cần sắp xếp.

D. Khi cần giảm thiểu bộ nhớ sử dụng.

22. Thuật toán tìm kiếm nhị phân hoạt động dựa trên nguyên tắc chia để trị. Để áp dụng thuật toán này, điều kiện tiên quyết đối với tập dữ liệu là gì?

A. Dữ liệu phải được sắp xếp tăng dần.

B. Dữ liệu phải có cấu trúc cây.

C. Dữ liệu phải là duy nhất.

D. Dữ liệu phải có kích thước cố định.

23. Thuật toán tìm kiếm nhị phân có độ phức tạp thời gian là O(log n). Điều này có nghĩa là gì?

A. Số phép toán tăng tuyến tính với kích thước dữ liệu.

B. Số phép toán tăng theo bình phương của kích thước dữ liệu.

C. Số phép toán tăng rất chậm, tương ứng với việc chia đôi phạm vi tìm kiếm.

D. Số phép toán không phụ thuộc vào kích thước dữ liệu.

24. Tìm kiếm theo băm (hashing) là một phương pháp tìm kiếm hiệu quả. Điểm mạnh chính của phương pháp này là gì?

A. Yêu cầu dữ liệu phải được sắp xếp theo thứ tự tăng dần.

B. Thời gian tìm kiếm trung bình rất nhanh, thường là O(1).

C. Dễ dàng cài đặt trên mọi loại cấu trúc dữ liệu.

D. Phù hợp với các tập dữ liệu rất nhỏ.

25. Cây tìm kiếm nhị phân (Binary Search Tree - BST) là một cấu trúc dữ liệu cho phép tìm kiếm hiệu quả. Đặc điểm nào sau đây là cốt lõi của BST?

A. Mọi nút con bên trái lớn hơn nút cha.

B. Mọi nút con bên phải nhỏ hơn nút cha.

C. Mọi nút con bên trái nhỏ hơn hoặc bằng nút cha, mọi nút con bên phải lớn hơn hoặc bằng nút cha.

D. Mọi nút con bên trái nhỏ hơn nút cha, mọi nút con bên phải lớn hơn nút cha.