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

1. Sắp xếp nổi bọt có ưu điểm gì khi nói về việc triển khai đơn giản và dễ hiểu?

A. Nó sử dụng ít bộ nhớ nhất.

B. Logic của nó rất trực quan và dễ dàng lập trình.

C. Nó nhanh nhất cho mọi kích thước dữ liệu.

D. Nó tự động nhận diện cấu trúc dữ liệu.

2. Cấu trúc dữ liệu nào thường được sử dụng để biểu diễn danh sách các phần tử cần sắp xếp bằng thuật toán nổi bọt?

A. Cây nhị phân tìm kiếm

B. Mảng (Array) hoặc danh sách liên kết

C. Hàng đợi (Queue)

D. Ngăn xếp (Stack)

3. Độ phức tạp thời gian (time complexity) của thuật toán sắp xếp nổi bọt trong trường hợp xấu nhất là bao nhiêu, với N là số phần tử của danh sách?

A. O(N)

B. O(N log N)

C. O(N^2)

D. O(log N)

4. Trong thuật toán sắp xếp nổi bọt, nếu danh sách ban đầu là [1, 2, 3, 4, 5], sau bao nhiêu lượt duyệt đầy đủ (pass) danh sách sẽ được coi là đã sắp xếp?

A. 1 lượt duyệt

B. 2 lượt duyệt

C. N-1 lượt duyệt

D. N lượt duyệt

5. Số lượng phần tử cần so sánh trong lượt duyệt thứ k (bắt đầu từ k=1) của thuật toán sắp xếp nổi bọt trên danh sách N phần tử là bao nhiêu?

A. N - k

B. N - k + 1

C. N

D. N - 1

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

A. [1, 3, 2, 4]

B. [1, 4, 3, 2]

C. [4, 1, 2, 3]

D. [1, 2, 3, 4]

7. Số lần so sánh tối đa trong thuật toán sắp xếp nổi bọt cho một danh sách có N phần tử, khi danh sách ban đầu chưa được sắp xếp là bao nhiêu?

A. N-1

B. N

C. N*(N-1)/2

D. N*(N+1)/2

8. 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 nổi lên vị trí cuối cùng. Điều này đúng với loại sắp xếp nào?

A. Sắp xếp tăng dần (ascending sort)

B. Sắp xếp giảm dần (descending sort)

C. Sắp xếp theo thứ tự bảng chữ cái

D. Sắp xếp theo thời gian thực

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

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

B. Độ phức tạp thời gian cao đối với dữ liệu lớn.

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

D. Yêu cầu bộ nhớ ngoài.

10. Thuật toán sắp xếp nổi bọt có thể được áp dụng cho loại dữ liệu nào?

A. Chỉ các số nguyên dương.

B. Bất kỳ kiểu dữ liệu nào có thể so sánh được.

C. Chỉ các chuỗi ký tự.

D. Chỉ các số thực.

11. Trong thuật toán sắp xếp nổi bọt, mỗi lượt duyệt đảm bảo rằng phần tử nào sẽ được đặt đúng vị trí cuối cùng của nó trong danh sách đã sắp xếp?

A. Phần tử nhỏ nhất chưa được sắp xếp.

B. Phần tử lớn nhất chưa được sắp xếp.

C. Phần tử trung vị.

D. Phần tử đầu tiên của danh sách chưa sắp xếp.

12. Giả sử có một cờ đã đổi chỗ (swapped flag) được sử dụng trong thuật toán nổi bọt. Nếu trong một lượt duyệt, cờ này không được bật lên, điều này có ý nghĩa gì?

A. Thuật toán phải tiếp tục duyệt thêm một lượt nữa.

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

C. Cần phải khởi tạo lại cờ.

D. Có lỗi trong quá trình so sánh.

13. Trong thuật toán sắp xếp nổi bọt, nếu ta muốn sắp xếp một danh sách theo thứ tự giảm dần, điều kiện so sánh giữa hai phần tử liền kề `a` và `b` (với `a` đứng trước `b`) sẽ là gì để thực hiện đổi chỗ?

A. Nếu `a < b`

B. Nếu `a > b`

