[Cánh diều] Trắc nghiệm Tin học 7 bài 4 Sắp xếp nổi bọt

1. Trong thuật toán nổi bọt, nếu ta muốn sắp xếp mảng theo thứ tự tăng dần, điều kiện để hoán đổi hai phần tử a và b liền kề là gì?

A. a > b

B. a < b

C. a == b

D. a <= b

2. Trong thuật toán sắp xếp nổi bọt, ở mỗi lượt duyệt qua danh sách, phần tử lớn nhất chưa được sắp xếp sẽ được đưa về vị trí nào?

A. Vị trí đầu tiên của danh sách chưa sắp xếp.

B. Vị trí cuối cùng của danh sách chưa sắp xếp.

C. Vị trí ngẫu nhiên trong danh sách chưa sắp xếp.

D. Vị trí thứ hai của danh sách chưa sắp xếp.

3. Thuật toán nổi bọt có ưu điểm gì so với các thuật toán sắp xếp khác như Selection Sort trong một số trường hợp?

A. Luôn nhanh hơn Selection Sort.

B. Hiệu quả hơn với mảng đã sắp xếp một phần.

C. Yêu cầu ít bộ nhớ hơn.

D. Dễ cài đặt hơn Selection Sort.

4. Mục đích chính của việc sử dụng cờ hiệu (flag) trong phiên bản tối ưu của thuật toán sắp xếp nổi bọt là gì?

A. Tăng số lần hoán đổi.

B. Giảm số lần so sánh.

C. Cho phép thuật toán dừng sớm nếu mảng đã sắp xếp.

D. Tăng độ phức tạp của thuật toán.

5. Đâu là một hạn chế chính của thuật toán sắp xếp nổi bọt khi so sánh với các thuật toán hiệu quả hơn như QuickSort hay MergeSort?

A. Độ phức tạp thời gian cao trong hầu hết các trường hợp.

B. Yêu cầu bộ nhớ phụ lớn.

C. Khó cài đặt hơn.

D. Không thể sắp xếp được mảng có phần tử trùng lặp.

6. Trong ngôn ngữ lập trình Python, đoạn mã giả sau đây thực hiện chức năng gì? (Giả sử arr là một danh sách và n là độ dài của danh sách)

A. Sắp xếp nổi bọt theo thứ tự giảm dần.

B. Sắp xếp nổi bọt theo thứ tự tăng dần.

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

D. Đảo ngược danh sách.

7. Mỗi lần hoàn thành một lượt duyệt trong thuật toán sắp xếp nổi bọt (sắp xếp tăng dần), phần tử nào chắc chắn đã ở đúng vị trí cuối cùng của nó trong mảng đã sắp xếp?

A. Phần tử nhỏ nhất.

B. Phần tử lớn nhất.

C. Phần tử thứ hai nhỏ nhất.

D. Phần tử ở giữa mảng.

8. Khi sử dụng thuật toán sắp xếp nổi bọt, nếu một lượt duyệt không thực hiện bất kỳ phép hoán đổi nào, điều này có ý nghĩa gì?

A. Mảng đã được sắp xếp.

B. Cần thực hiện thêm các lượt duyệt phức tạp hơn.

C. Thuật toán sẽ dừng sớm.

D. Cả A và C đều đúng.

9. Nếu chúng ta muốn sắp xếp một mảng theo thứ tự giảm dần bằng thuật toán nổi bọt, 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, hoán đổi nếu phần tử hiện tại < phần tử tiếp theo.

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

C. Luôn hoán đổi mọi cặp phần tử liền kề.

D. So sánh phần tử đầu và cuối mảng.

10. Sắp xếp nổi bọt có thể được coi là hiệu quả khi nào?

A. Khi mảng có kích thước rất lớn.

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

C. Khi mảng hoàn toàn ngẫu nhiên.

D. Khi cần tốc độ xử lý nhanh nhất cho mọi trường hợp.

11. Độ phức tạp không gian (space complexity) của thuật toán sắp xếp nổi bọt là bao nhiêu?

A. O(n)

B. O(n log n)

C. O(1)

D. O(n^2)

12. Việc nổi bọt của các phần tử lớn nhất lên cuối mảng trong thuật toán nổi bọt là do cơ chế nào?

A. So sánh và hoán đổi các phần tử liền kề sai thứ tự.

B. Chỉ so sánh phần tử đầu và cuối.

