Trắc nghiệm Tin học 11 Bài 9: Lập trình sắp xếp nhanh - Cánh diều

Đáp án: C

Giải thích: Thuật toán sắp xếp nhanh (Quick Sort) sử dụng chiến lược chia để trị, nơi mà dãy số được phân đoạn thành các phần nhỏ hơn và sắp xếp từng phần một.

Đáp án: C

Giải thích: Pivot có thể là bất kỳ phần tử nào trong dãy, tuy nhiên, việc lựa chọn pivot có thể ảnh hưởng đến hiệu suất của thuật toán.

Đáp án: B

Giải thích: Trong lược đồ phân đoạn Lomuto, chỉ số i được duy trì để xác định vị trí phân tách, trong khi chỉ số j được sử dụng để duyệt dãy số.

Đáp án: C

Giải thích: Phân đoạn Hoare rà soát từ hai phía, trái và phải, cùng tiến dần vào giữa để tìm các phần tử vi phạm yêu cầu phân đoạn.

Đáp án: B

Giải thích: Để sắp xếp giảm dần, phép so sánh trong câu lệnh if a[j] <= pivot: cần được thay đổi thành ifa[j] >= pivot:.

Đáp án: B

Giải thích: Trong thuật toán phân đoạn Lomuto, giá trị của phần tử đứng cuối dãy được chọn làm pivot.

Đáp án: B

Giải thích: Sau khi một dãy số đã được phân đoạn, thuật toán sẽ tiếp tục phân đoạn và sắp xếp các đoạn con cho đến khi tất cả các đoạn đều chỉ còn không quá một phần tử.

Đáp án: B

Giải thích: Thuật toán Quick Sort có độ phức tạp thời gian trung bình là O(n log n), làm cho nó nhanh hơn nhiều thuật toán sắp xếp khác trong nhiều trường hợp.

Đáp án: C

Giải thích: Nếu dãy số đã được sắp xếp hoàn toàn và thuật toán chọn pivot là phần tử đầu tiên hoặc cuối cùng, độ phức tạp sẽ trở thành O(n²) trong trường hợp tồi tệ nhất.

Đáp án: C

Giải thích: Thuật toán sắp xếp nhanh không nhất thiết phải chọn phần tử giữa làm pivot; pivot có thể là bất kỳ phần tử nào trong dãy.

a) Sai. Thuật toán Lomuto không sử dụng phần tử đứng giữa làm pivot; nó chọn phần tử đứng cuối.

b) Sai. Việc chọn phần tử đứng đầu làm pivot không phải là đặc điểm của thuật toán Lomuto.

c) Đúng. Trong thuật toán Lomuto, giá trị của phần tử đứng cuối được chọn làm pivot, giúp phân đoạn dãy số.

d) Sai. Lựa chọn giá trị trung bình của tất cả các phần tử không phải là cách phân đoạn trong thuật toán Lomuto

a) Sai. Thuật toán Hoare kiểm tra dãy số từ cả hai phía (trái và phải), không chỉ từ trái sang phải.

b) Đúng. Ý tưởng chính của thuật toán phân đoạn Hoare là rà soát từ hai phía và đổi chỗ các phần tử khi phát hiện phần tử vi phạm yêu cầu phân đoạn.

c) Sai. Trong thuật toán Hoare, pivot có thể là phần tử đứng đầu, nhưng không giới hạn ở đó; nó có thể là bất kỳ phần tử nào.

d) Sai. Thuật toán Hoare vẫn có thể thực hiện phân đoạn ngay cả khi dãy số chỉ có hai phần tử.

Câu 1: Đáp án: Lược đồ phân đoạn trong thuật toán sắp xếp nhanh là quy trình chọn một phần tử làm pivot (giá trị chốt), sau đó chia dãy số thành hai đoạn: một đoạn chứa các phần tử nhỏ hơn hoặc bằng pivot và một đoạn chứa các phần tử lớn hơn hoặc bằng pivot. Việc phân đoạn này được lặp lại cho đến khi tất cả các đoạn con chỉ còn một phần tử.

Giải thích: Việc phân đoạn giúp giảm quy mô của bài toán sắp xếp bằng cách chia nó thành các bài toán nhỏ hơn, từ đó làm cho quá trình sắp xếp nhanh hơn và hiệu quả hơn. Lược đồ này cho phép sắp xếp trong nội bộ hai đoạn con sau mỗi lần phân đoạn.

Câu 2: Đáp án: Ý tưởng chính của thuật toán phân đoạn Lomuto là chọn pivot là phần tử đứng cuối của dãy số, sau đó sử dụng một chỉ số để duyệt qua dãy và hoán đổi các phần tử sao cho các phần tử nhỏ hơn hoặc bằng pivot nằm bên trái, trong khi các phần tử lớn hơn nằm bên phải.

Giải thích: Thuật toán này duy trì chỉ số phân tách và thực hiện hoán đổi khi phát hiện một phần tử nhỏ hơn hoặc bằng pivot. Cuối cùng, nó trả về vị trí phân tách để tiếp tục sắp xếp hai đoạn con. Điều này giúp tối ưu hóa quá trình sắp xếp, đảm bảo rằng pivot sẽ ở đúng vị trí sau mỗi lần phân đoạn.

Câu 3: Đáp án: Phân đoạn Hoare khác với phân đoạn Lomuto ở chỗ nó thực hiện kiểm tra từ cả hai phía (trái và phải) và hoán đổi các phần tử cho đến khi hai chỉ số gặp nhau, trong khi Lomuto chỉ kiểm tra từ một phía.

Giải thích: Phân đoạn Hoare sử dụng hai chỉ số để duyệt và hoán đổi các phần tử cho đến khi phát hiện một phần tử vi phạm yêu cầu phân đoạn. Điều này giúp nó thường có hiệu suất tốt hơn trong nhiều trường hợp, vì nó có thể giảm thiểu số lần hoán đổi cần thiết. Khi các chỉ số gặp nhau, thuật toán kết thúc và vị trí gặp nhau sẽ là vị trí phân tách cho dãy.