Trắc nghiệm Kết nối Tin học 11 KHMT bài 20 Thực hành bài toán tìm kiếm

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

A. O(log n)

B. O(1)

C. O(n^2)

D. O(n)

2. Ý tưởng cốt lõi của thuật toán tìm kiếm Jump Search là gì?

A. Kiểm tra tất cả các phần tử theo bước nhảy cố định.

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

C. Sử dụng cấu trúc cây để nhảy qua các phần tử không liên quan.

D. Duyệt qua từng phần tử cho đến khi tìm thấy.

3. Khi thực hành bài toán tìm kiếm, việc hiểu rõ độ phức tạp của thuật toán giúp chúng ta điều gì?

A. Chỉ ra cách viết mã nguồn.

B. Đánh giá hiệu quả và khả năng mở rộng của thuật toán với các bộ dữ liệu lớn.

C. Quyết định ngôn ngữ lập trình nào sẽ sử dụng.

D. Tăng cường bảo mật cho dữ liệu.

4. Trong một bài thực hành lập trình, khi viết hàm tìm kiếm, việc sử dụng đệ quy cho tìm kiếm nhị phân có ưu điểm gì so với vòng lặp?

A. Luôn nhanh hơn và sử dụng ít bộ nhớ hơn.

B. Cấu trúc code có thể gọn gàng và phản ánh trực tiếp logic chia để trị.

C. Không cần quản lý biến chỉ số đầu và cuối.

D. Xử lý tốt hơn trường hợp danh sách trống.

5. Nếu ta cần xây dựng một hệ thống tìm kiếm nhanh cho một cơ sở dữ liệu rất lớn, có thể bao gồm hàng tỷ bản ghi, thì thuật toán tìm kiếm nào là lựa chọn kém hiệu quả nhất?

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

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

C. Tìm kiếm dựa trên băm (Hash-based search).

D. Tìm kiếm cây nhị phân cân bằng (Balanced Binary Search Tree).

6. Một trong những ưu điểm chính của việc sử dụng cấu trúc dữ liệu mảng (array) để thực hiện tìm kiếm là gì?

A. Khả năng tự động sắp xếp dữ liệu.

B. Truy cập ngẫu nhiên (random access) đến bất kỳ phần tử nào bằng chỉ số.

C. Dễ dàng thêm hoặc xóa phần tử ở giữa.

D. Tiêu thụ ít bộ nhớ hơn danh sách liên kết.

7. Trong quá trình thực hành, nếu gặp lỗi IndexOutOfBoundsException khi truy cập phần tử mảng, nguyên nhân phổ biến nhất là gì?

A. Sử dụng sai tên biến.

B. Cố gắng truy cập một phần tử bằng chỉ số nằm ngoài phạm vi hợp lệ của mảng (ví dụ: âm hoặc lớn hơn hoặc bằng độ dài mảng).

C. Thiếu dấu chấm phẩy ở cuối câu lệnh.

D. Quên khai báo kiểu dữ liệu cho mảng.

8. Khi tìm kiếm một phần tử trong danh sách, tại sao việc sử dụng tìm kiếm nhị phân hiệu quả hơn tìm kiếm tuần tự đối với danh sách lớn đã sắp xếp?

A. Tìm kiếm nhị phân luôn chỉ cần một lần so sánh.

B. Tìm kiếm nhị phân giảm không gian tìm kiếm theo cấp số nhân, trong khi tìm kiếm tuần tự chỉ giảm tuyến tính.

C. Tìm kiếm tuần tự yêu cầu nhiều bộ nhớ hơn.

D. Tìm kiếm nhị phân có thể hoạt động trên cả danh sách không sắp xếp.

9. Trong trường hợp nào thì việc sử dụng thuật toán tìm kiếm tuần tự có thể hợp lý hơn tìm kiếm nhị phân, ngay cả khi danh sách đã sắp xếp?

A. Khi danh sách rất lớn và phần tử cần tìm thường nằm ở cuối.

B. Khi danh sách quá nhỏ, chi phí cho việc sắp xếp và logic phức tạp của tìm kiếm nhị phân không mang lại lợi ích.

C. Khi cần tìm tất cả các lần xuất hiện của một phần tử.

D. Khi danh sách có nhiều phần tử trùng lặp.

10. Khi tìm kiếm một giá trị trong danh sách, nếu giá trị đó không tồn tại, thuật toán tìm kiếm tuần tự thường trả về giá trị nào để biểu thị điều này?

A. Giá trị của phần tử đầu tiên trong danh sách.

B. Giá trị của phần tử cuối cùng trong danh sách.

C. -1 hoặc một giá trị đặc biệt khác không nằm trong phạm vi chỉ số hợp lệ.

D. Giá trị trung bình của danh sách.

11. Nếu một thuật toán tìm kiếm được mô tả là không có thứ tự (unordered), điều này có nghĩa là gì đối với cách hoạt động của nó?

A. Nó không thể tìm thấy phần tử đó.

B. Nó có thể sử dụng các cấu trúc dữ liệu đặc biệt để truy cập nhanh.

C. Nó không yêu cầu dữ liệu phải được sắp xếp để hoạt động hiệu quả.

D. Nó chỉ hoạt động trên các danh sách có kích thước nhỏ.

12. Trong bài toán tìm kiếm, ý nghĩa cơ bản của thuật toán tìm kiếm tuần tự (linear search) là gì?

A. Sắp xếp danh sách theo thứ tự tăng dần rồi tìm kiếm.

B. Kiểm tra lần lượt từng phần tử của danh sách cho đến khi tìm thấy hoặc hết danh sách.

