[Chân trời] Trắc nghiệm Tin học 7 bài 14 Thuật toán sắp xếp

1. Đâu là ưu điểm chính của sắp xếp nhanh (Quick Sort) so với sắp xếp vun đống (Heap Sort) trong nhiều trường hợp thực tế?

A. Quick Sort luôn ổn định.

B. Quick Sort thường có hằng số tốt hơn trong độ phức tạp O(n log n), dẫn đến tốc độ nhanh hơn trên thực tế.

C. Quick Sort yêu cầu ít bộ nhớ hơn.

D. Quick Sort dễ cài đặt hơn Heap Sort.

2. Trong sắp xếp nhanh (Quick Sort), bước phân hoạch (partitioning) có vai trò gì?

A. Trộn hai nửa danh sách đã sắp xếp.

B. Tìm phần tử nhỏ nhất để đưa về đầu.

C. Sắp xếp đệ quy các phần tử nhỏ hơn và lớn hơn phần tử chốt.

D. Đưa phần tử chốt về vị trí cuối cùng của nó và chia danh sách thành hai phần.

3. Khi so sánh sắp xếp nổi bọt (Bubble Sort) và sắp xếp chọn (Selection Sort), thuật toán nào thường thực hiện ít thao tác hoán đổi (swaps) hơn?

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

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

C. Cả hai thực hiện số hoán đổi như nhau.

D. Không thể xác định.

4. Trong các thuật toán sắp xếp cơ bản, thuật toán nào KHÔNG ổn định?

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

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

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

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

5. Khi sắp xếp một danh sách các chuỗi ký tự, thuật toán nào có thể hoạt động hiệu quả hơn nếu các chuỗi có cùng tiền tố?

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 Radix (Radix Sort)

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

6. Nếu bạn có một danh sách rất lớn gồm các số nguyên và bạn muốn sắp xếp nó một cách hiệu quả nhất, bạn sẽ ưu tiên thuật toán nào?

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

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

C. Sắp xếp nhanh (Quick Sort) hoặc Sắp xếp trộn (Merge Sort)

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

7. Đâu là ưu điểm chính của thuật toán sắp xếp chèn (Insertion Sort) so với sắp xếp nổi bọt (Bubble Sort) khi dữ liệu đã gần được sắp xếp?

A. Nó luôn có độ phức tạp O(n log n).

B. Nó thực hiện ít phép so sánh và dịch chuyển hơn trong trường hợp này.

C. Nó dễ dàng song song hóa hơn.

D. Nó yêu cầu ít bộ nhớ hơn.

8. Khi cần sắp xếp một danh sách đã gần như được sắp xếp, thuật toán nào thường cho hiệu quả tốt hơn so với các thuật toán khác như sắp xếp nổi bọ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 trộn (Merge Sort)

9. Thuật toán sắp xếp nào có độ phức tạp thời gian trung bình là O(n log n) và thường được coi là một trong những thuật toán sắp xếp hiệu quả nhất trong thực tế?

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

10. Thuật toán sắp xếp nào chia danh sách thành hai nửa, sắp xếp đệ quy từng nửa, rồi trộn hai nửa đã sắp xếp lại với nhau?

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

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

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

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

11. Thuật toán sắp xếp nào có nguyên tắc cơ bản là lặp đi lặp lại việc duyệt qua danh sách, so sánh các phần tử liền kề và đổi chỗ chúng nếu sai thứ tự?

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 nhanh (Quick Sort)

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

12. Đâu là độ phức tạp thời gian tệ nhất (worst-case time complexity) của thuật toán sắp xếp nổi bọt (Bubble Sort)?

A. O(n)

B. O(n log n)

C. O(n^2)

D. O(log n)

13. Trong thuật toán sắp xếp nhanh (Quick Sort), việc lựa chọn phần tử chốt (pivot) đóng vai trò quan trọng. Nếu phần tử chốt luôn là phần tử nhỏ nhất hoặc lớn nhất, điều gì có thể xảy ra với hiệu suất của thuật toán?

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

