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

1. Để cải thiện hiệu suất của thuật toán sắp xếp nhanh khi xử lý các mảng có nhiều phần tử trùng lặp, người ta thường sử dụng kỹ thuật nào?

A. Sử dụng thuật toán Sắp xếp trộn thay cho Sắp xếp nhanh.

B. Chuyển sang Sắp xếp vun đống (Heap Sort).

C. Sử dụng kỹ thuật phân hoạch 3 đường (3-way partitioning) để nhóm các phần tử bằng chốt vào một khu vực riêng.

D. Luôn chọn phần tử ngẫu nhiên làm chốt.

2. Khi phân tích độ phức tạp của Quick Sort, trường hợp xấu nhất (worst-case) xảy ra khi nào?

A. Khi mảng được sắp xếp hoàn hảo theo thứ tự tăng dần và chốt luôn là phần tử đầu tiên.

B. Khi mảng được sắp xếp hoàn hảo theo thứ tự tăng dần hoặc giảm dần và chốt luôn là phần tử nhỏ nhất hoặc lớn nhất của mảng con.

C. Khi mảng chứa toàn các phần tử giống nhau và chốt là giá trị đó.

D. Khi mảng được sắp xếp ngẫu nhiên.

3. Khi thực hiện thuật toán sắp xếp nhanh (Quick Sort) trên một mảng các số nguyên, nếu mảng ban đầu đã được sắp xếp theo thứ tự tăng dần, chiến lược chọn chốt nào sau đây sẽ dẫn đến hiệu suất kém nhất (gần với trường hợp xấu nhất)?

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

B. Chọn phần tử có giá trị trung vị (median) làm chốt.

C. Chọn phần tử đầu tiên của mảng con làm chốt.

D. Chọn phần tử cuối cùng của mảng con làm chốt.

4. Trong một phiên bản của Quick Sort, bước phân hoạch Lomuto được sử dụng. Con trỏ i được duy trì để chỉ ra ranh giới giữa các phần tử nhỏ hơn hoặc bằng chốt và các phần tử chưa được xét. Nếu phần tử hiện tại nhỏ hơn chốt, điều gì sẽ xảy ra?

A. Con trỏ i được giảm đi một đơn vị.

B. Phần tử hiện tại được hoán vị với phần tử tại vị trí i, sau đó i được tăng lên một đơn vị.

C. Phần tử hiện tại được hoán vị với phần tử chốt.

D. Không có hành động nào xảy ra.

5. Nếu ta có một mảng chỉ chứa các phần tử giống nhau, ví dụ: [7, 7, 7, 7, 7]. Khi áp dụng Quick Sort với chốt là 7, bước phân hoạch sẽ hoạt động như thế nào theo cách thông thường?

A. Mảng sẽ được chia thành hai mảng con có kích thước gần bằng nhau.

B. Mảng sẽ bị chia thành một mảng con rỗng và một mảng con chứa tất cả các phần tử.

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

D. Mảng sẽ được sắp xếp ngay lập tức.

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

A. O(n)

B. O(n log n)

C. O(n^2)

D. O(log n)

7. Trong thuật toán sắp xếp nhanh, bước phân hoạch Lomuto và Hoare có điểm khác biệt cơ bản nào?

A. Lomuto luôn chọn phần tử đầu tiên làm chốt, Hoare chọn phần tử cuối cùng.

B. Lomuto đảm bảo chốt nằm ở vị trí cuối cùng sau phân hoạch, còn Hoare thì không nhất thiết.

C. Hoare hiệu quả hơn Lomuto trong mọi trường hợp.

D. Lomuto sử dụng hai con trỏ, Hoare chỉ sử dụng một con trỏ.

8. Một biến thể phổ biến của thuật toán sắp xếp nhanh là IntroSort. Mục đích chính của IntroSort là gì?

A. Tăng tốc độ sắp xếp trên mảng đã sắp xếp.

B. Đảm bảo hiệu suất O(n log n) trong mọi trường hợp, tránh trường hợp xấu nhất O(n^2) của Quick Sort bằng cách chuyển sang HeapSort khi độ sâu đệ quy đạt ngưỡng nhất định.

C. Giảm thiểu việc sử dụng bộ nhớ so với Quick Sort.

D. Sử dụng ít phép so sánh hơn.

9. Khi cài đặt thuật toán sắp xếp nhanh (Quick Sort) bằng đệ quy, điều kiện dừng (base case) cho đệ quy là gì?

A. Khi mảng có một phần tử.

B. Khi mảng con có 0 hoặc 1 phần tử.

C. Khi phần tử chốt được đặt đúng vị trí.

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

