Trắc nghiệm Kết nối Tin học 11 KHMT bài 21 Các thuật toán sắp xếp đơn giản

1. Độ phức tạp thời gian xấu nhất của thuật toán sắp xếp nổi bọt (Bubble Sort) là bao nhiêu?

A. O(n)

B. O(n log n)

C. O(n^2)

D. O(log n)

2. Khi thực hiện sắp xếp một mảng bằng thuật toán sắp xếp chọn (Selection Sort), nếu mảng có các phần tử trùng lặp, thứ tự tương đối của các phần tử trùng lặp đó có được bảo toàn không?

A. Có, Selection Sort là thuật toán sắp xếp ổn định.

B. Không, Selection Sort không phải là thuật toán sắp xếp ổn định.

C. Chỉ khi mảng có số lượng phần tử chẵn.

D. Chỉ khi các phần tử trùng lặp đứng cạnh nhau.

3. Thuật toán sắp xếp nào có thể được mô tả như việc đặt một chiếc thẻ vào đúng vị trí của nó trong một bộ bài đã được sắp xếp?

A. Sắp xếp chọn (Selection Sort)

B. Sắp xếp nổi bọt (Bubble Sort)

C. Sắp xếp chèn (Insertion Sort)

D. Sắp xếp vun đống (Heap Sort)

4. Khi sắp xếp một mảng gồm n phần tử, thuật toán sắp xếp chọn (Selection Sort) thực hiện bao nhiêu lượt đổi chỗ (swap) trong trường hợp xấu nhất?

A. n lượt đổi chỗ

B. n-1 lượt đổi chỗ

C. n*(n-1)/2 lượt đổi chỗ

D. 0 lượt đổi chỗ

5. Trong thuật toán sắp xếp chọn (Selection Sort), mục đích của mỗi vòng lặp là gì?

A. Tìm phần tử lớn nhất và đặt nó vào vị trí cuối.

B. Tìm phần tử nhỏ nhất và đặt nó vào vị trí đầu tiên.

C. Tìm phần tử lớn nhất và đặt nó vào vị trí đầu tiên.

D. Tìm phần tử nhỏ nhất và đặt nó vào vị trí cuối.

6. Thuật toán sắp xếp nào hoạt động hiệu quả nhất khi danh sách đầu vào gần như đã được sắp xếp?

A. Sắp xếp chọn (Selection Sort)

B. Sắp xếp chèn (Insertion Sort)

C. Sắp xếp nổi bọt (Bubble Sort)

D. Sắp xếp vun đống (Heap Sort)

7. Nếu danh sách cần sắp xếp có kích thước rất nhỏ (ví dụ: dưới 10 phần tử), thuật toán nào trong các thuật toán đơn giản thường có hiệu suất tốt nhất do chi phí khởi tạo thấp?

A. Sắp xếp vun đống (Heap Sort)

B. Sắp xếp nhanh (Quick Sort)

C. Sắp xếp chèn (Insertion Sort)

D. Sắp xếp trộn (Merge Sort)

8. Thuật toán nào có xu hướng sử dụng ít bộ nhớ phụ (không tính bộ nhớ cho mảng ban đầu) nhất?

A. Sắp xếp trộn (Merge Sort)

B. Sắp xếp nhanh (Quick Sort)

C. Sắp xếp vun đống (Heap Sort)

D. Sắp xếp nổi bọt (Bubble Sort)

9. Việc thực hiện các phép đổi chỗ (swap) trong thuật toán sắp xếp chèn (Insertion Sort) có ý nghĩa gì?

A. Đưa phần tử nhỏ nhất về đầu mảng.

B. Đưa phần tử lớn nhất về cuối mảng.

C. Chèn phần tử hiện tại vào đúng vị trí trong phần đã sắp xếp.

D. Hoán vị ngẫu nhiên các phần tử để tăng tốc độ.

10. Cấu trúc dữ liệu nào thường được sử dụng để triển khai thuật toán sắp xếp vun đống (Heap Sort)?

A. Danh sách liên kết (Linked List)

B. Cây tìm kiếm nhị phân (Binary Search Tree)

C. Đống (Heap)

D. Hàng đợi ưu tiên (Priority Queue)

11. Độ phức tạp thời gian tốt nhất của thuật toán sắp xếp nổi bọt (Bubble Sort) là bao nhiêu?

A. O(n)

B. O(n log n)

C. O(n^2)

D. O(1)

12. Trong các thuật toán sắp xếp đơn giản, thuật toán nào thường có số lượt so sánh nhiều nhất trong trường hợp xấu 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 chèn (Insertion Sort)

D. Sắp xếp nhanh (Quick Sort)

13. Thuật toán sắp xếp nào thực hiện việc chia mảng thành hai phần: một phần đã sắp xếp và một phần chưa sắp xếp?

