Trắc nghiệm Cánh diều Tin học 11 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 nổi bọt (Bubble Sort), ở mỗi lần lặp qua danh sách, phần tử lớn nhất chưa được sắp xếp sẽ được di chuyển đến vị trí nào?

A. Vị trí đầu tiên của danh sách chưa được sắp xếp.

B. Vị trí cuối cùng của danh sách chưa được sắp xếp.

C. Vị trí giữa của danh sách chưa được sắp xếp.

D. Vị trí ngẫu nhiên trong danh sách chưa được sắp xếp.

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 nhanh (Quick Sort) có thể lên tới bao nhiêu?

A. O(n)

B. O(n log n)

C. O(n^2)

D. O(log n)

3. Trong Quick Sort, bước phân hoạch (partitioning) có vai trò gì?

A. Để đếm số phần tử nhỏ hơn phần tử chốt.

B. Để đặt phần tử chốt (pivot) vào đúng vị trí của nó trong mảng đã sắp xếp.

C. Để hoán đổi các phần tử lớn nhất với nhau.

D. Để chia mảng thành hai nửa có kích thước bằng nhau.

4. Khi sử dụng thuật toán sắp xếp chèn (Insertion Sort), nếu phần tử cần chèn nhỏ hơn tất cả các phần tử trong phần đã sắp xếp, nó sẽ được đặt ở đâu?

A. Cuối phần đã sắp xếp.

B. Giữa phần đã sắp xếp.

C. Đầu phần đã sắp xếp.

D. Nó sẽ không được chèn vào phần đã sắp xếp.

5. Thuật toán sắp xếp nào thực hiện việc xây dựng một Max-Heap từ mảng ban đầu?

A. Quick Sort

B. Merge Sort

C. Heap Sort

D. Insertion Sort

6. Thuật toán nào thường được sử dụng trong các hệ thống sắp xếp phân tán hoặc khi cần sự ổn định (stable sort)?

A. Quick Sort

B. Heap Sort

C. Merge Sort

D. Selection Sort

7. Trong thuật toán sắp xếp vun đống (Heap Sort), cấu trúc dữ liệu Heap được sử dụng để làm gì?

A. Để lưu trữ các phần tử đã sắp xếp.

B. Để tìm phần tử nhỏ nhất một cách hiệu quả.

C. Để tìm phần tử lớn nhất (hoặc nhỏ nhất tùy loại heap) một cách hiệu quả.

D. Để đếm số lần so sánh.

8. Khi nào thuật toán sắp xếp nổi bọt (Bubble Sort) đạt hiệu quả tốt nhất?

A. Khi mảng đã được sắp xếp theo thứ tự ngược lại.

B. Khi mảng đã được sắp xếp theo thứ tự tăng dần.

C. Khi mảng có các phần tử ngẫu nhiên.

D. Khi mảng có số lượng phần tử lớn.

9. Trong thuật toán sắp xếp chọn (Selection Sort), ở mỗi lượt duyệt, thuật toán tìm phần tử gì và đặt nó vào đâu?

A. Phần tử lớn nhất và đặt nó vào đầu mảng.

B. Phần tử nhỏ nhất và đặt nó vào cuối mảng.

C. Phần tử nhỏ nhất và đặt nó vào vị trí đầu tiên của phần chưa được sắp xếp.

D. Phần tử lớn nhất và đặt nó vào vị trí cuối cùng của phần chưa được sắp xếp.

10. Ưu điểm chính của thuật toán sắp xếp chèn (Insertion Sort) là gì?

A. Nhanh chóng trên mọi loại dữ liệu.

B. Hiệu quả trên mảng nhỏ hoặc gần như đã sắp xếp, và là thuật toán tại chỗ.

C. Có độ phức tạp thời gian O(n log n) trong mọi trường hợp.

D. Dễ dàng song song hóa.

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

