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

1. Khi thực hiện tìm kiếm nhị phân trên một mảng, nếu phần tử cần tìm lớn hơn phần tử ở giữa, chúng ta sẽ cập nhật chỉ số đầu (start) bằng cách nào?

A. Chỉ số đầu = chỉ số giữa.

B. Chỉ số đầu = chỉ số giữa + 1.

C. Chỉ số đầu = chỉ số giữa - 1.

D. Chỉ số đầu = chỉ số đầu + 1.

2. Trong thuật toán tìm kiếm nhị phân, khi nào thuật toán kết thúc và trả về kết quả là không tìm thấy phần tử?

A. Khi phần tử cần tìm lớn hơn phần tử ở giữa.

B. Khi phạm vi tìm kiếm (khoảng giữa hai chỉ số) trở nên trống rỗng (chỉ số đầu lớn hơn chỉ số cuối).

C. Khi thuật toán đã thực hiện N lần lặp, với N là kích thước mảng.

D. Khi phần tử cần tìm nhỏ hơn phần tử đầu tiên trong phạm vi tìm kiếm.

3. Giả sử ta 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 sẽ so sánh 23 với phần tử nào?

A. 2

B. 91

C. 16

D. 23

4. Trong thuật toán tìm kiếm nhị phân, khi phạm vi tìm kiếm thu hẹp lại chỉ còn một phần tử, và phần tử đó không phải là giá trị cần tìm, điều này có nghĩa là gì?

A. Phần tử đó là phần tử nhỏ nhất trong mảng.

B. Phần tử đó là phần tử lớn nhất trong mảng.

C. Phần tử cần tìm không có trong mảng.

D. Cần thực hiện thêm một bước so sánh nữa.

5. Yếu tố nào sau đây là quan trọng nhất để đảm bảo thuật toán tìm kiếm nhị phân hoạt động hiệu quả và chính xác?

A. Kích thước của tập dữ liệu.

B. Sự tồn tại của các giá trị ngoại lệ (outliers) trong dữ liệu.

C. Tập dữ liệu phải được sắp xếp.

D. Số lượng phần tử cần tìm.

6. Khi áp dụng tìm kiếm nhị phân, nếu phần tử cần tìm bằng với phần tử ở chỉ số giữa, kết quả tìm kiếm là gì?

A. Phần tử đó không có trong mảng.

B. Phần tử đó được tìm thấy và thuật toán kết thúc.

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

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

7. Khi áp dụng tìm kiếm nhị phân trên một mảng đã sắp xếp, nếu phần tử cần tìm nhỏ hơn phần tử ở giữa mảng, chúng ta sẽ tiếp tục tìm kiếm ở đâu?

A. Nửa bên phải của mảng.

B. Nửa bên trái của mảng.

C. Toàn bộ mảng.

D. Bỏ qua phần tử ở giữa và tìm hai nửa còn lại.

8. Phát biểu nào sau đây mô tả đúng nhất về chỉ số giữa (midpoint index) trong thuật toán tìm kiếm nhị phân?

A. Luôn là phần tử lớn nhất trong phạm vi tìm kiếm.

B. Là giá trị trung bình của phần tử đầu và cuối.

C. Là chỉ số chia đôi phạm vi tìm kiếm hiện tại.

D. Là phần tử ngay sau phần tử đầu tiên.

9. Tìm kiếm nhị phân có thể áp dụng cho cấu trúc dữ liệu nào sau đây, miễn là chúng được sắp xếp?

A. Danh sách liên kết (Linked List)

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

C. Mảng (Array) hoặc Danh sách (List) có truy cập ngẫu nhiên.

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

10. Điểm yếu chính của thuật toán tìm kiếm nhị phân là gì, đặc biệt khi so sánh với các thuật toán sắp xếp khác?

A. Tốn nhiều bộ nhớ.

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

C. Chậm hơn tìm kiếm tuần tự trên mảng nhỏ.

D. Khó cài đặt.

11. Trong thuật toán tìm kiếm nhị phân, nếu phần tử cần tìm nằm ở cuối của mảng đã sắp xếp, số lần so sánh sẽ như thế nào so với việc tìm phần tử ở đầu mảng?

A. Luôn ít hơn.

B. Luôn nhiều hơn.

C. Tương đương nhau trong trường hợp xấu nhất.

D. Phụ thuộc vào việc mảng có số phần tử chẵn hay lẻ.

12. Khi tìm kiếm một giá trị không có trong mảng đã sắp xếp bằng thuật toán tìm kiếm nhị phân, quá trình tìm kiếm sẽ dừng lại khi nào?

A. Khi phần tử giữa luôn lớn hơn giá trị cần tìm.

B. Khi phần tử giữa luôn nhỏ hơn giá trị cần tìm.

C. Khi chỉ số bắt đầu vượt quá chỉ số kết thúc của phạm vi tìm kiếm.

D. Khi thuật toán đã lặp đủ số lần.

13. Phát biểu nào sau đây là SAI về thuật toán tìm kiếm nhị phân?

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

B. Nó có độ phức tạp thời gian là O(log N).

C. Nó có thể tìm thấy phần tử ở bất kỳ vị trí nào trong mảng một cách hiệu quả như nhau.

