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

1. Thuật toán sắp xếp nào có thể được mô tả là tìm phần tử nhỏ nhất trong phần chưa sắp xếp và đưa nó về đầu danh sách?

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 trộn (Merge Sort)

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

2. Khi sử dụng thuật toán sắp xếp chèn (Insertion Sort) để sắp xếp danh sách [3, 6, 1, 8, 4], sau khi chèn phần tử 1 vào đúng vị trí, danh sách sẽ có dạng nào?

A. [1, 3, 6, 8, 4]

B. [1, 6, 3, 8, 4]

C. [3, 1, 6, 8, 4]

D. [1, 4, 3, 6, 8]

3. Thuật toán sắp xếp nào thường có hiệu suất kém nhất trong trường hợp dữ liệu đã được sắp xếp sẵn?

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

B. Sắp xếp nhanh (Quick Sort) với pivot là phần tử đầu tiên

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

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

4. Trong sắp xếp nhanh (Quick Sort), vai trò của pivot (chốt) là gì?

A. Là phần tử lớn nhất trong danh sách.

B. Là phần tử nhỏ nhất trong danh sách.

C. Là phần tử dùng để phân chia danh sách thành hai phần nhỏ hơn.

D. Là phần tử được sử dụng để đếm số lần hoán đổi.

5. Trong sắp xếp nổi bọt (Bubble Sort), để sắp xếp danh sách theo thứ tự giảm dần, ta cần thay đổi điều kiện so sánh như thế nào?

A. So sánh phần tử hiện tại với phần tử tiếp theo, nếu phần tử hiện tại < phần tử tiếp theo thì đổi chỗ.

B. So sánh phần tử hiện tại với phần tử tiếp theo, nếu phần tử hiện tại > phần tử tiếp theo thì đổi chỗ.

C. So sánh phần tử hiện tại với phần tử trước đó, nếu phần tử hiện tại > phần tử trước đó thì đổi chỗ.

D. Không thể sắp xếp giảm dần bằng Bubble Sort.

6. Đặc điểm nào sau đây mô tả đúng nhất về sắp xếp ổn định (stable sort)?

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

B. Không yêu cầu bộ nhớ phụ ngoài.

C. Giữ nguyên thứ tự tương đối của các phần tử có giá trị bằng nhau.

D. Chỉ hoạt động trên các mảng số nguyên.

7. Nếu ta cần sắp xếp một danh sách các chuỗi ký tự theo thứ tự từ điển, thuật toán nào dưới đây có thể được áp dụng hiệu quả?

A. Chỉ có thể dùng thuật toán sắp xếp chuỗi chuyên biệt.

B. Bubble Sort, Insertion Sort, Merge Sort, Quick Sort đều có thể áp dụng.

C. Chỉ có thể dùng thuật toán sắp xếpRadix Sort.

D. Chỉ có thể dùng thuật toán sắp xếpBucket Sort.

8. Khi sắp xếp danh sách [4, 1, 3, 2] bằng thuật toán sắp xếp trộn (Merge Sort), bước chia danh sách thành các danh sách con nhỏ hơn sẽ diễn ra như thế nào?

A. [4], [1], [3], [2]

B. [4, 1], [3, 2]

C. [4, 1, 3], [2]

D. [4, 1, 3, 2]

9. Mục đích chính của việc sử dụng thuật toán sắp xếp trong tin học là gì?

A. Để tăng dung lượng bộ nhớ của máy tính.

B. Để giảm thời gian tìm kiếm và truy cập dữ liệu.

C. Để làm cho dữ liệu trông đẹp mắt hơn trên màn hình.

D. Để tự động hóa quá trình nhập liệu.

10. Khi so sánh thuật toán sắp xếp chèn (Insertion Sort) và sắp xếp chọn (Selection Sort) về mặt số lần hoán đổi (swap) để sắp xếp một danh sách, thuật toán nào thường thực hiện ít hoán đổi hơn trong trường hợp trung bình?

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

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

C. Cả hai thực hiện số lần hoán đổi như nhau.

D. Phụ thuộc vào dữ liệu đầu vào.

11. Đâu KHÔNG phải là một đặc điểm của thuật toán sắp xếp nhanh (Quick Sort)?

A. Nó sử dụng kỹ thuật chia để trị.

B. Nó có độ phức tạp thời gian trung bình là O(n log n).

C. Nó là thuật toán sắp xếp ổn định (stable sort).

D. Nó cần thêm bộ nhớ phụ để hoạt động.

12. Trong sắp xếp vun đống (Heap Sort), bước đầu tiên là xây dựng một cấu trúc dữ liệu gọi là đống (heap). Loại đống nào thường được sử dụng để sắp xếp theo thứ tự tăng dần?

A. Max-heap (Đống cực đại)

B. Min-heap (Đống cực tiểu)

C. Cả Max-heap và Min-heap đều có thể dùng được.