12. Độ phức tạp không gian (space complexity) của hầu hết các thuật toán sắp xếp tại chỗ (in-place sorting algorithms) như Bubble Sort, Insertion Sort, Selection Sort là bao nhiêu?

A. O(n)

B. O(n log n)

C. O(log n)

D. O(1)

13. Độ 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 nổi bọt (Bubble Sort) là bao nhiêu?

A. O(n^2)

B. O(n log n)

C. O(n)

D. O(log n)

14. Trong thuật toán sắp xếp nổi bọt (Bubble Sort), nếu một lượt duyệt không thực hiện bất kỳ hoán vị nào, điều đó có ý nghĩa gì?

A. Mảng đã được sắp xếp hoàn toàn.

B. Cần thực hiện thêm một lượt duyệt nữa.

C. Phần tử lớn nhất đã được đặt đúng vị trí.

D. Mảng có các phần tử trùng lặp.

15. Trong thuật toán Quick Sort, việc lựa chọn phần tử chốt (pivot) như thế nào ảnh hưởng đến hiệu suất của thuật toán?

A. Không ảnh hưởng, mọi lựa chọn đều cho hiệu suất như nhau.

B. Lựa chọn phần tử chốt ngẫu nhiên hoặc trung vị của ba phần tử giúp tránh trường hợp xấu nhất.

C. Phần tử chốt luôn phải là phần tử đầu tiên.

D. Phần tử chốt luôn phải là phần tử cuối cùng.

16. Thuật toán nào có thể sử dụng để sắp xếp các mảng lớn một cách hiệu quả với độ phức tạp thời gian trung bình là O(n log n)?

A. Bubble Sort

B. Insertion Sort

C. Merge Sort

D. Selection Sort

17. Độ phức tạp thời gian của thuật toán sắp xếp trộn (Merge Sort) có thể được cải thiện bằng cách nào?

A. Sử dụng phần tử chốt.

B. Sắp xếp mảng con trước khi trộn.

C. Tối ưu hóa quá trình trộn.

D. Độ phức tạp của Merge Sort không thể cải thiện đáng kể về mặt thời gian.

18. Trong thuật toán sắp xếp chèn (Insertion Sort), mục đích của việc chèn là gì?

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

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

C. Để đặt phần tử hiện tại vào đúng vị trí trong phần đã sắp xếp của mảng.

D. Để đếm số lần hoán vị đã thực hiện.

19. Độ 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(log n)

20. Thuật toán sắp xếp nào có độ phức tạp thời gian O(n log n) trong mọi trường hợp (tốt nhất, trung bình, xấu nhất)?

A. Quick Sort

B. Merge Sort

C. Heap Sort

D. Insertion Sort

21. Thuật toán sắp xếp nào phù hợp nhất cho các mảng nhỏ hoặc mảng gần như đã sắp xếp?

A. Merge Sort

B. Quick Sort

C. Insertion Sort

D. Heap Sort

22. Thuật toán nào thường có độ phức tạp thời gian không đổi O(1) cho thao tác tìm kiếm phần tử?

A. Bubble Sort

B. Insertion Sort

C. Selection Sort

D. Thuật toán sắp xếp không có thao tác tìm kiếm phần tử cố định O(1) độc lập với kích thước mảng.

23. Trong sắp xếp nổi bọt (Bubble Sort), nếu mảng có n phần tử, số lần so sánh tối đa trong lượt duyệt đầu tiên là bao nhiêu?

A. n

B. n-1

C. n/2

D. 1

24. Thuật toán sắp xếp nào dựa trên nguyên tắc chia để trị, chia mảng thành hai nửa, sắp xếp từng nửa rồi trộn chúng lại?

A. Bubble Sort

B. Insertion Sort

C. Merge Sort

D. Selection Sort

25. Độ phức tạp thời gian của thuật toán sắp xếp chèn (Insertion Sort) trên một mảng đã được sắp xếp là bao nhiêu?

A. O(n^2)

B. O(n log n)

C. O(n)

D. O(log n)