Trắc nghiệm Chân trời Tin học 7 bài 13 Thuật toán tìm kiếm

1. Trong tìm kiếm nhị phân, bước tiếp theo sau khi xác định phần tử giữa là gì nếu phần tử giữa lớn hơn giá trị cần tìm?

A. Tìm kiếm trong nửa trái của danh sách.

B. Tìm kiếm trong nửa phải của danh sách.

C. So sánh với phần tử cuối.

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

2. So sánh hai thuật toán tìm kiếm tuần tự và tìm kiếm nhị phân trên một danh sách lớn đã sắp xếp, thuật toán nào thường được ưa chuộng hơn về hiệu suất?

A. Tìm kiếm tuần tự, vì nó đơn giản hơn.

B. Tìm kiếm nhị phân, vì nó nhanh hơn.

C. Cả hai đều có hiệu suất tương đương.

D. Phụ thuộc vào ngôn ngữ lập trình.

3. Phát biểu nào sau đây mô tả đúng về tìm kiếm tuần tự?

A. Nó yêu cầu danh sách phải được sắp xếp.

B. Nó có hiệu quả cao đối với các danh sách rất lớn.

C. Nó kiểm tra từng phần tử một cho đến khi tìm thấy hoặc hết danh sách.

D. Nó luôn nhanh hơn tìm kiếm nhị phân.

4. Khi nào thì việc sử dụng thuật toán tìm kiếm tuần tự là hợp lý nhất?

A. Khi danh sách rất lớn và đã được sắp xếp.

B. Khi danh sách nhỏ hoặc không chắc chắn về việc nó đã được sắp xếp hay chưa.

C. Khi cần tìm kiếm nhiều lần trên cùng một danh sách lớn.

D. Khi cần độ chính xác tuyệt đối và tốc độ không quan trọng.

5. Yếu tố nào quyết định hiệu quả của thuật toán tìm kiếm nhị phân?

A. Số lượng phần tử có giá trị trùng lặp.

B. Thứ tự sắp xếp của danh sách.

C. Giá trị trung bình của các phần tử.

D. Số lượng phần tử chẵn/lẻ.

6. Đâu là đặc điểm chính của trường hợp xấu nhất (worst-case scenario) trong thuật toán tìm kiếm?

A. Thuật toán tìm thấy giá trị ngay lần so sánh đầu tiên.

B. Thuật toán yêu cầu số bước thực hiện nhiều nhất.

C. Thuật toán yêu cầu số bước thực hiện ít nhất.

D. Thuật toán không tìm thấy giá trị.

7. Phát biểu nào sau đây mô tả chính xác ưu điểm của tìm kiếm nhị phân so với tìm kiếm tuần tự?

A. Tìm kiếm nhị phân có thể áp dụng cho danh sách không sắp xếp.

B. Tìm kiếm nhị phân thường nhanh hơn tìm kiếm tuần tự trên các danh sách lớn.

C. Tìm kiếm nhị phân yêu cầu ít bộ nhớ hơn.

D. Tìm kiếm nhị phân dễ cài đặt hơn.

8. Trong thuật toán tìm kiếm tuần tự, nếu phần tử cần tìm không có trong danh sách, quá trình tìm kiếm sẽ kết thúc sau bao nhiêu lần so sánh?

A. 0 lần so sánh.

B. Số phần tử trong danh sách.

C. 1 lần so sánh.

D. Số phần tử trong danh sách trừ đi 1.

9. Khi tìm kiếm một phần tử trong một danh sách không được sắp xếp, thuật toán nào sau đây là lựa chọn phù hợp nhất?

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

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

C. Tìm kiếm cây.

D. Tìm kiếm trên đồ thị.

10. Một danh sách đã sắp xếp có 100 phần tử. Sử dụng tìm kiếm nhị phân để tìm một phần tử. Số lần so sánh tối đa ước tính là bao nhiêu?

A. 100.

B. 50.

C. Khoảng 7 (vì 2^7 = 128).

D. Khoảng 6 (vì 2^6 = 64).

11. Độ phức tạp thời gian của thuật toán tìm kiếm nhị phân trên một danh sách đã sắp xếp có n phần tử, trong trường hợp xấu nhất, là bao nhiêu?

A. O(n)

B. O(n log n)

C. O(log n)

D. O(1)

12. Khi nói về thuật toán tìm kiếm, độ phức tạp thường đề cập đến điều gì?

