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

1. Giả sử mảng đã sắp xếp là [10, 20, 30, 40, 50]. Tìm kiếm giá trị 60. Phần tử nào sẽ được so sánh ở bước thứ hai nếu 60 không tìm thấy ở bước đầu?

A. 30

B. 40

C. 50

D. Không có bước thứ hai vì 60 lớn hơn phần tử giữa.

2. Trong tìm kiếm nhị phân, chỉ số giữa (mid) thường được tính như thế nào để tránh tràn số (integer overflow) khi low và high rất lớn?

A. (low + high) / 2

B. low + (high - low) / 2

C. high - (high - low) / 2

D. (low + high) / 2 + 1

3. Nếu mảng là [1, 3, 5, 7, 9] và ta tìm kiếm giá trị 4, bước tiếp theo sau khi so sánh với 5 (phần tử giữa) là gì?

A. So sánh với 3.

B. So sánh với 7.

C. So sánh với 1.

D. Dừng lại, không tìm thấy.

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

A. Giá trị cần tìm đã được tìm thấy.

B. Phạm vi tìm kiếm hiện tại còn rất nhiều phần tử.

C. Giá trị cần tìm không có trong mảng.

D. Cần tăng giá trị `high` lên.

5. Khi tìm kiếm một giá trị nhỏ hơn phần tử đầu tiên trong mảng đã sắp xếp, thuật toán tìm kiếm nhị phân sẽ dừng lại sau bao nhiêu bước (xấp xỉ)?

A. Khoảng N/2 lần so sánh.

B. Khoảng log₂(N) lần so sánh.

C. Chỉ 1 lần so sánh với phần tử đầu tiên, sau đó phạm vi tìm kiếm sẽ rỗng.

D. Khoảng N lần so sánh.

6. Tìm kiếm tuyến tính (linear search) và tìm kiếm nhị phân (binary search) khác nhau cơ bản nhất ở điểm nào?

A. Tìm kiếm tuyến tính yêu cầu mảng sắp xếp, tìm kiếm nhị phân không.

B. Tìm kiếm nhị phân hiệu quả hơn khi mảng lớn và đã sắp xếp.

C. Tìm kiếm tuyến tính luôn nhanh hơn tìm kiếm nhị phân.

D. Cả hai đều có độ phức tạp thời gian O(N).

7. Tìm kiếm nhị phân có thể áp dụng trực tiếp trên cấu trúc dữ liệu nào sau đây mà không cần chuyển đổi?

A. Danh sách liên kết (linked list) không có con trỏ truy cập ngẫu nhiên.

B. Cây tìm kiếm nhị phân (Binary Search Tree).

C. Mảng (Array).

D. Hàng đợi (Queue).

8. Nếu mảng tìm kiếm rỗng, kết quả của thuật toán tìm kiếm nhị phân sẽ là gì?

A. Trả về phần tử đầu tiên.

B. Trả về phần tử cuối cùng.

C. Không tìm thấy giá trị.

D. Báo lỗi chương trình.

9. Khi tìm kiếm một giá trị lớn hơn tất cả các phần tử trong mảng đã sắp xếp, thuật toán tìm kiếm nhị phân sẽ thực hiện bao nhiêu lần so sánh trong trường hợp xấu nhất?

A. Khoảng N/2 lần, với N là kích thước mảng.

B. Khoảng log₂(N) lần.

C. Chỉ 1 lần so sánh với phần tử cuối cùng.

D. Khoảng N lần.

10. Khi tìm kiếm nhị phân trong một mảng có N phần tử, số lần so sánh lớn nhất mà thuật toán có thể thực hiện là bao nhiêu?

A. N

B. N/2

C. log₂(N)

D. 2^N

11. Tìm kiếm nhị phân có thể được xem là một dạng của chiến lược chia để trị (divide and conquer) không?

A. Không, nó là thuật toán tìm kiếm tuần tự.

B. Có, vì nó chia vấn đề lớn thành các vấn đề nhỏ hơn.

C. Có, nhưng chỉ khi mảng có kích thước nhỏ.

D. Không, chia để trị chỉ áp dụng cho sắp xếp.

12. Nếu một mảng chứa 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 hoặc phần tử cuối cùng của nhóm phần tử trùng lặp đó không?

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

B. Có, luôn tìm thấy phần tử cuối cùng.

C. Không, chỉ đảm bảo tìm thấy một trong các phần tử trùng lặp.

D. Có, nếu mảng được sắp xếp theo thứ tự giảm dần.

13. Trong thuật toán tìm kiếm nhị phân, khi nào vòng lặp tìm kiếm sẽ dừng lại?

A. Khi tìm thấy giá trị cần tìm.

