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

1. Trong tìm kiếm nhị phân, việc làm tròn chỉ số (ví dụ: làm tròn xuống hoặc lên) có thể ảnh hưởng đến kết quả như thế nào?

A. Không ảnh hưởng gì, miễn là nhất quán.

B. Có thể dẫn đến việc bỏ sót phần tử cần tìm nếu không cẩn thận.

C. Luôn làm tăng tốc độ tìm kiếm.

D. Chỉ ảnh hưởng đến độ phức tạp thời gian.

2. Tìm kiếm nhị phân hiệu quả hơn tìm kiếm tuần tự trong trường hợp nào?

A. Khi dãy dữ liệu rất nhỏ.

B. Khi dãy dữ liệu không được sắp xếp.

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

D. Khi chỉ cần tìm một phần tử duy nhất.

3. Tìm kiếm nhị phân có thể được áp dụng để tìm phần tử lớn nhất hoặc nhỏ nhất trong một dãy đã sắp xếp không?

A. Không, chỉ tìm kiếm các giá trị cụ thể.

B. Có, nhưng không hiệu quả bằng tìm kiếm tuần tự.

C. Có, vì phần tử lớn nhất/nhỏ nhất nằm ở hai đầu dãy đã sắp xếp.

D. Chỉ khi dãy có ít hơn 5 phần tử.

4. Tìm kiếm nhị phân có thể áp dụng cho dữ liệu có cấu trúc nào sau đây?

A. Dãy ký tự không sắp xếp.

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

C. Mảng các số đã được sắp xếp.

D. Tập hợp các từ điển.

5. Trong một dãy có n phần tử, tìm kiếm nhị phân cần thực hiện tối đa bao nhiêu phép so sánh để tìm thấy một phần tử?

A. n

B. n/2

C. log₂(n)

D. log₂(n) + 1

6. Cho dãy đã sắp xếp: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]. Tìm kiếm giá trị 1. Bước 1: So sánh với 5. 1 < 5, tìm tiếp [1, 2, 3, 4]. Bước 2: So sánh với 2. 1 < 2, tìm tiếp [1]. Bước 3: So sánh với 1. 1 == 1. Kết quả là gì?

A. Tìm kiếm tiếp ở nửa phải.

B. Giá trị 1 không có trong dãy.

C. Đã tìm thấy giá trị 1.

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

7. Khi nào thì việc sử dụng tìm kiếm nhị phân trở nên không khả thi?

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

B. Khi dãy dữ liệu quá lớn.

C. Khi dữ liệu không được sắp xếp hoặc cấu trúc dữ liệu không cho phép truy cập ngẫu nhiên.

D. Khi cần tìm kiếm nhiều lần trên cùng một dãy.

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

A. So sánh lần lượt từng phần tử với giá trị cần tìm.

B. Chia đôi phạm vi tìm kiếm dựa trên phần tử ở giữa.

C. Sử dụng bảng băm để truy cập trực tiếp.

D. Duyệt qua tất cả các phần tử cho đến khi tìm thấy.

9. Trong tìm kiếm nhị phân, nếu bạn sử dụng chỉ số trung bình (mid = (low + high) / 2) và có số phần tử chẵn, đôi khi bạn có thể gặp vấn đề lặp vô hạn nếu không xử lý cẩn thận. Cách khắc phục phổ biến là gì?

A. Luôn làm tròn chỉ số trung bình lên.

B. Luôn làm tròn chỉ số trung bình xuống.

C. Sử dụng (low + high + 1) / 2 để làm tròn lên.

D. Sử dụng (low + high) / 2 hoặc (low + high + 1) / 2 tùy thuộc vào cách cập nhật low/high.

10. Khi tìm kiếm nhị phân, nếu phạm vi tìm kiếm (ví dụ: chỉ số bắt đầu lớn hơn chỉ số kết thúc) trở nên không hợp lệ, điều đó có nghĩa là gì?

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

B. Giá trị cần tìm không có trong dãy.

C. Cần phải sắp xếp lại dãy.

D. Thuật toán đã bị lỗi.

11. Nếu bạn cần tìm kiếm một giá trị trong một tập dữ liệu lớn và biết chắc chắn rằng dữ liệu đó đã được sắp xếp, bạn nên ưu tiên thuật toán nào?

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

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

C. Tìm kiếm ngẫu nhiên.

D. Tìm kiếm theo mẫu.

12. Nếu bạn đã thực hiện tìm kiếm nhị phân trên một dãy và nhận được kết quả là không tìm thấy, điều đó có ý nghĩa gì về dãy ban đầu?

A. Dãy ban đầu có thể chưa được sắp xếp.

B. Dãy ban đầu chắc chắn không chứa giá trị bạn đang tìm.

C. Thuật toán tìm kiếm đã bị lỗi.

D. Dãy ban đầu có thể có các phần tử trùng lặp.