B. Hiệu suất sẽ giảm xuống O(n^2), tương tự sắp xếp nổi bọt

C. Thuật toán sẽ không chạy được

D. Hiệu suất sẽ không thay đổi

14. Đâu là độ phức tạp thời gian tốt nhất (best-case time complexity) của thuật toán sắp xếp chèn (Insertion Sort)?

A. O(n^2)

B. O(n log n)

C. O(n)

D. O(1)

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

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

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

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

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

16. Nếu bạn cần sắp xếp một danh sách mà các phần tử có thể có giá trị rất lớn hoặc rất nhỏ, và bạn muốn một thuật toán có hiệu suất ổn định, bạn có thể xem xét thuật toán nào?

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

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

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

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

17. Ưu điểm của thuật toán sắp xếp trộn (Merge Sort) là gì khi so sánh với sắp xếp nhanh (Quick Sort) về mặt sử dụng bộ nhớ?

A. Merge Sort yêu cầu ít bộ nhớ phụ hơn.

B. Merge Sort thường yêu cầu bộ nhớ phụ tỉ lệ với kích thước danh sách (O(n)).

C. Merge Sort không yêu cầu bộ nhớ phụ.

D. Bộ nhớ yêu cầu là như nhau giữa hai thuật toán.

18. Thuật toán nào thường được sử dụng để sắp xếp các số nguyên dựa trên giá trị của từng chữ số, từ chữ số ít quan trọng nhất đến chữ số quan trọng nhất (hoặc ngược lại)?

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

B. Sắp xếp Radix (Radix Sort)

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

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

19. Khi nói về độ ổn định của thuật toán sắp xếp, điều đó có nghĩa là gì?

A. Thuật toán luôn chạy nhanh bất kể kích thước dữ liệu.

B. Thuật toán giữ nguyên thứ tự tương đối của các phần tử có giá trị bằng nhau.

C. Thuật toán chỉ hoạt động với dữ liệu số.

D. Thuật toán yêu cầu thêm bộ nhớ phụ để hoạt động.

20. Trong thuật toán sắp xếp trộn (Merge Sort), bước trộn (merge) có vai trò gì?

A. Chia danh sách thành hai phần không bằng nhau.

B. Tìm phần tử chốt để phân hoạch.

C. Kết hợp hai danh sách con đã sắp xếp thành một danh sách lớn hơn đã sắp xếp.

D. Đưa phần tử nhỏ nhất về vị trí đầu.

21. Trong sắp xếp chèn (Insertion Sort), phần tử hiện tại được lấy ra và chèn vào đúng vị trí trong phần đã sắp xếp. Quá trình này có thể được mô tả như thế nào?

A. Tìm phần tử nhỏ nhất và đưa nó về đầu.

B. So sánh các phần tử liền kề và đổi chỗ nếu sai thứ tự.

C. Lặp lại việc tìm kiếm và di chuyển phần tử vào đúng chỗ trong phần đã sắp xếp.

D. Chia danh sách thành các phần nhỏ và trộn chúng lại.

22. Thuật toán nào có thể phân loại dữ liệu dựa trên các chữ số hoặc ký tự mà không cần so sánh trực tiếp các phần tử với nhau?

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

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

C. Sắp xếp Radix (Radix Sort)

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

23. Thuật toán sắp xếp nào thực hiện việc tìm phần tử nhỏ nhất trong phần chưa sắp xếp và đặt nó vào vị trí đầu tiên của phần chưa sắp xếp?

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

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

24. Nếu bạn có một danh sách rất ngắn, thuật toán nào có thể là lựa chọn tốt nhất do chi phí cài đặt thấp và hiệu quả chấp nhận được?

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) hoặc Sắp xếp chèn (Insertion Sort)

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

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

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

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

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

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