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

1. Hàm `bisect_left` trong module `bisect` của Python dùng để làm gì?

A. Tìm kiếm tuần tự một phần tử trong danh sách đã sắp xếp.

B. Chèn một phần tử vào danh sách đã sắp xếp tại vị trí thích hợp để duy trì thứ tự, trả về chỉ số của vị trí đó.

C. Tìm kiếm nhị phân một phần tử và trả về True/False.

D. Trả về chỉ số của phần tử đầu tiên trong danh sách lớn hơn hoặc bằng giá trị cho trước.

2. Trong tìm kiếm nhị phân, làm thế nào để tính toán chỉ số của phần tử ở giữa (`mid`) để tránh tràn số nguyên (integer overflow) trên một số ngôn ngữ lập trình?

A. mid = (low + high) / 2

B. mid = low + (high - low) / 2

C. mid = high - (high - low) / 2

D. mid = (low * high) / 2

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

A. O(1)

B. O(log N)

C. O(N)

D. O(N^2)

4. Độ phức tạp thời gian để tìm kiếm một phần tử cụ thể trong một danh sách liên kết đơn có N phần tử là bao nhiêu (trường hợp xấu nhất)?

A. O(1)

B. O(log N)

C. O(N)

D. O(N^2)

5. Trong thuật toán tìm kiếm nhị phân, nếu `low` lớn hơn `high`, điều này có ý nghĩa gì?

A. Phần tử đã được tìm thấy.

B. Phần tử không có trong mảng.

C. Cần tiếp tục tìm kiếm.

D. Đã xảy ra lỗi trong quá trình tìm kiếm.

6. Tìm kiếm nhị phân có thể được xem là một dạng của chiến lược chia để trị (divide and conquer) vì sao?

A. Nó chia nhỏ vấn đề thành hai bài toán con giống hệt nhau.

B. Nó chia nhỏ vấn đề thành hai bài toán con, giải quyết từng bài toán và kết hợp kết quả.

C. Nó chia phạm vi tìm kiếm thành hai phần và loại bỏ một phần.

D. Nó chia mảng thành nhiều phần nhỏ và tìm kiếm tuần tự từng phần.

7. Hàm `list.count(value)` trong Python được sử dụng để làm gì liên quan đến tìm kiếm?

A. Tìm kiếm vị trí đầu tiên của value.

B. Kiểm tra xem value có tồn tại trong danh sách hay không.

C. Đếm số lần xuất hiện của value trong danh sách.

D. Tìm kiếm nhị phân và trả về vị trí gần đúng.

8. Trong bài toán tìm kiếm tuần tự trên mảng đã sắp xếp, điều kiện dừng của vòng lặp `while` khi tìm kiếm phần tử `x` là gì?

A. Chỉ số hiện tại vượt quá độ dài mảng.

B. Phần tử tại chỉ số hiện tại bằng với phần tử cần tìm.

C. Chỉ số hiện tại vượt quá độ dài mảng HOẶC phần tử tại chỉ số hiện tại bằng với phần tử cần tìm.

D. Phần tử tại chỉ số hiện tại lớn hơn phần tử cần tìm.

9. Ưu điểm chính của tìm kiếm nhị phân so với tìm kiếm tuần tự là gì?

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

B. Nhanh hơn đáng kể khi tìm kiếm trên tập dữ liệu lớn.

C. Có thể áp dụng cho dữ liệu chưa sắp xếp.

D. Dễ cài đặt hơn.

10. Nếu một mảng có N phần tử và bạn đang tìm kiếm một phần tử không tồn tại trong mảng bằng tìm kiếm tuần tự, bạn sẽ thực hiện bao nhiêu phép so sánh?

A. 0 phép so sánh.

B. Khoảng N/2 phép so sánh.

C. N phép so sánh.

D. N^2 phép so sánh.

11. Để tìm kiếm hiệu quả một phần tử trong tập dữ liệu lớn, lựa chọn nào sau đây là tốt nhất?

A. Sắp xếp dữ liệu và sử dụng tìm kiếm tuần tự.

B. Sắp xếp dữ liệu và sử dụng tìm kiếm nhị phân.

C. Sử dụng tìm kiếm tuần tự mà không cần sắp xếp.

D. Sử dụng tìm kiếm nhị phân mà không cần sắp xếp.

12. Mục đích của việc sử dụng biến `mid` trong thuật toán tìm kiếm nhị phân là gì?

A. Lưu trữ giá trị của phần tử cần tìm.

B. Lưu trữ chỉ số bắt đầu của phạm vi tìm kiếm.

C. Lưu trữ chỉ số của phần tử ở giữa phạm vi tìm kiếm hiện tại.

D. Lưu trữ độ dài của mảng.

13. Trong Python, nếu bạn sử dụng `numpy.searchsorted(a, v)` với mảng `a` đã sắp xếp, hành vi của nó tương tự như hàm nào đã được đề cập?

A. list.index()

B. list.count()

C. bisect.bisect_left()

D. list.append()