D. Nó hoạt động tốt nhất trên các tập dữ liệu có kích thước lớn.

14. Nếu bạn cần tìm một mục trong một danh sách rất lớn các mục đã được sắp xếp theo thứ tự bảng chữ cái, phương pháp nào sau đây là hiệu quả nhất?

A. Tìm kiếm tuần tự từ đầu danh sách.

B. Nhảy cóc (Jump Search).

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

D. Tìm kiếm theo mẫu (Pattern Matching).

15. Tại sao việc sử dụng tìm kiếm nhị phân lại không hiệu quả trên một danh sách liên kết (linked list) mà không có chỉ số truy cập ngẫu nhiên?

A. Danh sách liên kết không thể sắp xếp.

B. Việc tìm phần tử ở giữa danh sách liên kết rất tốn thời gian.

C. Danh sách liên kết chỉ cho phép truy cập tuần tự.

D. Thuật toán nhị phân chỉ hoạt động với mảng.

16. Trong việc triển khai tìm kiếm nhị phân bằng đệ quy, trường hợp cơ bản (base case) nào sẽ dừng quá trình đệ quy?

A. Tìm thấy phần tử cần tìm.

B. Phạm vi tìm kiếm trở nên không hợp lệ (ví dụ: chỉ số bắt đầu > chỉ số kết thúc).

C. Đã lặp đủ số lần.

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

17. Nếu một mảng có 1024 phần tử đã sắp xếp, tìm kiếm nhị phân sẽ cần tối đa bao nhiêu lần so sánh để tìm thấy một phần tử (hoặc xác định nó không có trong mảng)?

A. 10

B. 11

C. 1024

D. Khoảng 512

18. Trong thuật toán tìm kiếm nhị phân, tập dữ liệu ban đầu cần phải đáp ứng điều kiện tiên quyết nào để thuật toán hoạt động chính xác?

A. Dữ liệu phải được sắp xếp theo thứ tự giảm dầ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 chứa các phần tử duy nhất, không có phần tử trùng lặp.

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

19. Trong tìm kiếm nhị phân, nếu giá trị cần tìm là 50 và mảng đã sắp xếp là [10, 20, 30, 40, 50, 60, 70], sau khi so sánh với 40 (phần tử giữa), bước tiếp theo là gì?

A. Tìm kiếm trong [10, 20, 30].

B. Tìm kiếm trong [60, 70].

C. Tìm thấy 50 và kết thúc.

D. Tìm kiếm trong [60, 70] và phần tử giữa là 70.

20. Thuật toán tìm kiếm nhị phân có ưu điểm nổi bật gì so với tìm kiếm tuần tự (linear search) trên một tập dữ liệu lớn đã sắp xếp?

A. Luôn tìm thấy phần tử nhanh hơn trong mọi trường hợp.

B. Có độ phức tạp thời gian tốt hơn, giảm số lần so sánh.

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

D. Dễ cài đặt và hiểu hơn.

21. Giả sử mảng đã sắp xếp: [1, 3, 5, 7, 9, 11, 13]. Tìm kiếm giá trị 8. Bước nào sau đây là sai trong quá trình tìm kiếm nhị phân?

A. Tìm thấy phần tử giữa là 7. 8 > 7, nên tìm tiếp bên phải.

B. Phạm vi tìm kiếm tiếp theo là [9, 11, 13].

C. Tìm thấy phần tử giữa của phạm vi mới là 11. 8 < 11, nên tìm tiếp bên trái.

D. Phạm vi tìm kiếm tiếp theo là trống rỗng, 8 không có trong mảng.

22. Độ phức tạp thời gian (time complexity) của thuật toán tìm kiếm nhị phân trên một tập dữ liệu có N phần tử là bao nhiêu, với N là số lượng phần tử?

A. O(N)

B. O(log N)

C. O(N^2)

D. O(1)

23. Khi một thuật toán tìm kiếm nhị phân được viết dưới dạng vòng lặp (iterative), biến nào thường được sử dụng để theo dõi phạm vi tìm kiếm hiện tại?

A. Chỉ số đầu (start index) và chỉ số cuối (end index).

B. Chỉ số giữa (mid index).

C. Biến đếm số lần lặp.

D. Biến lưu trữ giá trị cần tìm.

24. Khi tìm kiếm một giá trị trong mảng [10, 20, 30, 40, 50, 60, 70, 80, 90] với giá trị cần tìm là 75, bước tiếp theo sau khi so sánh với 50 là gì?

A. Tìm kiếm trong phạm vi [10, 20, 30, 40].

B. Tìm kiếm trong phạm vi [60, 70, 80, 90].

C. Tìm kiếm trong phạm vi [60, 70, 80].

D. Phần tử 75 không có trong mảng.

25. Trong trường hợp mảng có số lượng phần tử là số chẵn, cách tính chỉ số giữa (midpoint) nào thường được sử dụng để đảm bảo tính chính xác và tránh lỗi tràn bộ nhớ?

A. Chỉ số đầu + (chỉ số cuối - chỉ số đầu) / 2

B. (chỉ số đầu + chỉ số cuối) / 2

C. Chỉ số đầu + 1

D. Chỉ số cuối - 1