Trắc nghiệm Tin học 11 Cánh diều KHMT bài 8 Lập trình một số thuật toán sắp xếp

1. Trong thuật toán sắp xếp nhanh (Quick Sort), bước quan trọng nhất để đạt hiệu quả cao là gì?

A. Chọn phần tử trung vị làm chốt (pivot).

B. Chia mảng thành hai phần bằng nhau.

C. Chọn phần tử chốt (pivot) sao cho các phần tử nhỏ hơn chốt nằm về một bên và các phần tử lớn hơn nằm về phía bên kia.

D. Hoán đổi các phần tử theo thứ tự ngẫu nhiên.

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

A. O(n)

B. O(n log n)

C. O(n^2)

D. O(log n)

3. Thuật toán sắp xếp nào có ưu điểm là không cần thêm bộ nhớ phụ đáng kể (in-place sorting)?

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

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

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

D. Sắp xếp theo cơ số (Radix Sort)

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

A. Tìm phần tử nhỏ nhất và đặt nó vào cuối mảng.

B. Tìm phần tử nhỏ nhất trong phần chưa sắp xếp và hoán đổi nó với phần tử đầu tiên của phần chưa sắp xếp đó.

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 đổi ngẫu nhiên các phần tử.

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

A. O(n)

B. O(n log n)

C. O(n^2)

D. O(log n)

6. Trong thuật toán sắp xếp nổi bọt cải tiến (Optimized Bubble Sort), làm thế nào để xác định xem mảng đã được sắp xếp hay chưa để dừng sớm?

A. Kiểm tra xem có bất kỳ hoán đổi nào được thực hiện trong một lượt duyệt qua hay không.

B. Kiểm tra xem phần tử đầu tiên có bằng phần tử cuối cùng không.

C. Đếm số lần hoán đổi.

D. So sánh phần tử đầu và phần tử cuối.

7. Độ 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)

B. O(n log n)

C. O(n^2)

D. O(n^3)

8. Khi so sánh thuật toán sắp xếp nổi bọt (Bubble Sort) và sắp xếp chèn (Insertion Sort), thuật toán nào thường được coi là kém hiệu quả hơn trên các tập dữ liệu lớn không có cấu trúc?

A. Cả hai đều có hiệu quả tương đương.

B. Sắp xếp chèn (Insertion Sort) kém hiệu quả hơn.

C. Sắp xếp nổi bọt (Bubble Sort) kém hiệu quả hơn.

D. Cả hai đều rất hiệu quả.

9. Trong thuật toán sắp xếp vun đống (Heap Sort), sau khi phần tử lớn nhất được chuyển ra khỏi đống, làm thế nào để duy trì tính chất đống?

A. Phần tử cuối cùng của đống được đặt lên gốc và sau đó vun đống xuống.

B. Phần tử đầu tiên của đống được đặt vào cuối mảng và vun đống lên.

C. Toàn bộ mảng được sắp xếp lại từ đầu.

D. Không cần làm gì, đống vẫn được duy trì.

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

A. O(n)

B. O(n log n)

C. O(n^2)

D. O(1)

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

A. O(n)

B. O(n log n)

C. O(n^2)

D. O(log n)

12. Thuật toán sắp xếp nào sau đây có thể sử dụng phân hoạch (partitioning) để chia mảng thành các phần nhỏ hơn và sắp xếp chúng một cách đệ quy?

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)

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

13. Mục tiêu chính của việc vun đống (heapify) trong thuật toán sắp xếp vun đống (Heap Sort) là gì?

A. Tìm phần tử nhỏ nhất trong mảng.

B. Đảm bảo rằng một cây con bắt đầu từ nút gốc thỏa mãn tính chất của một đống (heap).

C. Chia mảng thành hai nửa để xử lý đệ quy.

D. Hoán đổi ngẫu nhiên các phần tử.

14. Trong thuật toán sắp xếp chèn (Insertion Sort), mỗi phần tử của mảng được xem xét như thế nào?

A. Nó được so sánh với tất cả các phần tử khác và đặt vào vị trí đúng.

B. Nó được chèn vào đúng vị trí trong phần mảng đã được sắp xếp trước đó.

C. Nó được hoán đổi với phần tử lớn nhất.