14. Khi tìm kiếm một phần tử trong danh sách liên kết đơn, điều gì xảy ra nếu phần tử đó không tồn tại?

A. Thuật toán dừng ngay lập tức.

B. Thuật toán sẽ duyệt qua tất cả các nút cho đến khi con trỏ `next` là null.

C. Thuật toán sẽ trả về một giá trị đặc biệt (ví dụ: -1 hoặc null).

D. Thuật toán sẽ gây ra lỗi tràn bộ nhớ.

15. Khi thực hiện tìm kiếm tuần tự trên một chuỗi ký tự, chúng ta đang tìm kiếm gì?

A. Một ký tự cụ thể.

B. Một chuỗi con (substring) cụ thể.

C. Cả ký tự và chuỗi con.

D. Vị trí của ký tự kết thúc chuỗi.

16. Trong lập trình Python, hàm `list.index(value)` thực hiện tìm kiếm gì và trả về gì?

A. Tìm kiếm nhị phân, trả về True nếu tìm thấy, False nếu không.

B. Tìm kiếm tuần tự, trả về chỉ số của phần tử đầu tiên tìm thấy hoặc báo lỗi nếu không có.

C. Tìm kiếm nhị phân, trả về chỉ số của phần tử đầu tiên tìm thấy hoặc -1 nếu không có.

D. Tìm kiếm tuần tự, trả về True nếu tìm thấy, False nếu không.

17. Thuật toán tìm kiếm nhị phân yêu cầu điều kiện tiên quyết gì đối với dữ liệu đầu vào?

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 là duy nhất, không có phần tử trùng lặp.

D. Dữ liệu phải có kích thước là lũy thừa của 2.

18. Trong bài toán tìm kiếm, nếu chúng ta cần tìm một phần tử trong một tập hợp các phần tử mà thứ tự của chúng không quan trọng và chúng ta chỉ quan tâm đến việc phần tử có tồn tại hay không, cấu trúc dữ liệu nào thường được ưu tiên?

A. Mảng đã sắp xếp.

B. Danh sách liên kết.

C. Tập hợp (Set) hoặc Bảng băm (Hash Table).

D. Cây nhị phân tìm kiếm.

19. Nếu bạn có một danh sách rất lớn và cần thực hiện nhiều truy vấn tìm kiếm riêng lẻ, lựa chọn nào là tối ưu nhất về hiệu suất?

A. Sắp xếp danh sách một lần và sử dụng tìm kiếm nhị phân cho mỗi truy vấn.

B. Sử dụng tìm kiếm tuần tự cho mỗi truy vấn mà không cần sắp xếp.

C. Chuyển đổi danh sách sang cấu trúc dữ liệu khác như hash table.

D. Thực hiện tìm kiếm tuần tự và chỉ dừng lại khi tìm thấy.

20. Độ phức tạp thời gian của thuật toán tìm kiếm nhị phân trên một mảng có N phần tử trong trường hợp trung bình là bao nhiêu?

A. O(1)

B. O(log N)

C. O(N)

D. O(N log N)

21. Yếu tố nào sau đây không phải là yếu tố quyết định hiệu quả của thuật toán tìm kiếm?

A. Kích thước của tập dữ liệu.

B. Tính sắp xếp của dữ liệu.

C. Tốc độ xử lý của CPU.

D. Độ phức tạp thời gian của thuật toán.

22. Trong thuật toán tìm kiếm nhị phân, nếu phần tử cần tìm bằng với phần tử ở giữa, hành động tiếp theo là gì?

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

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

C. Thuật toán kết thúc và trả về chỉ số của phần tử đó.

D. So sánh với phần tử tiếp theo để xác định.

23. Khi thực hiện tìm kiếm nhị phân, nếu phần tử cần tìm nhỏ hơn phần tử ở giữa mảng, chúng ta sẽ tiếp tục tìm kiếm ở đâu?

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

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

C. Toàn bộ mảng.

D. Vị trí phần tử ở giữa.

24. Khi so sánh tìm kiếm tuần tự và tìm kiếm nhị phân, trường hợp nào tìm kiếm tuần tự có thể hiệu quả hơn?

A. Khi mảng có kích thước rất lớn và đã được sắp xếp.

B. Khi mảng có kích thước nhỏ hoặc phần tử cần tìm nằm ở vị trí đầu.

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

D. Khi cần tìm kiếm nhiều lần trên cùng một tập dữ liệu.

25. Trong tìm kiếm tuần tự, nếu chúng ta tìm thấy phần tử cần tìm tại vị trí `i`, thuật toán có cần tiếp tục kiểm tra các phần tử từ `i+1` trở đi không?

A. Có, để đảm bảo tìm được tất cả các lần xuất hiện.

B. Không, thuật toán thường dừng lại sau khi tìm thấy lần xuất hiện đầu tiên.

C. Chỉ khi phần tử đó là phần tử cuối cùng của mảng.

D. Phụ thuộc vào việc mảng có sắp xếp hay không.