Trắc nghiệm Tin học 11 Cánh diều KHMT bài 7 Lập trình giải bài toán tìm kiếm

1. Trong tìm kiếm nhị phân, nếu phần tử ở giữa mảng bằng với giá trị cần tìm, thuật toán sẽ dừng lại và trả về vị trí nào?

A. Vị trí của phần tử đầu tiên trong mảng.

B. Vị trí của phần tử cuối cùng trong mảng.

C. Vị trí của phần tử ở giữa.

D. Vị trí tiếp theo sau phần tử ở giữa.

2. Điều kiện tiên quyết để có thể áp dụng thuật toán tìm kiếm nhị phân (Binary Search) là gì?

A. Dữ liệu phải là mảng động.

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.

D. Dữ liệu phải có kích thước cố định.

3. Trong tìm kiếm nhị phân, nếu `low` và `high` là các chỉ số của phạm vi tìm kiếm hiện tại, và `mid = (low + high) / 2`, điều gì xảy ra nếu `arr[mid] < target`?

A. Phạm vi tìm kiếm mới là từ `mid + 1` đến `high`.

B. Phạm vi tìm kiếm mới là từ `low` đến `mid - 1`.

C. Phạm vi tìm kiếm mới là từ `low` đến `mid`.

D. Thuật toán dừng lại vì không tìm thấy.

4. Thuật toán tìm kiếm nào có thể cho kết quả không chính xác nếu tập dữ liệu có giá trị trùng lặp và ta tìm kiếm vị trí đầu tiên của một phần tử?

A. Linear Search.

B. Binary Search tiêu chuẩn.

C. Hash Table Lookup.

D. Tất cả các thuật toán tìm kiếm.

5. Xét một mảng đã sắp xếp có 16 phần tử. Số lần so sánh tối đa theo thuật toán tìm kiếm nhị phân là bao nhiêu?

A. 4 lần.

B. 8 lần.

C. 16 lần.

D. 5 lần.

6. Khi nào thì việc sử dụng tìm kiếm tuyến tính (Linear Search) là hợp lý hoặc thậm chí tối ưu?

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

B. Khi tập dữ liệu nhỏ hoặc không được sắp xếp.

C. Khi cần hiệu suất nhanh nhất có thể.

D. Khi dữ liệu luôn được truy cập theo thứ tự.

7. Đâu là một ví dụ về cấu trúc dữ liệu mà các thuật toán tìm kiếm thường hoạt động trên đó?

A. Một hàm toán học.

B. Một chuỗi ký tự đơn lẻ.

C. Một mảng hoặc danh sách.

D. Một biến số nguyên.

8. Đâu là phương pháp tìm kiếm tuyến tính (tuần tự) cơ bản nhất?

A. Binary Search.

B. Linear Search.

C. Jump Search.

D. Interpolation Search.

9. Khi thực hiện tìm kiếm tuyến tính, nếu phần tử cần tìm nằm ở cuối cùng của danh sách, số lần so sánh sẽ là bao nhiêu?

A. 1 lần.

B. N/2 lần (trung bình).

C. N lần (với N là số phần tử).

D. Số lần so sánh không xác định.

10. Trong bài toán tìm kiếm, độ phức tạp thời gian (time complexity) đo lường điều gì?

A. Lượng bộ nhớ mà thuật toán sử dụng.

B. Số lượng lỗi cú pháp trong mã nguồn.

C. Thời gian thực thi của thuật toán tùy thuộc vào kích thước đầu vào.

D. Số dòng mã trong chương trình.

11. Trong lập trình, bài toán tìm kiếm với mục tiêu tìm kiếm một giá trị cụ thể trong một tập hợp dữ liệu được gọi chung là gì?

A. Bài toán sắp xếp.

B. Bài toán tìm kiếm.

C. Bài toán đếm.

D. Bài toán sinh mẫu.

12. Một thuật toán tìm kiếm có độ phức tạp thời gian O(log N) thường được biết đến là:

A. Tìm kiếm tuyến tính.

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

C. Tìm kiếm trên cây nhị phân không cân bằng.

D. Tìm kiếm trên danh sách liên kết đơn.

