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

1. Giả sử ta có danh sách [10, 20, 30, 40, 50] và muốn tìm kiếm giá trị 25. Bước đầu tiên, ta so sánh 25 với phần tử nào?

A. 10

B. 20

C. 30

D. 40

2. Trong thuật toán tìm kiếm nhị phân, nếu giá trị cần tìm là 56 trong danh sách [2, 5, 8, 12, 16, 23, 38, 56, 72, 91], bước tiếp theo sau khi so sánh với 16 là gì?

A. So sánh 56 với phần tử ở giữa của toàn bộ danh sách lần nữa.

B. Tìm kiếm trong khoảng từ phần tử thứ 5 đến hết.

C. Tìm kiếm trong khoảng từ phần tử thứ 5 đến phần tử ở giữa.

D. Tìm kiếm trong khoảng từ phần tử thứ 5 đến phần tử cuối cùng.

3. Nguyên tắc cơ bản của thuật toán tìm kiếm nhị phân là gì?

A. So sánh phần tử cần tìm với từng phần tử trong danh sách theo thứ tự.

B. Chia đôi danh sách và so sánh phần tử cần tìm với phần tử ở giữa.

C. Duyệt qua toàn bộ danh sách từ đầu đến cuối.

D. Sử dụng cấu trúc dữ liệu cây để lưu trữ và tìm kiếm.

4. Tại sao việc sắp xếp dữ liệu trước khi áp dụng tìm kiếm nhị phân lại quan trọng?

A. Để tăng tốc độ xử lý của thuật toán tìm kiếm tuần tự.

B. Để thuật toán có thể loại bỏ một nửa phạm vi tìm kiếm ở mỗi bước.

C. Để giảm dung lượng bộ nhớ cần thiết.

D. Để đảm bảo thuật toán luôn tìm thấy giá trị.

5. Trong một bài toán lập trình, nếu cần tìm kiếm một phần tử trong một mảng rất lớn đã được sắp xếp, thuật toán nào sau đây là lựa chọn tốt nhất về hiệu năng?

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.

6. So với thuật toán tìm kiếm tuần tự, thuật toán tìm kiếm nhị phân có ưu điểm gì nổi bật?

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

B. Hiệu quả hơn trên các tập dữ liệu lớn đã sắp xếp.

C. Không yêu cầu tập dữ liệu phải sắp xếp.

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

7. Khi thực hiện tìm kiếm nhị phân trên một danh sách chỉ có một phần tử, và phần tử đó không khớp với giá trị cần tìm, kết quả sẽ là gì?

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

B. Giá trị không có trong danh sách.

C. Thuật toán sẽ tiếp tục tìm kiếm.

D. Cần phải sắp xếp lại danh sách.

8. Khi nào thuật toán tìm kiếm nhị phân dừng lại và trả về kết quả tìm thấy?

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

B. Khi phạm vi tìm kiếm chỉ còn một phần tử và nó khớp với giá trị cần tìm.

C. Khi phạm vi tìm kiếm trở nên rỗng.

D. Cả A và B đều đúng.

9. Xem xét danh sách đã sắp xếp: [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]. Nếu tìm kiếm giá trị 23, sau khi so sánh với 38 và thấy 23 < 38, ta sẽ tiếp tục tìm kiếm ở đâu?

A. Phần bên trái của 38 (bao gồm [2, 5, 8, 12, 16, 23]).

B. Phần bên phải của 38 (bao gồm [56, 72, 91]).

C. Phần bên trái của 16 (bao gồm [2, 5, 8, 12]).

D. Phần bên phải của 16 (bao gồm [23, 38, 56, 72, 91]).

10. Nếu phần tử ở giữa danh sách lớn hơn giá trị cần tìm, ta sẽ tiếp tục tìm kiếm ở phần nào của danh sách?

A. Phần bên trái của phần tử ở giữa.

B. Phần bên phải của phần tử ở giữa.

C. Toàn bộ danh sách.

D. Không tìm kiếm nữa vì giá trị không tồn tại.

11. Sau khi so sánh 25 với 30 (trong danh sách [10, 20, 30, 40, 50]) và thấy 25 < 30, ta tiếp tục tìm kiếm ở đâu?

A. Phần bên trái của 30 ([10, 20]).

B. Phần bên phải của 30 ([40, 50]).

C. Toàn bộ danh sách.

D. Không tìm kiếm nữa.

12. Xem xét danh sách đã 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. 16

B. 23

C. 38

D. 12

13. Nếu một danh sách có 100 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?

A. 100

B. 50

C. Khoảng 7

D. Khoảng 10

