Trắc nghiệm đúng sai Khoa học máy tính 11 kết nối Bài 21: Các thuật toán sắp xếp đơn giản

CHỦ ĐỀ 6. KĨ THUẬT LẬP TRÌNH

BÀI 21: CÁC THUẬT TOÁN SẮP XẾP ĐƠN GIẢN

Câu 1: Cho đoạn thông tin:
Trong lập trình Python, thuật toán sắp xếp chèn (Insertion Sort) là một trong những thuật toán cơ bản và dễ hiểu. Thuật toán này hoạt động bằng cách chia danh sách thành hai phần: phần đã sắp xếp và phần chưa sắp xếp. Mỗi phần tử từ phần chưa sắp xếp sẽ được chèn vào đúng vị trí trong phần đã sắp xếp. 

Hãy đánh giá tính đúng sai của các nhận định sau: 

a) Thuật toán sắp xếp chèn chỉ thích hợp cho danh sách có kích thước lớn.
b) Thuật toán sắp xếp chèn có độ phức tạp thời gian trung bình là O(n^2).
c) Thuật toán sắp xếp chèn hoạt động bằng cách chia danh sách thành hai phần.
d) Thuật toán sắp xếp chèn không thể sử dụng cho danh sách đã sắp xếp.

Đáp án:

- B, C đúng

- A, D sai

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

Thuật toán sắp xếp chọn (Selection Sort) là một phương pháp sắp xếp đơn giản, trong đó danh sách được chia thành hai phần: phần đã sắp xếp và phần chưa sắp xếp. Mỗi lần, thuật toán 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.

Hãy đánh giá tính đúng sai của các nhận định sau: 

a) Thuật toán sắp xếp chọn thực hiện nhiều phép hoán đổi trong mỗi lần lặp.
b) Độ phức tạp thời gian của thuật toán sắp xếp chọn là O(n log n).
c) Thuật toán sắp xếp chọn có thể hoạt động hiệu quả với danh sách nhỏ.
d) Thuật toán sắp xếp chọn không cần sử dụng thêm bộ nhớ.

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

Thuật toán sắp xếp nổi bọt (Bubble Sort) là một trong những thuật toán sắp xếp đơn giản nhất. Nó hoạt động bằng cách so sánh từng cặp phần tử gần kề và hoán đổi chúng nếu chúng không theo thứ tự. Độ phức tạp thời gian trong trường hợp tệ nhất là O(n^2).  Quá trình này được lặp lại cho đến khi không còn sự hoán đổi nào cần thiết. 

Hãy đánh giá tính đúng sai của các nhận định sau: 

1. Thuật toán sắp xếp nổi bọt có thể sắp xếp một danh sách mà không cần hoán đổi.
   b) Độ phức tạp thời gian của thuật toán sắp xếp nổi bọt trong trường hợp tệ nhất là O(n^2).
   c) Thuật toán sắp xếp nổi bọt là một thuật toán không ổn định.
   d) Thuật toán sắp xếp nổi bọt là dễ hiểu và dễ triển khai nhất trong các thuật toán. 

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

Các thuật toán sắp xếp như sắp xếp chèn, sắp xếp chọn và sắp xếp nổi bọt đều có ưu điểm và nhược điểm riêng. Sắp xếp chèn thường hiệu quả hơn với danh sách nhỏ, trong khi sắp xếp nổi bọt dễ triển khai nhưng chậm hơn. 

Hãy đánh giá tính đúng sai của các nhận định sau: 

a) Sắp xếp chèn luôn nhanh hơn sắp xếp nổi bọt.
b) Sắp xếp chọn là thuật toán có độ phức tạp thời gian tốt nhất trong tất cả các thuật toán sắp xếp đơn giản.
c) Sắp xếp nổi bọt dễ triển khai hơn nhưng không hiệu quả cho danh sách lớn.
d) Các thuật toán sắp xếp khác nhau sẽ có độ phức tạp thời gian thời gian khác nhau. 

Câu 5: Cho đoạn thông tin:
Khi sử dụng các thuật toán sắp xếp trong Python, người lập trình cần cân nhắc đến độ phức tạp thời gian và không gian của từng thuật toán. Sắp xếp chèn và sắp xếp chọn đều có độ phức tạp thời gian O(n^2), nhưng sắp xếp chèn thường có hiệu suất tốt hơn trong thực tế. 

Hãy đánh giá tính đúng sai của các nhận định sau: 

a) Sắp xếp chèn có độ phức tạp thời gian O(n^2) nhưng không phải tất cả các trường hợp.
b) Sắp xếp chọn có thể được cải thiện bằng cách sử dụng bộ nhớ bổ sung.
c) Sắp xếp nổi bọt không thích hợp cho danh sách đã sắp xếp.
d) Sắp xếp chèn có thể hoạt động tốt hơn trên danh sách gần như đã sắp xếp.

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