Trắc nghiệm Cánh diều Tin học 7 bài 2 Tìm kiếm nhị phân

1. Nếu mảng có 100 phần tử và phần tử cần tìm nằm ở cuối cùng, số lần so sánh tối đa theo tìm kiếm nhị phân là bao nhiêu?

A. 100

B. 7

C. 8

D. 10

2. Khi thực hiện tìm kiếm nhị phân trên một mảng, nếu `low` và `high` bằng nhau, điều này có nghĩa là gì?

A. Phạm vi tìm kiếm đã hết.

B. Chỉ còn một phần tử trong phạm vi tìm kiếm.

C. Phần tử đã được tìm thấy.

D. Cần phải tăng `high` lên.

3. Nếu `low` = 5 và `high` = 15, giá trị của `mid` khi sử dụng công thức `mid = low + (high - low) // 2` là bao nhiêu?

A. 10

B. 5

C. 15

D. 7

4. So sánh tìm kiếm nhị phân và tìm kiếm Fibonacci. Khi nào tìm kiếm Fibonacci có thể vượt trội hơn tìm kiếm nhị phân?

A. Khi dữ liệu được lưu trữ trên đĩa và việc truy cập tuần tự hiệu quả hơn.

B. Khi không biết trước kích thước của tập dữ liệu.

C. Khi cần tìm kiếm trên cấu trúc dữ liệu cây.

D. Khi dữ liệu có nhiều phần tử trùng lặp.

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

A. Trả về chỉ số của phần tử gần nhất.

B. Lặp vô hạn.

C. Trả về một giá trị đặc biệt (ví dụ: -1) để chỉ không tìm thấy.

D. Báo lỗi tràn bộ nhớ.

6. Trong một hệ thống tìm kiếm tài liệu lớn, việc sử dụng chỉ mục được sắp xếp và thuật toán tìm kiếm nhị phân sẽ có lợi ích gì?

A. Giảm đáng kể thời gian tìm kiếm tài liệu.

B. Tăng dung lượng lưu trữ cần thiết.

C. Yêu cầu người dùng phải nhớ vị trí chính xác của tài liệu.

D. Làm chậm quá trình lập chỉ mục.

7. Đâu là một nhược điểm tiềm ẩn của thuật toán tìm kiếm nhị phân?

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

B. Không hiệu quả với các mảng nhỏ.

C. Cần nhiều bộ nhớ để lưu trữ.

D. Chỉ hoạt động với các số nguyên.

8. Khi tìm kiếm một phần tử trong một mảng đã sắp xếp bằng thuật toán tìm kiếm nhị phân, nếu phần tử cần tìm nhỏ hơn phần tử ở giữa mảng, thì bước tiếp theo là gì?

A. Tìm kiếm trong nửa bên phải của mảng.

B. Tìm kiếm trong nửa bên trái của mảng.

C. Dừng tìm kiếm và báo không tìm thấy.

D. So sánh phần tử cần tìm với phần tử đầu tiên của mảng.

9. Tìm kiếm nhị phân hiệu quả nhất khi áp dụng trên cấu trúc dữ liệu nào?

A. Danh sách liên kết.

B. Mảng hoặc mảng động (array/vector).

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

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

10. Trong thuật toán tìm kiếm nhị phân, thuật ngữ high (hoặc right) thường biểu thị:

A. Chỉ số đầu tiên của mảng.

B. Chỉ số cuối cùng của phạm vi tìm kiếm hiện tại.

C. Chỉ số của phần tử nhỏ nhất trong mảng.

D. Chỉ số của phần tử không được tìm thấy.

11. Trong tìm kiếm nhị phân, điều kiện tiên quyết để thuật toán hoạt động hiệu quả là gì?

A. Dữ liệu được sắp xếp theo thứ tự giảm dần.

B. Dữ liệu được sắp xếp theo thứ tự tăng dần hoặc giảm dần.

C. Dữ liệu được lưu trữ dưới dạng danh sách liên kết.

D. Dữ liệu không cần sắp xếp.

12. Ưu điểm chính của tìm kiếm nhị phân so với tìm kiếm tuần tự là gì?

A. Tìm kiếm nhị phân hiệu quả hơn trên dữ liệu chưa sắp xếp.

B. Tìm kiếm nhị phân nhanh hơn đáng kể trên tập dữ liệu lớn.

C. Tìm kiếm nhị phân yêu cầu ít bộ nhớ hơn.

D. Tìm kiếm nhị phân có thể tìm thấy bất kỳ loại dữ liệu nào.

13. Xét mảng đã sắp xếp: [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]. Tìm kiếm giá trị 23. Vòng lặp đầu tiên, mid sẽ là chỉ số nào?

A. Chỉ số 4 (giá trị 16).

B. Chỉ số 5 (giá trị 23).

C. Chỉ số 4.5 (trung bình cộng của 0 và 9).