10. Nếu một mảng được sắp xếp bằng thuật toán sắp xếp nhanh (Quick Sort) và ta quan sát thấy nó luôn thực hiện phân hoạch rất mất cân bằng, dẫn đến độ phức tạp O(n^2), thì nguyên nhân khả dĩ nhất là gì?

A. Mảng có ít phần tử.

B. Chiến lược chọn chốt không phù hợp (ví dụ: luôn chọn phần tử đầu/cuối của mảng đã sắp xếp hoặc sắp xếp ngược).

C. Thuật toán được cài đặt bằng ngôn ngữ lập trình chậm.

D. Sử dụng quá nhiều bộ nhớ.

11. Khi so sánh Quick Sort và Merge Sort về tính ổn định (stability), thuật toán nào thường được coi là không ổn định?

A. Merge Sort

B. Cả hai đều ổn định.

C. Quick Sort

D. Cả hai đều không ổn định.

12. Khi thực hiện thuật toán sắp xếp nhanh trên một mảng có nhiều phần tử trùng lặp, ví dụ: [5, 2, 8, 5, 1, 5, 9, 5]. Nếu ta chọn chốt là 5 và thực hiện phân hoạch theo cách thông thường (chỉ chia thành nhỏ hơn chốt và lớn hơn chốt), điều gì có thể xảy ra?

A. Thuật toán sẽ hoạt động rất nhanh vì có nhiều phần tử bằng chốt.

B. Các phần tử bằng chốt có thể bị phân tán vào cả hai mảng con, dẫn đến hiệu suất kém và có thể là trường hợp xấu nhất nếu chốt là giá trị xuất hiện nhiều nhất.

C. Thuật toán sẽ tự động xử lý các phần tử trùng lặp và sắp xếp chúng ở vị trí chính xác.

D. Các phần tử bằng chốt sẽ bị loại bỏ.

13. Trong thuật toán sắp xếp nhanh (Quick Sort), bước chọn chốt (pivot) có vai trò quan trọng nhất đối với hiệu quả hoạt động của thuật toán. Theo phân tích phổ biến, yếu tố nào sau đây được xem là quan trọng nhất khi lựa chọn chốt để đảm bảo hiệu suất tốt nhất trên thực tế, đặc biệt khi dữ liệu có thể đã được sắp xếp hoặc sắp xếp ngược?

A. Chọn phần tử đầu tiên làm chốt để dễ cài đặt.

B. Chọn phần tử có giá trị lớn nhất làm chốt.

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

D. Chọn phần tử cuối cùng làm chốt để tối ưu hóa việc chia mảng.

14. Trong quá trình phân hoạch (partitioning) của Quick Sort, nếu ta sử dụng hai con trỏ i và j chạy từ hai đầu mảng về phía giữa, dừng lại khi A[i] > pivot và A[j] < pivot, sau đó hoán vị A[i] và A[j]. Quy trình này tiếp tục cho đến khi nào?

A. Khi con trỏ i vượt qua con trỏ j.

B. Khi tìm thấy phần tử lớn nhất trong mảng.

C. Khi con trỏ i gặp phần tử chốt.

D. Khi con trỏ j gặp phần tử chốt.

15. Phân hoạch (partitioning) là một bước cốt lõi trong thuật toán sắp xếp nhanh. Mục tiêu chính của bước phân hoạch là gì?

A. Sắp xếp tất cả các phần tử trong mảng theo thứ tự tăng dần.

B. Chia mảng thành hai mảng con: một mảng chứa các phần tử nhỏ hơn hoặc bằng chốt, và một mảng chứa các phần tử lớn hơn chốt.

C. Tìm phần tử có giá trị nhỏ nhất trong mảng để đặt vào vị trí đầu tiên.

D. Đảo ngược thứ tự của toàn bộ mảng.

16. Thuật toán sắp xếp nhanh (Quick Sort) là một thuật toán sắp xếp dựa trên phương pháp nào?

A. So sánh và hoán vị (Comparison and Swapping).

B. Chia để trị (Divide and Conquer).

C. Lặp (Iteration).

D. Chọn lọc (Selection).

17. Khi số lượng phần tử trong mảng cần sắp xếp rất nhỏ (ví dụ: dưới 10 phần tử), việc sử dụng thuật toán sắp xếp nhanh (Quick Sort) có thể kém hiệu quả hơn so với các thuật toán sắp xếp đơn giản như Sắp xếp chèn (Insertion Sort). Tại sao lại như vậy?

A. Overhead của việc gọi đệ quy và phân hoạch lớn hơn lợi ích của việc chia để trị.

B. Quick Sort có độ phức tạp O(n^2) cho các mảng nhỏ.

C. Insertion Sort có độ phức tạp O(n) cho các mảng nhỏ.

