Trắc nghiệm Tin học 7 kết nối bài 15 Thuật toán tìm kiếm nhị phân

1. Giả sử ta có mảng đã sắp xếp: [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]. Tìm kiếm phần tử 23. Bước đầu tiên, ta so sánh 23 với phần tử nào?

A. 2

B. 91

C. 16 (phần tử ở giữa)

D. 56 (phần tử ở giữa)

2. Tìm kiếm nhị phân có thể áp dụng trên cấu trúc dữ liệu nào KHÔNG phải là mảng liên tục?

A. Cây tìm kiếm nhị phân (Binary Search Tree) cân bằng

B. Danh sách liên kết đôi

C. Hàng đợi

D. Ngăn xếp

3. Thuật toán tìm kiếm nhị phân (Binary Search) có thể áp dụng hiệu quả nhất trên loại cấu trúc dữ liệu nào sau đây?

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

B. Mảng đã được sắp xếp

C. Cây nhị phân không cân bằng

D. Bảng băm

4. Trong tìm kiếm nhị phân, chỉ số mid được tính như thế nào để tránh tràn số nguyên khi low và high rất lớn?

A. mid = (low + high) / 2

B. mid = low + (high - low) / 2

C. mid = high - (high - low) / 2

D. mid = low * (high / 2)

5. Thuật toán tìm kiếm nhị phân hoạt động dựa trên nguyên tắc nào?

A. Chia để trị

B. Quy hoạch động

C. Tham lam

D. Duyệt tuần tự

6. Tìm kiếm nhị phân có thể gây ra lỗi gì nếu mảng không được sắp xếp đúng cách?

A. Vòng lặp vô hạn

B. Trả về kết quả sai hoặc không tìm thấy phần tử có thật

C. Lỗi tràn bộ nhớ

D. Tăng tốc độ xử lý

7. Việc thêm một phần tử vào mảng đã sắp xếp để chuẩn bị cho tìm kiếm nhị phân có thể tốn thời gian 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 log n)

8. Nếu ta cần tìm kiếm trong một danh sách các từ theo thứ tự bảng chữ cái, thuật toán nào là phù hợp nhất?

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

D. Tìm kiếm theo chiều sâu

9. Khi tìm kiếm nhị phân trên mảng [1, 3, 5, 7, 9, 11, 13] để tìm số 9, nếu lần đầu ta so sánh với 7 và 9 lớn hơn 7, phạm vi tìm kiếm tiếp theo sẽ là gì?

A. [1, 3, 5, 7]

B. [9, 11, 13]

C. [7, 9, 11, 13]

D. [9]

10. Mục đích của việc sử dụng các biến low và high trong thuật toán tìm kiếm nhị phân là gì?

A. Lưu trữ phần tử cần tìm và phần tử hiện tại

B. Đánh dấu phạm vi tìm kiếm hiện tại trong mảng

C. Đếm số lần so sánh đã thực hiện

D. Ghi lại vị trí của phần tử tìm thấy

11. Trong thuật toán tìm kiếm nhị phân, khi nào thì quá trình tìm kiếm dừng lại vì tìm thấy phần tử?

A. Khi chỉ số đầu và chỉ số cuối trùng nhau

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

C. Khi chỉ số đầu lớn hơn chỉ số cuối

D. Khi tìm thấy phần tử nhỏ hơn hoặc lớn hơn phần tử cần tìm

12. Trong quá trình tìm kiếm nhị phân, nếu phần tử cần tìm KHÔNG có trong mảng, 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. Trả về một giá trị đặc biệt (ví dụ: -1 hoặc false) để chỉ ra không tìm thấy

C. Lặp vô hạn

D. Trả về phần tử đầu tiên của mảng

13. Ưu điểm 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 mảng lớn là gì?

A. Luôn nhanh hơn trong mọi trường hợp

B. Giảm đáng kể số lần so sánh

C. Không cần sắp xếp mảng

D. Dễ dàng tìm thấy phần tử bị trùng lặp