A. Sắp xếp chọn (Selection Sort)

B. Sắp xếp nổi bọt (Bubble Sort)

C. Sắp xếp chèn (Insertion Sort)

D. Sắp xếp vun đống (Heap Sort)

14. Khi sử dụng thuật toán sắp xếp chèn (Insertion Sort) trên một danh sách có n phần tử, số lượt so sánh tối đa trong trường hợp xấu nhất là bao nhiêu?

A. n

B. n-1

C. n*(n-1)/2

D. n log n

15. Thuật toán nào trong các thuật toán sắp xếp đơn giản thường có số lượt so sánh ít nhất trong trường hợp tốt nhất (danh sách đã sắp xếp)?

A. Sắp xếp chọn (Selection Sort)

B. Sắp xếp chèn (Insertion Sort)

C. Sắp xếp nổi bọt (Bubble Sort)

D. Sắp xếp vun đống (Heap Sort)

16. Trong thuật toán sắp xếp nổi bọt (Bubble Sort), nếu danh sách đã được sắp xếp, thuật toán có thể dừng sớm hay không?

A. Không, nó luôn phải chạy đủ n-1 vòng lặp.

B. Có, nếu không có lượt đổi chỗ nào xảy ra trong một vòng lặp, danh sách đã sắp xếp.

C. Có, nếu phần tử đầu tiên bằng phần tử cuối cùng.

D. Có, nếu chỉ có một lượt đổi chỗ xảy ra.

17. Thuật toán nào có ưu điểm là ổn định (stable sort), tức là các phần tử có giá trị bằng nhau sẽ giữ nguyên thứ tự tương đối của chúng sau khi sắp xếp?

A. Sắp xếp chọn (Selection Sort)

B. Sắp xếp nổi bọt (Bubble Sort)

C. Sắp xếp vun đống (Heap Sort)

D. Sắp xếp nhanh (Quick Sort)

18. Độ phức tạp thời gian của thuật toán sắp xếp chọn (Selection Sort) trong mọi trường hợp (tốt nhất, trung bình, xấu nhất) là bao nhiêu?

A. O(n)

B. O(n log n)

C. O(n^2)

D. O(log n)

19. Thuật toán sắp xếp nào có thể gây ra nhiều lượt đổi chỗ nhất trong trường hợp xấu nhất?

A. Sắp xếp chọn (Selection Sort)

B. Sắp xếp chèn (Insertion Sort)

C. Sắp xếp nổi bọt (Bubble Sort)

D. Sắp xếp vun đống (Heap Sort)

20. Thuật toán nào có thể được sử dụng để sắp xếp một danh sách mà các phần tử có giá trị nằm trong một phạm vi nhỏ và biết trước?

A. Sắp xếp chèn (Insertion Sort)

B. Sắp xếp nổi bọt (Bubble Sort)

C. Sắp xếp đếm (Counting Sort)

D. Sắp xếp chọn (Selection Sort)

21. Thuật toán nào được coi là đơn giản nhất trong số các thuật toán sắp xếp cơ bản về mặt ý tưởng và triển khai?

A. Sắp xếp trộn (Merge Sort)

B. Sắp xếp nhanh (Quick Sort)

C. Sắp xếp nổi bọt (Bubble Sort)

D. Sắp xếp vun đống (Heap Sort)

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

A. O(n)

B. O(n log n)

C. O(n^2)

D. O(log n)

23. Độ phức tạp thời gian của thuật toán sắp xếp vun đống (Heap Sort) là bao nhiêu, bất kể trường hợp nào?

A. O(n)

B. O(n log n)

C. O(n^2)

D. O(log n)

24. Trong thuật toán sắp xếp chèn (Insertion Sort), mỗi lần lặp sẽ lấy phần tử nào để đưa vào đúng vị trí trong phần đã sắp xếp?

A. Phần tử lớn nhất từ phần chưa sắp xếp.

B. Phần tử nhỏ nhất từ phần chưa sắp xếp.

C. Phần tử đầu tiên từ phần chưa sắp xếp.

D. Phần tử cuối cùng từ phần chưa sắp xếp.

25. Trong thuật toán sắp xếp nổi bọt (Bubble Sort), ở mỗi vòng lặp, phần tử lớn nhất (hoặc nhỏ nhất) sẽ được nổi lên vị trí cuối cùng của phần chưa sắp xếp. Đúng hay Sai?

A. Đúng, đó là nguyên lý cốt lõi của Bubble Sort.

B. Sai, chỉ phần tử nhỏ nhất mới nổi lên.

C. Sai, phần tử lớn nhất sẽ ở vị trí đầu tiên.

D. Sai, Bubble Sort chỉ so sánh các cặp liền kề mà không có sự nổi bọt.