D. Quick Sort cần nhiều bộ nhớ hơn cho các mảng nhỏ.

18. Cải tiến randomized Quick Sort (Quick Sort ngẫu nhiên) thực hiện bằng cách nào để cải thiện hiệu suất?

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

B. Chọn ngẫu nhiên một phần tử trong mảng con làm chốt.

C. Chuyển sang Sắp xếp chèn cho các mảng nhỏ.

D. Sử dụng phân hoạch 3 đường.

19. Trong một biến thể của Quick Sort, người ta chọn phần tử chốt bằng cách lấy trung vị của ba phần tử: phần tử đầu tiên, phần tử giữa và phần tử cuối cùng của mảng con. Ưu điểm chính của phương pháp này là gì?

A. Đảm bảo chốt luôn là phần tử nhỏ nhất hoặc lớn nhất.

B. Giảm thiểu khả năng xảy ra trường hợp xấu nhất và cải thiện hiệu suất trung bình, ngay cả với dữ liệu có cấu trúc.

C. Giảm số lượng phép hoán vị cần thực hiện.

D. Tăng tốc độ phân hoạch.

20. Thuật toán Quick Sort hoạt động như thế nào trên một mảng rỗng hoặc mảng chỉ có một phần tử?

A. Nó sẽ gây ra lỗi vì không có phần tử để so sánh.

B. Nó sẽ thực hiện một số phép hoán vị không cần thiết.

C. Nó sẽ trả về mảng đó ngay lập tức vì nó đã được sắp xếp.

D. Nó sẽ chuyển sang một thuật toán sắp xếp khác.

21. Độ phức tạp thời gian trung bình của thuật toán sắp xếp nhanh (Quick Sort) là bao nhiêu?

A. O(n)

B. O(n log n)

C. O(n^2)

D. O(log n)

22. So với thuật toán sắp xếp trộn (Merge Sort), thuật toán sắp xếp nhanh (Quick Sort) thường có ưu điểm gì về việc sử dụng bộ nhớ (space complexity)?

A. Quick Sort yêu cầu nhiều bộ nhớ hơn vì nó sử dụng đệ quy.

B. Quick Sort có độ phức tạp không gian O(log n) (trong trường hợp trung bình) hoặc O(n) (trường hợp xấu nhất) do đệ quy, trong khi Merge Sort yêu cầu O(n) để lưu trữ mảng tạm.

C. Cả hai thuật toán đều có độ phức tạp không gian là O(1).

D. Merge Sort yêu cầu ít bộ nhớ hơn vì nó không sử dụng đệ quy.

23. Khi áp dụng thuật toán sắp xếp nhanh cho một mảng rất lớn, việc sử dụng đệ quy sâu có thể dẫn đến lỗi tràn bộ nhớ (stack overflow). Để khắc phục vấn đề này, một kỹ thuật thường được áp dụng là gì?

A. Thay thế tất cả các phép gọi đệ quy bằng vòng lặp.

B. Giới hạn độ sâu của đệ quy và chuyển sang thuật toán khác (như Heap Sort) khi đạt ngưỡng.

C. Tăng kích thước bộ nhớ heap của chương trình.

D. Chia mảng lớn thành nhiều mảng nhỏ hơn trước khi sắp xếp.

24. Trong quá trình sắp xếp nhanh (Quick Sort), nếu ta quyết định sử dụng Sắp xếp chèn (Insertion Sort) cho các mảng con có kích thước nhỏ hơn hoặc bằng một ngưỡng nhất định (ví dụ: 10 phần tử), thì lợi ích chính của việc kết hợp này là gì?

A. Giảm độ phức tạp của thuật toán xuống O(n).

B. Tăng tốc độ xử lý các mảng nhỏ, nơi Insertion Sort hiệu quả hơn do ít overhead hơn Quick Sort.

C. Giảm thiểu việc sử dụng bộ nhớ.

D. Đảm bảo tính ổn định của thuật toán.

25. Trong bước phân hoạch của Quick Sort, khi sử dụng phương pháp Hoare, hai con trỏ i và j di chuyển từ hai phía. Con trỏ i tăng cho đến khi A[i] >= pivot, và con trỏ j giảm cho đến khi A[j] <= pivot. Nếu i < j, chúng ta hoán vị A[i] và A[j]. Sau khi hoán vị, điều gì xảy ra với các con trỏ?

A. Cả hai con trỏ đều dừng lại.

B. Con trỏ i tiếp tục tăng và con trỏ j tiếp tục giảm.

C. Con trỏ i được giảm đi và con trỏ j được tăng lên.

D. Chỉ con trỏ i được tăng lên một đơn vị.