Trắc nghiệm Cánh diều Tin học 11 KHMT bài 9 Lập trình thuật toán sắp xếp nhanh

1. Trong thuật toán sắp xếp nhanh, bước phân hoạch (partitioning) có vai trò gì?

A. Chia mảng thành hai mảng con có kích thước bằng nhau.

B. Sắp xếp các phần tử nhỏ hơn phần tử chốt sang trái và các phần tử lớn hơn sang phải.

C. Tìm phần tử nhỏ nhất trong mảng.

D. Hoán đổi vị trí của hai phần tử bất kỳ trong mảng.

2. Thuật toán sắp xếp nhanh có phải là thuật toán sắp xếp ổn định (stable sort) không?

A. Có, vì nó luôn giữ nguyên thứ tự tương đối của các phần tử bằng nhau.

B. Không, vì các phần tử bằng nhau có thể thay đổi thứ tự tương đối của chúng trong quá trình phân hoạch.

C. Chỉ khi chọn chiến lược chốt phù hợp.

D. Phụ thuộc vào cách triển khai chi tiết.

3. Trong một triển khai Quick Sort sử dụng đệ quy, điều kiện dừng của đệ quy là gì?

A. Khi toàn bộ mảng đã được sắp xếp.

B. Khi chỉ số bắt đầu lớn hơn hoặc bằng chỉ số kết thúc của mảng con.

C. Khi tìm thấy phần tử chốt.

D. Khi mảng con có kích thước lớn hơn 10.

4. Nếu ta có một mảng gồm các phần tử [7, 2, 1, 6, 8, 5, 3, 4] và chọn phần tử đầu tiên (7) làm chốt, sau bước phân hoạch đầu tiên, vị trí của phần tử chốt (7) có thể là ở đâu?

A. Vị trí 0 (đầu mảng).

B. Vị trí cuối cùng của mảng (vị trí 7).

C. Vị trí mà mọi phần tử bên trái nhỏ hơn 7 và mọi phần tử bên phải lớn hơn 7.

D. Vị trí ngẫu nhiên.

5. Biện pháp nào sau đây giúp giảm thiểu nguy cơ rơi vào trường hợp xấu nhất của thuật toán sắp xếp nhanh?

A. Luôn chọn phần tử đầu tiên làm chốt.

B. Sử dụng phương pháp sắp xếp nổi bọt thay thế cho phân hoạch.

C. Sử dụng chiến lược chọn chốt ngẫu nhiên hoặc trung vị ba phần tử.

D. Chỉ áp dụng thuật toán cho các mảng nhỏ.

6. Điểm mạnh chính của thuật toán sắp xếp nhanh so với các thuật toán sắp xếp khác như Bubble Sort hay Insertion Sort là gì?

A. Đơn giản hơn trong việc triển khai.

B. Có độ phức tạp thời gian trung bình tốt hơn.

C. Yêu cầu ít bộ nhớ phụ hơn.

D. Luôn đảm bảo độ phức tạp thời gian là O(n log n).

7. Khi so sánh Quick Sort với Merge Sort về mặt độ phức tạp thời gian trung bình, Quick Sort thường được ưu tiên hơn vì sao?

A. Quick Sort yêu cầu ít bộ nhớ phụ hơn.

B. Merge Sort có độ phức tạp thời gian xấu nhất là O(n log n), trong khi Quick Sort là O(n^2).

C. Quick Sort có khả năng sắp xếp tại chỗ (in-place) tốt hơn Merge Sort.

D. Cả ba lý do trên đều đúng.

8. Nếu ta áp dụng thuật toán sắp xếp nhanh cho một mảng chỉ chứa một phần tử, kết quả sẽ là gì?

A. Mảng sẽ bị xóa.

B. Mảng sẽ không thay đổi và được coi là đã sắp xếp.

C. Thuật toán sẽ báo lỗi.

D. Mảng sẽ được sắp xếp lại theo thứ tự ngược lại.

9. Độ phức tạp không gian (space complexity) của thuật toán sắp xếp nhanh (sử dụng đệ quy) thường là bao nhiêu?

A. O(1)

B. O(n)

C. O(log n)

D. O(n^2)

10. Sử dụng kỹ thuật three-way partitioning (phân hoạch ba đường) trong Quick Sort có lợi ích gì?

A. Giúp sắp xếp mảng theo thứ tự giảm dần.

B. Giảm số lần hoán đổi khi có nhiều phần tử trùng lặp.

C. Tăng độ phức tạp thời gian lên O(n log n).

D. Làm cho thuật toán ổn định.

11. Thuật toán phân hoạch Lomuto và Hoare khác nhau ở điểm nào cơ bản nhất?

A. Lomuto chọn chốt từ giữa mảng, Hoare chọn từ đầu mảng.

B. Lomuto đặt chốt vào vị trí cuối cùng sau phân hoạch, Hoare có thể không đặt chốt vào vị trí cuối cùng.

C. Lomuto sử dụng hai con trỏ từ hai đầu, Hoare sử dụng một con trỏ.

D. Lomuto không sử dụng đệ quy, Hoare có sử dụng đệ quy.

12. Độ phức tạp thời gian trường hợp xấu nhất (worst-case time complexity) của thuật toán sắp xếp nhanh là bao nhiêu?

A. O(n log n)

B. O(n^2)

C. O(n)

D. O(log n)

13. Thuật toán sắp xếp nhanh (Quick Sort) lựa chọn phần tử chốt (pivot) như thế nào để đảm bảo hiệu quả tốt nhất trong trường hợp trung bình?

A. Luôn chọn phần tử đầu tiên làm chốt.

B. Luôn chọn phần tử cuối cùng làm chốt.

C. Chọn phần tử ngẫu nhiên làm chốt.