C. Chèn phần tử vào vị trí đúng.

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

13. Xét mảng: [5, 1, 4, 2, 8]. Sau lượt duyệt đầu tiên của thuật toán sắp xếp nổi bọt (sắp xếp tăng dần), mảng sẽ có dạng nào?

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

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

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

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

14. Nếu mảng ban đầu là [9, 8, 7, 6, 5], sau lượt duyệt thứ ba của thuật toán sắp xếp nổi bọt (sắp xếp tăng dần), mảng sẽ có dạng nào?

A. [5, 6, 7, 8, 9]

B. [7, 8, 9, 6, 5]

C. [5, 6, 7, 8, 9]

D. [9, 8, 7, 6, 5]

15. Độ 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ốt nhất (ví dụ: mảng ban đầu đã được sắp xếp theo thứ tự tăng dần) là bao nhiêu, nếu có cờ hiệu để dừng sớm?

A. O(n^2)

B. O(n log n)

C. O(n)

D. O(1)

16. Độ 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 xấu nhất (ví dụ: mảng ban đầu được sắp xếp theo thứ tự giảm dần) là bao nhiêu?

A. O(n)

B. O(n log n)

C. O(n^2)

D. O(log n)

17. Phát biểu nào sau đây mô tả đúng nhất cách hoạt động của một cặp so sánh và hoán đổi trong thuật toán nổi bọt?

A. So sánh hai phần tử bất kỳ trong mảng và hoán đổi nếu chúng sai thứ tự.

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

C. So sánh phần tử đầu và cuối mảng, hoán đổi nếu chúng sai thứ tự.

D. Chỉ so sánh các phần tử ở vị trí chẵn và lẻ.

18. Thuật toán sắp xếp nổi bọt thuộc nhóm thuật toán sắp xếp nào?

A. Thuật toán sắp xếp dựa trên so sánh.

B. Thuật toán sắp xếp phi so sánh.

C. Thuật toán sắp xếp phân hoạch.

D. Thuật toán sắp xếp vun đống.

19. Xét mảng [3, 1, 2]. Sau lượt duyệt thứ hai của thuật toán sắp xếp nổi bọt (sắp xếp tăng dần), mảng sẽ có dạng nào?

A. [1, 2, 3]

B. [3, 1, 2]

C. [1, 3, 2]

D. [2, 1, 3]

20. Trong một lượt duyệt của thuật toán nổi bọt, nếu ta có một mảng [A, B, C, D] và thực hiện so sánh (A, B), (B, C), (C, D). Nếu A>B và B<C và C<D, thì sau lượt duyệt này, thứ tự các phần tử có thể thay đổi như thế nào (giả sử không có hoán đổi nào khác)?

A. [B, A, C, D]

B. [A, B, C, D]

C. [B, C, A, D]

D. [B, A, C, D] hoặc [B, C, A, D]

21. Khi thực hiện sắp xếp nổi bọt cho mảng [4, 1, 3, 2] theo thứ tự tăng dần, sau bao nhiêu lượt duyệt mảng mới được sắp xếp hoàn chỉnh?

A. 2 lượt.

B. 3 lượt.

C. 4 lượt.

D. 1 lượt.

22. Trong sắp xếp nổi bọt, mỗi phần tử có thể di chuyển tối đa bao nhiêu vị trí trong một lượt duyệt?

A. 1 vị trí.

B. 2 vị trí.

C. n vị trí.

D. n-1 vị trí.

23. Phát biểu nào sau đây KHÔNG đúng về thuật toán sắp xếp nổi bọt?

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

B. Nó là một thuật toán sắp xếp tại chỗ (in-place sort).

C. Nó hiệu quả nhất cho các mảng lớn chưa sắp xếp.

D. Nó có độ phức tạp thời gian O(n^2) trong trường hợp xấu nhất.

24. Nếu mảng có n phần tử, số lượng phép so sánh tối đa mà thuật toán nổi bọt thực hiện là bao nhiêu?

A. n * (n-1) / 2

B. n * (n+1) / 2

C. n^2

D. n

25. Để sắp xếp một mảng theo thứ tự tăng dần bằng thuật toán nổi bọt, ta cần thực hiện bao nhiêu lượt duyệt qua mảng, nếu mảng có n phần tử?

A. n lượt.

B. n-1 lượt.

C. n+1 lượt.

D. 1 lượt.