[KNTT] Trắc nghiệm Tin học 11 KHMT bài 21 Các thuật toán sắp xếp đơn giản

1. Đâu là thuật toán sắp xếp có độ phức tạp thời gian trong trường hợp xấu nhất (worst-case time complexity) là O(n^2)?

A. Sắp xếp chọn (Selection Sort).

B. Sắp xếp trộn (Merge Sort).

C. Sắp xếp nhanh (Quick Sort) với pivot được chọn ngẫu nhiên.

D. Sắp xếp vun đống (Heap Sort).

2. Giả sử ta có mảng A = [5, 1, 4, 2, 8]. Sau lượt duyệt đầu tiên của thuật toán sắp xếp nổi bọt (sắp xếp tăng dần), mảng sẽ có dạng nào?

A. [1, 4, 2, 5, 8]

B. [1, 2, 4, 5, 8]

C. [5, 1, 4, 2, 8]

D. [1, 5, 4, 2, 8]

3. Trong thuật toán sắp xếp chèn (insertion sort), để chèn một phần tử vào đúng vị trí trong phần đã sắp xếp, ta thường thực hiện thao tác gì?

A. Dịch chuyển các phần tử lớn hơn nó sang phải để tạo chỗ trống.

B. So sánh nó với tất cả các phần tử còn lại trong danh sách.

C. Đổi chỗ nó với phần tử nhỏ nhất trong danh sách.

D. Xóa tất cả các phần tử lớn hơn nó.

4. Đặc điểm ổn định (stable) của một thuật toán sắp xếp có nghĩa là gì?

A. Thứ tự tương đối của các phần tử có khóa bằng nhau được giữ nguyên sau khi sắp xếp.

B. Thuật toán luôn hoạt động với hiệu suất cao nhất.

C. Số lần đổi chỗ luôn nhỏ hơn số lần so sánh.

D. Thuật toán có thể sắp xếp cả các phần tử trùng lặp.

5. Đâu là thuật toán sắp xếp đơn giản nhưng không hiệu quả về mặt hiệu suất cho các tập dữ liệu lớn?

A. Sắp xếp vun đống (Heap Sort).

B. Sắp xếp chèn (Insertion Sort).

C. Sắp xếp nổi bọt (Bubble Sort).

D. Sắp xếp trộn (Merge Sort).

6. Phát biểu nào sau đây mô tả sai về thuật toán sắp xếp nhanh (quick sort)?

A. Nó là thuật toán sắp xếp ổn định (stable sort).

B. Số lần đổi chỗ thường ít hơn so với sắp xếp nổi bọt.

C. Độ phức tạp thời gian trung bình là O(n log n).

D. Nó sử dụng phương pháp chia để trị.

7. Nếu một thuật toán sắp xếp có độ phức tạp thời gian là O(n log n) trong hầu hết các trường hợp, nó được coi là:

A. Hiệu quả cho các tập dữ liệu lớn.

B. Không hiệu quả, chỉ phù hợp với dữ liệu nhỏ.

C. Luôn là lựa chọn tốt nhất, bất kể kích thước dữ liệu.

D. Yêu cầu nhiều bộ nhớ phụ trợ.

8. Thuật toán sắp xếp nào có thể được mô tả là lấy một phần tử từ danh sách chưa sắp xếp và chèn nó vào vị trí đúng trong phần đã sắp xếp của danh sách?

A. Sắp xếp chèn (Insertion Sort).

B. Sắp xếp nổi bọt (Bubble Sort).

C. Sắp xếp chọn (Selection Sort).

D. Sắp xếp trộn (Merge Sort).

9. Trong thuật toán sắp xếp trộn (merge sort), quá trình chia (divide) có ý nghĩa gì?

A. Chia danh sách ban đầu thành các danh sách con nhỏ hơn cho đến khi mỗi danh sách con chỉ có một phần tử.

B. Chia danh sách thành hai nửa bằng nhau để so sánh.

C. Chia danh sách thành các phần tử lớn nhất và nhỏ nhất.

D. Chia danh sách thành các phần tử đã sắp xếp và chưa sắp xếp.