14. Nếu danh sách được sắp xếp theo thứ tự giảm dần, thuật toán tìm kiếm nhị phân sẽ hoạt động như thế nào?

A. Vẫn hoạt động bình thường như sắp xếp tăng dần.

B. Cần phải đảo ngược logic so sánh.

C. Không hoạt động được.

D. Chỉ hoạt động nếu giá trị cần tìm là lớn nhất.

15. Nếu sau nhiều lần chia đôi, phạm vi tìm kiếm trở nên rỗng (không còn phần tử nào để xét), đ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 danh sách.

C. Thuật toán đã hoàn thành thành công.

D. Cần phải bắt đầu lại quá trình tìm kiếm.

16. Nếu phần tử ở giữa danh sách nhỏ hơn giá trị cần tìm, ta sẽ tiếp tục tìm kiếm ở phần nào của danh sách?

A. Phần bên trái của phần tử ở giữa.

B. Phần bên phải của phần tử ở giữa.

C. Toàn bộ danh sách.

D. Không tìm kiếm nữa vì giá trị không tồn tại.

17. Thuật toán tìm kiếm nhị phân hoạt động hiệu quả nhất khi nào?

A. Khi tập dữ liệu nhỏ và không cần sắp xếp.

B. Khi tập dữ liệu lớn và đã được sắp xếp.

C. Khi tập dữ liệu không có thứ tự.

D. Khi cần tìm tất cả các lần xuất hiện của một giá trị.

18. Khi tìm kiếm một giá trị trong một danh sách đã sắp xếp bằng thuật toán tìm kiếm nhị phân, bước đầu tiên là gì?

A. So sánh giá trị cần tìm với phần tử đầu tiên của danh sách.

B. So sánh giá trị cần tìm với phần tử cuối cùng của danh sách.

C. Xác định phần tử ở vị trí giữa của danh sách và so sánh với giá trị cần tìm.

D. Chia danh sách thành hai nửa và tìm kiếm ở cả hai nửa.

19. Nếu một danh sách chứa các phần tử lặp lại, và ta tìm kiếm một giá trị xuất hiện nhiều lần, tìm kiếm nhị phân sẽ trả về vị trí nào?

A. Vị trí đầu tiên của giá trị đó.

B. Vị trí cuối cùng của giá trị đó.

C. Một trong các vị trí mà giá trị đó xuất hiện.

D. Không xác định được vị trí cụ thể.

20. Việc sử dụng chỉ số (index) trong thuật toán tìm kiếm nhị phân giúp gì?

A. Xác định giá trị của phần tử ở giữa.

B. Quản lý phạm vi tìm kiếm hiệu quả.

C. So sánh trực tiếp giá trị cần tìm với chỉ số.

D. Lưu trữ toàn bộ danh sách.

21. Thuật toán tìm kiếm nhị phân có thể áp dụng hiệu quả trên tập dữ liệu nào sau đây?

A. Tập dữ liệu đã được sắp xếp theo thứ tự tăng dần.

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

C. Tập dữ liệu không cần sắp xếp nhưng có cấu trúc cây.

D. Tập dữ liệu chỉ chứa các phần tử giống nhau.

22. Để tìm tất cả các lần xuất hiện của một giá trị trong danh sách đã sắp xếp, ta có thể làm gì sau khi tìm thấy một lần xuất hiện bằng tìm kiếm nhị phân?

A. Dừng tìm kiếm và báo cáo đã tìm thấy.

B. Tiếp tục tìm kiếm nhị phân ở nửa bên trái của vị trí tìm thấy.

C. Tiếp tục tìm kiếm tuần tự sang cả hai bên từ vị trí tìm thấy.

D. Thực hiện lại tìm kiếm nhị phân trên toàn bộ danh sách.

23. Trong các trường hợp sau, trường hợp nào KHÔNG THỂ áp dụng thuật toán tìm kiếm nhị phân?

A. Tìm kiếm tên học sinh trong danh sách học sinh đã sắp xếp theo alphabet.

B. Tìm kiếm số điện thoại trong danh bạ điện thoại đã sắp xếp theo tên.

C. Tìm kiếm một từ khóa trong một văn bản không có cấu trúc rõ ràng.

D. Tìm kiếm số trong một mảng các số nguyên đã được sắp xếp tăng dần.

24. Nhược điểm chính của thuật toán tìm kiếm nhị phân là gì?

A. Tốc độ xử lý chậm trên tập dữ liệu lớn.

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

C. Chỉ tìm được phần tử đầu tiên của giá trị cần tìm.

D. Tốn nhiều bộ nhớ để lưu trữ.

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

A. O(N)

B. O(log N)

C. O(N^2)

D. O(1)