1. Nếu một thuật toán sắp xếp có độ phức tạp thời gian O(n log n), điều này có nghĩa là gì khi kích thước đầu vào (n) tăng gấp đôi?
A. Thời gian thực hiện sẽ tăng gấp đôi.
B. Thời gian thực hiện sẽ tăng gấp bốn lần.
C. Thời gian thực hiện sẽ tăng hơn gấp đôi một chút, gần với gấp đôi cộng thêm một lượng logarit.
D. Thời gian thực hiện sẽ giảm đi.
2. Thuật toán sắp xếp nổi bọt hoạt động dựa trên nguyên tắc nào sau đây?
A. Chia tập dữ liệu thành hai nửa rồi sắp xếp từng nửa.
B. So sánh và hoán đổi vị trí các cặp phần tử liền kề nếu chúng sai thứ tự.
C. Tìm phần tử nhỏ nhất và đặt nó vào vị trí đầu tiên.
D. Sử dụng cấu trúc dữ liệu "vun đống" để sắp xếp.
3. Giả sử bạn có một mảng gồm 100 phần tử. Nếu một thuật toán sắp xếp có độ phức tạp thời gian là O(n^2), nó sẽ thực hiện khoảng bao nhiêu phép toán?
A. Khoảng 100 phép toán.
B. Khoảng 1000 phép toán.
C. Khoảng 10.000 phép toán.
D. Khoảng 100.000 phép toán.
4. Trong ngữ cảnh của bài toán sắp xếp, "phân tích độ phức tạp" (complexity analysis) chủ yếu đề cập đến việc đánh giá:
A. Độ phức tạp của việc viết code cho thuật toán.
B. Số lượng thao tác cơ bản (như so sánh, hoán đổi) mà thuật toán thực hiện theo hàm của kích thước đầu vào.
C. Khả năng thuật toán hoạt động trên các loại dữ liệu khác nhau.
D. Độ khó hiểu của thuật toán đối với người học.
5. Tính ổn định của một thuật toán sắp xếp là gì?
A. Thuật toán luôn cho ra kết quả sắp xếp giống nhau cho cùng một đầu vào.
B. Thuật toán đảm bảo thứ tự tương đối của các phần tử bằng nhau không thay đổi sau khi sắp xếp.
C. Thuật toán có thể hoạt động tốt trên nhiều loại cấu trúc dữ liệu khác nhau.
D. Thuật toán yêu cầu bộ nhớ phụ tối thiểu.
6. Yếu tố nào sau đây KHÔNG phải là tiêu chí để đánh giá hiệu quả của một thuật toán sắp xếp?
A. Độ phức tạp thời gian.
B. Độ phức tạp không gian (bộ nhớ sử dụng).
C. Tính ổn định của thuật toán.
D. Số lượng dòng code của thuật toán.
7. Khi nào thì Sắp xếp nổi bọt (Bubble Sort) có thể có hiệu năng chấp nhận được?
A. Khi sắp xếp một mảng có hàng triệu phần tử.
B. Khi mảng đầu vào đã được sắp xếp hoặc gần được sắp xếp.
C. Khi cần sắp xếp dữ liệu theo thứ tự giảm dần.
D. Khi muốn tối ưu hóa việc sử dụng bộ nhớ.
8. Thuật toán nào sau đây có độ phức tạp thời gian tốt nhất trong trường hợp trung bình và trường hợp xấu nhất đối với các bài toán sắp xếp mảng lớn?
A. Sắp xếp nổi bọt (Bubble Sort).
B. Sắp xếp chọn (Selection Sort).
C. Sắp xếp nhanh (Quick Sort) và Sắp xếp trộn (Merge Sort).
D. Sắp xếp chèn (Insertion Sort).
9. Khi so sánh thuật toán Sắp xếp trộn (Merge Sort) và Sắp xếp nhanh (Quick Sort) về mặt hiệu năng trên các tập dữ liệu lớn, điểm khác biệt chính thường nằm ở đâu?
A. Sắp xếp trộn có độ phức tạp thời gian không đổi, còn Sắp xếp nhanh thay đổi.
B. Sắp xếp trộn yêu cầu ít bộ nhớ phụ hơn Sắp xếp nhanh.
C. Sắp xếp trộn có độ phức tạp thời gian trung bình và trường hợp xấu nhất là như nhau (O(n log n)), trong khi Sắp xếp nhanh có thể là O(n^2) trong trường hợp xấu nhất.
D. Sắp xếp nhanh luôn ổn định, còn Sắp xếp trộn thì không.
10. Giả sử có một mảng chưa sắp xếp: [5, 1, 4, 2, 8]. Sau lần duyệt đầu tiên của thuật toán sắp xếp nổi bọt (theo thứ tự 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]
11. Phát biểu nào sau đây mô tả đúng nhất bản chất của bài toán sắp xếp?
A. Tìm kiếm một phần tử cụ thể trong một tập hợp dữ liệu.
B. Tổ chức lại một tập hợp dữ liệu theo một thứ tự nhất định.
C. Tính toán tổng hoặc trung bình của các phần tử trong tập hợp.
D. Xóa các phần tử trùng lặp khỏi tập hợp dữ liệu.
12. Trong các thuật toán sắp xếp được học, thuật toán nào thường được sử dụng trong các hệ điều hành hoặc cơ sở dữ liệu để sắp xếp các tập tin hoặc bản ghi lớn một cách hiệu quả?
A. Sắp xếp nổi bọt (Bubble Sort).
B. Sắp xếp chèn (Insertion Sort).
C. Sắp xếp nhanh (Quick Sort) hoặc Sắp xếp trộn (Merge Sort) hoặc Heap Sort.
D. Sắp xếp chọn (Selection Sort).
13. Phát biểu nào sau đây mô tả đúng về thuật toán Sắp xếp vun đống (Heap Sort) so với Sắp xếp trộn (Merge Sort)?
A. Heap Sort yêu cầu nhiều bộ nhớ phụ hơn Merge Sort.
B. Heap Sort là thuật toán ổn định, còn Merge Sort thì không.
C. Heap Sort thường được coi là sắp xếp "trong chỗ" (in-place) vì yêu cầu bộ nhớ phụ ít hơn đáng kể so với Merge Sort.
D. Cả hai thuật toán đều có độ phức tạp thời gian là O(n^2).
14. Nếu bạn đang làm việc với một danh sách các đối tượng phức tạp, mỗi đối tượng có nhiều thuộc tính và bạn muốn sắp xếp chúng dựa trên một thuộc tính cụ thể, bạn có thể sử dụng kỹ thuật nào?
A. Sắp xếp bằng cách so sánh trực tiếp các đối tượng.
B. Sử dụng một hàm so sánh tùy chỉnh (custom comparison function) hoặc định nghĩa một phương thức so sánh cho các đối tượng.
C. Chỉ có thể sắp xếp các kiểu dữ liệu cơ bản.
D. Chuyển đổi đối tượng thành chuỗi rồi sắp xếp.
15. Khi nào thì việc sử dụng Sắp xếp trộn (Merge Sort) có thể gặp bất lợi về bộ nhớ?
A. Khi mảng đầu vào đã được sắp xếp.
B. Khi kích thước của mảng đầu vào rất lớn và cần bộ nhớ phụ để trộn các phần tử.
C. Khi thuật toán cần thực hiện quá nhiều phép hoán đổi.
D. Khi các phần tử trong mảng có giá trị âm.
16. Phát biểu nào sau đây mô tả đúng về thuật toán Sắp xếp nhanh (Quick Sort) và cách chọn điểm xoay (pivot)?
A. Việc chọn điểm xoay không ảnh hưởng đến hiệu năng của thuật toán.
B. Chọn điểm xoay là phần tử đầu tiên luôn cho hiệu năng tốt nhất.
C. Việc chọn điểm xoay có ảnh hưởng lớn đến hiệu năng, đặc biệt là trường hợp xấu nhất có thể xảy ra khi điểm xoay luôn là phần tử nhỏ nhất hoặc lớn nhất.
D. Sắp xếp nhanh chỉ hiệu quả khi điểm xoay là phần tử trung vị.
17. Tại sao thuật toán sắp xếp chọn (Selection Sort) lại hiệu quả hơn sắp xếp nổi bọt (Bubble Sort) trong một số trường hợp nhất định về số lần hoán đổi?
A. Sắp xếp chọn thực hiện nhiều phép so sánh hơn.
B. Sắp xếp chọn luôn thực hiện số lần hoán đổi tối thiểu.
C. Sắp xếp chọn chỉ hoán đổi khi tìm thấy phần tử nhỏ nhất và đặt vào đúng vị trí.
D. Sắp xếp chọn không cần lặp lại nhiều lần.
18. Thuật toán sắp xếp chèn (Insertion Sort) phù hợp với loại dữ liệu nào nhất?
A. Dữ liệu có kích thước rất lớn và hoàn toàn ngẫu nhiên.
B. Dữ liệu đã được sắp xếp gần hết hoặc có kích thước nhỏ.
C. Dữ liệu có các giá trị nằm trong một phạm vi rất hẹp.
D. Dữ liệu có nhiều phần tử trùng lặp.
19. Độ phức tạp thời gian của thuật toán Sắp xếp nổi bọt (Bubble Sort) trong trường hợp xấu nhất là bao nhiêu?
A. O(n)
B. O(n log n)
C. O(n^2)
D. O(log n)
20. Trong thực hành, nếu bạn cần sắp xếp một mảng rất lớn chứa các số nguyên và ưu tiên tốc độ, thuật toán nào thường được khuyến nghị nhất?
A. Sắp xếp nổi bọt (Bubble Sort).
B. Sắp xếp chọn (Selection Sort).
C. Sắp xếp trộn (Merge Sort) hoặc Sắp xếp nhanh (Quick Sort).
D. Sắp xếp chèn (Insertion Sort).
21. Tại sao việc phân biệt các thuật toán sắp xếp dựa trên "tính ổn định" lại quan trọng trong một số ứng dụng thực tế?
A. Để đảm bảo thuật toán luôn chạy nhanh nhất.
B. Để giữ nguyên thứ tự của các mục có khóa giống nhau, điều này hữu ích khi sắp xếp dữ liệu theo nhiều tiêu chí.
C. Để giảm thiểu số lần hoán đổi.
D. Để thuật toán dễ lập trình hơn.
22. Khi sắp xếp một danh sách các chuỗi ký tự, thứ tự sắp xếp thường tuân theo quy tắc nào?
A. Theo độ dài của chuỗi, chuỗi ngắn đứng trước.
B. Theo thứ tự bảng chữ cái (alphabetical order), dựa trên mã ASCII hoặc Unicode của các ký tự.
C. Theo thứ tự ngược của bảng chữ cái.
D. Theo số lượng nguyên âm trong chuỗi.
23. Sắp xếp vun đống (Heap Sort) sử dụng cấu trúc dữ liệu nào để thực hiện việc sắp xếp?
A. Hàng đợi ưu tiên (Priority Queue).
B. Đồ thị (Graph).
C. Cây nhị phân tìm kiếm (Binary Search Tree).
D. Vun đống (Heap).
24. Trong các thuật toán sắp xếp, phương pháp nào thường được coi là đơn giản và dễ hiểu nhất cho người mới bắt đầu?
A. Sắp xếp nhanh (Quick Sort).
B. Sắp xếp trộn (Merge Sort).
C. Sắp xếp nổi bọt (Bubble Sort).
D. Sắp xếp vun đống (Heap Sort).
25. Thuật toán nào sau đây KHÔNG phải là thuật toán sắp xếp ổn định theo mặc định?
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 nổi bọt (Bubble Sort).
