[Cánh diều] Trắc nghiệm Tin học 11 KHMT bài 8 Lập trình một số thuật toán sắp xếp
1. Đâu là thuật toán có độ phức tạp thời gian tốt nhất trong trường hợp xấu nhất (worst-case time complexity) trong số các thuật toán sau?
A. Sắp xếp nổi bọt (Bubble Sort) - O(n^2).
B. Sắp xếp chọn (Selection Sort) - O(n^2).
C. Sắp xếp trộn (Merge Sort) - O(n log n).
D. Sắp xếp chèn (Insertion Sort) - O(n^2).
2. Thuật toán sắp xếp nổi bọt (Bubble Sort) thực hiện bao nhiêu lượt so sánh và hoán đổi tối đa trên một mảng có n phần tử?
A. Khoảng n so sánh.
B. Khoảng n^2 so sánh.
C. Khoảng n log n so sánh.
D. Khoảng n/2 so sánh.
3. Trong thuật toán sắp xếp vun đống (Heap Sort), sau khi xây dựng max-heap, phần tử lớn nhất của mảng sẽ nằm ở đâu?
A. Ở cuối mảng.
B. Ở gốc của cây vun đống (phần tử đầu tiên của mảng).
C. Ở một vị trí ngẫu nhiên.
D. Ở giữa mảng.
4. Trong thuật toán sắp xếp chèn (Insertion Sort), nếu mảng đã được sắp xếp, độ phức tạp thời gian sẽ là bao nhiêu?
A. O(n^2).
B. O(n log n).
C. O(n).
D. O(log n).
5. Đâu là thuật toán sắp xếp có thể được sử dụng để sắp xếp các mảng chứa các giá trị nằm trong một phạm vi nhỏ và biết trước?
A. Sắp xếp vun đống (Heap 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).
6. Khi áp dụng thuật toán sắp xếp vun đống (Heap Sort), cấu trúc dữ liệu nào thường được sử dụng để biểu diễn cây vun đống?
A. Danh sách liên kết đôi.
B. Hàng đợi ưu tiên.
C. Mảng hoặc cấu trúc tương tự mảng.
D. Cây nhị phân tìm kiếm.
7. Khi sắp xếp một mảng có 10 phần tử, thuật toán sắp xếp chọn (Selection Sort) sẽ thực hiện tối đa bao nhiêu lượt tìm kiếm phần tử nhỏ nhất trong phần chưa sắp xếp?
A. 10 lượt.
B. 9 lượt.
C. 5 lượt.
D. 1 lượt.
8. Đâu là mục tiêu chính của việc phân hoạch (partitioning) trong thuật toán sắp xếp nhanh (Quick Sort)?
A. Chia mảng thành hai phần bằng nhau.
B. Đưa tất cả các phần tử nhỏ hơn phần tử chốt về một bên và các phần tử lớn hơn về bên còn lại.
C. Tìm phần tử nhỏ nhất và đặt nó ở đầu.
D. Sắp xếp mảng bằng cách đổi chỗ các phần tử liền kề.
9. Thuật toán sắp xếp trộn (Merge Sort) có tính chất ổn định (stable sort) hay không?
A. Có, vì nó không thay đổi thứ tự tương đối của các phần tử bằng nhau.
B. Không, vì nó sử dụng phép hoán đổi các phần tử không liền kề.
C. Có, vì nó luôn sắp xếp theo thứ tự tăng dần.
D. Không, vì nó có độ phức tạp thời gian O(n log n).
10. Đâu là ưu điểm chính của thuật toán sắp xếp nhanh (Quick Sort) so với sắp xếp nổi bọt hoặc sắp xếp chọn trong trường hợp mảng lớn?
A. Dễ cài đặt và hiểu rõ hơn.
B. Luôn có độ phức tạp thời gian tuyến tính O(n).
C. Có hiệu suất trung bình tốt hơn, thường là O(n log n).
D. Yêu cầu ít bộ nhớ phụ trợ hơn.
11. Độ phức tạp thời gian trung bình của thuật toán sắp xếp trộn (Merge Sort) là bao nhiêu?
A. O(n).
B. O(n^2).
C. O(n log n).
D. O(log n).
12. Thuật toán sắp xếp trộn (Merge Sort) thuộc loại thuật toán nào?
A. Thuật toán tham lam (Greedy Algorithm).
B. Thuật toán chia để trị (Divide and Conquer Algorithm).
C. Thuật toán quay lui (Backtracking Algorithm).
D. Thuật toán quy hoạch động (Dynamic Programming Algorithm).
13. Đâu là cách lựa chọn chốt (pivot) phổ biến trong thuật toán sắp xếp nhanh (Quick Sort) để giảm thiểu trường hợp xấu nhất?
A. Luôn chọn phần tử đầu tiên của mảng.
B. Chọn ngẫu nhiên một phần tử trong mảng.
C. Chọn phần tử lớn nhất trong mảng.
D. Chọn phần tử thứ hai của mảng.
14. Đâu là đặc điểm chính của thuật toán sắp xếp nổi bọt (Bubble Sort) về cách thức hoạt động?
A. So sánh và đổi chỗ các cặp phần tử liền kề nếu chúng sai thứ tự, lặp lại quá trình này cho đến khi mảng được sắp xếp.
B. Chia mảng thành hai nửa, sắp xếp từng nửa rồi trộn chúng lại với nhau.
C. Tìm phần tử nhỏ nhất trong phần chưa sắp xếp và đặt nó vào đầu.
D. Lặp đi lặp lại việc tìm phần tử nhỏ nhất trong phần chưa sắp xếp và hoán vị nó với phần tử đầu tiên của phần chưa sắp xếp.
15. Khi thực hiện thuật toán sắp xếp vun đống (Heap Sort), bước heapify (hoặc sift-down) có vai trò gì?
A. Chia mảng thành hai phần.
B. Tìm phần tử nhỏ nhất.
C. Đảm bảo tính chất vun đống (heap property) của một cây con sau khi một nút bị thay đổi.
D. Hoán đổi các phần tử liền kề.
16. Thuật toán nào trong số các thuật toán sau đây có thể yêu cầu bộ nhớ phụ trợ đáng kể (O(n)) để hoạt động?
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) (trong trường hợp đệ quy sâu).
D. Sắp xếp trộn (Merge Sort).
17. Trong thuật toán sắp xếp chèn (Insertion Sort), để chèn một phần tử vào đúng vị trí trong mảng con đã sắp xếp, ta thường sử dụng phương pháp nào?
A. Duyệt ngược từ cuối mảng con đã sắp xếp để tìm vị trí.
B. Tìm kiếm nhị phân để xác định vị trí.
C. Sử dụng phép hoán đổi các phần tử liền kề.
D. Tìm kiếm tuyến tính từ đầu mảng con đã sắp xếp.
18. Đâu là thuật toán sắp xếp 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 nhanh (Quick Sort).
B. Sắp xếp vun đống (Heap Sort).
C. Sắp xếp đếm (Counting Sort).
D. Sắp xếp trộn (Merge Sort).
19. Đâu là nhược điểm chính của thuật toán sắp xếp nhanh (Quick Sort) khi dữ liệu đầu vào có nhiều phần tử trùng lặp?
A. Độ phức tạp thời gian tăng lên đáng kể, có thể trở thành O(n^2).
B. Yêu cầu bộ nhớ phụ trợ lớn hơn O(n).
C. Hoạt động chậm hơn các thuật toán O(n log n) khác.
D. Khó cài đặt hơn.
20. Thuật toán sắp xếp vun đống (Heap Sort) sử dụng hai giai đoạn chính. Giai đoạn đầu tiên là gì?
A. Trộn các phần tử đã sắp xếp.
B. Xây dựng một cây vun đống từ mảng ban đầu.
C. Chia mảng thành các phần tử nhỏ.
D. So sánh các phần tử liền kề.
21. Trong thuật toán sắp xếp chọn (Selection Sort), mỗi bước lặp sẽ đảm bảo điều gì?
A. Các phần tử liền kề được sắp xếp đúng thứ tự.
B. Phần tử nhỏ nhất trong phần chưa sắp xếp được đặt vào vị trí đúng.
C. Mảng được chia thành hai nửa đã sắp xếp.
D. Các phần tử được chèn vào đúng vị trí.
22. Khi nào thuật toán sắp xếp nổi bọt (Bubble Sort) tỏ ra hiệu quả nhất?
A. Khi mảng có kích thước rất lớn và không có thứ tự.
B. Khi mảng đã gần được sắp xếp hoặc có kích thước nhỏ.
C. Khi cần một thuật toán có độ phức tạp thời gian không đổi.
D. Khi cần sắp xếp theo thứ tự giảm dần.
23. Thuật toán sắp xếp chèn (Insertion Sort) hoạt động dựa trên nguyên tắc nào?
A. Chia mảng thành các đoạn nhỏ, sắp xếp chúng rồi hợp nhất lại.
B. Lấy từng phần tử từ mảng chưa sắp xếp và chèn vào vị trí đúng trong mảng đã sắp xếp một phần.
C. So sánh và đổi chỗ các phần tử liền kề.
D. Tìm phần tử có giá trị nhỏ nhất trong mảng và đưa nó về đầu.
24. Trong thuật toán sắp xếp nhanh (Quick Sort), nếu phần tử chốt được chọn là phần tử nhỏ nhất hoặc lớn nhất trong mảng, điều gì sẽ xảy ra với hiệu suất?
A. Hiệu suất sẽ là O(n log n).
B. Hiệu suất sẽ là O(n).
C. Hiệu suất sẽ là O(n^2) (trường hợp xấu nhất).
D. Hiệu suất sẽ là O(log n).
25. Thuật toán sắp xếp chèn (Insertion Sort) có thể được mô tả như thế nào trong thực tế?
A. Giống như cách bạn sắp xếp một bộ bài bằng cách nhặt từng lá bài và đặt vào đúng vị trí trong bộ bài đã sắp xếp.
B. Giống như việc liên tục tìm lá bài nhỏ nhất và đặt nó lên đầu bộ bài.
C. Giống như việc chia bộ bài thành hai phần, sắp xếp từng phần rồi ghép lại.
D. Giống như việc liên tục xem xét từng cặp lá bài liền kề và đổi chỗ nếu sai thứ tự.