D. Nó được bỏ qua nếu đã đúng vị trí.

15. Phát biểu nào mô tả chính xác nhất cách thuật toán sắp xếp vun đống (Heap Sort) sử dụng cấu trúc dữ liệu đống (heap)?

A. Nó sử dụng một hàng đợi ưu tiên (priority queue) được triển khai bằng đống.

B. Nó xây dựng một đống từ mảng, sau đó lần lượt lấy phần tử lớn nhất (hoặc nhỏ nhất) ra khỏi đống và đặt vào cuối mảng đã sắp xếp.

C. Nó chỉ dùng đống để tìm phần tử nhỏ nhất.

D. Nó không sử dụng cấu trúc dữ liệu đống.

16. Trong thuật toán sắp xếp nhanh (Quick Sort), khái niệm phần tử chốt (pivot) được sử dụng để làm gì?

A. Để xác định phần tử lớn nhất trong mảng.

B. Để chia mảng thành hai tập con: một tập chứa các phần tử nhỏ hơn chốt và một tập chứa các phần tử lớn hơn chốt.

C. Để xác định phần tử nhỏ nhất trong mảng.

D. Để quyết định thuật toán nào sẽ được sử dụng tiếp theo.

17. Trong thuật toán sắp xếp chèn (Insertion Sort), tại sao việc dịch chuyển các phần tử sang phải lại cần thiết?

A. Để làm cho mảng có cấu trúc đẹp hơn.

B. Để tạo ra một khoảng trống để chèn phần tử hiện tại vào đúng vị trí.

C. Để tăng tốc độ so sánh.

D. Để loại bỏ các phần tử trùng lặp.

18. Trong thuật toán sắp xếp nổi bọt (Bubble Sort), phát biểu nào sau đây là đúng về việc hoán đổi vị trí các phần tử?

A. Luôn hoán đổi hai phần tử liền kề nếu phần tử đứng trước lớn hơn phần tử đứng sau.

B. Chỉ hoán đổi nếu phần tử đứng trước nhỏ hơn phần tử đứng sau.

C. Hoán đổi hai phần tử bất kỳ trong mảng nếu chúng sai thứ tự.

D. Không thực hiện hoán đổi, chỉ so sánh.

19. Thuật toán sắp xếp nào sau đây có thể được coi là ổn định (stable sort)?

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

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

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

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

20. Thuật toán sắp xếp nào sau đây có thể có độ phức tạp thời gian O(n^2) trong trường hợp xấu nhất nhưng lại có thể đạt O(n) trong trường hợp tốt nhất?

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 chọn (Selection Sort)

21. Phát biểu nào sau đây mô tả đúng về thuật toán sắp xếp nổi bọt (Bubble Sort)?

A. Nó chia mảng thành hai phần và sắp xếp đệ quy.

B. Nó liên tục đi qua danh sách, so sánh các phần tử liền kề và hoán đổi chúng nếu chúng sai thứ tự.

C. Nó tìm phần tử nhỏ nhất và đặt nó vào đầu mảng.

D. Nó chèn từng phần tử vào vị trí đúng trong phần đã sắp xếp.

22. Trong thuật toán sắp xếp chèn (Insertion Sort), nếu chúng ta đang chèn phần tử thứ k, số lần so sánh tối đa có thể xảy ra là bao nhiêu?

A. k

B. k-1

C. n (tổng số phần tử)

D. 1

23. Trong thuật toán sắp xếp nhanh (Quick Sort), nếu phần tử chốt (pivot) luôn được chọn là phần tử nhỏ nhất hoặc lớn nhất trong phạm vi hiện tại, điều gì sẽ xảy ra với hiệu suất của thuật toán?

A. Hiệu suất sẽ rất tốt, gần với O(n log n).

B. Hiệu suất sẽ suy giảm về trường hợp xấu nhất, O(n^2).

C. Hiệu suất sẽ không bị ảnh hưởng.

D. Thuật toán sẽ dừng lại.

24. Thuật toán sắp xếp nào sau đây có xu hướng hiệu quả hơn khi mảng đã gần đượ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)

25. Độ 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 trong trường hợp xấu nhất?

A. O(n)

B. O(n log n)

C. O(n^2)

D. O(log n)