D. Chọn phần tử trung vị của ba phần tử (đầu, giữa, cuối) làm chốt.

14. Khái niệm divide and conquer (chia để trị) được thể hiện như thế nào trong thuật toán sắp xếp nhanh?

A. Chia mảng thành hai nửa, sắp xếp từng nửa, rồi hợp nhất kết quả.

B. Chia mảng thành hai mảng con dựa trên phần tử chốt, sau đó đệ quy sắp xếp các mảng con.

C. Chia mảng thành các phần tử nhỏ nhất và sắp xếp chúng trước.

D. Chia mảng thành các cặp và so sánh chúng.

15. Đâu KHÔNG phải là một trường hợp sử dụng thuật toán sắp xếp nhanh?

A. Sắp xếp một danh sách lớn các số nguyên.

B. Sắp xếp các đối tượng phức tạp dựa trên một khóa nào đó.

C. Khi cần đảm bảo tính ổn định của thuật toán sắp xếp.

D. Sắp xếp một mảng dữ liệu lớn trong bộ nhớ RAM.

16. Nếu một mảng đã được sắp xếp tăng dần, và ta chọn phần tử đầu tiên làm chốt trong thuật toán sắp xếp nhanh, điều gì sẽ xảy ra?

A. Thuật toán sẽ chạy rất nhanh với độ phức tạp O(n log n).

B. Mỗi lần phân hoạch, một mảng con sẽ rỗng và mảng kia chứa n-1 phần tử, dẫn đến trường hợp xấu nhất O(n^2).

C. Thuật toán sẽ bị lỗi và dừng lại.

D. Thuật toán sẽ thực hiện hoán đổi tất cả các cặp phần tử.

17. Khi nào thuật toán sắp xếp nhanh hoạt động kém hiệu quả nhất?

A. Khi mảng chứa các phần tử giống nhau.

B. Khi mảng đã được sắp xếp hoặc sắp xếp ngược và chiến lược chọn chốt không tốt.

C. Khi mảng có kích thước nhỏ.

D. Khi mảng có các phần tử ngẫu nhiên.

18. Trong thuật toán sắp xếp nhanh, nếu ta chọn phần tử chốt là phần tử lớn nhất trong mảng, điều gì sẽ xảy ra trong bước phân hoạch?

A. Mảng sẽ được chia thành hai nửa gần bằng nhau.

B. Tất cả các phần tử sẽ được chuyển sang bên trái của chốt.

C. Tất cả các phần tử sẽ được chuyển sang bên phải của chốt.

D. Chốt sẽ ở vị trí đầu tiên.

19. Chiến lược chọn chốt nào sau đây KHÔNG được khuyến khích trong thuật toán sắp xếp nhanh vì dễ dẫn đến trường hợp xấu nhất?

A. Chọn phần tử đầu tiên làm chốt.

B. Chọn phần tử cuối cùng làm chốt.

C. Chọn phần tử ngẫu nhiên làm chốt.

D. Chọn phần tử trung vị của ba phần tử (đầu, giữa, cuối) làm chốt.

20. Khái niệm đệ quy (recursion) được áp dụng như thế nào trong thuật toán sắp xếp nhanh?

A. Chỉ sử dụng một lần ở bước phân hoạch.

B. Chia mảng thành hai mảng con và gọi chính nó để sắp xếp các mảng con đó.

C. Dùng để tìm phần tử chốt.

D. Sử dụng để kiểm tra xem mảng đã sắp xếp chưa.

21. Trong quá trình phân hoạch của thuật toán sắp xếp nhanh, nếu ta sử dụng hai con trỏ i và j bắt đầu từ hai đầu mảng và di chuyển vào trong, khi nào ta thực hiện hoán đổi?

A. Khi con trỏ i tìm thấy phần tử lớn hơn chốt và con trỏ j tìm thấy phần tử nhỏ hơn chốt.

B. Khi con trỏ i và j gặp nhau.

C. Khi con trỏ i tìm thấy phần tử nhỏ hơn chốt và con trỏ j tìm thấy phần tử lớn hơn chốt.

D. Chỉ hoán đổi khi tìm thấy phần tử nhỏ nhất.

22. Tại sao việc sử dụng đệ quy trong Quick Sort có thể dẫn đến tràn ngăn xếp (stack overflow) với các mảng rất lớn?

A. Do số lượng phép so sánh quá lớn.

B. Do độ sâu của các lời gọi đệ quy trong trường hợp xấu nhất có thể đạt đến n.

C. Do các biến cục bộ chiếm quá nhiều bộ nhớ.

D. Do thuật toán không hiệu quả với các mảng lớn.

23. Trong một số triển khai của Quick Sort, khi kích thước mảng con trở nên đủ nhỏ (ví dụ: dưới 10 phần tử), người ta thường chuyển sang sử dụng Insertion Sort. Tại sao lại làm vậy?

A. Insertion Sort hiệu quả hơn cho các mảng nhỏ vì có chi phí gọi hàm đệ quy thấp hơn.

B. Insertion Sort có độ phức tạp O(n^2) nên phù hợp với mảng nhỏ.

C. Để tránh trường hợp xấu nhất của Quick Sort.

D. Insertion Sort đơn giản hơn để kiểm thử.

24. Độ phức tạp thời gian của thuật toán sắp xếp nhanh khi tất cả các phần tử trong mảng là giống nhau là bao nhiêu?

A. O(n)

B. O(n log n)

C. O(n^2)

D. O(log n)

25. Độ phức tạp thời gian trường hợp trung bình (average-case time complexity) của thuật toán sắp xếp nhanh là bao nhiêu?

A. O(n)

B. O(n^2)

C. O(n log n)

D. O(log n)