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

1. Độ 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 có N phần tử là bao nhiêu trong trường hợp trung bình?

A. O(N)

B. O(N log N)

C. O(log N)

D. O(1)

2. Nếu một cây tìm kiếm nhị phân bị mất cân bằng (ví dụ: trở thành một danh sách liên kết), độ phức tạp tìm kiếm sẽ tệ nhất là bao nhiêu?

A. O(log N)

B. O(N)

C. O(N^2)

D. O(1)

3. Sự khác biệt chính giữa tìm kiếm nhị phân đệ quy và tìm kiếm nhị phân lặp (iterative) là gì?

A. Tìm kiếm nhị phân lặp sử dụng bộ nhớ stack, trong khi đệ quy thì không.

B. Tìm kiếm nhị phân đệ quy có thể gây tràn bộ nhớ stack nếu độ sâu đệ quy lớn.

C. Tìm kiếm nhị phân lặp luôn nhanh hơn tìm kiếm nhị phân đệ quy.

D. Tìm kiếm nhị phân đệ quy chỉ hoạt động trên cây, còn lặp thì không.

4. Khi nào thì việc triển khai tìm kiếm bằng cách sử dụng chỉ mục (index) trong cơ sở dữ liệu là hiệu quả nhất?

A. Khi bảng chỉ có một vài bản ghi.

B. Khi chỉ mục được xây dựng trên cột được truy vấn thường xuyên và dữ liệu có sự phân bố đa dạng.

C. Khi chỉ mục được tạo trên cột có giá trị trùng lặp cao.

D. Khi không có yêu cầu về tốc độ truy vấn.

5. Tìm kiếm nội suy (Interpolation Search) cải thiện hiệu suất so với tìm kiếm nhị phân trong trường hợp nào?

A. Khi dữ liệu được phân phối ngẫu nhiên.

B. Khi dữ liệu được phân phối đồng đều hoặc có xu hướng tuyến tính.

C. Khi kích thước danh sách rất nhỏ.

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

6. Trong thuật toán tìm kiếm nhị phân, bước đầu tiên sau khi chọn điểm giữa là gì?

A. So sánh phần tử tại điểm giữa với phần tử cần tìm.

B. Chia đôi phần còn lại của danh sách thành hai nửa.

C. Bắt đầu lại quá trình tìm kiếm từ đầu danh sách.

D. Sắp xếp lại danh sách để đảm bảo tính nhất quán.

7. Thuật toán tìm kiếm tuyến tính (Linear Search) thực hiện công việc như thế nào?

A. Chia đôi danh sách và tìm kiếm ở một nửa phù hợp.

B. Kiểm tra lần lượt từng phần tử của danh sách từ đầu đến cuối.

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

D. Dựa vào giá trị hash của phần tử để truy cập trực tiếp.

8. Trong lập trình Python, hàm `list.index(value)` hoạt động tương tự với thuật toán tìm kiếm nào?

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

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

C. Tìm kiếm nội suy.

D. Tìm kiếm nhảy.

9. Thuật toán tìm kiếm nhị phân (Binary Search) yêu cầu điều kiện tiên quyết nào về tập dữ liệu?

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 có cấu trúc cây nhị phân.

D. Dữ liệu phải là duy nhất, không có phần tử trùng lặp.

10. Khi nào một thuật toán tìm kiếm được coi là ổn định (stable)?

A. Khi nó luôn tìm thấy phần tử.

B. Khi nó có độ phức tạp thời gian không đổi.

C. Khi nó giữ nguyên thứ tự tương đối của các phần tử bằng nhau.

D. Khi nó hoạt động hiệu quả trên cả dữ liệu đã sắp xếp và chưa sắp xếp.

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

A. O(log N)

B. O(1)

C. O(N)

D. O(N^2)

12. Nếu bạn có một danh sách lớn các số nguyên đã được sắp xếp và cần tìm kiếm một giá trị cụ thể một cách nhanh chóng, bạn nên ưu tiên sử dụng thuật toán nào?

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

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

C. Tìm kiếm brute-force.

D. Tìm kiếm dựa trên băm (hashing).

13. Khi nào thuật toán tìm kiếm nhị phân sẽ gặp hiệu quả kém hơn hoặc không thể áp dụng so với tìm kiếm tuyến tính?

A. Khi danh sách có kích thước rất nhỏ, dưới 10 phần tử.

B. Khi dữ liệu không được sắp xếp và cần sắp xếp lại liên tục.

C. Khi cần tìm kiếm nhiều lần trên cùng một tập dữ liệu lớn đã sắp xếp.

D. Khi sử dụng các cấu trúc dữ liệu phi tuyến tính.

14. Trong bài toán tìm kiếm, yếu tố nào là quan trọng nhất để lựa chọn thuật toán phù hợp về hiệu quả và độ phức tạp?

A. Kích thước của tập dữ liệu và cấu trúc của dữ liệu đó.

