1. Độ 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 log n)
B. O(n^2)
C. O(n)
D. O(log n)
2. Chiến lược "chốt trung vị của ba phần tử" (median-of-three pivot selection) nhằm mục đích gì?
A. Chọn một phần tử chốt có khả năng gần với giá trị trung vị thực sự của mảng con, giảm thiểu khả năng chia mảng không cân bằng.
B. Sắp xếp ba phần tử đầu tiên của mảng con.
C. Tăng tốc độ của bước phân hoạch bằng cách xử lý ba phần tử cùng lúc.
D. Giảm số lần hoán vị trong quá trình sắp xếp.
3. Khi số lượng phần tử trong mảng con trở nên rất nhỏ (ví dụ: dưới 10 phần tử), người ta thường áp dụng chiến lược gì để cải thiện hiệu suất của Quick Sort?
A. Chuyển sang sử dụng một thuật toán sắp xếp khác hiệu quả hơn cho mảng nhỏ, như Insertion Sort.
B. Tiếp tục sử dụng Quick Sort với các mảng con rất nhỏ.
C. Dừng quá trình sắp xếp và báo cáo kết quả.
D. Sử dụng thuật toán Heap Sort cho các mảng nhỏ.
4. Khái niệm "sắp xếp tại chỗ" (in-place sorting) trong Quick Sort có nghĩa là gì?
A. Thuật toán thực hiện sắp xếp trực tiếp trên mảng dữ liệu gốc mà không cần mảng phụ lớn.
B. Thuật toán chỉ sắp xếp các phần tử tại vị trí ban đầu của chúng.
C. Thuật toán cần một bản sao của mảng để thực hiện sắp xếp.
D. Thuật toán chỉ làm việc với các phần tử đã được đánh dấu là "tại chỗ".
5. Khi so sánh với thuật toán sắp xếp trộn (Merge Sort), Quick Sort có ưu điểm gì về mặt bộ nhớ?
A. Quick Sort thường yêu cầu ít bộ nhớ phụ hơn vì nó có thể sắp xếp tại chỗ (in-place).
B. Merge Sort yêu cầu ít bộ nhớ phụ hơn vì nó chia mảng thành các phần tử nhỏ.
C. Cả hai thuật toán đều yêu cầu lượng bộ nhớ phụ tương đương nhau.
D. Quick Sort luôn yêu cầu bộ nhớ phụ lớn hơn Merge Sort.
6. Trong thuật toán phân hoạch Lomuto, phần tử chốt thường được chọn là:
A. Phần tử cuối cùng của mảng con.
B. Phần tử đầu tiên của mảng con.
C. Phần tử có giá trị nhỏ nhất trong mảng con.
D. Phần tử có giá trị lớn nhất trong mảng con.
7. Vì sao thuật toán sắp xếp nhanh lại được ưa chuộng trong thực tế?
A. Tốc độ trung bình nhanh và hiệu quả trên nhiều loại dữ liệu.
B. Độ phức tạp thời gian luôn là O(n log n) bất kể trường hợp nào.
C. Dễ dàng cài đặt và hiểu rõ hơn Merge Sort.
D. Sử dụng ít bộ nhớ phụ hơn Bubble Sort.
8. Nếu sử dụng thuật toán sắp xếp nhanh trên một mảng đã được sắp xếp theo thứ tự tăng dần và luôn chọn phần tử đầu tiên làm chốt, điều gì sẽ xảy ra?
A. Thuật toán sẽ rơi vào trường hợp xấu nhất với độ phức tạp O(n^2).
B. Thuật toán sẽ hoạt động hiệu quả nhất với độ phức tạp O(n log n).
C. Thuật toán sẽ bị lỗi và không hoàn thành việc sắp xếp.
D. Thuật toán sẽ chuyển sang sử dụng một phương pháp sắp xếp khác.
9. Việc chọn phần tử chốt là phần tử đầu tiên trong mảng con có thể dẫn đến trường hợp xấu nhất khi:
A. Mảng con đã được sắp xếp hoặc sắp xếp ngược.
B. Mảng con chứa các phần tử ngẫu nhiên.
C. Mảng con chứa các phần tử giống nhau.
D. Mảng con có kích thước nhỏ.
10. Độ 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 xảy ra khi nào?
A. Khi phần tử chốt luôn là phần tử nhỏ nhất hoặc lớn nhất trong mảng con, dẫn đến việc chia mảng không cân bằng.
B. Khi phần tử chốt luôn là phần tử trung vị của mảng con.
C. Khi mảng đã được sắp xếp hoặc sắp xếp ngược.
D. Khi tất cả các phần tử trong mảng là giống nhau.
11. Chiến lược chọn phần tử chốt ngẫu nhiên (randomized pivot selection) giúp cải thiện điều gì cho thuật toán sắp xếp nhanh?
A. Giảm khả năng xảy ra trường hợp xấu nhất (O(n^2)).
B. Tăng tốc độ sắp xếp trong mọi trường hợp lên O(n).
C. Giảm lượng bộ nhớ sử dụng.
D. Đảm bảo độ phức tạp O(n log n) cho mọi trường hợp.
12. Ý nghĩa của việc "phân hoạch không ổn định" (unstable partition) trong Quick Sort là gì?
A. Thứ tự tương đối của các phần tử bằng nhau có thể bị thay đổi sau quá trình phân hoạch.
B. Thuật toán không thể sắp xếp các phần tử bằng nhau.
C. Phần tử chốt luôn được đặt ở vị trí chính xác giữa mảng.
D. Thuật toán chỉ hoạt động với các phần tử duy nhất.
13. Trong quá trình đệ quy của Quick Sort, mỗi lần gọi hàm phân hoạch sẽ giảm kích thước của bài toán bằng cách nào?
A. Phần tử chốt được đặt vào đúng vị trí cuối cùng của nó trong mảng đã sắp xếp, và các phần tử được chia thành hai mảng con độc lập.
B. Mảng được chia thành hai nửa với kích thước gần bằng nhau.
C. Phần tử nhỏ nhất được đưa về đầu mảng.
D. Hai phần tử liền kề sai thứ tự được hoán đổi.
14. Khi nào thì Quick Sort vượt trội hơn Merge Sort về hiệu suất trong thực tế?
A. Khi bộ nhớ có hạn và cần sắp xếp tại chỗ.
B. Khi cần đảm bảo tính ổn định của thuật toán.
C. Khi dữ liệu có kích thước rất lớn và cần độ phức tạp O(n log n) nghiêm ngặt.
D. Khi cần một thuật toán có độ phức tạp xấu nhất là O(n log n).
15. Thuật toán sắp xếp nhanh (Quick Sort) thuộc nhóm thuật toán nào?
A. Thuật toán chia để trị.
B. Thuật toán tham lam.
C. Thuật toán quay lui.
D. Thuật toán duyệt theo chiều rộng.
16. So với thuật toán phân hoạch Lomuto, thuật toán phân hoạch Hoare có ưu điểm gì?
A. Thường thực hiện ít phép hoán đổi hơn và hiệu quả hơn trên dữ liệu có nhiều phần tử trùng lặp.
B. Luôn nhanh hơn Lomuto trong mọi trường hợp.
C. Dễ cài đặt hơn Lomuto.
D. Yêu cầu ít bộ nhớ phụ hơn Lomuto.
17. Phần tử "chốt" (pivot) trong thuật toán sắp xếp nhanh thường được chọn như thế nào?
A. Có thể là phần tử đầu tiên, cuối cùng, giữa hoặc một phần tử ngẫu nhiên.
B. Luôn là phần tử có giá trị nhỏ nhất trong mảng.
C. Luôn là phần tử có giá trị lớn nhất trong mảng.
D. Luôn là phần tử có giá trị trung vị của mảng.
18. Thuật toán Quick Sort hoạt động dựa trên nguyên tắc cơ bản nào?
A. Chia để trị.
B. Quy hoạch động.
C. Duyệt đồ thị.
D. Tìm kiếm nhị phân.
19. Việc sử dụng "tail recursion optimization" trong Quick Sort có thể ảnh hưởng đến điều gì?
A. Giảm độ phức tạp không gian của ngăn xếp đệ quy xuống O(log n) ngay cả trong trường hợp xấu nhất.
B. Tăng tốc độ xử lý của thuật toán.
C. Giảm số lượng phép so sánh.
D. Làm cho thuật toán trở nên ổn định.
20. Trong thuật toán sắp xếp nhanh, bước "phân hoạch" (partitioning) có vai trò gì?
A. Chọn một phần tử làm "chốt" (pivot) và sắp xếp lại các phần tử sao cho các phần tử nhỏ hơn chốt nằm trước chốt, các phần tử lớn hơn nằm sau chốt.
B. Hoán đổi vị trí của hai phần tử liền kề nếu chúng sai thứ tự.
C. Tìm phần tử nhỏ nhất trong mảng và đưa nó về vị trí đầu tiên.
D. Chia mảng thành hai nửa và sắp xếp từng nửa một cách độc lập.
21. Độ phức tạp không gian (space complexity) của Quick Sort, khi sử dụng đệ quy và không có tối ưu hóa tail recursion, thường là:
A. O(log n) trong trường hợp trung bình và O(n) trong trường hợp xấu nhất.
B. O(n) trong mọi trường hợp.
C. O(1) trong mọi trường hợp.
D. O(n log n) trong trường hợp trung bình.
22. Trong cài đặt đệ quy của Quick Sort, khi nào thì việc gọi đệ quy dừng lại?
A. Khi mảng con có 0 hoặc 1 phần tử.
B. Khi mảng con có 2 phần tử.
C. Khi mảng con có 10 phần tử.
D. Khi mảng con đã được sắp xếp hoàn toàn.
23. Trong thuật toán phân hoạch Hoare, quá trình phân hoạch thường bắt đầu với:
A. Hai con trỏ, một từ đầu và một từ cuối mảng con, tiến về phía nhau.
B. Một con trỏ bắt đầu từ đầu mảng con và một con trỏ cố định ở cuối.
C. Hai con trỏ cùng bắt đầu từ giữa mảng con và di chuyển ra hai bên.
D. Một con trỏ duy nhất di chuyển từ đầu đến cuối mảng con.
24. Nếu một mảng có tất cả các phần tử giống nhau, ví dụ [5, 5, 5, 5, 5], và ta áp dụng Quick Sort với phần tử đầu tiên làm chốt, độ phức tạp sẽ là:
A. O(n^2)
B. O(n log n)
C. O(n)
D. O(log n)
25. Trong một cài đặt Quick Sort, hàm phân hoạch (partition) thường trả về giá trị nào?
A. Chỉ số của phần tử chốt sau khi phân hoạch.
B. Số lượng phần tử nhỏ hơn chốt.
C. Số lượng phần tử lớn hơn chốt.
D. Tổng giá trị của các phần tử trong mảng con.