13. Nếu phần tử ở giữa dãy tìm kiếm nhỏ hơn giá trị cần tìm, bạn sẽ thực hiện hành động nào tiếp theo trong tìm kiếm nhị phân?

A. Tìm kiếm ở nửa bên trái của dãy.

B. Tìm kiếm ở nửa bên phải của dãy.

C. Bỏ qua phần tử ở giữa và tìm kiếm lại.

D. Dừng tìm kiếm vì không tìm thấy.

14. Cho dãy đã sắp xếp: [10, 20, 30, 40, 50]. Tìm kiếm giá trị 30. Bước 1: Chọn 30. Kết quả là gì?

A. Tìm kiếm tiếp ở nửa trái.

B. Tìm kiếm tiếp ở nửa phải.

C. Đã tìm thấy giá trị 30.

D. Giá trị 30 không có trong dãy.

15. Giả sử bạn đang tìm kiếm số 25 trong dãy số đã sắp xếp: [5, 10, 15, 20, 25, 30, 35]. Ở bước đầu tiên, bạn sẽ so sánh 25 với phần tử nào?

A. 10 (phần tử đầu tiên)

B. 20 (phần tử gần với trung bình cộng của dãy)

C. 25 (phần tử ở giữa dãy)

D. 30 (phần tử gần với giá trị tìm kiếm)

16. Cho dãy: [2, 4, 6, 8, 10, 12, 14, 16]. Tìm kiếm giá trị 11. Bước 1: Chọn 8 (phần tử giữa). Vì 11 > 8, ta tìm tiếp ở nửa phải: [10, 12, 14, 16]. Bước 2: Chọn 12 (phần tử giữa của nửa phải). Vì 11 < 12, ta tìm tiếp ở nửa trái của nửa phải: [10]. Giá trị 11 có được tìm thấy không?

A. Có, ở vị trí thứ 5.

B. Có, ở vị trí thứ 6.

C. Không, vì 11 không có trong dãy.

D. Có, ở vị trí thứ 4.

17. Việc loại bỏ một nửa dãy không chứa giá trị cần tìm trong tìm kiếm nhị phân giúp:

A. Tăng số lượng phép so sánh cần thiết.

B. Giảm số lượng phần tử cần xem xét trong các bước tiếp theo.

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

D. Đảm bảo tìm thấy giá trị ngay lập tức.

18. 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. Dãy dữ liệu phải chứa các phần tử là số nguyên.

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

C. Dãy dữ liệu phải có kích thước tối thiểu là 10 phần tử.

D. Dãy dữ liệu phải được lưu trữ dưới dạng mảng.

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

A. Không, vì nó chỉ tìm kiếm.

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

C. Có, nhưng chỉ khi dãy rất lớn.

D. Không, vì nó không kết hợp các kết quả con.

20. Khi sử dụng tìm kiếm nhị phân, nếu dãy dữ liệu có một số lượng phần tử chẵn, phần tử ở giữa thường được chọn như thế nào?

A. Luôn là phần tử đầu tiên của dãy.

B. Luôn là phần tử cuối cùng của dãy.

C. Là một trong hai phần tử gần trung tâm nhất, tùy thuộc vào cách cài đặt.

D. Phần tử có giá trị nhỏ nhất trong hai phần tử gần trung tâm.

21. Độ 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 dãy có n phần tử là bao nhiêu?

A. O(n)

B. O(n log n)

C. O(log n)

D. O(1)

22. Trong tìm kiếm nhị phân, nếu chỉ số bắt đầu (low) và chỉ số kết thúc (high) của dãy là như nhau (low == high), thì phần tử đó có thể là phần tử cần tìm không?

A. Không, vì cần ít nhất 2 phần tử để tìm kiếm.

B. Có thể, nếu giá trị của phần tử đó trùng với giá trị cần tìm.

C. Chỉ khi đó là phần tử đầu tiên của dãy ban đầu.

D. Luôn sai, vì đó là trường hợp cuối cùng của tìm kiếm thất bại.

23. Giả sử bạn có dãy đã sắp xếp: [1, 3, 5, 7, 9, 11] và cần tìm số 6. Sau bước đầu tiên so sánh với 7, bạn sẽ tìm kiếm tiếp ở đâu?

A. [1, 3, 5]

B. [9, 11]

C. [1, 3, 5, 7]

D. [7, 9, 11]

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

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

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

C. Dừng tìm kiếm và trả về vị trí của phần tử đó.

D. Kiểm tra lại toàn bộ dãy để chắc chắn.

25. Cho dãy đã sắp xếp: [3, 6, 8, 12, 16, 23, 38, 56, 72, 91]. Tìm kiếm giá trị 40. Bước 1: Chọn 16. 40 > 16, tìm tiếp [23, 38, 56, 72, 91]. Bước 2: Chọn 56. 40 38, tìm tiếp []. Bước tiếp theo là gì?

A. So sánh với 72.

B. So sánh với 23.

C. Dãy tìm kiếm trở thành trống, kết thúc tìm kiếm.

D. So sánh lại với 38.