13. Trong tìm kiếm nhị phân, nếu giá trị cần tìm nhỏ hơn phần tử ở giữa, ta sẽ tìm kiếm tiếp ở đâu?

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

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

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

D. Tìm kiếm lại toàn bộ mảng.

14. Nếu thuật toán tìm kiếm nhị phân không tìm thấy phần tử cần tìm trong mảng đã sắp xếp, kết quả trả về thường là gì?

A. Vị trí của phần tử gần nhất.

B. Giá trị của phần tử đầu tiên.

C. Một giá trị chỉ định (ví dụ: -1 hoặc false).

D. Lỗi hệ thống.

15. Đâu không phải là một ứng dụng phổ biến của các thuật toán tìm kiếm?

A. Tìm kiếm tên trong danh bạ điện thoại.

B. Tìm kiếm sản phẩm trên trang thương mại điện tử.

C. Sắp xếp danh sách các bài hát theo thứ tự abc.

D. Tìm kiếm một từ khóa trong văn bản.

16. Thuật toán tìm kiếm Exponetial Search (tìm kiếm theo cấp số nhân) thường được sử dụng khi nào?

A. Khi tập dữ liệu rất nhỏ.

B. Khi tập dữ liệu đã được sắp xếp và có khả năng phần tử cần tìm nằm gần đầu danh sách.

C. Khi tập dữ liệu chưa được sắp xếp.

D. Khi không biết trước kích thước của tập dữ liệu.

17. Tìm kiếm nhị phân có thể được triển khai bằng phương pháp nào sau đây?

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

B. Chỉ bằng đệ quy.

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

D. Chỉ bằng vòng lặp for.

18. Giả sử bạn có một danh sách các số nguyên đã sắp xếp và bạn muốn tìm xem một số có tồn tại trong danh sách đó hay không. Thuật toán nào sau đây là phù hợp nhất?

A. Linear Search.

B. Binary Search.

C. Hash Table Lookup.

D. Linear Probing.

19. Đâu là một ví dụ về mảng hai chiều (2D array) mà bài toán tìm kiếm có thể áp dụng?

A. Danh sách các số nguyên.

B. Bảng tính (spreadsheet) với hàng và cột.

C. Một biến lưu trữ một số duy nhất.

D. Một chuỗi văn bản dài.

20. Độ phức tạp thời gian của thuật toán tìm kiếm tuyến tính (Linear Search) trên một mảng không sắp xếp có N phần tử là bao nhiêu trong trường hợp xấu nhất?

A. O(log N).

B. O(N).

C. O(N log N).

D. O(1).

21. Ưu điểm chính của thuật toán tìm kiếm nhị phân (Binary Search) so với tìm kiếm tuyến tính là gì?

A. Hoạt động hiệu quả trên danh sách không sắp xếp.

B. Độ phức tạp thời gian thường thấp hơn trên tập dữ liệu lớn.

C. Dễ dàng triển khai với mọi loại cấu trúc dữ liệu.

D. Không yêu cầu bộ nhớ bổ sung.

22. Thuật toán nào sau đây thuộc nhóm tìm kiếm nội suy (Interpolation Search), một biến thể của tìm kiếm nhị phân?

A. Linear Search.

B. Jump Search.

C. Interpolation Search.

D. Exponential Search.

23. Trong lập trình, thuật toán là gì?

A. Một ngôn ngữ lập trình.

B. Một thiết bị phần cứng.

C. Một tập hợp các bước hữu hạn, rõ ràng để giải quyết một bài toán.

D. Một loại dữ liệu.

24. Khi tìm kiếm trong một cấu trúc dữ liệu không có thứ tự, phương pháp nào là khả thi nhất để đảm bảo tìm thấy phần tử?

A. Binary Search.

B. Linear Search.

C. Jump Search.

D. Interpolation Search.

25. Nếu bạn có một tập dữ liệu rất lớn và bạn chỉ có thể truy cập các phần tử tuần tự với chi phí cao, thuật toán nào có thể hiệu quả hơn tìm kiếm nhị phân thông thường?

A. Linear Search.

B. Jump Search.

C. Quicksort.

D. Bubble Sort.