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

1. Nếu ta có danh sách [3, 1, 4, 1, 5, 9, 2, 6] và tìm kiếm số 1, thuật toán tìm kiếm tuần tự sẽ dừng lại ở vị trí nào trước tiên?

A. Vị trí thứ hai (chứa giá trị 1). Kết luận Lý giải.

B. Vị trí thứ tư (chứa giá trị 1). Kết luận Lý giải.

C. Vị trí thứ tám (chứa giá trị 6). Kết luận Lý giải.

D. Vị trí thứ năm (chứa giá trị 5). Kết luận Lý giải.

2. Tìm kiếm tuần tự có thể được áp dụng để tìm kiếm trên một danh sách rỗng không?

A. Có, thuật toán sẽ thực hiện không có vòng lặp nào và kết thúc ngay lập tức. Kết luận Lý giải.

B. Không, vì không có phần tử nào để so sánh. Kết luận Lý giải.

C. Chỉ khi danh sách rỗng được định nghĩa rõ ràng. Kết luận Lý giải.

D. Có, nhưng sẽ gây ra lỗi. Kết luận Lý giải.

3. Trong tìm kiếm tuần tự, giả sử ta tìm một giá trị V trong danh sách A. Nếu A[i] là phần tử đang được so sánh và A[i] == V, hành động tiếp theo là gì theo quy trình thông thường?

A. Dừng tìm kiếm và trả về vị trí i. Kết luận Lý giải.

B. Tiếp tục so sánh với phần tử tiếp theo A[i+1]. Kết luận Lý giải.

C. So sánh V với phần tử tiếp theo A[i+1] trước khi trả về. Kết luận Lý giải.

D. Bắt đầu lại tìm kiếm từ đầu. Kết luận Lý giải.

4. Tìm kiếm tuần tự hoạt động tốt nhất trên loại cấu trúc dữ liệu nào?

A. Danh sách hoặc mảng tuyến tính. Kết luận Lý giải.

B. Cây tìm kiếm nhị phân. Kết luận Lý giải.

C. Đồ thị. Kết luận Lý giải.

D. Bảng băm (hash table). Kết luận Lý giải.

5. Thuật toán tìm kiếm tuần tự có yêu cầu dữ liệu phải được sắp xếp trước khi thực hiện không?

A. Không, nó hoạt động hiệu quả trên cả dữ liệu chưa sắp xếp. Kết luận Lý giải.

B. Có, đó là yêu cầu bắt buộc để thuật toán hoạt động. Kết luận Lý giải.

C. Chỉ yêu cầu sắp xếp nếu tìm kiếm phần tử ở cuối danh sách. Kết luận Lý giải.

D. Có, nhưng chỉ khi danh sách có nhiều hơn 10 phần tử. Kết luận Lý giải.

6. Giả sử ta có một danh sách các số nguyên: [15, 8, 22, 5, 10, 18]. Nếu áp dụng thuật toán tìm kiếm tuần tự để tìm số 10, theo quy trình thông thường, bước so sánh đầu tiên sẽ là gì?

A. So sánh 10 với 15 (phần tử đầu tiên). Kết luận Lý giải.

B. So sánh 10 với 18 (phần tử cuối cùng). Kết luận Lý giải.

C. So sánh 10 với 5 (phần tử nhỏ nhất). Kết luận Lý giải.

D. So sánh 10 với 22 (phần tử ở giữa). Kết luận Lý giải.

7. Khi tìm kiếm tuần tự gặp một phần tử trong danh sách có giá trị lớn hơn giá trị cần tìm, và danh sách đã được sắp xếp, hành động nào là hợp lý nhất theo logic của tìm kiếm tuần tự?

A. Dừng tìm kiếm vì phần tử cần tìm (nếu có) sẽ không xuất hiện sau đó. Kết luận Lý giải.

B. Tiếp tục tìm kiếm cho đến hết danh sách. Kết luận Lý giải.

C. Nhảy đến phần tử cuối cùng của danh sách để kiểm tra. Kết luận Lý giải.

D. So sánh lại với phần tử đầu tiên. Kết luận Lý giải.

8. Trong thuật toán tìm kiếm tuần tự, khi thực hiện tìm kiếm một phần tử có giá trị X trong một mảng chưa sắp xếp, theo cách tiếp cận phổ biến nhất, quá trình so sánh sẽ diễn ra như thế nào?

A. So sánh X với từng phần tử của mảng từ đầu đến cuối cho đến khi tìm thấy hoặc hết mảng. Kết luận Lý giải.

B. So sánh X với phần tử ở giữa mảng trước, sau đó chia đôi mảng để tìm kiếm tiếp. Kết luận Lý giải.

