Trắc nghiệm Tin học 7 kết nối bài 16 Thuật toán sắp xếp

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

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 nổi bọt (Bubble Sort).

2. Khi một thuật toán sắp xếp được gọi là không gian bổ sung (in-place), điều đó có ý nghĩa gì?

A. Nó không yêu cầu bất kỳ bộ nhớ bổ sung nào ngoài mảng dữ liệu ban đầu.

B. Nó chỉ yêu cầu một lượng nhỏ bộ nhớ bổ sung, thường là hằng số hoặc logarit.

C. Nó sử dụng một mảng phụ để lưu trữ kết quả.

D. Nó yêu cầu bộ nhớ gấp đôi kích thước của mảng ban đầu.

3. Thuật toán Sắp xếp trộn (Merge Sort) sử dụng nguyên tắc nào là chính?

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

B. So sánh các phần tử liền kề và đổi chỗ.

C. Chia mảng thành hai nửa, sắp xếp từng nửa rồi trộn lại để có mảng sắp xếp hoàn chỉnh.

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

4. Đâu là một thuật toán sắp xếp dựa trên việc đếm số lần xuất hiện của mỗi giá trị?

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

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

C. Sắp xếp đếm (Counting Sort).

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

5. Độ phức tạp thời gian của thuật toán Sắp xếp vun đống (Heap Sort) là bao nhiêu?

A. O(n).

B. O(n log n).

C. O(n^2).

D. O(log n).

6. Sắp xếp chọn (Selection Sort) hoạt động theo nguyên tắc nào?

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

B. Tìm phần tử nhỏ nhất (hoặc lớn nhất) trong phần chưa sắp xếp và đưa nó về vị trí đầu của phần chưa sắp xếp đó.

C. So sánh lần lượt các phần tử liền kề và đổi chỗ nếu sai thứ tự.

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

7. So sánh Sắp xếp chèn (Insertion Sort) và Sắp xếp chọn (Selection Sort) về số lượng hoán đổi:

A. Insertion Sort luôn có ít hoán đổi hơn Selection Sort.

B. Selection Sort luôn có ít hoán đổi hơn Insertion Sort.

C. Cả hai thuật toán có số lượng hoán đổi tương đương nhau.

D. Số lượng hoán đổi phụ thuộc vào việc lựa chọn pivot.

8. Khi sử dụng thuật toán sắp xếp nổi bọt trên một mảng đã được sắp xếp, hiệu suất sẽ như thế nào?

A. Hiệu suất tốt nhất, chỉ cần một lượt duyệt.

B. Hiệu suất kém nhất, cần nhiều lượt duyệt nhất.

C. Hiệu suất trung bình, vẫn cần nhiều lượt duyệt.

D. Hiệu suất không thay đổi so với mảng chưa sắp xếp.

9. Khi một thuật toán sắp xếp được mô tả là ổn định (stable), điều đó có nghĩa là gì?

A. Thuật toán luôn cho ra kết quả sắp xếp đúng.

B. Thuật toán không bị ảnh hưởng bởi các phần tử trùng lặp.

C. Thứ tự tương đối của các phần tử có giá trị bằng nhau được bảo toàn.

D. Thuật toán có thể dừng sớm nếu phát hiện mảng đã sắp xếp.

10. Độ phức tạp thời gian của thuật toán Sắp xếp trộn (Merge Sort) là bao nhiêu?

A. O(n).

B. O(n log n).

C. O(n^2).

D. O(log n).

11. Khi so sánh độ phức tạp thời gian của các thuật toán sắp xếp, O(n log n) được xem là:

A. Rất kém hiệu quả, chỉ phù hợp với mảng nhỏ.

B. Hiệu quả tốt, phù hợp cho hầu hết các trường hợp, đặc biệt với dữ liệu lớn.

C. Chỉ hiệu quả khi dữ liệu đã được sắp xếp một phần.

D. Hiệu quả nhất khi dữ liệu hoàn toàn ngẫu nhiên.

12. Thuật toán nào có thể sắp xếp dữ liệu dựa trên các chữ số của số?

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

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

C. Sắp xếp theo cơ số (Radix Sort).

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

13. Thuật toán nào thường được sử dụng để sắp xếp các mảng rất lớn với hiệu suất cao trên máy tính hiện đại?

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

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

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

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