14. Nếu chỉ số low (bắt đầu) lớn hơn chỉ số high (kết thúc) trong tìm kiếm nhị phân, điều đó có nghĩa là gì?

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

B. Phạm vi tìm kiếm đã cạn kiệt mà không tìm thấy phần tử

C. Cần tăng chỉ số low

D. Cần giảm chỉ số high

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

A. Nửa đầu của mảng

B. Nửa cuối của mảng

C. Bỏ qua phần tử ở giữa và tìm kiếm ở cả hai nửa

D. Không thể xác định

16. Giả sử mảng đã sắp xếp là [10, 20, 30, 40, 50] và ta tìm kiếm phần tử 25. Sau lần so sánh đầu tiên với 30 (phần tử giữa), ta loại bỏ phần nào?

A. Nửa đầu [10, 20, 30]

B. Nửa cuối [30, 40, 50]

C. Phần tử 30

D. Nửa đầu [10, 20]

17. Điều kiện tiên quyết để thuật toán tìm kiếm nhị phân hoạt động đúng là gì?

A. Dữ liệu phải là số nguyên

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

C. Dữ liệu phải có kích thước là lũy thừa của 2

D. Dữ liệu phải được lưu trữ trên ổ cứng

18. Nếu một mảng có các phần tử trùng lặp, tìm kiếm nhị phân có đảm bảo tìm thấy phần tử đầu tiên xuất hiện không?

A. Có, luôn tìm thấy phần tử đầu tiên

B. Không, có thể tìm thấy bất kỳ phần tử trùng lặp nào

C. Chỉ khi mảng được sắp xếp theo thứ tự giảm dần

D. Không thể áp dụng trên mảng có phần tử trùng lặp

19. Thuật toán tìm kiếm nhị phân có thể được triển khai bằng cách nào?

A. Chỉ bằng vòng lặp

B. Chỉ bằng đệ quy

C. Bằng cả vòng lặp và đệ quy

D. Chỉ bằng cấu trúc dữ liệu dạng cây

20. Khi tìm kiếm phần tử 56 trong mảng [2, 5, 8, 12, 16, 23, 38, 56, 72, 91] (đã sắp xếp), sau khi so sánh với 16 và loại bỏ nửa đầu, phạm vi tìm kiếm tiếp theo là gì?

A. [2, 5, 8, 12, 16]

B. [23, 38, 56, 72, 91]

C. [16, 23, 38, 56, 72, 91]

D. [23, 38, 56]

21. Khi sử dụng tìm kiếm nhị phân đệ quy, thông số nào thường được truyền vào hàm đệ quy cho lần gọi tiếp theo để tìm kiếm ở nửa sau?

A. mid + 1 (chỉ số giữa cộng 1) và high (chỉ số cuối)

B. low (chỉ số đầu) và mid - 1 (chỉ số giữa trừ 1)

C. low (chỉ số đầu) và high (chỉ số cuối)

D. mid (chỉ số giữa) và mid + 1 (chỉ số giữa cộng 1)

22. Một mảng có 1000 phần tử. Tìm kiếm nhị phân sẽ thực hiện tối đa bao nhiêu phép so sánh để tìm một phần tử?

A. 1000

B. 500

C. Khoảng 10 (vì 2^10 ≈ 1000)

D. Khoảng 100 (vì 1000 / 10)

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

A. Nhanh hơn khi tìm kiếm trên mảng không sắp xếp

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

C. Nhanh hơn đáng kể trên các mảng lớn đã sắp xếp

D. Đơn giản hơn để cài đặt

24. Trong trường hợp nào tìm kiếm nhị phân sẽ kém hiệu quả hơn tìm kiếm tuần tự?

A. Khi mảng có rất ít phần tử

B. Khi mảng chưa được sắp xếp

C. Khi phần tử cần tìm nằm ở cuối mảng

D. Khi mảng có kích thước lớn

25. Độ phức tạp thời gian (time complexity) 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(n)

B. O(log n)

C. O(n^2)

D. O(1)