C. Chia đôi danh sách và tìm kiếm ở một nửa.

D. Sử dụng cấu trúc dữ liệu cây để tăng tốc độ tìm kiếm.

13. Trong ngữ cảnh của bài toán tìm kiếm, thuật ngữ phạm vi tìm kiếm (search space) đề cập đến điều gì?

A. Tổng số lần so sánh cần thực hiện.

B. Tập hợp tất cả các phần tử có thể chứa phần tử cần tìm.

C. Số lượng bộ nhớ cần thiết cho thuật toán.

D. Độ dài của danh sách đầu vào.

14. Trong bối cảnh các bài toán tìm kiếm, thuật ngữ tồn tại (existence) của một phần tử thường được hiểu là gì?

A. Phần tử đó có giá trị lớn nhất trong danh sách.

B. Phần tử đó có mặt trong tập hợp dữ liệu đang được tìm kiếm.

C. Phần tử đó là phần tử đầu tiên trong danh sách.

D. Phần tử đó chỉ xuất hiện duy nhất một lần.

15. Nếu một hàm tìm kiếm trả về một giá trị là chỉ số của phần tử được tìm thấy, thì chỉ số (index) này thường bắt đầu từ đâu trong hầu hết các ngôn ngữ lập trình phổ biến (ví dụ: Python, Java, C++)?

A. Luôn bắt đầu từ 1.

B. Bắt đầu từ 0.

C. Bắt đầu từ giá trị của phần tử đầu tiên.

D. Phụ thuộc vào ngôn ngữ lập trình cụ thể, có thể bắt đầu từ 0 hoặc 1.

16. Khi triển khai tìm kiếm nhị phân trên một danh sách, ta cần quản lý các biến nào để xác định phạm vi tìm kiếm hiện tại?

A. Chỉ số bắt đầu và độ dài của danh sách.

B. Chỉ số bắt đầu và chỉ số kết thúc của phạm vi tìm kiếm hiện tại.

C. Giá trị trung bình và độ lệch chuẩn của danh sách.

D. Số lượng phần tử đã được kiểm tra.

17. Khi tìm kiếm một giá trị trong một danh sách mà ta biết rằng các giá trị có xu hướng phân bố không đồng đều (ví dụ: nhiều giá trị gần nhau ở đầu và thưa ở cuối), thuật toán nào có thể hiệu quả hơn tìm kiếm nhị phân?

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

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

C. Tìm kiếm nội suy (Interpolation Search).

D. Tìm kiếm Exponential (Exponential Search).

18. 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 đối với danh sách cần tìm kiếm?

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

B. Danh sách phải có cấu trúc cây.

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 chứa các phần tử duy nhất.

19. Giả sử ta có một danh sách các tên học sinh đã được sắp xếp theo thứ tự bảng chữ cái. Nếu muốn tìm tên của một học sinh cụ thể, việc sử dụng tìm kiếm nhị phân có thể loại bỏ bao nhiêu phần trăm dữ liệu không cần thiết sau mỗi lần so sánh?

A. Khoảng 25%

B. Khoảng 50%

C. Khoảng 75%

D. Tùy thuộc vào tên cần tìm, không có tỷ lệ cố định.

20. Khái niệm phần tử trung vị (median element) trong thuật toán tìm kiếm nhị phân thường được xác định như thế nào?

A. Luôn là phần tử đầu tiên của danh sách.

B. Là phần tử có giá trị nhỏ nhất trong danh sách.

C. Là phần tử nằm ở giữa danh sách, thường được tính bằng chỉ số (đầu + cuối) / 2.

D. Là phần tử có giá trị lớn nhất trong danh sách.

21. Trong bài toán thực hành tìm kiếm, nếu ta có một danh sách lớn các số nguyên và cần tìm một số cụ thể một cách nhanh chóng, thuật toán nào thường được ưu tiên hơn nếu danh sách đã đượ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 nội suy (Interpolation Search).

D. Tìm kiếm Jump (Jump Search).

22. Trong lập trình, khi triển khai thuật toán tìm kiếm tuần tự, vòng lặp thường được sử dụng để làm gì?

A. Để khởi tạo giá trị ban đầu cho biến đếm.

B. Để duyệt qua từng phần tử của mảng hoặc danh sách.

C. Để lưu trữ kết quả tìm kiếm.

D. Để xác định độ dài của danh sách.

23. Độ 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 là bao nhiêu trong trường hợp trung bình và xấu nhất?

A. O(n)

B. O(n log n)

C. O(log n)

D. O(1)

24. Trong tìm kiếm nhị phân, sau khi so sánh phần tử giữa với phần tử cần tìm, nếu phần tử giữa lớn hơn phần tử cần tìm, thì bước tiếp theo là gì?

A. Tìm kiếm ở nửa bên phải của danh sách.

B. Tìm kiếm ở nửa bên trái của danh sách.

C. Kết thúc tìm kiếm và báo không tìm thấy.

D. Duyệt lại từ đầu danh sách.

25. Trong bài toán tìm kiếm, khi so sánh hiệu quả giữa tìm kiếm tuần tự và tìm kiếm nhị phân trên một danh sách có 1.000.000 phần tử đã sắp xếp, sự khác biệt về số lần so sánh tối đa là bao nhiêu?

A. Tìm kiếm nhị phân ít hơn khoảng 100 lần.

B. Tìm kiếm nhị phân ít hơn khoảng 1.000 lần.

C. Tìm kiếm nhị phân ít hơn khoảng 10.000 lần.

D. Tìm kiếm nhị phân ít hơn khoảng 100.000 lần.