Trắc Nghiệm Tin Học 11 KHMT Kết Nối Tri Thức Chủ Đề 6 Bài 21: Các Thuật Toán Sắp Xếp Đơn Giản là bộ câu hỏi thuộc môn Tin học, được biên soạn nhằm giúp học sinh lớp 11 nắm vững nguyên lý hoạt động của các thuật toán sắp xếp cơ bản như đổi chỗ trực tiếp, chọn trực tiếp và chèn trực tiếp. Đây là đề ôn tập của Trường THPT Nguyễn Thượng Hiền (TP. Hồ Chí Minh), do cô Lê Mai Phương – giáo viên Tin học biên soạn năm 2024. Bộ đề được trình bày theo dạng trắc nghiệm Tin học 11 KHMT, tích hợp trên hệ thống detracnghiem.edu.vn giúp học sinh luyện tập dễ dàng, bám sát nội dung SGK Kết nối tri thức và rèn kỹ năng tư duy thuật toán.

Trắc nghiệm Tin học 11 ở chủ đề này tập trung kiểm tra khả năng phân tích cách thức hoạt động của từng thuật toán, so sánh thời gian thực hiện và đánh giá tính hiệu quả trong các tình huống xử lý dữ liệu khác nhau. Mỗi câu hỏi đều được kèm đáp án và giải thích chi tiết, hỗ trợ học sinh tự học, tự kiểm tra và nâng cao kỹ năng xử lý thuật toán trong lập trình cơ bản. Bộ câu hỏi là nguồn tài liệu hữu ích cho học sinh lớp 11 trong quá trình ôn tập và chuẩn bị kiểm tra cuối chương. Trắc nghiệm ôn tập lớp 11

Trắc nghiệm Tin học 11 KHMT Kết nối tri thức

Chủ đề 6: Kỹ thuật lập trình

Bài 21: Các thuật toán sắp xếp đơn giản

Câu 1: Ba thuật toán sắp xếp đơn giản phổ biến nhất được học trong chương trình là gì?
A. Sắp xếp nhanh (Quick Sort), Sắp xếp vun đống (Heap Sort), Sắp xếp trộn (Merge Sort).
B. Sắp xếp chèn (Insertion Sort), Sắp xếp chọn (Selection Sort), Sắp xếp nổi bọt (Bubble Sort).
C. Sắp xếp chèn, Sắp xếp nhanh, Sắp xếp nổi bọt.
D. Sắp xếp chọn, Sắp xếp cây, Sắp xếp nổi bọt.

Câu 2: Ý tưởng chính của thuật toán Sắp xếp chèn (Insertion Sort) là gì?
A. Tìm phần tử nhỏ nhất trong dãy và đổi chỗ nó về đầu dãy.
B. So sánh các cặp phần tử kề nhau và đổi chỗ nếu chúng sai thứ tự.
C. Chia dãy số thành hai nửa, sắp xếp từng nửa rồi trộn lại.
D. Lấy lần lượt các phần tử của dãy chưa sắp xếp và chèn nó vào đúng vị trí trong dãy con đã được sắp xếp trước đó.

Câu 3: Cho dãy số A = [5, 2, 9, 1]. Sau bước thứ nhất của thuật toán Sắp xếp chọn (Selection Sort) (chọn phần tử nhỏ nhất đưa về đầu), dãy số sẽ trở thành:
A. [2, 5, 9, 1]
B. [5, 2, 1, 9]
C. [1, 2, 9, 5]
D. [1, 5, 9, 2]

Câu 4: Trong thuật toán Sắp xếp nổi bọt (Bubble Sort), sau mỗi một lượt duyệt qua dãy (một vòng lặp lớn), điều gì được đảm bảo?
A. Dãy số đã được sắp xếp hoàn chỉnh.
B. Phần tử nhỏ nhất chắc chắn nằm ở vị trí cuối cùng.
C. Phần tử lớn nhất (hoặc nhỏ nhất tùy cách cài đặt) trong phần chưa sắp xếp sẽ “nổi” về đúng vị trí cuối cùng (hoặc đầu tiên) của nó.
D. Các phần tử ở vị trí chẵn đã được sắp xếp đúng.

Câu 5: Đoạn mã Python sau mô tả thuật toán nào?
code
Python
for i in range(1, len(A)):
key = A[i]
j = i – 1
while j >= 0 and key < A[j]:
A[j + 1] = A[j]
j -= 1
A[j + 1] = key
A. Sắp xếp nổi bọt.
B. Sắp xếp chọn.
C. Sắp xếp nhanh.
D. Sắp xếp chèn.

