Trắc nghiệm Tin học 7 cánh diều bài 3 Sắp xếp chọn

1. Trong sắp xếp chọn, khi tìm phần tử nhỏ nhất trong một phạm vi, chúng ta cần so sánh nó với bao nhiêu phần tử?

A. Chỉ một phần tử.

B. Tất cả các phần tử còn lại trong phạm vi đó.

C. Phần tử đầu tiên của phạm vi.

D. Một nửa số phần tử còn lại trong phạm vi đó.

2. Nếu ta muốn sắp xếp một mảng theo thứ tự tăng dần, và mảng ban đầu là [5, 2, 5, 1]. Sau lần lặp đầu tiên của sắp xếp chọn, mảng sẽ là gì?

A. [1, 2, 5, 5]

B. [1, 5, 5, 2]

C. [2, 5, 5, 1]

D. [5, 1, 5, 2]

3. Mục đích của việc chọn trong thuật toán Sắp xếp chọn là gì?

A. Chọn ngẫu nhiên một phần tử để đổi chỗ.

B. Chọn phần tử nhỏ nhất (hoặc lớn nhất) để đặt vào vị trí đúng.

C. Chọn một cặp phần tử để so sánh.

D. Chọn một phạm vi để thực hiện sắp xếp.

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

A. Có, vì nó luôn đặt các phần tử bằng nhau vào đúng vị trí.

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. Chỉ khi dữ liệu đầu vào không có phần tử trùng lặp.

D. Phụ thuộc vào cách cài đặt cụ thể.

5. Xét mảng [10, 4, 6, 2, 8]. Sau hai lần lặp của sắp xếp chọn, mảng sẽ trông như thế nào?

A. [2, 4, 6, 10, 8]

B. [4, 2, 6, 10, 8]

C. [2, 4, 10, 6, 8]

D. [2, 6, 4, 10, 8]

6. Mảng [6, 3, 8, 2, 9]. Sau lần lặp thứ hai của sắp xếp chọn (sắp xếp tăng dần), phần tử nào sẽ nằm ở vị trí thứ ba (index 2)?

A. 8

B. 3

C. 6

D. 2

7. Trong sắp xếp chọn, nếu phần tử đầu tiên của phần chưa sắp xếp cũng là phần tử nhỏ nhất, thì thao tác đổi chỗ có diễn ra không?

A. Có, luôn luôn diễn ra.

B. Không, nếu phần tử đó đã ở đúng vị trí.

C. Chỉ khi đó là phần tử duy nhất còn lại.

D. Tùy thuộc vào ngôn ngữ lập trình.

8. Nhược điểm lớn nhất của thuật toán sắp xếp chọn là gì khi áp dụng cho các tập dữ liệu lớn?

A. Số lần so sánh vẫn còn cao, không hiệu quả với dữ liệu lớn.

B. Yêu cầu bộ nhớ phụ lớn để lưu trữ tạm thời.

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

D. Chỉ hiệu quả với các mảng có kích thước nhỏ.

9. Độ phức tạp thời gian của thuật toán sắp xếp chọn là bao nhiêu?

A. O(n)

B. O(n log n)

C. O(n^2)

D. O(n^3)

10. Nếu một mảng đã được sắp xếp hoàn toàn, thuật toán sắp xếp chọn sẽ thực hiện bao nhiêu lần đổi chỗ?

A. 0 lần.

B. 1 lần.

C. N-1 lần.

D. N lần (với N là số phần tử).

11. Giả sử mảng là [7, 3, 9, 1, 5]. Sau lần lặp thứ hai của sắp xếp chọn, phần tử nào sẽ nằm ở vị trí thứ hai (index 1)?

A. 3

B. 1

C. 5

D. 7

12. Nếu ta muốn sắp xếp một mảng theo thứ tự giảm dần bằng sắp xếp chọn, ta sẽ tìm kiếm và đổi chỗ với phần tử nào trong mỗi lần lặp?

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

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

C. Phần tử trung vị.

D. Phần tử ngẫu nhiên.

13. Trong thuật toán sắp xếp chọn, làm thế nào để xác định vị trí của phần tử nhỏ nhất trong phần chưa sắp xếp?

A. Duy trì một biến lưu chỉ số của phần tử nhỏ nhất đã tìm thấy.

B. Sử dụng hàm tìm kiếm nhị phân.

C. So sánh phần tử đầu tiên với tất cả các phần tử khác.

D. Duy trì một biến lưu giá trị của phần tử nhỏ nhất đã tìm thấy.