B. Khi phạm vi tìm kiếm trở nên rỗng (chỉ số đầu > chỉ số cuối).

C. Khi đã thực hiện đủ số lần lặp tương ứng với log₂(N).

D. Tất cả các trường hợp trên.

14. Giả sử bạn có một mảng rất lớn đã sắp xếp và cần tìm kiếm một giá trị. Lựa chọn nào sau đây mô tả cách tìm kiếm nhị phân hoạt động hiệu quả nhất?

A. Kiểm tra ngẫu nhiên các phần tử cho đến khi tìm thấy.

B. Bắt đầu từ phần tử đầu tiên và di chuyển tuần tự.

C. Liên tục chia đôi phạm vi tìm kiếm, loại bỏ một nửa không chứa giá trị cần tìm.

D. So sánh với giá trị trung bình của toàn bộ mảng.

15. Khi thực hiện tìm kiếm nhị phân trên mảng có kích thước N, số lượng phần tử được loại bỏ ở mỗi bước là bao nhiêu (xấp xỉ)?

A. Khoảng N/2.

B. Khoảng N.

C. Khoảng 1.

D. Khoảng log₂(N).

16. Nếu giá trị cần tìm trong tìm kiếm nhị phân nhỏ hơn phần tử ở giữa mảng, bước tiếp theo thuật toán sẽ làm 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. So sánh với phần tử đầu tiên của mảng.

D. Kết thúc tìm kiếm vì không tìm thấy.

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

A. Kiểm tra từng phần tử từ đầu đến cuối.

B. Chia phạm vi tìm kiếm thành hai phần bằng nhau ở mỗi bước.

C. Ưu tiên kiểm tra các phần tử ở hai đầu mảng.

D. Sử dụng bảng băm để tra cứu nhanh.

18. Việc sử dụng tìm kiếm nhị phân có lợi ích gì so với tìm kiếm tuyến tính khi xử lý tập dữ liệu rất lớn?

A. Giảm đáng kể số lượng phép so sánh cần thực hiện.

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

C. Không cần sắp xếp dữ liệu.

D. Tăng tốc độ xử lý cho mọi loại dữ liệu.

19. Nếu trong quá trình tìm kiếm nhị phân, giá trị cần tìm bằng với phần tử ở giữa, thuật toán sẽ làm gì tiếp theo?

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. Trả về vị trí của phần tử đó.

D. Dừng lại và kiểm tra phần tử ngay trước đó.

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

A. Mảng phải được sắp xếp theo thứ tự giảm dần.

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

C. Mảng phải chứa các phần tử là số nguyên.

D. Mảng phải có kích thước là lũy thừa của 2.

21. Điểm yếu lớn nhất của tìm kiếm nhị phân so với tìm kiếm tuyến tính là gì?

A. Độ phức tạp thời gian cao hơn trên mảng nhỏ.

B. Yêu cầu mảng phải được sắp xếp trước.

C. Không thể tìm kiếm trên mảng có phần tử trùng lặp.

D. Tốn nhiều bộ nhớ hơn.

22. Giả sử có một mảng đã sắp xếp: [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]. Nếu tìm kiếm giá trị 23, bước đầu tiên của tìm kiếm nhị phân sẽ so sánh giá trị nào?

A. 56 (phần tử ở giữa mảng)

B. 16 (phần tử ở giữa mảng)

C. 23 (chính là giá trị cần tìm)

D. 8 (phần tử đầu tiên của nửa bên trái)

23. Điều gì xảy ra nếu bạn cố gắng áp dụng tìm kiếm nhị phân trên một mảng chưa được sắp xếp?

A. Thuật toán sẽ tự động sắp xếp mảng rồi tìm kiếm.

B. Thuật toán sẽ hoạt động bình thường và cho kết quả chính xác.

C. Thuật toán có thể trả về kết quả sai hoặc không tìm thấy giá trị ngay cả khi nó tồn tại.

D. Chương trình sẽ bị lỗi ngay lập tức.

24. Tìm kiếm nhị phân có thể được áp dụng để tìm phần tử lớn nhất nhỏ hơn hoặc bằng một giá trị cho trước (lower bound) trong một mảng đã sắp xếp không?

A. Không, chỉ tìm thấy chính xác giá trị.

B. Có, bằng cách điều chỉnh điều kiện dừng và so sánh.

C. Có, nhưng sẽ chậm hơn tìm kiếm tuyến tính.

D. Chỉ có thể tìm phần tử nhỏ nhất lớn hơn hoặc bằng.

25. Độ phức tạp thời gian của thuật toán tìm kiếm nhị phân là bao nhiêu?

A. O(N)

B. O(N²)

C. O(log N)

D. O(1)