14. Thuật toán chia để trị (Divide and Conquer) là gì?

A. Một thuật toán chỉ dùng để tìm kiếm.

B. Một phương pháp giải quyết vấn đề bằng cách chia nhỏ vấn đề thành các bài toán con tương tự, giải quyết các bài toán con đó rồi kết hợp kết quả.

C. Một thuật toán chỉ dành cho các bài toán có dữ liệu lớn.

D. Một thuật toán yêu cầu nhiều bộ nhớ nhất.

15. Một trong những yêu cầu cơ bản đối với thuật toán sắp xếp là gì?

A. Phải có khả năng tự động học hỏi từ dữ liệu.

B. Phải đảm bảo tính đúng đắn, tức là cho ra kết quả đúng với thứ tự yêu cầu.

C. Phải có giao diện đồ họa thân thiện với người dùng.

D. Phải có khả năng chạy trên mọi hệ điều hành mà không cần cài đặt.

16. Thuật toán sắp xếp nổi bọt hoạt động dựa trên nguyên tắc nào?

A. Chia để trị, chia mảng thành các phần nhỏ hơn.

B. So sánh và đổi chỗ các cặp phần tử liền kề nếu chúng sai thứ tự.

C. Tìm phần tử nhỏ nhất và đưa nó về vị trí đầu tiên.

D. Xây dựng một cấu trúc dữ liệu dạng cây để sắp xếp.

17. Điểm khác biệt chính giữa Sắp xếp nhanh (Quick Sort) và Sắp xếp trộn (Merge Sort) về cách xử lý là gì?

A. Quick Sort sắp xếp trước rồi mới chia, Merge Sort chia trước rồi mới sắp xếp.

B. Quick Sort chọn một pivot để phân chia mảng, còn Merge Sort chia mảng thành hai nửa bằng nhau.

C. Quick Sort luôn ổn định, còn Merge Sort không ổn định.

D. Quick Sort yêu cầu nhiều bộ nhớ hơn Merge Sort.

18. Trong tin học, thuật toán sắp xếp dùng để làm gì?

A. Để tìm kiếm thông tin nhanh chóng trong một tập hợp dữ liệu.

B. Để tổ chức lại một tập hợp dữ liệu theo một thứ tự nhất định.

C. Để mã hóa dữ liệu nhằm bảo mật thông tin.

D. Để thực hiện các phép tính toán học phức tạp.

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

A. Các mảng rất lớn và hoàn toàn ngẫu nhiên.

B. Các mảng nhỏ hoặc gần như đã được sắp xếp.

C. Các mảng có giá trị trùng lặp rất nhiều.

D. Các mảng chỉ chứa các số âm.

20. Thuật toán sắp xếp nào thường được coi là đơn giản nhất để hiểu và cài đặt ban đầu?

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).

21. Thuật toán sắp xếp nào có độ phức tạp thời gian trung bình là O(n log n)?

A. Sắp xếp chọn (Selection 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).

22. Thuật toán Sắp xếp đếm (Counting Sort) hiệu quả nhất khi nào?

A. Khi phạm vi giá trị của các phần tử rất lớn.

B. Khi phạm vi giá trị của các phần tử là hữu hạn và không quá lớn.

C. Khi mảng có kích thước rất nhỏ.

D. Khi dữ liệu là số thực.

23. Trong thuật toán Quick Sort, việc lựa chọn pivot có ảnh hưởng như thế nào đến hiệu suất?

A. Việc lựa chọn pivot không ảnh hưởng đến hiệu suất.

B. Lựa chọn pivot tốt (gần trung vị) giúp đạt hiệu suất O(n log n), pivot xấu (phần tử nhỏ nhất/lớn nhất) dẫn đến O(n^2).

C. Pivot chỉ ảnh hưởng đến tính ổn định của thuật toán.

D. Pivot chỉ ảnh hưởng đến số lượng bước nhớ.

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

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

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

C. Đống (Heap).

D. Hàng đợi ưu tiên (Priority Queue).

25. Độ 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 (tốt nhất, trung bình, xấu nhất) là bao nhiêu?

A. O(n).

B. O(n log n).

C. O(n^2).

D. O(log n).