C. Nếu `a == b`

D. Không cần điều kiện so sánh.

14. Trong trường hợp nào thuật toán sắp xếp nổi bọt hoạt động hiệu quả nhất về số lần so sánh?

A. Danh sách đã sắp xếp theo thứ tự giảm dần.

B. Danh sách đã sắp xếp theo thứ tự tăng dần.

C. Danh sách xáo trộn ngẫu nhiên hoàn toàn.

D. Danh sách có các phần tử trùng lặp nhiều.

15. Nếu chúng ta có danh sách [9, 8, 7, 6, 5] và áp dụng sắp xếp nổi bọt tăng dần, sau lượt duyệt thứ ba, phần tử nào sẽ nằm ở vị trí thứ ba từ cuối lên (tức là vị trí N-2, với N=5)?

A. 5

B. 6

C. 7

D. 8

16. Khi so sánh hai phần tử liền kề a và b trong thuật toán sắp xếp nổi bọt tăng dần, nếu a > b thì hành động tiếp theo là gì?

A. Giữ nguyên vị trí của a và b.

B. Đổi chỗ a và b.

C. So sánh a với phần tử tiếp theo.

D. Dừng thuật toán.

17. Thuật toán sắp xếp nổi bọt có được coi là thuật toán sắp xếp ổn định (stable sort) không?

A. Có, vì nó luôn giữ nguyên thứ tự tương đối của các phần tử bằng nhau.

B. Không, vì nó có thể thay đổi thứ tự tương đối của các phần tử bằng nhau.

C. Có, nhưng chỉ áp dụng cho số nguyên.

D. Không, vì nó là thuật toán sắp xếp không tại chỗ.

18. Sắp xếp nổi bọt thuộc loại thuật toán sắp xếp nào?

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

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

C. Sắp xếp trao đổi (Exchange Sort)

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

19. Trong một lần triển khai sắp xếp nổi bọt, có thể tối ưu hóa bằng cách nào để giảm số lượt duyệt khi danh sách đã được sắp xếp?

A. Tăng kích thước mảng.

B. Sử dụng cờ đã đổi chỗ để thoát sớm.

C. Giảm kích thước phần tử so sánh.

D. Chỉ duyệt một lần duy nhất.

20. Độ 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 (danh sách đã sắp xếp) là bao nhiêu?

A. O(N^2)

B. O(N log N)

C. O(N)

D. O(1)

21. Khi thực hiện sắp xếp nổi bọt cho danh sách [3, 1, 4, 1, 5, 9, 2, 6], sau hai lượt duyệt (theo chiều tăng dần), phần tử nào chắc chắn nằm ở vị trí cuối cùng và vị trí áp cuối của danh sách đã sắp xếp?

A. Vị trí cuối: 9, Vị trí áp cuối: 6

B. Vị trí cuối: 6, Vị trí áp cuối: 9

C. Vị trí cuối: 5, Vị trí áp cuối: 6

D. Vị trí cuối: 9, Vị trí áp cuối: 5

22. Nếu danh sách ban đầu là [5, 4, 3, 2, 1] và ta áp dụng sắp xếp nổi bọt tăng dần, số lần đổi chỗ tối đa sẽ xảy ra trong lượt duyệt nào?

A. Lượt duyệt đầu tiên

B. Lượt duyệt thứ hai

C. Lượt duyệt cuối cùng

D. Số lần đổi chỗ là như nhau trong mỗi lượt.

23. Nếu một thuật toán sắp xếp sử dụng kỹ thuật hoán vị các phần tử liền kề để đưa các phần tử về đúng vị trí, thì nó có thể thuộc loại nào?

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

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

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

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

24. Nếu một thuật toán sắp xếp thực hiện so sánh và hoán đổi các phần tử dựa trên vị trí của chúng trong một dãy, thuật toán đó có thể là:

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

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

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

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

25. Xét danh sách [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 (theo chiều tăng dần), các phần tử nào sẽ được đặt đúng vị trí cuối cùng của nó trong danh sách đã sắp xếp?

A. Phần tử 1

B. Phần tử 2

C. Phần tử 4

D. Phần tử 8