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

1. Đâu là một ví dụ về thuật toán sắp xếp không ổn định (unstable sort)?

A. Sắp xếp nhanh (Quick Sort) với cách chọn chốt không cẩn thận.

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

2. Thuật toán nào hiệu quả nhất trong việc sắp xếp các mảng lớn và có thể song song hóa tốt?

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

3. Khi sắp xếp một mảng bằng thuật toán sắp xếp chọn (Selection Sort), bước quan trọng nhất ở mỗi lần lặp là gì?

A. 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.

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

C. So sánh phần tử hiện tại với phần tử trước đó và hoán đổi nếu sai thứ tự.

D. Chia danh sách thành hai nửa và sắp xếp độc lập.

4. Thuật toán sắp xếp trộn (Merge Sort) dựa trên nguyên tắc cơ bản nào?

A. Chia để trị (Divide and Conquer)

B. Tham lam (Greedy Algorithm)

C. Quy hoạch động (Dynamic Programming)

D. Duyệt toàn bộ (Brute Force)

5. Trong thuật toán sắp xếp trộn (Merge Sort), giai đoạn trộn (merge) đóng vai trò gì?

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

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

C. Hoán đổi các cặp phần tử liền kề sai thứ tự.

D. Phân chia danh sách thành các phần tử riêng lẻ.

6. Thuật toán sắp xếp nhanh (Quick Sort) thường chọn phần tử nào làm chốt (pivot) để phân chia mảng?

A. Có thể là phần tử đầu, phần tử cuối, phần tử giữa, hoặc một phần tử ngẫu nhiên.

B. Luôn là phần tử nhỏ nhất trong mảng.

C. Luôn là phần tử lớn nhất trong mảng.

D. Luôn là phần tử ở giữa mảng.

7. Trong thuật toán sắp xếp nổi bọt (Bubble Sort), mục đích của việc duyệt qua danh sách nhiều lần là gì?

A. Để đảm bảo rằng phần tử lớn nhất di chuyển dần về vị trí cuối cùng sau mỗi lượt duyệt.

B. Để tìm phần tử nhỏ nhất và đặt nó ở đầu.

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

D. Để chia danh sách thành các phần nhỏ hơn.

8. Nếu ta có một danh sách rất lớn gồm các số nguyên và cần sắp xếp chúng một cách hiệu quả, thuật toán nào thường được ưu tiên?

A. Sắp xếp trộn (Merge Sort) hoặc Sắp xếp nhanh (Quick 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 chèn (Insertion Sort)

9. Thuật toán nào sử dụng nhiều phép hoán đổi nhất trong trường hợp mảng được sắp xếp theo thứ tự ngược lại?

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

D. Sắp xếp nhanh (Quick Sort) với chốt đầu tiên

10. Nếu ta cần sắp xếp một danh sách nhỏ (ví dụ: dưới 20 phần tử), thuật toán nào có thể hiệu quả hơn do chi phí cài đặt thấp?

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

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

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

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

11. Khi nói về độ phức tạp không gian (space complexity), thuật toán nào thường yêu cầu thêm không gian phụ đáng kể?

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

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

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

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

12. Thuật toán sắp xếp nào thường được mô tả là bay các phần tử lớn nhất về cuối danh sách qua các lần so sánh và hoán đổi liền kề?

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

13. Mục tiêu của thuật toán sắp xếp là gì?

A. Tổ chức lại các phần tử của một danh sách theo một thứ tự xác định (tăng dần hoặc giảm dần).

B. Giảm kích thước của danh sách.

C. Tìm kiếm một phần tử cụ thể trong danh sách.

D. Xóa bỏ các phần tử trùng lặp khỏi danh sách.

14. Độ 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 mọi trường hợp (tốt nhất, trung bình, xấu nhất)?

A. O(n^2)

B. O(n log n)

C. O(n)

D. O(log n)

15. Trong thuật toán sắp xếp nổi bọt (bubble sort), ở mỗi lượt duyệt qua danh sách, phần tử lớn nhất (hoặc nhỏ nhất tùy cách sắp xếp) sẽ được đưa về vị trí cuối cùng. Điều này diễn ra như thế nào?

A. So sánh và hoán đổi các cặp phần tử liền kề nếu chúng sai thứ tự, lặp lại cho đến khi không còn hoán đổi nào.

B. Tìm phần tử nhỏ nhất trong danh sách chưa sắp xếp và đặt nó vào vị trí đầu tiên.

C. Chia danh sách thành hai nửa, sắp xếp từng nửa rồi trộn lại với nhau.

D. Chọn một phần tử làm chốt, phân chia các phần tử còn lại thành hai nhóm: nhỏ hơn và lớn hơn chốt, sau đó sắp xếp đệ quy hai nhóm đó.

16. Trong sắp xếp chèn (Insertion Sort), khi đưa một phần tử từ phần chưa sắp xếp vào phần đã sắp xếp, ta cần thực hiện hành động gì?

A. Tìm vị trí đúng trong phần đã sắp xếp và dịch chuyển các phần tử lớn hơn sang phải để tạo chỗ trống.

B. Hoán đổi với phần tử đầu tiên của phần chưa sắp xếp.

C. So sánh với tất cả các phần tử còn lại và hoán đổi nếu sai.

D. Đưa phần tử đó về cuối danh sách.

17. Ưu điểm chính của thuật toán sắp xếp nhanh (Quick Sort) so với sắp xếp nổi bọt (Bubble Sort) là gì?

A. Nhanh hơn đáng kể trên tập dữ liệu lớn, với độ phức tạp trung bình O(n log n).

B. Dễ hiểu và cài đặt hơn.

C. Yêu cầu ít bộ nhớ hơn.

D. Hiệu quả như nhau trên mọi kích thước dữ liệu.

18. Thuật toán 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 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)