14. Nếu ta có mảng [9, 8, 7, 6, 5] và áp dụng sắp xếp chọn để sắp xếp tăng dần, sau lần lặp thứ 3, mảng sẽ như thế nào?

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

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

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

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

15. Trong quá trình sắp xếp chọn, mỗi lần lặp sẽ đặt một phần tử vào vị trí đúng của nó. Vị trí này nằm ở đâu trong mảng?

A. Cuối của phần mảng chưa sắp xếp.

B. Đầu của phần mảng chưa sắp xếp.

C. Giữa của phần mảng chưa sắp xếp.

D. Tùy thuộc vào giá trị của phần tử đó.

16. Nếu ta có một mảng gồm các số nguyên [5, 2, 8, 1, 9], sau lần lặp đầu tiên của thuật toán sắp xếp chọn, mảng sẽ có dạng như thế nào?

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

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

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

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

17. Đâu là một ứng dụng thực tế của thuật toán sắp xếp chọn, mặc dù không phổ biến bằng các thuật toán khác?

A. Sắp xếp danh sách bài hát theo thứ tự alphabet.

B. Sắp xếp các giao dịch tài chính theo thời gian.

C. Sắp xếp các bản ghi dữ liệu khi số lượng bản ghi rất nhỏ và ưu tiên giảm thiểu số lần ghi (write operations).

D. Sắp xếp ảnh trong một thư viện.

18. Ưu điểm chính của thuật toán sắp xếp chọn so với các thuật toán sắp xếp đơn giản khác (ví dụ: sắp xếp nổi bọt) là gì?

A. Số lần thực hiện thao tác đổi chỗ (swap) ít hơn.

B. Số lần thực hiện thao tác so sánh ít hơn.

C. Hoạt động hiệu quả hơn với các mảng đã sắp xếp một phần.

D. Có độ phức tạp thời gian tốt hơn trong mọi trường hợp.

19. Mảng [3, 1, 4, 2]. Sau lần lặp thứ ba của sắp xếp chọn (sắp xếp tăng dần), mảng sẽ có dạng nào?

A. [1, 2, 3, 4]

B. [1, 2, 4, 3]

C. [1, 3, 2, 4]

D. [1, 3, 4, 2]

20. Thuật toán sắp xếp chọn có thể được mô tả là một dạng của thuật toán nào?

A. Chia để trị (Divide and Conquer).

B. Tham lam (Greedy).

C. Quay lui (Backtracking).

D. Quy hoạch động (Dynamic Programming).

21. Nếu ta áp dụng sắp xếp chọn cho một mảng chỉ có một phần tử, kết quả sẽ là gì?

A. Mảng sẽ không thay đổi.

B. Mảng sẽ bị xóa.

C. Mảng sẽ bị đảo ngược.

D. Kết quả không xác định.

22. Số lượng so sánh tối thiểu mà thuật toán sắp xếp chọn cần thực hiện trên một mảng gồm N phần tử là bao nhiêu?

A. N-1

B. N * (N-1) / 2

C. N^2

D. N

23. Khi sắp xếp một mảng với thuật toán sắp xếp chọn, số lượng phần tử cần phải được sắp xếp giảm đi bao nhiêu sau mỗi lần lặp?

A. Một phần tử.

B. Hai phần tử.

C. Nửa phần tử.

D. Không giảm, chỉ đổi chỗ các phần tử đã có.

24. Tại sao sắp xếp chọn lại ít được sử dụng trong thực tế cho các ứng dụng yêu cầu hiệu suất cao so với các thuật toán khác như QuickSort hay MergeSort?

A. Vì độ phức tạp thời gian O(n^2) không hiệu quả với dữ liệu lớn.

B. Vì nó yêu cầu nhiều bộ nhớ phụ.

C. Vì nó không ổn định (không giữ nguyên thứ tự tương đối của các phần tử bằng nhau).

D. Vì nó chỉ hoạt động tốt với các mảng đã sắp xếp.

25. Trong thuật toán sắp xếp chọn (Selection Sort), mục tiêu của mỗi lần lặp là gì?

A. Tìm phần tử nhỏ nhất trong phần chưa sắp xếp và đổi chỗ nó với phần tử đầu tiên của phần chưa sắp xếp.

B. Tìm phần tử lớn nhất trong phần chưa sắp xếp và đổi chỗ nó với phần tử cuối cùng của phần chưa sắp xếp.

C. Chia danh sách thành hai phần và sắp xếp từng phần một cách độc lập.

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