Trắc nghiệm Kết nối Tin học 11 KHMT bài 22 Thực hành bài toán sắp xếp

1. Đâu là đặc điểm chung của các thuật toán sắp xếp cơ bản?

A. Luôn có độ phức tạp thời gian O(n^2).

B. Cần thêm bộ nhớ phụ để lưu trữ.

C. Thường liên quan đến việc so sánh và hoán đổi các cặp phần tử.

D. Chỉ áp dụng được cho mảng đã sắp xếp một phần.

2. Thuật toán sắp xếp nào có thể được cải tiến để dừng sớm nếu mảng đã được sắp xếp?

A. Selection Sort

B. Bubble Sort

C. Heap Sort

D. Merge Sort

3. Độ phức tạp thời gian trung bình của thuật toán Quick Sort là bao nhiêu?

A. O(n)

B. O(n log n)

C. O(n^2)

D. O(log n)

4. Khái niệm sắp xếp ổn định (stable sort) nghĩa là gì?

A. Thuật toán luôn sắp xếp mảng trong thời gian O(n log n).

B. Thứ tự tương đối của các phần tử có khóa bằng nhau được giữ nguyên.

C. Thuật toán chỉ sử dụng bộ nhớ phụ O(1).

D. Thuật toán có thể sắp xếp cả số nguyên dương và số nguyên âm.

5. Trong bài toán sắp xếp, mục tiêu chính là gì?

A. Tìm kiếm phần tử trong mảng một cách hiệu quả.

B. Thực hiện các phép toán trên mảng.

C. Sắp xếp các phần tử của mảng theo một thứ tự nhất định.

D. Xóa bỏ các phần tử trùng lặp trong mảng.

6. Trong thuật toán sắp xếp chọn (Selection Sort), ở mỗi bước, thuật toán sẽ làm gì?

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

B. Tìm phần tử lớn nhất còn lại và hoán đổi nó với phần tử cuối cùng của phần chưa sắp xếp.

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

D. Tìm phần tử nhỏ nhất còn lại và hoán đổi nó với phần tử đầu tiên của phần chưa sắp xếp.

7. Khi một mảng có các phần tử lặp lại nhiều lần, thuật toán nào có thể không hiệu quả bằng các thuật toán khác có cơ chế xử lý phần tử trùng lặp tốt hơn?

A. Quick Sort

B. Merge Sort

C. Heap Sort

D. Bubble Sort (trong một số trường hợp)

8. Độ phức tạp thời gian của thuật toán sắp xếp nổi bọt (Bubble Sort) trong trường hợp xấu nhất là bao nhiêu?

A. O(n)

B. O(n log n)

C. O(n^2)

D. O(log n)

9. Trong bối cảnh thực hành, việc lựa chọn thuật toán sắp xếp nào phụ thuộc vào yếu tố nào?

A. Chỉ phụ thuộc vào kích thước của mảng.

B. Chỉ phụ thuộc vào ngôn ngữ lập trình sử dụng.

C. Phụ thuộc vào kích thước mảng, đặc điểm dữ liệu (ví dụ: đã sắp xếp một phần hay ngẫu nhiên), yêu cầu về tính ổn định và bộ nhớ sử dụng.

D. Chỉ phụ thuộc vào việc thuật toán có dễ cài đặt hay không.

10. Cấu trúc dữ liệu nào thường được sử dụng để triển khai thuật toán Heap Sort?

A. Danh sách liên kết (Linked List)

B. Cây nhị phân tìm kiếm (Binary Search Tree)

C. Heap (Đống)

D. Ngăn xếp (Stack)

11. Thuật toán sắp xếp nào có thể được xem là tự học (self-adjusting) vì nó điều chỉnh hiệu suất dựa trên mức độ sắp xếp ban đầu của dữ liệu?

A. Selection Sort

B. Bubble Sort (phiên bản cải tiến)

C. Heap Sort

D. Merge Sort

12. Nếu một bài toán yêu cầu sắp xếp một tập dữ liệu lớn mà tính ổn định là bắt buộc, thuật toán nào có thể là lựa chọn tốt?

A. Quick Sort

B. Heap Sort

C. Merge Sort

D. Selection Sort