C. So sánh X với tất cả các phần tử cùng lúc để tăng tốc độ tìm kiếm. Kết luận Lý giải.

D. So sánh X với phần tử cuối cùng của mảng trước, sau đó lùi dần về đầu. Kết luận Lý giải.

9. Độ 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 xấu nhất (worst-case) là bao nhiêu, với n là số phần tử trong danh sách?

A. O(n). Kết luận Lý giải.

B. O(log n). Kết luận Lý giải.

C. O(1). Kết luận Lý giải.

D. O(n^2). Kết luận Lý giải.

10. Trong tìm kiếm tuần tự, việc lặp qua từng phần tử của mảng được thực hiện bằng cách nào?

A. Sử dụng vòng lặp (ví dụ: for, while). Kết luận Lý giải.

B. Sử dụng đệ quy. Kết luận Lý giải.

C. Sử dụng cấu trúc dữ liệu cây. Kết luận Lý giải.

D. Sử dụng kỹ thuật chia để trị. Kết luận Lý giải.

11. Trong tình huống nào, việc sử dụng tìm kiếm tuần tự có thể bị coi là kém hiệu quả hoặc không tối ưu?

A. Khi danh sách rất lớn và cần tìm kiếm nhanh chóng. Kết luận Lý giải.

B. Khi danh sách có kích thước nhỏ. Kết luận Lý giải.

C. Khi danh sách không được sắp xếp. Kết luận Lý giải.

D. Khi cần tìm kiếm một phần tử duy nhất. Kết luận Lý giải.

12. Trong việc triển khai tìm kiếm tuần tự, điều kiện dừng của vòng lặp thường bao gồm hai yếu tố chính là gì?

A. Chưa tìm thấy phần tử và chưa hết danh sách. Kết luận Lý giải.

B. Đã tìm thấy phần tử và hết danh sách. Kết luận Lý giải.

C. Phần tử hiện tại lớn hơn hoặc nhỏ hơn phần tử tìm. Kết luận Lý giải.

D. Đã duyệt qua một nửa danh sách và chưa hết. Kết luận Lý giải.

13. Giả sử ta có một danh sách các tên học sinh và cần tìm xem tên An có trong danh sách hay không bằng tìm kiếm tuần tự. Nếu danh sách là [Bình, An, Cường, Dũng], bước so sánh đầu tiên sẽ là:

A. So sánh An với Bình. Kết luận Lý giải.

B. So sánh An với Dũng. Kết luận Lý giải.

C. So sánh An với Cường. Kết luận Lý giải.

D. So sánh An với chính nó trước. Kết luận Lý giải.

14. Khi áp dụng tìm kiếm tuần tự cho một danh sách rất lớn và phần tử cần tìm nằm ở cuối cùng, điều này thường dẫn đến nhược điểm nào về hiệu suất?

A. Tốn nhiều thời gian do phải thực hiện số lượng lớn các phép so sánh. Kết luận Lý giải.

B. Tốn nhiều bộ nhớ để lưu trữ danh sách. Kết luận Lý giải.

C. Cần phải sắp xếp lại danh sách trước khi tìm kiếm. Kết luận Lý giải.

D. Không thể tìm thấy phần tử nếu nó nằm ở cuối. Kết luận Lý giải.

15. Khi tìm kiếm tuần tự, nếu phần tử cần tìm xuất hiện nhiều lần trong danh sách, thuật toán sẽ trả về vị trí của lần xuất hiện nào?

A. Lần xuất hiện đầu tiên theo thứ tự duyệt. Kết luận Lý giải.

B. Lần xuất hiện cuối cùng theo thứ tự duyệt. Kết luận Lý giải.

C. Vị trí trung bình của tất cả các lần xuất hiện. Kết luận Lý giải.

D. Vị trí ngẫu nhiên trong số các lần xuất hiện. Kết luận Lý giải.

16. Xét danh sách [7, 2, 9, 4, 5]. Nếu tìm kiếm số 9 bằng thuật toán tìm kiếm tuần tự, thứ tự các phép so sánh sẽ diễn ra như thế nào?

A. 7 == 9? (Sai) -> 2 == 9? (Sai) -> 9 == 9? (Đúng). Kết luận Lý giải.

B. 7 == 9? (Sai) -> 4 == 9? (Sai) -> 9 == 9? (Đúng). Kết luận Lý giải.

C. 9 == 9? (Đúng). Kết luận Lý giải.

D. 7 == 9? (Sai) -> 2 == 9? (Sai) -> 4 == 9? (Sai) -> 5 == 9? (Sai). Kết luận Lý giải.

