Trắc nghiệm đúng sai Khoa học máy tính 11 cánh diều Bài 9: Lập trình thuật toán sắp xếp nhanh

CHỦ ĐỀ F^CS. GIẢI QUYẾT VẤN ĐỀ VỚI SỰ TRỢ GIÚP CỦA MÁY TÍNH

BÀI 9: LẬP TRÌNH THUẬT TOÁN SẮP XẾP NHANH

Câu 1: Cho đoạn thông tin:

Thuật toán sắp xếp nhanh (Quick Sort) là một trong những thuật toán sắp xếp hiệu quả nhất, sử dụng phương pháp chia để trị. Thuật toán này hoạt động bằng cách chọn một phần tử làm "pivot", sau đó phân đoạn danh sách thành hai phần: các phần tử nhỏ hơn hoặc bằng pivot và các phần tử lớn hơn pivot. Quá trình này được lặp lại cho các phân đoạn cho đến khi danh sách được sắp xếp hoàn toàn.

Nhận định nào đúng? Nhận định nào sai?

a) Sắp xếp nhanh chỉ hoạt động hiệu quả với danh sách đã được sắp xếp trước.
b) Phương pháp chia để trị là nguyên tắc chính của thuật toán sắp xếp nhanh.
c) Thuật toán sắp xếp nhanh có thể sử dụng nhiều cách để chọn pivot.
d) Sắp xếp nhanh là thuật toán sắp xếp chậm nhất trong các thuật toán sắp xếp.

Đáp án:

- B, C đúng

- A, D sai

Câu 2:Cho đoạn thông tin:

Trong thuật toán sắp xếp nhanh áp dụng phân đoạn Lomuto, phần tử đầu tiên của mảng thường được chọn làm pivot. Sau khi phân đoạn, tất cả các phần tử nhỏ hơn pivot sẽ nằm bên trái, trong khi các phần tử lớn hơn sẽ nằm bên phải. Phân đoạn này được thực hiện bằng cách sử dụng hai chỉ số để so sánh và hoán đổi các phần tử.

Nhận định nào đúng? Nhận định nào sai?

a) Chỉ có phần tử đầu tiên mới có thể được chọn làm pivot trong phân đoạn Lomuto.
b) Phân đoạn Lomuto có thể dẫn đến việc tạo ra các phân đoạn không đều.
c) Thuật toán sắp xếp nhanh với phân đoạn Lomuto luôn có độ phức tạp O(n log n).
d) Phân đoạn Lomuto yêu cầu nhiều phép hoán đổi hơn so với phân đoạn Hoare.

Câu 3:Cho đoạn thông tin:

Thuật toán sắp xếp nhanh áp dụng phân đoạn Hoare sử dụng một phần tử làm pivot và phân đoạn danh sách thành hai phần mà không cần hoán đổi ngay lập tức. Thay vào đó, nó di chuyển các chỉ số từ hai đầu về giữa cho đến khi tìm thấy các phần tử không đúng vị trí và sau đó thực hiện hoán đổi.

Nhận định nào đúng? Nhận định nào sai?

a) Phân đoạn Hoare thường nhanh hơn phân đoạn Lomuto trong thực tế.
b) Trong phân đoạn Hoare, việc chọn pivot không quan trọng.
c) Phân đoạn Hoare làm cho phân đoạn được đồng đều hơn. 
d) Phân đoạn Hoare không cần hoán đổi phần tử ngay lập tức.

Câu 4:Cho đoạn thông tin:

 Một trong những ưu điểm của thuật toán sắp xếp nhanh là khả năng xử lý các mảng lớn với tốc độ nhanh hơn so với các thuật toán sắp xếp khác như sắp xếp chèn hoặc sắp xếp nổi bọt. Tuy nhiên, trong trường hợp xấu nhất, độ phức tạp của thuật toán có thể lên đến O(n^2).

Nhận định nào đúng? Nhận định nào sai?

a) Sắp xếp nhanh luôn có độ phức tạp O(n log n).
b) Sắp xếp nhanh có thể xử lý mảng lớn hiệu quả hơn các thuật toán khác.
c) Độ phức tạp trong trường hợp xấu nhất của sắp xếp nhanh là O(n^2).
d) Sắp xếp nhanh không phù hợp cho các mảng nhỏ.

Câu 5:Cho đoạn thông tin:

Để tối ưu hóa thuật toán sắp xếp nhanh, người ta thường sử dụng một kỹ thuật gọi là "sắp xếp chèn" cho các phân đoạn nhỏ, vì sắp xếp chèn có hiệu suất tốt hơn trên các mảng nhỏ.

Nhận định nào đúng? Nhận định nào sai?

a) Sắp xếp chèn không thể được sử dụng trong thuật toán sắp xếp nhanh.
b) Kết hợp sắp xếp nhanh với sắp xếp chèn có thể cải thiện hiệu suất.
c) Sắp xếp nhanh không cần tối ưu hóa cho các phân đoạn nhỏ.
d) Sử dụng sắp xếp chèn cho các phân đoạn nhỏ là một kỹ thuật tối ưu hóa phổ biến.

--------------- Còn tiếp ---------------