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

1. Thuật toán nào sử dụng chiến lược chia để trị hiệu quả?

A. Sắp xếp chèn (Insertion Sort)

B. Sắp xếp vun đống (Heap Sort)

C. Sắp xếp nhanh (Quick Sort) và Sắp xếp trộn (Merge Sort)

D. Sắp xếp nổi bọt (Bubble Sort)

2. Đâu là nhược điểm của thuật toán Sắp xếp nhanh (Quick Sort) trong trường hợp xấu nhất?

A. Độ phức tạp thời gian O(n log n).

B. Độ phức tạp thời gian O(n^2).

C. Độ phức tạp không gian O(log n).

D. Không thể sắp xếp các phần tử trùng lặp.

3. Nếu bạn có một danh sách rất lớn và cần sắp xếp nhanh chóng, thuật toán nào thường được ưu tiên?

A. Sắp xếp nổi bọt (Bubble Sort)

B. Sắp xếp chèn (Insertion Sort)

C. Sắp xếp nhanh (Quick Sort) hoặc Sắp xếp trộn (Merge Sort)

D. Sắp xếp chọn (Selection Sort)

4. Trong Sắp xếp nhanh (Quick Sort), việc chọn phần tử chốt (pivot) không tốt có thể dẫn đến điều gì?

A. Tăng hiệu quả sắp xếp.

B. Giảm độ phức tạp thời gian xuống O(n).

C. Tăng độ phức tạp thời gian lên O(n^2).

D. Làm cho thuật toán không ổn định.

5. Đâu là một ví dụ về thuật toán sắp xếp không ổn định (unstable)?

A. Sắp xếp chèn (Insertion Sort)

B. Sắp xếp trộn (Merge Sort)

C. Sắp xếp nhanh (Quick Sort)

D. Sắp xếp vun đống (Heap Sort)

6. Độ phức tạp thời gian của Sắp xếp trộn (Merge 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)

7. Trong Sắp xếp vun đống (Heap Sort), bước heapify có vai trò gì?

A. Xây dựng lại cấu trúc đống sau khi loại bỏ phần tử gốc.

B. Chia danh sách thành các phần tử nhỏ hơn.

C. So sánh các phần tử liền kề để đổi chỗ.

D. Tìm phần tử lớn nhất trong danh sách.

8. Sắp xếp chèn (Insertion Sort) phù hợp nhất với loại dữ liệu nào?

A. Danh sách rất lớn và hoàn toàn ngẫu nhiên.

B. Danh sách đã được sắp xếp gần như hoàn chỉnh hoặc danh sách nhỏ.

C. Danh sách có các giá trị lặp lại rất nhiều.

D. Danh sách cần sắp xếp theo nhiều tiêu chí cùng lúc.

9. Khi so sánh Sắp xếp nổi bọt (Bubble Sort) và Sắp xếp chọn (Selection Sort), điểm khác biệt chính về cách thức hoạt động là gì?

A. Bubble Sort tìm phần tử nhỏ nhất, Selection Sort đổi chỗ các cặp liền kề.

B. Bubble Sort đổi chỗ các cặp phần tử liền kề sai thứ tự, Selection Sort tìm phần tử nhỏ nhất và đưa về vị trí đúng.

C. Cả hai đều tìm phần tử nhỏ nhất.

D. Cả hai đều sử dụng chiến lược chia để trị.

10. Thuật toán nào có thể được cải tiến để đạt hiệu suất tốt hơn cho các danh sách gần như đã sắp xếp?

A. Sắp xếp vun đống (Heap Sort)

B. Sắp xếp nhanh (Quick Sort)

C. Sắp xếp nổi bọt (Bubble Sort) với cờ hiệu (flag) để kiểm tra đã sắp xếp hay chưa

D. Sắp xếp trộn (Merge Sort)

11. Khái niệm phân hoạch (partitioning) liên quan đến thuật toán nào?

A. Sắp xếp trộn (Merge Sort)

B. Sắp xếp chèn (Insertion Sort)

C. Sắp xếp nhanh (Quick Sort)

D. Sắp xếp nổi bọt (Bubble Sort)

12. Sắp xếp chọn (Selection Sort) hoạt động bằng cách nào?

A. Chia danh sách thành hai nửa, sắp xếp từng nửa rồi trộn lại.

B. Lặp đi lặp lại việc tìm phần tử nhỏ nhất và đưa nó về vị trí đầu.

C. Chèn từng phần tử vào vị trí đúng trong danh sách đã sắp xếp.

D. Đổi chỗ các cặp phần tử liền kề nếu chúng sai thứ tự.

13. Trong bài toán sắp xếp, mục tiêu chính của thuật toán là gì?