17. 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 khác trên dữ liệu chưa sắp xếp?

A. Đơn giản, dễ cài đặt và hiệu quả trên các danh sách nhỏ hoặc chưa sắp xếp. Kết luận Lý giải.

B. Luôn có hiệu suất nhanh nhất bất kể kích thước danh sách. Kết luận Lý giải.

C. Chỉ yêu cầu một lượng bộ nhớ rất nhỏ để hoạt động. Kết luận Lý giải.

D. Có thể tìm kiếm nhiều phần tử cùng lúc một cách hiệu quả. Kết luận Lý giải.

18. Tìm kiếm tuần tự có thể được mô tả là một thuật toán:

A. Thô sơ (brute-force). Kết luận Lý giải.

B. Chia để trị (divide and conquer). Kết luận Lý giải.

C. Tham lam (greedy). Kết luận Lý giải.

D. Quy hoạch động (dynamic programming). Kết luận Lý giải.

19. Độ phức tạp thời gian (time complexity) của tìm kiếm tuần tự trong trường hợp tốt nhất (best-case) là bao nhiêu, với n là số phần tử trong danh sách?

A. O(1). Kết luận Lý giải.

B. O(n). Kết luận Lý giải.

C. O(log n). Kết luận Lý giải.

D. O(n^2). Kết luận Lý giải.

20. So sánh tìm kiếm tuần tự và tìm kiếm nhị phân, thuật toán nào đòi hỏi dữ liệu phải được sắp xếp?

A. Tìm kiếm nhị phân. Kết luận Lý giải.

B. Tìm kiếm tuần tự. Kết luận Lý giải.

C. Cả hai thuật toán đều yêu cầu sắp xếp. Kết luận Lý giải.

D. Không thuật toán nào yêu cầu sắp xếp. Kết luận Lý giải.

21. Nếu một chương trình sử dụng tìm kiếm tuần tự để xử lý một danh sách gồm 1 triệu phần tử và phần tử cần tìm ở cuối cùng, ước tính số phép so sánh có thể lên tới:

A. Khoảng 1 triệu phép so sánh. Kết luận Lý giải.

B. Khoảng 500.000 phép so sánh. Kết luận Lý giải.

C. Khoảng 10 phép so sánh. Kết luận Lý giải.

D. Khoảng 1 triệu phép so sánh, nhưng chỉ cần 1 phép so sánh. Kết luận Lý giải.

22. Thuật toán tìm kiếm tuần tự có thể được áp dụng hiệu quả nhất trong trường hợp nào sau đây?

A. Danh sách dữ liệu có kích thước nhỏ và không yêu cầu tốc độ xử lý quá cao. Kết luận Lý giải.

B. Danh sách dữ liệu đã được sắp xếp theo thứ tự tăng dần. Kết luận Lý giải.

C. Cần tìm kiếm một phần tử trong một mảng rất lớn một cách nhanh chóng. Kết luận Lý giải.

D. Dữ liệu được lưu trữ dưới dạng cây nhị phân tìm kiếm. Kết luận Lý giải.

23. Nếu ta cần tìm kiếm một giá trị trong một danh sách chỉ có vài phần tử, thuật toán tìm kiếm tuần tự có thể được coi là:

A. Hoàn toàn phù hợp và hiệu quả. Kết luận Lý giải.

B. Quá phức tạp và không cần thiết. Kết luận Lý giải.

C. Chỉ phù hợp nếu danh sách đã sắp xếp. Kết luận Lý giải.

D. Chậm hơn mọi thuật toán khác. Kết luận Lý giải.

24. 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 khi nào?

A. Sau khi đã so sánh phần tử cần tìm với tất cả các phần tử trong danh sách mà không tìm thấy. Kết luận Lý giải.

B. Ngay lập tức khi so sánh với phần tử đầu tiên không khớp. Kết luận Lý giải.

C. Khi đến phần tử lớn nhất trong danh sách nhưng vẫn chưa tìm thấy. Kết luận Lý giải.

D. Khi gặp một phần tử lớn hơn phần tử cần tìm (nếu danh sách đã sắp xếp). Kết luận Lý giải.

25. Nếu một thuật toán tìm kiếm duyệt qua các phần tử theo một thứ tự cố định từ đầu đến cuối và dừng lại khi tìm thấy hoặc hết danh sách, thì đó là thuật toán nào?

A. Tìm kiếm tuần tự. Kết luận Lý giải.

B. Tìm kiếm nhị phân. Kết luận Lý giải.

C. Tìm kiếm nội suy. Kết luận Lý giải.

D. Tìm kiếm nhảy. Kết luận Lý giải.