19. Thuật toán nào thực hiện ít thao tác so sánh nhất khi danh sách đã được sắp xếp theo thứ tự tăng dần?

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

20. Thuật toán nào phân chia mảng dựa trên một phần tử chốt và sau đó sắp xếp đệ quy hai phần mảng con?

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

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

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

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

21. Trong thuật toán sắp xếp chèn (Insertion Sort), khi phần tử cần chèn nhỏ hơn tất cả các phần tử đã sắp xếp, ta thực hiện hành động gì?

A. Dịch chuyển tất cả các phần tử đã sắp xếp sang phải một vị trí và đặt phần tử mới vào đầu.

B. Hoán đổi phần tử mới với phần tử cuối cùng của phần đã sắp xếp.

C. Đặt phần tử mới vào cuối phần đã sắp xếp.

D. Không cần thực hiện gì vì nó đã ở đúng vị trí.

22. Thuật toán nào có thể được xem là ổn định (stable) nếu nó duy trì thứ tự tương đối của các phần tử bằng nhau?

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

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

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

D. Tất cả các thuật toán trên

23. Trong thuật toán sắp xếp chèn (Insertion Sort), nếu một phần tử cần chèn lớn hơn tất cả các phần tử đã sắp xếp, nó sẽ được đặt ở đâu?

A. Ở cuối của phần đã sắp xếp.

B. Ở đầu của phần đã sắp xếp.

C. Ở vị trí ngẫu nhiên.

D. Cần phải hoán đổi với phần tử đầu tiên.

24. Đâu là đặc điểm chung của thuật toán sắp xếp chèn (Insertion Sort) và sắp xếp nổi bọt (Bubble Sort) về mặt hiệu suất trong trường hợp xấu nhất?

A. Cả hai đều có độ phức tạp thời gian O(n^2).

B. Cả hai đều có độ phức tạp thời gian O(n log n).

C. Cả hai đều có độ phức tạp thời gian O(n).

D. Cả hai đều có độ phức tạp thời gian O(log n).

25. Khi sử dụng thuật toán sắp xếp nhanh (Quick Sort) và chọn phần tử ở giữa làm chốt, điều gì có thể xảy ra nếu mảng đã được sắp xếp hoặc sắp xếp ngược?

A. Độ phức tạp có thể trở thành O(n^2) do phân chia không cân bằng.

B. Thuật toán sẽ hoạt động hiệu quả nhất với O(n log n).

C. Sẽ không ảnh hưởng đến hiệu suất của thuật toán.

D. Thuật toán sẽ chuyển sang sử dụng sắp xếp nổi bọt.