B. Ngôn ngữ lập trình được sử dụng để triển khai thuật toán.

C. Môi trường hoạt động của chương trình (hệ điều hành, phần cứng).

D. Sự quen thuộc của lập trình viên với các thuật toán tìm kiếm khác nhau.

15. Một cách để cải thiện hiệu suất tìm kiếm trên một tập dữ liệu lớn không sắp xếp là gì?

A. Sử dụng thuật toán tìm kiếm nhị phân trực tiếp.

B. Sắp xếp dữ liệu trước, sau đó sử dụng tìm kiếm nhị phân.

C. Chỉ sử dụng tìm kiếm tuyến tính.

D. Xây dựng một cây tìm kiếm nhị phân từ dữ liệu chưa sắp xếp.

16. Trong lập trình, việc sử dụng một vòng lặp `while` với điều kiện `low <= high` thường thấy trong thuật toán nào?

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

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

C. Sắp xếp nổi bọt.

D. Duyệt cây theo chiều rộng.

17. Yếu tố nào làm cho thuật toán tìm kiếm nhị phân vượt trội hơn tìm kiếm tuyến tính đối với các tập dữ liệu lớn và đã sắp xếp?

A. Khả năng xử lý dữ liệu không được sắp xếp.

B. Độ phức tạp thời gian giảm dần theo kích thước dữ liệu.

C. Giảm phạm vi tìm kiếm một nửa ở mỗi bước.

D. Yêu cầu ít bộ nhớ hơn.

18. Độ phức tạp thời gian của thuật toán tìm kiếm nhảy trên một danh sách có N phần tử, với kích thước bước nhảy là sqrt(N), là bao nhiêu?

A. O(N)

B. O(log N)

C. O(sqrt N)

D. O(N log N)

19. Khi nào việc sử dụng cấu trúc dữ liệu Hash Table sẽ mang lại hiệu suất tìm kiếm trung bình tốt nhất (gần O(1))?

A. Khi có nhiều xung đột băm (hash collisions) xảy ra.

B. Khi hàm băm phân phối các khóa dữ liệu một cách đồng đều.

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

D. Khi kích thước của bảng băm nhỏ hơn số lượng phần tử.

20. Trong bài toán tìm kiếm, yếu tố nào liên quan đến độ phức tạp không gian (space complexity)?

A. Số lượng phép so sánh cần thiết để tìm thấy phần tử.

B. Lượng bộ nhớ phụ mà thuật toán yêu cầu để hoạt động.

C. Thời gian tối đa mà thuật toán cần để hoàn thành.

D. Số bước lặp trong vòng lặp chính của thuật toán.

21. Phân tích độ phức tạp trường hợp xấu nhất (worst-case complexity) của một thuật toán tìm kiếm nhằm mục đích gì?

A. Ước tính thời gian thực thi trung bình trên các đầu vào khác nhau.

B. Đảm bảo thuật toán luôn hoạt động trong một giới hạn thời gian nhất định.

C. Tìm kiếm hiệu quả nhất trên các đầu vào được sắp xếp.

D. Đánh giá thời gian thực thi trong trường hợp đầu vào gây khó khăn nhất cho thuật toán.

22. Thuật toán tìm kiếm nhảy (Jump Search) hoạt động dựa trên nguyên tắc nào?

A. Kiểm tra tất cả các phần tử cách đều nhau, sau đó tìm tuyến tính.

B. Chia danh sách thành các khối nhỏ và tìm kiếm trong khối phù hợp.

C. Sử dụng hàm băm để xác định khối chứa phần tử.

D. Áp dụng tìm kiếm nhị phân trên toàn bộ danh sách.

23. Nếu bạn cần tìm tất cả các lần xuất hiện của một từ khóa trong một văn bản lớn, thuật toán nào sẽ phù hợp nhất?

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

B. Tìm kiếm tuyến tính hoặc các thuật toán tìm kiếm chuỗi nâng cao (KMP, Boyer-Moore).

C. Tìm kiếm nội suy.

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

24. Các thuật toán tìm kiếm trên chuỗi (String Searching Algorithms) như KMP (Knuth-Morris-Pratt) và Boyer-Moore giúp cải thiện hiệu suất bằng cách nào?

A. Bỏ qua các ký tự không khớp một cách thông minh dựa trên mẫu.

B. Kiểm tra tất cả các vị trí có thể của mẫu trong văn bản.

C. Sử dụng băm để đối sánh chuỗi.

D. Chia văn bản thành các phần nhỏ và xử lý song song.

25. Trong cấu trúc dữ liệu cây tìm kiếm nhị phân (Binary Search Tree - BST), khi tìm kiếm một giá trị, nếu giá trị đó nhỏ hơn nút hiện tại, chúng ta sẽ di chuyển đi đâu?

A. Sang nút con bên phải.

B. Sang nút con bên trái.

C. Sang nút cha.

D. Kết thúc tìm kiếm.