10. Nếu một danh sách đã được sắp xếp theo thứ tự tăng dần, thuật toán sắp xếp nổi bọt sẽ thực hiện bao nhiêu lượt duyệt để kết thúc?

A. Một lượt duyệt mà không có bất kỳ phép đổi chỗ nào.

B. N lượt duyệt, với N là số phần tử.

C. N-1 lượt duyệt.

D. Luôn thực hiện đủ N lượt duyệt.

11. Đâu là ưu điểm chính của thuật toán sắp xếp chèn (insertion sort) khi làm việc với các danh sách gần như đã được sắp xếp?

A. Hiệu quả cao, vì nó chỉ cần thực hiện ít phép dịch chuyển phần tử.

B. Luôn nhanh hơn các thuật toán sắp xếp khác trong mọi trường hợp.

C. Thực hiện số lần so sánh ít nhất khi danh sách đã sắp xếp.

D. Yêu cầu ít bộ nhớ phụ trợ nhất.

12. Khi một thuật toán sắp xếp không phải là ổn định (unstable), điều này có thể dẫn đến hệ quả gì nếu có các phần tử trùng lặp?

A. Thứ tự ban đầu của các phần tử có giá trị giống nhau có thể bị thay đổi.

B. Thuật toán sẽ không bao giờ hoàn thành việc sắp xếp.

C. Số lượng phép so sánh sẽ tăng lên đáng kể.

D. Dung lượng bộ nhớ yêu cầu sẽ tăng gấp đôi.

13. Thuật toán sắp xếp nào thường được sử dụng để sắp xếp các danh sách có kích thước rất nhỏ hoặc gần như đã sắp xếp?

A. Sắp xếp chèn (Insertion Sort).

B. Sắp xếp trộn (Merge Sort).

C. Sắp xếp nhanh (Quick Sort).

D. Sắp xếp vun đống (Heap Sort).

14. Trong thuật toán sắp xếp nổi bọt (bubble sort), ở mỗi lượt duyệt qua danh sách, phần tử lớn nhất (hoặc nhỏ nhất tùy cách sắp xếp) sẽ được nổi lên vị trí cuối cùng. Phát biểu nào sau đây mô tả đúng nhất nguyên tắc hoạt động của thuật toán này?

A. So sánh và đổi chỗ các cặp phần tử liền kề nếu chúng sai thứ tự, lặp lại cho đến khi danh sách được sắp xếp.

B. Chia danh sách thành hai nửa, sắp xếp từng nửa rồi trộn lại.

C. Tìm phần tử nhỏ nhất trong danh sách chưa sắp xếp và đưa nó về đầu danh sách.

D. Chèn từng phần tử từ danh sách nguồn vào vị trí đúng trong danh sách đích đã sắp xếp.

15. Đâu là nhược điểm chính của thuật toán sắp xếp trộn (merge sort) về mặt sử dụng bộ nhớ?

A. Cần bộ nhớ phụ trợ bằng với kích thước của danh sách gốc để thực hiện bước trộn.

B. Không cần bất kỳ bộ nhớ phụ trợ nào.

C. Chỉ cần một lượng bộ nhớ phụ trợ rất nhỏ.

D. Yêu cầu bộ nhớ phụ trợ gấp đôi kích thước danh sách gốc.

16. Trong sắp xếp nổi bọt, để sắp xếp mảng theo thứ tự giảm dần, ta cần thay đổi điều kiện so sánh như thế nào?

A. Đổi chỗ nếu phần tử đứng trước nhỏ hơn phần tử đứng sau.

B. Đổi chỗ nếu phần tử đứng trước lớn hơn phần tử đứng sau.

C. Không cần thay đổi điều kiện so sánh.

D. Chỉ đổi chỗ khi phần tử đứng trước bằng phần tử đứng sau.

17. Thuật toán sắp xếp chọn (selection sort) có đặc điểm gì nổi bật so với sắp xếp nổi bọt về số lần đổi chỗ?

A. Có số lần đổi chỗ tối thiểu, chỉ thực hiện đổi chỗ khi tìm thấy phần tử nhỏ nhất hoặc lớn nhất.