A. Số lượng bộ nhớ cần sử dụng.

B. Thời gian thực thi hoặc số lượng phép toán.

C. Khả năng dễ hiểu của thuật toán.

D. Mức độ trừu tượng của thuật toán.

13. Thuật toán tìm kiếm nhị phân yêu cầu điều kiện tiên quyết nào để hoạt động hiệu quả?

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

B. Danh sách phải chứa các phần tử là số nguyên.

C. Danh sách phải được sắp xếp theo thứ tự tăng dần (hoặc giảm dần).

D. Danh sách phải có ít nhất 10 phần tử.

14. Trong thuật toán tìm kiếm nhị phân, sau khi so sánh phần tử giữa với giá trị cần tìm, nếu phần tử giữa nhỏ hơn giá trị cần tìm, ta sẽ tiếp tục tìm kiếm ở đâu?

A. Nửa trái của danh sách.

B. Nửa phải của danh sách.

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

D. Phần tử ngay sau phần tử giữa.

15. Trong tìm kiếm nhị phân, bước đầu tiên là xác định giới hạn dưới và giới hạn trên của phạm vi tìm kiếm. Giới hạn dưới thường được gán giá trị nào?

A. 1

B. 0

C. n (số phần tử)

D. -1

16. Giả sử bạn đang tìm kiếm một tên trong danh bạ điện thoại đã được sắp xếp theo tên. Bạn mở danh bạ đến trang giữa và thấy tên bạn tìm nằm trước tên ở trang giữa. Bước tiếp theo bạn nên làm là gì?

A. Tiếp tục tìm kiếm ở nửa sau của danh bạ.

B. So sánh lại với tên đầu tiên.

C. Tìm kiếm trong nửa đầu của danh bạ.

D. Tìm kiếm tuần tự từ đầu.

17. Một danh sách có 100 phần tử. Sử dụng tìm kiếm tuần tự để tìm một phần tử ở cuối danh sách. Số lần so sánh ước tính là bao nhiêu?

A. Khoảng 50.

B. 100.

C. 1.

D. 50.

18. Nếu bạn được cung cấp một tập hợp các số điện thoại và cần tìm số điện thoại của một người cụ thể, nhưng danh sách này chưa được sắp xếp, bạn sẽ sử dụng thuật toán tìm kiếm nào?

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

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

C. Tìm kiếm theo băm.

D. Tìm kiếm cây nhị phân.

19. Yếu tố nào sau đây KHÔNG phải là yêu cầu để thực hiện tìm kiếm nhị phân?

A. Danh sách phải có các phần tử duy nhất.

B. Danh sách phải được sắp xếp.

C. Cần có khả năng truy cập ngẫu nhiên tới các phần tử.

D. Giá trị cần tìm phải nằm trong phạm vi của danh sách.

20. Nếu một danh sách có n phần tử và ta sử dụng tìm kiếm tuần tự, thì trường hợp tốt nhất (best-case scenario) là khi nào?

A. Phần tử cần tìm ở cuối danh sách.

B. Phần tử cần tìm không có trong danh sách.

C. Phần tử cần tìm ở đầu danh sách.

D. Danh sách rỗng.

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

A. Dừng tìm kiếm và trả về vị trí của phần tử giữa.

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

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

D. So sánh lại với phần tử đầu tiên.

22. Trong thuật toán tìm kiếm tuần tự, nếu phần tử cần tìm nằm ở cuối danh sách, số lần so sánh tối đa có thể xảy ra là bao nhiêu?

A. Số phần tử trong danh sách trừ đi 1.

B. Số phần tử trong danh sách.

C. 1 lần so sánh.

D. Số phần tử trong danh sách cộng thêm 1.

23. Độ phức tạp thời gian của thuật toán tìm kiếm tuần tự trên một danh sách có n phần tử, trong trường hợp xấu nhất, là bao nhiêu?

A. O(log n)

B. O(n^2)

C. O(n)

D. O(1)

24. Thuật toán tìm kiếm nào có thể áp dụng để tìm kiếm một từ trong một cuốn từ điển đã được sắp xếp?

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

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

C. Tìm kiếm băm.

D. Tìm kiếm theo đồ thị.

25. Nếu một thuật toán tìm kiếm phải kiểm tra mọi phần tử của danh sách để tìm thấy giá trị mong muốn, thì nó là loại thuật toán nào?

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

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

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

D. Tìm kiếm theo từ khóa.