[KNTT] Trắc nghiệm Tin học 7 bài 14 Thuật toán tìm kiếm tuần tự

1. Giả sử có một danh sách gồm các số nguyên: [5, 12, 8, 3, 15]. Nếu ta tìm kiếm số 8 bằng thuật toán tìm kiếm tuần tự, bao nhiêu phép so sánh sẽ được thực hiện?

A. 1

B. 2

C. 3

D. 4

2. Độ phức tạp không gian (Space Complexity) của thuật toán tìm kiếm tuần tự là bao nhiêu?

A. O(1)

B. O(N)

C. O(log N)

D. O(N^2)

3. Khi so sánh 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 đã được sắp xếp, tìm kiếm nhị phân thường hiệu quả hơn bởi vì:

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

B. Tìm kiếm nhị phân chia đôi phạm vi tìm kiếm ở mỗi bước.

C. Tìm kiếm tuần tự yêu cầu sắp xếp danh sách trước.

D. Tìm kiếm nhị phân có độ phức tạp không gian lớn hơn.

4. Trong một danh sách rỗng, nếu áp dụng thuật toán tìm kiếm tuần tự để tìm một phần tử, kết quả sẽ là gì?

A. Tìm thấy phần tử ở vị trí đầu tiên.

B. Thuật toán sẽ bị lỗi do không có phần tử nào để so sánh.

C. Thông báo không tìm thấy phần tử.

D. Trường hợp này không thể xảy ra theo định nghĩa thuật toán.

5. Nếu danh sách chứa các phần tử trùng lặp và ta sử dụng tìm kiếm tuần tự để tìm một giá trị, thuật toán sẽ trả về vị trí của:

A. Tất cả các vị trí chứa giá trị đó.

B. Vị trí của phần tử trùng lặp đầu tiên được tìm thấy.

C. Vị trí của phần tử trùng lặp cuối cùng được tìm thấy.

D. Ngẫu nhiên một trong các vị trí chứa giá trị đó.

6. Trong thuật toán tìm kiếm tuần tự, việc kiểm tra xem toàn bộ danh sách đã được duyệt hết chưa là một phần quan trọng của điều kiện dừng. Đúng hay Sai?

A. Đúng, để đảm bảo thuật toán kết thúc khi không tìm thấy phần tử.

B. Sai, chỉ cần so sánh với phần tử hiện tại là đủ.

C. Đúng, nhưng chỉ khi phần tử cần tìm nằm ở cuối danh sách.

D. Sai, điều kiện dừng chỉ phụ thuộc vào việc tìm thấy phần tử.

7. Phát biểu nào sau đây mô tả đúng nhất cách thức hoạt động của thuật toán tìm kiếm tuần tự?

A. Chia danh sách thành hai nửa và loại bỏ một nửa không chứa phần tử cần tìm.

B. Duyệt qua từng phần tử của danh sách từ đầu đến cuối, so sánh với khóa tìm kiếm.

C. Sử dụng một hàm băm để xác định vị trí có thể chứa phần tử.

D. Tạo một cây tìm kiếm và duyệt qua các nút của cây.

8. Trong thuật toán tìm kiếm tuần tự, khi thực hiện so sánh phần tử hiện tại của danh sách với khóa tìm kiếm, nếu phần tử hiện tại KHÔNG khớp với khóa, hành động tiếp theo của thuật toán là gì?

A. Chuyển sang so sánh với phần tử tiếp theo trong danh sách.

B. Dừng thuật toán và thông báo không tìm thấy.

C. So sánh lại phần tử hiện tại với khóa tìm kiếm.

D. Báo lỗi và thoát khỏi chương trình.

9. Yếu tố nào sau đây KHÔNG phải là điều kiện tiên quyết để áp dụng thuật toán tìm kiếm tuần tự một cách hiệu quả?

A. Danh sách có thể chưa được sắp xếp.

B. Danh sách có thể có các phần tử trùng lặp.

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

D. Danh sách có thể có kích thước thay đổi.

10. Nếu danh sách chứa các phần tử có kiểu dữ liệu khác nhau và ta thực hiện tìm kiếm tuần tự, điều gì có thể xảy ra nếu không có cơ chế xử lý kiểu dữ liệu phù hợp?

A. Thuật toán sẽ luôn tìm thấy phần tử.

B. Có thể xảy ra lỗi so sánh hoặc kết quả không mong muốn.

C. Thuật toán sẽ tự động chuyển đổi kiểu dữ liệu.

D. Tìm kiếm tuần tự không hoạt động với các kiểu dữ liệu khác nhau.

11. Phát biểu nào sau đây là sai về thuật toán tìm kiếm tuần tự?

A. Nó có thể được áp dụng cho danh sách có thứ tự bất kỳ.

B. Hiệu quả của nó phụ thuộc vào vị trí của phần tử cần tìm.