B. Có số lần đổi chỗ luôn bằng số lần so sánh.

C. Có số lần đổi chỗ nhiều hơn sắp xếp nổi bọt trong mọi trường hợp.

D. Không có sự khác biệt rõ rệt về số lần đổi chỗ.

18. Thuật toán sắp xếp nào sử dụng cấu trúc dữ liệu đống (heap) để thực hiện sắp xếp?

A. Sắp xếp vun đống (Heap Sort).

B. Sắp xếp chèn (Insertion Sort).

C. Sắp xếp nổi bọt (Bubble Sort).

D. Sắp xếp trộn (Merge Sort).

19. Tại sao việc chọn pivot (chốt) đúng cách lại quan trọng trong thuật toán sắp xếp nhanh (quick sort)?

A. Pivot quyết định sự cân bằng của việc phân chia danh sách, ảnh hưởng đến hiệu suất.

B. Pivot là phần tử duy nhất cần được sắp xếp trong mỗi bước.

C. Pivot xác định số lượng phần tử trong danh sách.

D. Pivot chỉ là một phần tử ngẫu nhiên không ảnh hưởng đến hiệu suất.

20. Thuật toán nào sau đây được xem là không hiệu quả đối với các tập dữ liệu lớn vì độ phức tạp thời gian của nó trong trường hợp xấu nhất là O(n^2)?

A. Sắp xếp nổi bọt (Bubble Sort).

B. Sắp xếp trộn (Merge Sort).

C. Sắp xếp nhanh (Quick Sort).

D. Sắp xếp vun đống (Heap Sort).

21. Khi đánh giá hiệu suất của các thuật toán sắp xếp, độ phức tạp thời gian (time complexity) thường được đo bằng gì?

A. Số lượng phép so sánh và phép gán (hoặc hoán vị) cần thực hiện.

B. Số lượng phần tử trong danh sách cần sắp xếp.

C. Dung lượng bộ nhớ cần sử dụng.

D. Thời gian thực tế tính bằng giây trên một máy tính cụ thể.

22. Trong thuật toán sắp xếp trộn (merge sort), bước quan trọng nhất để đảm bảo tính đúng đắn là gì?

A. Thực hiện đúng thao tác trộn (merge) hai danh sách con đã sắp xếp để tạo thành danh sách sắp xếp lớn hơn.

B. Chia danh sách thành các phần tử riêng lẻ.

C. Tìm phần tử nhỏ nhất rồi đặt nó vào vị trí đầu tiên.

D. So sánh các phần tử liền kề và đổi chỗ nếu sai thứ tự.

23. Trong thuật toán sắp xếp chọn (selection sort), sau k lượt duyệt, điều gì có thể khẳng định về k phần tử đầu tiên của danh sách?

A. Chúng là k phần tử nhỏ nhất và đã được sắp xếp đúng vị trí.

B. Chúng là k phần tử đã được sắp xếp, nhưng có thể không phải là nhỏ nhất.

C. Chúng là k phần tử lớn nhất và đã được sắp xếp đúng vị trí.

D. Chúng là k phần tử lớn nhất và đã được sắp xếp, nhưng có thể không phải là nhỏ nhất.

24. Khi so sánh thuật toán sắp xếp chèn (insertion sort) và sắp xếp chọn (selection sort) trên một mảng có kích thước N:

A. Cả hai đều có độ phức tạp thời gian trung bình là O(n^2).

B. Sắp xếp chèn luôn nhanh hơn sắp xếp chọn.

C. Sắp xếp chọn luôn nhanh hơn sắp xếp chèn.

D. Sắp xếp chèn có độ phức tạp O(n log n) còn sắp xếp chọn là O(n^2).

25. Nếu bạn cần sắp xếp một danh sách rất lớn và ưu tiên hiệu suất cao, thuật toán nào sau đây là lựa chọn tốt nhất?

A. Sắp xếp nhanh (Quick Sort) hoặc Sắp xếp trộn (Merge Sort).

B. Sắp xếp nổi bọt (Bubble Sort).

C. Sắp xếp chèn (Insertion Sort).

D. Sắp xếp chọn (Selection Sort).