15 câu Trắc nghiệm Tin học 11 Cánh diều Bài 9: Lập trình thuật toán sắp xếp nhanh có đáp án
15 câu hỏi
PHẦN I. Câu trắc nghiệm nhiều phương án lựa chọn. Thí sinh trả lời từ câu 1 đến câu 10. Mỗi câu hỏi thí sinh chỉ lựa chọn một phương án.
Thuật toán sắp xếp nhanh thuộc loại thuật toán nào?
Tìm kiếm tuyến tính
Tìm kiếm nhị phân
Chia để trị
Đệ quy
Đá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.
Trong thuật toán sắp xếp nhanh, giá trị nào được chọn làm pivot?
Phần tử nhỏ nhất trong dãy
Phần tử lớn nhất trong dãy
Bất kỳ phần tử nào trong dãy
Phần tử đứng ở giữa
Đá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.
Lược đồ phân đoạn Lomuto sử dụng chỉ số nào để thực hiện việc phân đoạn?
Chỉ số j
Chỉ số i
Chỉ số k
Chỉ số p
Đá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ố.
Lượt kiểm tra trong phân đoạn Hoare bắt đầu từ đâu?
Bắt đầu từ vị trí trái và di chuyển sang phải
Bắt đầu từ vị trí phải và di chuyển sang trái
Cả hai đầu dãy số cùng tiến vào giữa
Từ giữa 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.
Để sắp xếp một danh sách theo thứ tự giảm dần trong thuật toán Quick Sort, điều gì cần được thay đổi?
Thay đổi giá trị pivot
Thay đổi phép so sánh trong câu lệnh if
Thay đổi cấu trúc của thuật toán
Thay đổi biến đầu vào
Đá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 if a[j] >= pivot:.
Trong thuật toán phân đoạn Lomuto, giá trị nào được sử dụng làm pivot?
Phần tử đầu tiên
Phần tử cuối cùng
Phần tử giữa
Phần tử bất kỳ
Đá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.
Điều gì xảy ra sau khi một dãy số đã được phân đoạn?
Dãy số sẽ được sắp xếp ngay lập tức.
Sẽ tiến hành phân đoạn lần nữa cho mỗi đoạn con.
Chỉ cần sắp xếp một lần duy nhất.
Dãy số sẽ không thay đổi.
Đá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ử.
Trong thuật toán Quick Sort, thuật toán được gọi là "nhanh" vì lý do gì?
Nó sử dụng ít bộ nhớ.
Nó có độ phức tạp thời gian trung bình thấp.
Nó không cần phân đoạn.
Nó chỉ cần một lần duy nhất để sắp xếp.
Đá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.
Trong quá trình thực hiện sắp xếp nhanh, nếu một dãy số đã được sắp xếp hoàn toàn, thuật toán sẽ có độ phức tạp là gì?
O(n)
O(n log n)
O(n²)
O(log n)
Đá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.
Đặc điểm nào sau đây không đúng với thuật toán sắp xếp nhanh?
Nó có thể không sử dụng thêm bộ nhớ.
Nó có thể xử lý cả số âm và số dương.
Nó luôn chọn phần tử giữa làm pivot.
Nó có thể thực hiện sắp xếp trên các danh sách lớn.
Đá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.
Lược đồ phân đoạn nào được sử dụng trong thuật toán sắp xếp nhanh Lomuto?
a) Lấy giá trị của phần tử đứng giữa làm pivot.
b) Lấy giá trị của phần tử đứng đầu làm pivot.
c) Lấy giá trị của phần tử đứng cuối làm pivot.
d) Lấy giá trị trung bình của tất cả các phần tử làm pivot.
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
Ý tưởng chính của thuật toán phân đoạn Hoare là gì?
a) Duyệt dãy số từ trái sang phải và phân tách theo một chiều.
b) Đổi chỗ hai phần tử khi phát hiện phần tử vi phạm yêu cầu phân đoạn từ cả hai phía.
c) Luôn chọn phần tử đứng đầu dãy làm pivot để thực hiện phân đoạn.
d) Chỉ thực hiện phân đoạn khi dãy số có hơn hai phần tử.
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ử.
Lược đồ phân đoạn trong thuật toán sắp xếp nhanh là gì?
Đá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.
Ý tưởng chính của thuật toán phân đoạn Lomuto là gì?
Đá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.
Phân đoạn Hoare khác với phân đoạn Lomuto như thế nào?
Đá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.