C. Nó là thuật toán tìm kiếm nhanh nhất cho mọi trường hợp.

D. Nó duyệt qua từng phần tử một theo một trình tự nhất định.

12. Nếu ta muốn tìm tất cả các vị trí của một giá trị cụ thể trong danh sách bằng tìm kiếm tuần tự, ta cần điều chỉnh thuật toán như thế nào?

A. Dừng ngay khi tìm thấy lần khớp đầu tiên.

B. Tiếp tục duyệt qua toàn bộ danh sách, ghi lại tất cả các vị trí khớp.

C. Bỏ qua các phần tử trùng lặp.

D. Sử dụng một cấu trúc dữ liệu khác thay thế.

13. Tìm kiếm tuần tự phù hợp nhất cho loại cấu trúc dữ liệu nào sau đây?

A. Mảng (Array) hoặc Danh sách liên kết (Linked List) chưa sắp xếp.

B. Cây nhị phân tìm kiếm (Binary Search Tree).

C. Heap.

D. Đồ thị (Graph).

14. Trong Python, đoạn mã sau đây thực hiện tìm kiếm tuần tự cho giá trị target trong danh sách my_list: ```python for i in range(len(my_list)): if my_list[i] == target: return i return -1 ``` Nếu target không có trong my_list, giá trị trả về sẽ là gì?

A. 0

B. -1

C. None

D. ValueError

15. Thuật toán tìm kiếm tuần tự (Linear Search) còn được gọi bằng tên nào khác?

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

B. Tìm kiếm theo chiều sâu.

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

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

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

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

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

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

D. Tìm kiếm theo băm (Hash Search).

17. Thuật toán tìm kiếm tuần tự có thể được áp dụng cho các tập dữ liệu được lưu trữ trên đĩa cứng hay không, miễn là có thể truy cập tuần tự từng phần tử?

A. Không, chỉ áp dụng cho dữ liệu trong bộ nhớ RAM.

B. Có, miễn là có cơ chế đọc tuần tự từng phần tử.

C. Chỉ khi dữ liệu trên đĩa đã được sắp xếp.

D. Không, vì tốc độ truy cập đĩa quá chậm.

18. Thuật toán tìm kiếm tuần tự có ưu điểm gì nổi bật so với các thuật toán tìm kiếm phức tạp hơn (như tìm kiếm nhị phân) trong một số trường hợp?

A. Tốc độ xử lý luôn nhanh hơn.

B. Không yêu cầu dữ liệu phải được sắp xếp.

C. Chỉ hoạt động hiệu quả trên các danh sách rất lớn.

D. Có thể tìm kiếm đồng thời nhiều phần tử.

19. Độ phức tạp thời gian (Time Complexity) của thuật toán tìm kiếm tuầ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^2)

20. Khi tìm kiếm một phần tử không có trong danh sách bằng thuật toán tìm kiếm tuần tự, số lượng phép so sánh tối đa mà thuật toán thực hiện là bao nhiêu (với danh sách có N phần tử)?

A. N - 1

B. N

C. 1

D. 0

21. Trong ngữ cảnh của thuật toán tìm kiếm tuần tự, khái niệm khóa tìm kiếm (search key) đề cập đến:

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

B. Giá trị mà ta muốn tìm trong danh sách.

C. Kích thước của danh sách.

D. Vị trí cuối cùng của phần tử cần tìm.

22. 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 về mặt hiệu quả?

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 có thông tin về việc sắp xếp của danh sách.

C. Khi cần tìm kiếm phần tử nhanh nhất có thể.

D. Khi thực hiện tìm kiếm trên cấu trúc dữ liệu cây.

23. Khi thực hiện tìm kiếm tuần tự và phần tử cần tìm nằm ở cuối danh sách, điều này tương ứng với trường hợp xấu nhất (worst-case scenario) về mặt hiệu năng. Đúng hay Sai?

A. Đúng, vì phải duyệt qua tất cả các phần tử.

B. Sai, trường hợp xấu nhất là khi phần tử không có trong danh sách.

C. Đúng, vì phần tử ở cuối đòi hỏi nhiều bước nhảy nhất.

D. Sai, trường hợp xấu nhất là khi phần tử ở đầu danh sách.

24. Nếu một danh sách có N phần tử, trong trường hợp tốt nhất (best-case scenario) về hiệu năng, thuật toán tìm kiếm tuần tự sẽ thực hiện bao nhiêu phép so sánh để tìm thấy một phần tử?

A. 0

B. 1

C. N

D. N/2

25. Giả sử ta có một danh sách các chuỗi ký tự: [apple, banana, cherry, date]. Nếu tìm kiếm chuỗi cherry bằng tìm kiếm tuần tự, bao nhiêu phép so sánh chuỗi sẽ diễn ra?

A. 1

B. 2

C. 3

D. 4