D. Không sử dụng đống mà sử dụng cây tìm kiếm nhị phân.

13. Trong thuật toán sắp xếp trộn (Merge Sort), giai đoạn trộn (merge) hai danh sách con đã sắp xếp là bước quan trọng nhất. Nếu ta có hai danh sách con đã sắp xếp là A = [2, 5, 8] và B = [1, 3, 9], sau khi trộn chúng lại theo thứ tự tăng dần, danh sách kết quả sẽ là gì?

A. [1, 2, 3, 5, 8, 9]

B. [2, 1, 5, 3, 8, 9]

C. [1, 3, 9, 2, 5, 8]

D. [2, 5, 8, 1, 3, 9]

14. Thuật toán nào sau đây KHÔNG phải là thuật toán sắp xếp dựa trên so sánh (comparison-based sort)?

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

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

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

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

15. Nếu ta có một danh sách rất lớn gồm các số nguyên dương và biết rằng các số này nằm trong một phạm vi hẹp (ví dụ: từ 1 đến 1000), thuật toán nào sau đây sẽ là lựa chọn hiệu quả nhất về mặt thời gian?

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 đếm (Counting Sort)

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

16. Thuật toán sắp xếp chèn (Insertion Sort) hoạt động tốt nhất khi nào?

A. Khi danh sách có kích thước rất lớn và dữ liệu xáo trộn hoàn toàn.

B. Khi danh sách đã được sắp xếp hoặc gần được sắp xếp.

C. Khi chỉ có một vài phần tử trong danh sách.

D. Khi cần thực hiện sắp xếp song song.

17. Khi áp dụng sắp xếp chèn (Insertion Sort) cho một danh sách, mỗi bước của thuật toán thực hiện công việc gì?

A. Tìm phần tử nhỏ nhất và đặt nó vào đầu danh sách.

B. Chia danh sách thành hai phần và sắp xếp chúng một cách đệ quy.

C. Lấy một phần tử từ phần chưa sắp xếp và chèn nó vào vị trí đúng trong phần đã sắp xếp.

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

18. Thuật toán sắp xếp chọn (Selection Sort) hoạt động bằng cách tìm phần tử nhỏ nhất (hoặc lớn nhất) trong phần chưa sắp xếp và đặt nó vào đúng vị trí ở đầu (hoặc cuối) của phần đã sắp xếp. Với danh sách [7, 2, 9, 1, 5], sau hai lần lặp của Selection Sort (theo thứ tự tăng dần), danh sách sẽ có dạng nào?

A. [1, 2, 9, 7, 5]

B. [1, 2, 5, 9, 7]

C. [2, 1, 9, 7, 5]

D. [1, 5, 9, 7, 2]

19. Thuật toán nào sau đây thường được coi là có độ phức tạp thời gian không xác định (non-deterministic) do phụ thuộc vào lựa chọn pivot?

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

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

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

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

20. Trong sắp xếp nổi bọt (bubble sort), mỗi lần duyệt qua danh sách, phần tử lớn nhất (hoặc nhỏ nhất) sẽ được đưa về vị trí cuối cùng (hoặc đầu tiên) trong phần chưa sắp xếp. Quá trình này lặp lại cho đến khi toàn bộ danh sách được sắp xếp. Nếu ta có danh sách [5, 1, 4, 2, 8], sau lần duyệt đầu tiên của thuật toán sắp xếp nổi bọt theo thứ tự tăng dần, danh sách sẽ có dạng nào sau đây?

A. [1, 4, 2, 5, 8]

B. [1, 4, 2, 8, 5]

C. [5, 1, 4, 2, 8]

D. [1, 2, 4, 5, 8]

21. Thuật toán sắp xếp nào thường được sử dụng trong các bảng tính điện tử (như Microsoft Excel) khi người dùng chọn sắp xếp một cột theo thứ tự bảng chữ cái hoặc số?

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. Tất cả các thuật toán trên đều có thể được sử dụng tùy theo cài đặt.

22. Nếu một thuật toán sắp xếp có độ phức tạp thời gian là O(n log n) và một thuật toán khác có độ phức tạp là O(n^2), thì thuật toán nào sẽ hiệu quả hơn khi kích thước tập dữ liệu (n) rất lớn?

A. Thuật toán có độ phức tạp O(n^2)

B. Thuật toán có độ phức tạp O(n log n)

C. Hiệu quả như nhau.

D. Phụ thuộc vào phần cứng của máy tính.

23. Thuật toán sắp xếp nào dưới đây thường có hiệu suất tốt nhất về mặt thời gian thực thi đối với các tập dữ liệu lớn và đã được sắp xếp một phầ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 trộn (Merge Sort)

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

24. Thuật toán nào sau đây yêu cầu bộ nhớ phụ (extra space) nhiều nhất để hoạt động?

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

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

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

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

25. Độ 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)