Câu 6: Cho dãy A = [10, 11, 9, 5]. Sử dụng Sắp xếp chèn. Tại bước khi i = 2 (xét phần tử giá trị 9), số lần so sánh cần thực hiện để chèn số 9 vào dãy con [10, 11] là bao nhiêu?
A. 1 lần (so với 11).
B. 2 lần (so với 11, sau đó so với 10).
C. 3 lần (so với 11, 10 và phần tử 5).
D. 0 lần.

Câu 7: Trong thuật toán Sắp xếp chọn (Selection Sort), số lần đổi chỗ (swap) tối đa của thuật toán là bao nhiêu với dãy có n phần tử?
A. n^2 lần.
B. n(n−1)/2 lần.
C. n−1 lần.
D. 1 lần duy nhất.

Câu 8: Với dãy số đầu vào đã được sắp xếp đúng thứ tự tăng dần (ví dụ [1, 2, 3, 4, 5]), thuật toán nào sau đây sẽ chạy nhanh nhất (thực hiện ít phép so sánh và gán nhất)?
A. Sắp xếp chọn (Selection Sort).
B. Sắp xếp chèn (Insertion Sort).
C. Cả 3 thuật toán đều chạy chậm như nhau (O(n^2).
D. Sắp xếp chọn và Sắp xếp nổi bọt.
Câu 9: Trong thuật toán Sắp xếp chọn, biến min_idx (hoặc k) dùng để lưu trữ thông tin gì trong mỗi vòng lặp?

A. Giá trị của phần tử nhỏ nhất tìm thấy.
B. Chỉ số (vị trí) của phần tử nhỏ nhất trong đoạn chưa sắp xếp.
C. Số lần đã thực hiện đổi chỗ.
D. Tổng giá trị các phần tử trong dãy.

Câu 10: Cho dãy A = [3, 1, 4, 2]. Mô phỏng Sắp xếp nổi bọt (đưa phần tử lớn về cuối):
Vòng 1: [1, 3, 2, 4] (4 về cuối)
Vòng 2 sẽ có kết quả là gì?
A. [1, 2, 3, 4]
B. [1, 2, 3, 4] (Số 3 nổi lên vị trí kế cuối).
C. [3, 1, 2, 4]
D. [1, 3, 4, 2]

Câu 11: Trong đoạn mã của thuật toán Sắp xếp chèn, câu lệnh while j >= 0 and A[j] > key: có ý nghĩa gì?
A. Tìm phần tử nhỏ nhất trong dãy.
B. Duyệt từ đầu dãy đến cuối dãy để in ra màn hình.
C. Dời các phần tử lớn hơn key sang phải để tạo chỗ trống chèn key.
D. Đổi chỗ trực tiếp A[j] và key.

Câu 12: Thuật toán sắp xếp nào có đặc điểm “liên tục đổi chỗ hai phần tử liền kề nếu chúng sai thứ tự”?
A. Insertion Sort.
B. Selection Sort.
C. Bubble Sort.
D. Quick Sort.

Câu 13: Độ phức tạp thời gian trung bình và xấu nhất của cả ba thuật toán (Chèn, Chọn, Nổi bọt) đều là:
A. O(n)
B. O(logn)
C. O(n^2)
D. O(nlogn)

Câu 14: Giả sử dãy số đầu vào được sắp xếp theo thứ tự ngược lại (giảm dần), ta muốn sắp xếp thành tăng dần. Thuật toán nào sẽ thực hiện số lần so sánh và di chuyển nhiều nhất (kém hiệu quả nhất) trong trường hợp này?
A. Sắp xếp chọn.
B. Sắp xếp nổi bọt.
C. Sắp xếp chèn.
D. Cả Sắp xếp chèn và Sắp xếp nổi bọt đều đạt độ phức tạp xấu nhất O(n^2) trong trường hợp này.

Câu 15: Câu lệnh hoán đổi giá trị hai biến x và y trong Python được viết gọn nhất là:
A. x = y; y = x
B. temp = x; x = y; y = temp
C. x, y = y, x
D. swap(x, y)

Câu 16: Trong thuật toán Sắp xếp nổi bọt, vòng lặp ngoài thường chạy từ i = 0 đến n-2 (hoặc n-1). Vòng lặp trong chạy biến j. Nhiệm vụ của vòng lặp trong là gì?
A. Chọn ra phần tử nhỏ nhất.
B. Chèn phần tử vào vị trí đúng.
C. Duyệt qua các cặp phần tử liền kề để so sánh và đổi chỗ.
D. Khởi tạo lại dãy số.

Câu 17: Sự khác biệt chính giữa Sắp xếp chọn và Sắp xếp chèn là gì?
A. Sắp xếp chọn nhanh hơn Sắp xếp chèn rất nhiều.
B. Sắp xếp chọn tìm phần tử nhỏ nhất rồi mới đổi chỗ, còn Sắp xếp chèn vừa tìm vị trí vừa dời chỗ các phần tử.
C. Sắp xếp chèn dùng 2 vòng lặp, Sắp xếp chọn chỉ dùng 1 vòng lặp.
D. Sắp xếp chèn không thể sắp xếp dãy số thực, chỉ sắp xếp được số nguyên.

Câu 18: Để sắp xếp dãy số theo thứ tự giảm dần thay vì tăng dần bằng thuật toán Sắp xếp chèn, ta cần sửa đổi gì trong mã nguồn chuẩn?
A. Thay vòng lặp for bằng vòng lặp while.
B. Đổi dấu so sánh trong vòng lặp while (từ key < A[j] thành key > A[j]).
C. Thay đổi cách khởi tạo biến key.
D. Thuật toán Sắp xếp chèn không thể sắp xếp giảm dần.

Câu 19: Cho đoạn mã Sắp xếp chọn:
code
Python
for i in range(n-1):
m = i
for j in range(i+1, n):
if A[j] < A[m]:
m = j
A[i], A[m] = A[m], A[i]
Nếu dãy A đã có thứ tự tăng dần, câu lệnh A[i], A[m] = A[m], A[i] được thực hiện bao nhiêu lần?
A. 0 lần.
B. 1 lần.
C. Vẫn thực hiện n-1 lần (đổi chỗ với chính nó nếu m không đổi, hoặc tùy cách cài đặt tối ưu if m!=i).
D. n^2 lần.

Câu 20: Tại sao thuật toán Sắp xếp nổi bọt thường bị coi là chậm nhất trong thực tế so với Chèn và Chọn, dù cùng độ phức tạp O(n^2)?
A. Vì nó dùng nhiều bộ nhớ nhất.
B. Vì nó khó cài đặt nhất.
C. Vì số lượng thao tác đổi chỗ (swap) xảy ra quá nhiều lần.
D. Vì Python không hỗ trợ tốt cho thuật toán này.

Câu 21: Vận dụng cao: Một biến thể của thuật toán Sắp xếp nổi bọt có sử dụng thêm một biến cờ hiệu (flag) tên là swapped. Biến này có tác dụng gì?
A. Để đánh dấu phần tử lớn nhất.
B. Để phát hiện nếu trong một lượt duyệt không có cặp nào bị đổi chỗ thì dừng thuật toán ngay lập tức (dãy đã sắp xếp).
C. Để đếm số lần đổi chỗ.
D. Để chuyển thuật toán thành Sắp xếp chọn.

Câu 22: Vận dụng cao: Xét về tính “ổn định” (Stable) – tức là giữ nguyên thứ tự ban đầu của các phần tử có giá trị bằng nhau. Thuật toán nào sau đây thường được cài đặt là thuật toán ổn định?
A. Sắp xếp chọn (Selection Sort).
B. Sắp xếp chèn (Insertion Sort) và Sắp xếp nổi bọt (Bubble Sort).
C. Chỉ có Sắp xếp chọn.
D. Không có thuật toán nào trong 3 thuật toán này ổn định.

Câu 23: Vận dụng cao: Cho dãy số [2, 3, 4, 5, 1].
Sắp xếp chèn mất 4 phép dời chỗ cho số 1.
Sắp xếp nổi bọt mất 4 lần đổi chỗ để đưa số 1 về đầu.
Thuật toán Sắp xếp chọn sẽ mất bao nhiêu lần đổi chỗ?
A. 4 lần.
B. 1 lần (Đổi chỗ số 1 với số 2 ở đầu dãy, sau đó các bước sau không đổi chỗ nữa).
C. 0 lần.
D. 5 lần.

Câu 24: Vận dụng cao: Khi nào thì thuật toán Sắp xếp chèn có độ phức tạp thời gian là O(n) (tốt nhất)?
A. Khi dãy số được sắp xếp theo thứ tự ngược lại.
B. Khi dãy số có tất cả phần tử bằng nhau.
C. Khi dãy số đã được sắp xếp đúng thứ tự (hoặc gần đúng).
D. Khi dãy số ngẫu nhiên hoàn toàn.

Câu 25: Vận dụng cao: Bạn cần sắp xếp danh sách điểm thi của 1 triệu học sinh. Bạn có nên dùng Sắp xếp nổi bọt (Bubble Sort) không? Tại sao?
A. Có, vì code ngắn gọn dễ viết.
B. Có, vì máy tính hiện nay rất mạnh.
C. Không, vì độ phức tạp O(n^2) sẽ khiến chương trình chạy quá lâu (hàng nghìn tỷ phép tính), không khả thi.
D. Không, vì Bubble Sort chỉ sắp xếp được số nguyên.