D. Chỉ số 0 (giá trị 2).

14. Tìm kiếm nhị phân có độ phức tạp thời gian là bao nhiêu trong trường hợp xấu nhất?

A. O(n)

B. O(log n)

C. O(n^2)

D. O(1)

15. Trong thuật toán tìm kiếm nhị phân, việc tính chỉ số mid bằng `mid = (low + high) // 2` có thể dẫn đến vấn đề gì với các mảng rất lớn?

A. Tràn số nguyên (integer overflow) nếu `low + high` vượt quá giới hạn của kiểu dữ liệu.

B. Chia cho 0 nếu `high` bằng 0.

C. Vòng lặp vô hạn nếu `low` và `high` bằng nhau.

D. Kết quả `mid` không bao giờ là số nguyên.

16. Khi nào tìm kiếm nhị phân KHÔNG phải là lựa chọn tốt nhất?

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ỏ và cần thực hiện nhiều lần tìm kiếm.

C. Khi tập dữ liệu lớn nhưng chưa được sắp xếp và việc sắp xếp tốn kém.

D. Khi cần tìm kiếm một phần tử và dữ liệu đã được sắp xếp.

17. Nếu một mảng chứa các phần tử trùng lặp và được sắp xếp, tìm kiếm nhị phân sẽ trả về chỉ số của:

A. Chỉ số của phần tử đầu tiên xuất hiện.

B. Chỉ số của phần tử cuối cùng xuất hiện.

C. Chỉ số của bất kỳ phần tử nào có giá trị đó.

D. Chỉ số của phần tử có giá trị gần nhất.

18. Tìm kiếm nhị phân có thể được sử dụng để tìm kiếm trong một cây tìm kiếm nhị phân (BST) không?

A. Có, vì cả hai đều dựa trên việc chia đôi phạm vi.

B. Không, cây tìm kiếm nhị phân có cấu trúc truy cập khác.

C. Chỉ khi cây tìm kiếm nhị phân cân bằng hoàn hảo.

D. Chỉ khi cây tìm kiếm nhị phân là cây nhị phân đầy đủ.

19. Tìm kiếm nhị phân có thể được áp dụng để tìm vị trí của một phần tử trong một mảng được sắp xếp theo thứ tự giảm dần không?

A. Không, chỉ áp dụng cho thứ tự tăng dần.

B. Có, bằng cách điều chỉnh logic so sánh.

C. Chỉ khi mảng có số lượng phần tử là số chẵn.

D. Có, nhưng hiệu quả sẽ giảm đi một nửa.

20. Trong cài đặt tìm kiếm nhị phân đệ quy, điều kiện dừng của đệ quy là gì?

A. Khi `low` lớn hơn `high`.

B. Khi phần tử ở giữa bằng với phần tử cần tìm.

C. Cả hai điều kiện trên.

D. Khi chỉ còn một phần tử trong phạm vi tìm kiếm.

21. Xét mảng đã sắp xếp: [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]. Tìm kiếm giá trị 23. Sau khi so sánh với phần tử ở giữa (giả sử mid = 4, giá trị 16), vì 23 > 16, phạm vi tìm kiếm tiếp theo sẽ là:

A. Từ chỉ số 0 đến 3.

B. Từ chỉ số 5 đến 9.

C. Từ chỉ số 0 đến 4.

D. Từ chỉ số 5 đến 8.

22. Giả sử bạn có một mảng đã sắp xếp gồm 16 phần tử và bạn đang tìm kiếm một giá trị cụ thể bằng tìm kiếm nhị phân. Số lần so sánh tối đa để tìm thấy hoặc xác định không có phần tử đó là bao nhiêu?

A. 4

B. 8

C. 5

D. 16

23. Tìm kiếm nhị phân có thể được coi là một ví dụ của chiến lược chia để trị (Divide and Conquer) không?

A. Không, nó chỉ là một phương pháp tìm kiếm đơn giản.

B. Có, vì nó chia bài toán lớn thành các bài toán con nhỏ hơn.

C. Chỉ khi áp dụng cho dữ liệu có cấu trúc cây.

D. Không, chiến lược chia để trị luôn yêu cầu đệ quy phức tạp hơn.

24. Trong thuật toán tìm kiếm nhị phân, thuật ngữ low (hoặc left) thường biểu thị:

A. Chỉ số cuối cùng của mảng.

B. Chỉ số bắt đầu của phạm vi tìm kiếm hiện tại.

C. Chỉ số của phần tử lớn nhất trong mảng.

D. Chỉ số của phần tử được tìm thấy.

25. Khi tìm kiếm nhị phân, nếu phần tử ở giữa mảng bằng với phần tử cần tìm, điều gì xảy ra tiếp theo?

A. Thuật toán tiếp tục tìm kiếm ở nửa bên trái.

B. Thuật toán 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. Thuật toán dừng tìm kiếm và báo không tìm thấy.