Trắc nghiệm Kết nối Tin học 7 bài 16 Thuật toán sắp xếp

1. Thuật toán sắp xếp nào ít bị ảnh hưởng bởi thứ tự ban đầu của dữ liệu, luôn có độ phức tạp thời gian là O(n log n)?

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

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

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

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

2. Độ 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?

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 thực hiện bằng cách lặp đi lặp lại việc tìm phần tử nhỏ nhất (hoặc lớn nhất) từ phần chưa sắp xếp và đặt nó vào đầu phần đã sắp xếp?

A. Sắp xếp trộn (Merge 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)

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

B. O(n log n)

C. O(log n)

D. O(n)

5. Khi sắp xếp một danh sách rất nhỏ, thuật toán nào có thể hiệu quả hơn do chi phí cài đặt thấp và ít phép so sánh?

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

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

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

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

6. Nếu bạn cần sắp xếp một mảng lớn gồm các số nguyên, và bạn biết rằng các số nguyên này nằm trong một phạm vi giá trị tương đối nhỏ, bạn có thể xem xét sử dụng thuật toán nào khác ngoài các thuật toán so sánh?

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

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

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

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

7. Độ phức tạp thời gian của Sắp xếp trộn (Merge 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^2)

B. O(n log n)

C. O(log n)

D. O(n)

8. Khi so sánh Sắp xếp nhanh (Quick Sort) và Sắp xếp trộn (Merge Sort), điểm khác biệt chính về tính ổn định là gì?

A. Quick Sort luôn ổn định, còn Merge Sort thì không.

B. Merge Sort luôn ổn định, còn Quick Sort thì không.

C. Cả hai đều không ổn định.

D. Cả hai đều ổn định.

9. Thuật toán sắp xếp nào đảm bảo tính ổn định (stable sort), nghĩa 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 trong danh sách ban đầu?

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

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

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

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

10. Trong thực tế, để sắp xếp một mảng lớn, thuật toán nào thường được ưu tiên vì hiệu suất cân bằng giữa tốc độ và độ phức tạp?

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 chèn (Insertion Sort)

11. Trong các thuật toán sắp xếp đã học, thuật toán nào yêu cầu không gian bộ nhớ phụ (extra space) nhiều nhất để hoạt động?

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 trộn (Merge Sort)

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

12. Khi nói về độ phức tạp không gian của Sắp xếp nhanh (Quick Sort) không tại chỗ, nó thường là bao nhiêu?

A. O(1)

B. O(n)

C. O(log n)

D. O(n^2)

13. Khi một danh sách đã được sắp xếp hoặc gần được sắp xếp, thuật toán nào sau đây có thể hoạt động hiệu quả hơn so với trường hợp ngẫu nhiên?

A. Sắp xếp vun đống (Heap 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 chọn (Selection Sort)

14. Thuật toán sắp xếp nào có thể được xem là một dạng tối ưu hóa của Sắp xếp nổi bọt, khi nó chỉ hoán đổi các phần tử liền kề nếu chúng sai thứ tự?

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

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

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

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

15. Trong các thuật toán sắp xếp sau đây, thuật toán nào thường được coi là đơn giản nhất để hiểu và cài đặt, mặc dù hiệu quả không cao với tập dữ liệu lớn?

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)

16. Thuật toán sắp xếp nào có thể thực hiện sắp xếp tại chỗ (in-place sort), tức là không yêu cầu không gian bộ nhớ phụ đáng kể?

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. Cả B và C

17. Thuật toán sắp xếp nào hoạt động bằng cách chia danh sách thành hai nửa, sắp xếp từng nửa rồi trộn chúng lại với nhau?

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

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

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

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

18. Khi sắp xếp một mảng với các phần tử có giá trị rất gần nhau, thuật toán nào có thể gặp khó khăn trong việc phân hoạch hiệu quả, dẫn đến hiệu suất giảm sút?

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

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

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

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

19. Thuật toán sắp xếp nào sử dụng cấu trúc dữ liệu vun đống (heap) để thực hiện việc sắp xếp?

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

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

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

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

20. Thuật toán sắp xếp nào có xu hướng chọn một phần tử làm chốt (pivot) và phân hoạch danh sách dựa trên phần tử đó?

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

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

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

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

21. Thuật toán sắp xếp nào có độ phức tạp thời gian O(n^2) trong mọi trường hợp?

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

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

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

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

22. Thuật toán sắp xếp nào thường được sử dụng làm thuật toán con trong các thuật toán sắp xếp phức tạp hơn như Timsort?

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

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

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

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

23. Trong sắp xếp chèn (Insertion Sort), mỗi phần tử được lấy từ tập hợp chưa sắp xếp và được đặt vào vị trí đúng trong tập hợp con đã sắp xếp như thế nào?

A. Bằng cách hoán đổi với phần tử nhỏ nhất trong tập đã sắp xếp.

B. Bằng cách duyệt ngược lại tập đã sắp xếp và chèn vào đúng chỗ.

C. Bằng cách so sánh với phần tử đầu tiên của tập đã sắp xếp.

D. Bằng cách thêm vào cuối tập đã sắp xếp.

24. Trong trường hợp xấu nhất, độ phức tạp thời gian của Sắp xếp nhanh (Quick Sort) có thể là bao nhiêu?

A. O(n log n)

B. O(n)

C. O(n^2)

D. O(log n)

25. Thuật toán sắp xếp nào hoạt động dựa trên nguyên lý phân chia mảng thành các chuyển động (runs) đã sắp xếp và sau đó trộn các chuyển động này lại?

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

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

C. Timsort

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