13. Trong các thuật toán sắp xếp cơ bản, thuật toán nào có xu hướng thực hiện nhiều phép so sánh nhất trong trường hợp trung bình?

A. Insertion Sort

B. Selection Sort

C. Bubble Sort

D. Cả A, B, C đều tương đương.

14. Thuật toán nào sau đây KHÔNG phải là thuật toán sắp xếp ổn định?

A. Merge Sort

B. Insertion Sort

C. Bubble Sort

D. Selection Sort

15. Khi so sánh Insertion Sort và Selection Sort về số lần hoán đổi, Insertion Sort thường có lợi thế hơn trong trường hợp nào?

A. Mảng có kích thước rất lớn và ngẫu nhiên.

B. Mảng đã được sắp xếp một phần.

C. Mảng được sắp xếp theo thứ tự ngược lại.

D. Cả hai đều có số lần hoán đổi tương đương.

16. Trong lập trình, khi làm việc với mảng, việc sắp xếp giúp ích gì cho các thao tác khác?

A. Tăng tốc độ ghi dữ liệu vào mảng.

B. Giảm dung lượng bộ nhớ cần thiết cho mảng.

C. Hỗ trợ hiệu quả cho các thao tác tìm kiếm, ví dụ như tìm kiếm nhị phân.

D. Tự động loại bỏ các phần tử bị lỗi.

17. Độ phức tạp thời gian của thuật toán sắp xếp chọn (Selection Sort) trong mọi trường hợp là bao nhiêu?

A. O(n)

B. O(n log n)

C. O(n^2)

D. O(log n)

18. Thuật toán sắp xếp chèn (Insertion Sort) hiệu quả nhất khi nào?

A. Khi mảng có kích thước rất lớn và hoàn toàn ngẫu nhiên.

B. Khi mảng đã được sắp xếp một phần hoặc có kích thước nhỏ.

C. Khi yêu cầu độ phức tạp thời gian là O(n log n).

D. Khi cần sắp xếp các phần tử không theo thứ tự số.

19. Thuật toán Quick Sort thường sử dụng chiến lược nào để phân chia mảng?

A. Chia mảng thành hai nửa có kích thước bằng nhau.

B. Chọn một phần tử chốt (pivot) và phân hoạch mảng xung quanh nó.

C. Sắp xếp từng phần tử một cách độc lập.

D. Sử dụng một mảng tạm để lưu trữ.

20. Khi thực hiện sắp xếp Merge Sort, bước trộn (merge) có vai trò gì?

A. Chia mảng thành các phần nhỏ hơn.

B. Tìm phần tử nhỏ nhất trong toàn bộ mảng.

C. Kết hợp hai hoặc nhiều mảng con đã sắp xếp thành một mảng lớn hơn đã sắp xếp.

D. Xác định phần tử chốt.

21. Khi cần sắp xếp một mảng lớn với yêu cầu hiệu suất cao, thuật toán nào thường được ưu tiên?

A. Bubble Sort

B. Selection Sort

C. Quick Sort hoặc Merge Sort

D. Insertion Sort

22. Đâu là thuật toán sắp xếp thuộc nhóm chia để trị?

A. Bubble Sort

B. Insertion Sort

C. Merge Sort

D. Selection Sort

23. Thuật toán sắp xếp nổi bọt (Bubble Sort) hoạt động dựa trên nguyên tắc nào là chính?

A. Chia mảng thành hai nửa và sắp xếp đệ quy.

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

C. So sánh các phần tử kề nhau và hoán đổi nếu sai thứ tự.

D. Chèn từng phần tử vào vị trí đúng trong phần mảng đã sắp xếp.

24. Đâu là ưu điểm chính của thuật toán Heap Sort?

A. Có độ phức tạp thời gian O(n) trong mọi trường hợp.

B. Là thuật toán sắp xếp ổn định (stable sort).

C. Không yêu cầu bộ nhớ phụ ngoài (in-place sorting) và có độ phức tạp thời gian O(n log n).

D. Dễ dàng cài đặt và hiểu rõ.

25. Đâu là một ví dụ về sắp xếp tại chỗ (in-place sort)?

A. Merge Sort

B. Quick Sort

C. Heap Sort

D. Cả B và C