A. Giảm thiểu thời gian thực thi của chương trình.

B. Sắp xếp các phần tử của dữ liệu theo một thứ tự nhất định.

C. Tăng dung lượng bộ nhớ sử dụng.

D. Đảm bảo tính ổn định của thuật toán.

14. Sắp xếp trộn (Merge Sort) thực hiện việc trộn (merge) như thế nào?

A. So sánh phần tử đầu của hai danh sách con và chọn phần tử nhỏ hơn để đưa vào danh sách kết quả.

B. Chèn từng phần tử của danh sách thứ hai vào vị trí đúng trong danh sách thứ nhất.

C. Lấy phần tử lớn nhất từ cả hai danh sách.

D. Hoán đổi vị trí của các phần tử giữa hai danh sách.

15. Tại sao việc lựa chọn thuật toán sắp xếp phù hợp lại quan trọng trong thực tế?

A. Để làm cho chương trình trông phức tạp hơn.

B. Để tối ưu hóa hiệu suất xử lý và sử dụng tài nguyên.

C. Để bắt buộc người dùng phải học nhiều thuật toán.

D. Để đảm bảo tất cả các thuật toán đều có cùng độ phức tạp.

16. Thuật toán nào có thể được coi là ổn định (stable) trong sắp xếp?

A. Sắp xếp nhanh (Quick Sort)

B. Sắp xếp chọn (Selection Sort)

C. Sắp xếp trộn (Merge Sort) và Sắp xếp chèn (Insertion Sort)

D. Sắp xếp vun đống (Heap Sort)

17. Trong thuật toán Sắp xếp nhanh (Quick Sort), bước quan trọng nhất là gì?

A. Chọn một phần tử chốt (pivot) và phân hoạch danh sách.

B. Trộn hai danh sách con đã sắp xếp.

C. Tìm phần tử nhỏ nhất và đưa về đầu.

D. Đổi chỗ các phần tử liền kề sai thứ tự.

18. Ưu điểm chính của Sắp xếp vun đống (Heap Sort) là gì?

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

B. Độ phức tạp thời gian O(n log n) trong mọi trường hợp và yêu cầu bộ nhớ phụ O(1).

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

D. Hiệu quả cao nhất với danh sách nhỏ.

19. Nếu một thuật toán sắp xếp yêu cầu bộ nhớ phụ đáng kể (ví dụ: tạo mảng mới), nó được gọi là gì?

A. Sắp xếp tại chỗ (In-place sort)

B. Sắp xếp bổ sung (Out-of-place sort) hoặc Sắp xếp sử dụng bộ nhớ phụ

C. Sắp xếp ổn định (Stable sort)

D. Sắp xếp không ổn định (Unstable sort)

20. Khi thực hành bài toán sắp xếp, yếu tố nào cần được cân nhắc để đánh giá hiệu quả của một thuật toán?

A. Chỉ số lượng dòng code.

B. Độ phức tạp thời gian, độ phức tạp không gian và tính ổn định.

C. Khả năng hiển thị đẹp mắt của kết quả.

D. Thời gian cài đặt của lập trình viên.

21. Đâu là thuật toán sắp xếp phù hợp nếu bạn cần đảm bảo tính ổn định và có danh sách dữ liệu rất lớn?

A. Sắp xếp nhanh (Quick Sort)

B. Sắp xếp vun đống (Heap Sort)

C. Sắp xếp trộn (Merge Sort)

D. Sắp xếp chọn (Selection Sort)

22. Đâu là một thuộc tính quan trọng của thuật toán sắp xếp hiệu quả?

A. Độ phức tạp không gian cao.

B. Độ phức tạp thời gian thấp.

C. Khả năng chỉ sắp xếp một lần duy nhất.

D. Yêu cầu bộ nhớ cố định không đổi.

23. Độ phức tạp không gian (space complexity) của thuật toán Sắp xếp nhanh (Quick Sort) thường là bao nhiêu, khi cài đặt đệ quy?

A. O(1)

B. O(log n)

C. O(n)

D. O(n log n)

24. Thuật toán sắp xếp nào thường có độ phức tạp thời gian O(n^2) trong trường hợp xấu nhất và trung bình?

A. Sắp xếp nhanh (Quick Sort)

B. Sắp xếp trộn (Merge Sort)

C. Sắp xếp nổi bọt (Bubble Sort)

D. Sắp xếp vun đống (Heap Sort)

25. Sắp xếp vun đống (Heap Sort) sử dụng cấu trúc dữ liệu nào?

A. Hàng đợi (Queue)

B. Ngăn xếp (Stack)

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

D. Đống (Heap) - thường là Max Heap hoặc Min Heap