1. Khi nói về độ phức tạp thuật toán (algorithm complexity), ký hiệu O(n) thường ám chỉ điều gì?
A. Thuật toán thực hiện tốt nhất khi n rất nhỏ.
B. Thời gian hoặc bộ nhớ sử dụng tăng tuyến tính theo kích thước đầu vào n.
C. Thuật toán cần thực hiện n lần lặp.
D. Thuật toán có hiệu suất không đổi bất kể kích thước đầu vào.
2. Đâu là đặc điểm quan trọng nhất của một thuật toán sắp xếp hiệu quả về mặt thời gian xử lý?
A. Sử dụng ít bộ nhớ nhất có thể.
B. Có khả năng xử lý dữ liệu lớn trong thời gian ngắn nhất.
C. Dễ dàng cài đặt và hiểu bởi người dùng.
D. Có thể áp dụng cho mọi loại dữ liệu khác nhau.
3. Khi sắp xếp một tập dữ liệu có kích thước rất lớn và các giá trị nằm trong một phạm vi hẹp, thuật toán nào có khả năng là lựa chọn tốt nhất về hiệu suất?
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 đếm (Counting Sort).
D. Sắp xếp chọn (Selection Sort).
4. Thuật toán Sắp xếp vun đống (Heap Sort) sử dụng cấu trúc dữ liệu nào làm nền tảng chính?
A. Hàng đợi (Queue).
B. Ngăn xếp (Stack).
C. Đống (Heap), cụ thể là đống nhị phân.
D. Danh sách liên kết (Linked List).
5. Khi so sánh thuật toán Sắp xếp nổi bọt và Sắp xếp chọn, điểm khác biệt cốt lõi về cách thức hoạt động là gì?
A. Sắp xếp nổi bọt dùng đệ quy, Sắp xếp chọn dùng lặp.
B. Sắp xếp nổi bọt đổi chỗ liên tục các phần tử liền kề, Sắp xếp chọn tìm và đặt phần tử nhỏ nhất vào vị trí đầu.
C. Sắp xếp nổi bọt hiệu quả hơn về thời gian, Sắp xếp chọn hiệu quả hơn về bộ nhớ.
D. Sắp xếp nổi bọt xử lý danh sách tăng dần, Sắp xếp chọn xử lý danh sách giảm dần.
6. Thuật toán Sắp xếp chọn (Selection Sort) có đặc điểm nổi bật là:
A. Thực hiện rất ít lần đổi chỗ.
B. Luôn tìm phần tử lớn nhất để đặt vào cuối danh sách.
C. Phù hợp nhất với các danh sách đã gần như sắp xếp.
D. Chia danh sách thành hai phần và sắp xếp đệ quy.
7. Thuật toán nào thường được xem là ổn định (stable sort) trong việc giữ nguyên thứ tự tương đối của các phần tử bằng nhau?
A. Sắp xếp nhanh (Quick Sort).
B. Sắp xếp trộn (Merge Sort).
C. Sắp xếp chọn (Selection Sort).
D. Sắp xếp nổi bọt (Bubble Sort) chỉ khi cài đặt đúng cách.
8. Trong thuật toán Sắp xếp trộn (Merge Sort), giai đoạn trộn (merge) có vai trò quan trọng là:
A. Chia mảng lớn thành các mảng con nhỏ hơn.
B. Kết hợp hai mảng con đã sắp xếp thành một mảng lớn hơn đã sắp xếp.
C. Tìm phần tử nhỏ nhất trong toàn bộ mảng.
D. Đổi chỗ các phần tử liền kề để tạo sự sắp xếp.
9. Một trong những ưu điểm của Sắp xếp vun đống (Heap Sort) là:
A. Là thuật toán sắp xếp ổn định.
B. Có độ phức tạp thời gian không đổi là O(n log n) trong mọi trường hợp.
C. Yêu cầu bộ nhớ phụ trợ rất nhỏ, chỉ O(1).
D. Dễ dàng song song hóa.
10. Khi sắp xếp một mảng các số nguyên theo thứ tự tăng dần, bước đầu tiên của thuật toán Sắp xếp nổi bọt thường là:
A. Tìm phần tử nhỏ nhất trong toàn bộ mảng.
B. So sánh phần tử đầu tiên với phần tử thứ hai và đổi chỗ nếu cần.
C. Chia mảng thành hai nửa.
D. Chèn phần tử đầu tiên vào vị trí thích hợp trong phần còn lại của mảng.
11. Ưu điểm chính của thuật toán Sắp xếp trộn (Merge Sort) là gì?
A. Luôn có độ phức tạp thời gian là O(n^2).
B. Yêu cầu ít bộ nhớ phụ trợ hơn so với các thuật toán O(n log n) khác.
C. Là một thuật toán ổn định (stable sort), giữ nguyên thứ tự tương đối của các phần tử bằng nhau.
D. Đơn giản để cài đặt và hiểu rõ.
12. Theo thuật ngữ Tin học, thuật toán sắp xếp là một tiến trình thực hiện các bước để đạt được mục tiêu nào sau đây?
A. Tìm kiếm một phần tử cụ thể trong một tập hợp dữ liệu đã cho.
B. Biến đổi một tập hợp dữ liệu thành một dạng có thứ tự nhất định.
C. Thực hiện các phép tính toán học phức tạp trên dữ liệu.
D. Lưu trữ dữ liệu vào bộ nhớ máy tính.
13. Ưu điểm của các thuật toán sắp xếp không dựa trên phép so sánh (như Sắp xếp đếm) là gì?
A. Chúng có thể có độ phức tạp thời gian tốt hơn O(n log n).
B. Chúng hoạt động hiệu quả với mọi loại dữ liệu.
C. Chúng luôn là thuật toán sắp xếp tại chỗ.
D. Chúng đơn giản và dễ hiểu hơn các thuật toán so sánh.
14. Thuật toán nào sau đây KHÔNG phải là thuật toán sắp xếp dựa trên phép so sánh (comparison sort)?
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 đếm (Counting Sort).
D. Sắp xếp nhanh (Quick Sort).
15. Thuật toán Sắp xếp theo cơ số (Radix Sort) thường sử dụng một thuật toán sắp xếp trung gian nào để sắp xếp theo từng cơ số (digit)?
A. Sắp xếp nhanh (Quick Sort).
B. Sắp xếp trộn (Merge Sort).
C. Sắp xếp chèn (Insertion Sort) hoặc Sắp xếp đếm (Counting Sort).
D. Sắp xếp nổi bọt (Bubble Sort).
16. Đâu là một ví dụ về bộ nhớ phụ trợ (auxiliary space) được sử dụng bởi một thuật toán sắp xếp?
A. Vùng nhớ chứa dữ liệu gốc cần sắp xếp.
B. Các biến tạm thời để lưu trữ giá trị trong quá trình hoán đổi.
C. Bộ nhớ cache của CPU.
D. Ổ cứng lưu trữ hệ điều hành.
17. Đâu là một ví dụ về việc sắp xếp theo cơ số (Radix Sort) được áp dụng?
A. Sắp xếp các chuỗi ký tự theo thứ tự từ điển.
B. Sắp xếp các số nguyên dương lớn.
C. Sắp xếp các bản ghi dựa trên nhiều trường dữ liệu khác nhau.
D. Tất cả các đáp án trên đều đúng.
18. Thuật toán Sắp xếp nhanh (Quick Sort) đạt hiệu suất tốt nhất khi nào?
A. Khi danh sách được sắp xếp theo thứ tự ngược lại.
B. Khi chọn đúng phần tử chốt (pivot) để chia danh sách.
C. Khi sử dụng phương pháp đệ quy lồng nhau.
D. Khi mọi phần tử trong danh sách đều khác nhau.
19. Nếu một thuật toán sắp xếp có độ phức tạp thời gian là O(n^2), điều này có ý nghĩa gì khi kích thước dữ liệu tăng gấp đôi?
A. Thời gian xử lý sẽ tăng gấp đôi.
B. Thời gian xử lý sẽ tăng gấp bốn lần.
C. Thời gian xử lý sẽ giảm đi một nửa.
D. Thời gian xử lý sẽ không thay đổi.
20. Nếu ta có một danh sách gồm các cặp (Tên, Điểm), và muốn sắp xếp theo Điểm giảm dần, sau đó nếu Điểm bằng nhau thì sắp xếp theo Tên tăng dần, đây gọi là loại sắp xếp gì?
A. Sắp xếp đơn giản.
B. Sắp xếp theo khóa chính.
C. Sắp xếp đa khóa (multi-key sort) hoặc sắp xếp theo tiêu chí kép.
D. Sắp xếp theo thứ tự ngẫu nhiên.
21. Thuật toán Sắp xếp chèn (Insertion Sort) hoạt động hiệu quả nhất khi nào?
A. Khi tập dữ liệu rất lớn và hoàn toàn ngẫu nhiên.
B. Khi tập dữ liệu đã gần như được sắp xếp hoặc có kích thước nhỏ.
C. Khi cần thực hiện sắp xếp song song trên nhiều bộ xử lý.
D. Khi bộ nhớ máy tính có hạn chế nghiêm trọng.
22. Đâu là nhược điểm tiềm ẩn của thuật toán Sắp xếp nhanh (Quick Sort) trong trường hợp xấu nhất?
A. Độ phức tạp thời gian có thể lên tới O(n^2).
B. Yêu cầu bộ nhớ phụ trợ lớn, lên tới O(n).
C. Không phải là thuật toán ổn định.
D. Chậm hơn Sắp xếp trộn trong mọi trường hợp.
23. Trong các thuật toán sắp xếp cơ bản, thuật toán Sắp xếp nổi bọt (Bubble Sort) hoạt động dựa trên nguyên tắc chính nào?
A. Chia đôi danh sách và sắp xếp từng phần.
B. Lặp đi lặp lại việc so sánh các cặp phần tử liền kề và đổi chỗ nếu sai thứ tự.
C. Tìm phần tử nhỏ nhất và đặt nó vào vị trí đầu tiên.
D. Chèn từng phần tử vào vị trí đúng trong danh sách đã sắp xếp.
24. Trong các thuật toán sắp xếp được học, thuật toán nào thường có độ phức tạp thời gian trung bình là O(n log n) với n là số lượng phần tử?
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 trộn (Merge Sort).
D. Sắp xếp chọn (Selection Sort).
25. Nếu một thuật toán sắp xếp được mô tả là sắp xếp tại chỗ (in-place sort), điều này có nghĩa là gì?
A. Nó chỉ hoạt động trên các dữ liệu được lưu trữ trong bộ nhớ chính.
B. Nó không cần bất kỳ bộ nhớ phụ trợ nào ngoài bộ nhớ cho dữ liệu gốc.
C. Nó sắp xếp dữ liệu trực tiếp trên ổ đĩa.
D. Nó sử dụng cấu trúc dữ liệu đệ quy để sắp xếp.
