12+ Đề Trắc Nghiệm Tin Học 11 (Kết Nối Tri Thức) Bài 21: Các Thuật Toán Sắp Xếp Đơn Giản

Câu 1: Thuật toán sắp xếp chèn (Insertion Sort) xây dựng mảng đã sắp xếp bằng cách nào?

• A. Tìm phần tử lớn nhất và đặt nó vào cuối mảng.
• B. So sánh các phần tử liền kề và đổi chỗ nếu sai thứ tự.
• C. Chèn từng phần tử vào đúng vị trí trong mảng con đã sắp xếp.
• D. Tìm phần tử nhỏ nhất và đổi chỗ với phần tử đầu tiên của phần chưa sắp xếp.

Câu 2: Cho dãy số A = [5, 2, 4, 6, 1, 3]. Sau bước lặp thứ 3 của thuật toán sắp xếp chèn (khi phần tử thứ 4, giá trị 6, được xem xét), dãy A sẽ có dạng như thế nào? (Giả sử các phần tử từ vị trí 0 đến k-1 đã được sắp xếp sau bước k-1).

• A. [1, 2, 3, 4, 5, 6]
• B. [2, 4, 5, 6, 1, 3]
• C. [1, 2, 4, 5, 6, 3]
• D. [2, 4, 5, 1, 6, 3]

Câu 3: Trường hợp nào sau đây giúp thuật toán sắp xếp chèn đạt hiệu quả thời gian tốt nhất?

• A. Mảng đầu vào đã được sắp xếp.
• B. Mảng đầu vào được sắp xếp theo thứ tự ngược lại.
• C. Tất cả các phần tử trong mảng đều giống nhau.
• D. Mảng có rất ít phần tử (ví dụ dưới 10).

Câu 4: Thuật toán sắp xếp chọn (Selection Sort) hoạt động dựa trên ý tưởng chính nào?

• A. So sánh và hoán đổi các phần tử liền kề.
• B. Chia mảng thành hai phần và sắp xếp từng phần.
• C. Chèn từng phần tử vào đúng vị trí trong mảng con đã sắp xếp.
• D. Tìm phần tử nhỏ nhất trong phần chưa sắp xếp và đưa về đầu phần đó.

Câu 5: Cho dãy số B = [8, 3, 5, 1, 7, 2]. Sau bước lặp thứ 2 của thuật toán sắp xếp chọn, dãy B sẽ có dạng như thế nào? (Sau bước lặp thứ i, i phần tử đầu tiên của mảng là i phần tử nhỏ nhất đã được sắp xếp).

• A. [1, 2, 5, 8, 7, 3]
• B. [1, 2, 3, 5, 7, 8]
• C. [1, 3, 5, 8, 7, 2]
• D. [2, 3, 5, 1, 7, 8]

Câu 6: Đối với một mảng có n phần tử, thuật toán sắp xếp chọn luôn thực hiện khoảng bao nhiêu phép so sánh trong mọi trường hợp (tốt nhất, trung bình, xấu nhất)?

• A. O(n)
• B. O(n log n)
• C. O(n^2)
• D. O(1)

Câu 7: Thuật toán sắp xếp nổi bọt (Bubble Sort) hoạt động dựa trên nguyên tắc nào?

• A. Tìm phần tử nhỏ nhất và đổi chỗ về đầu.
• B. So sánh và hoán đổi các cặp phần tử liền kề.
• C. Chèn phần tử vào mảng con đã sắp xếp.
• D. Chia mảng làm đôi và sắp xếp riêng.

Câu 8: Cho dãy số C = [7, 1, 5, 12, 3]. Sau pass (lần duyệt) đầu tiên của thuật toán sắp xếp nổi bọt, dãy C sẽ có dạng như thế nào?

• A. [1, 3, 5, 7, 12]
• B. [1, 5, 7, 12, 3]
• C. [1, 5, 7, 3, 12]
• D. [7, 1, 5, 3, 12]

Câu 9: Điểm khác biệt cơ bản về số lượng phép hoán đổi (swap) giữa thuật toán sắp xếp chọn và sắp xếp chèn là gì?

• A. Sắp xếp chọn thực hiện ít phép hoán đổi hơn đáng kể so với sắp xếp chèn trong trường hợp xấu nhất.
• B. Sắp xếp chèn thực hiện ít phép hoán đổi hơn so với sắp xếp chọn trong mọi trường hợp.
• C. Cả hai thuật toán đều thực hiện cùng số lượng phép hoán đổi trong trường hợp xấu nhất.
• D. Sắp xếp chọn chỉ hoán đổi các phần tử liền kề, còn sắp xếp chèn thì không.

Câu 10: Một thuật toán sắp xếp được gọi là "ổn định" (stable) nếu:

• A. Nó luôn có độ phức tạp thời gian O(n log n).
• B. Nó giữ nguyên thứ tự ban đầu của các phần tử có giá trị bằng nhau.
• C. Nó chỉ sử dụng một lượng bộ nhớ phụ cố định (O(1)).
• D. Nó hoạt động hiệu quả trên các tập dữ liệu lớn.

Câu 11: Trong ba thuật toán sắp xếp đơn giản (Chèn, Chọn, Nổi bọt), thuật toán nào KHÔNG phải là thuật toán ổn định?

• A. Sắp xếp chèn
• B. Sắp xếp chọn
• C. Sắp xếp nổi bọt
• D. Cả ba thuật toán đều ổn định.

Câu 12: Độ phức tạp thời gian trong trường hợp xấu nhất của cả ba thuật toán sắp xếp đơn giản (Chèn, Chọn, Nổi bọt) là gì?

• A. O(n)
• B. O(n log n)
• C. O(n^2)
• D. O(n!)

Câu 13: Bạn cần sắp xếp một danh sách điểm của 20 học sinh. Danh sách này thường xuyên được cập nhật thêm điểm mới và hầu hết thời gian nó gần như đã được sắp xếp. Thuật toán sắp xếp đơn giản nào phù hợp nhất cho tình huống này để tối ưu hiệu quả?

• A. Sắp xếp chèn (Insertion Sort)
• B. Sắp xếp chọn (Selection Sort)
• C. Sắp xếp nổi bọt (Bubble Sort)
• D. Cả ba đều có hiệu quả như nhau với dữ liệu gần sắp xếp.

Câu 14: Phát biểu nào sau đây là ĐÚNG khi so sánh sắp xếp chọn và sắp xếp nổi bọt?

• A. Sắp xếp chọn nhanh hơn sắp xếp nổi bọt trong trường hợp tốt nhất.
• B. Sắp xếp nổi bọt ít hoán đổi hơn sắp xếp chọn trong trường hợp xấu nhất.
• C. Cả hai thuật toán đều ổn định.
• D. Sắp xếp chọn có số lượng hoán đổi ít hơn hoặc bằng sắp xếp nổi bọt trong trường hợp xấu nhất.

Câu 15: Khi phân tích độ phức tạp thời gian của thuật toán sắp xếp, O(n^2) có ý nghĩa gì?

• A. Thời gian thực thi tăng tỷ lệ với bình phương kích thước dữ liệu đầu vào.
• B. Thời gian thực thi tăng tuyến tính với kích thước dữ liệu đầu vào.
• C. Thời gian thực thi tăng theo logarit của kích thước dữ liệu.
• D. Thuật toán chỉ hiệu quả với dữ liệu có kích thước nhỏ.

Câu 16: Cho dãy D = [9, 5, 2, 7]. Thực hiện thuật toán sắp xếp chèn. Sau khi xử lý xong phần tử có giá trị 2, dãy D sẽ có dạng như thế nào?

• A. [2, 5, 7, 9]
• B. [5, 9, 2, 7]
• C. [9, 5, 2, 7]
• D. [2, 5, 9, 7]

Câu 17: Thuật toán sắp xếp nào sau đây được gọi là "tại chỗ" (in-place) vì nó chỉ yêu cầu một lượng bộ nhớ phụ không đáng kể (thường là O(1)) ngoài không gian lưu trữ dữ liệu ban đầu?

• A. Sắp xếp chèn
• B. Sắp xếp chọn
• C. Sắp xếp nổi bọt
• D. Cả ba thuật toán trên.

Câu 18: Cho dãy E = [4, 1, 3, 9, 7]. Áp dụng thuật toán sắp xếp chọn. Sau khi phần tử nhỏ nhất của toàn bộ dãy được đưa về đúng vị trí đầu tiên, phần tử nào sẽ được chọn làm nhỏ nhất trong phần còn lại để đưa về vị trí thứ hai?

• A. 1
• B. 4
• C. 3
• D. 7

Câu 19: Một lập trình viên muốn sử dụng thuật toán sắp xếp nổi bọt nhưng muốn cải tiến để dừng sớm nếu mảng đã được sắp xếp hoàn toàn trước khi kết thúc tất cả các pass. Cải tiến này dựa vào việc kiểm tra điều kiện gì sau mỗi pass?

• A. Kiểm tra xem có bất kỳ cặp phần tử nào được hoán đổi trong pass đó hay không.
• B. Kiểm tra xem phần tử cuối cùng của pass đó có đúng vị trí hay không.
• C. Kiểm tra xem phần tử đầu tiên của pass đó có đúng vị trí hay không.
• D. So sánh số lượng hoán đổi trong pass hiện tại với pass trước đó.

Câu 20: Xét thuật toán sắp xếp chèn. Khi chèn phần tử `A[i]` vào mảng con đã sắp xếp `A[0...i-1]`, thuật toán thực hiện việc dịch chuyển các phần tử lớn hơn `A[i]` sang bên phải. Hành động này đảm bảo tính chất nào của thuật toán?

• A. Tính tại chỗ (in-place).
• B. Tính ổn định (stable).
• C. Độ phức tạp thời gian O(n).
• D. Số lượng hoán đổi tối thiểu.

Câu 21: Bạn có một danh sách 1000 số nguyên ngẫu nhiên cần được sắp xếp. Bạn cần chọn một trong ba thuật toán đơn giản (Chèn, Chọn, Nổi bọt). Dựa trên độ phức tạp thời gian trung bình, thuật toán nào sẽ có xu hướng thực thi nhanh nhất?

• A. Sắp xếp chèn (Insertion Sort)
• B. Sắp xếp chọn (Selection Sort)
• C. Sắp xếp nổi bọt (Bubble Sort)
• D. Hiệu quả trung bình của ba thuật toán là tương đương (đều là O(n^2)).

Câu 22: Cho dãy F = [10, 8, 6, 4, 2]. Áp dụng thuật toán sắp xếp nổi bọt có cải tiến (dừng sớm). Sau pass thứ nhất, dãy sẽ ở trạng thái nào và thuật toán có dừng lại không? (Giả sử sắp xếp tăng dần).

• A. [2, 4, 6, 8, 10], Thuật toán dừng lại.
• B. [8, 10, 6, 4, 2], Thuật toán chưa dừng.
• C. [8, 6, 4, 2, 10], Thuật toán chưa dừng.
• D. [10, 8, 6, 4, 2], Thuật toán dừng lại.

Câu 23: Khi thực hiện sắp xếp chọn trên một mảng có n phần tử, số lượng phép hoán đổi (swap) tối đa có thể xảy ra là bao nhiêu?

• A. O(n^2)
• B. n - 1
• C. n(n-1)/2
• D. 0

Câu 24: Thuật toán sắp xếp nào trong ba thuật toán đơn giản (Chèn, Chọn, Nổi bọt) có số lượng phép so sánh luôn là O(n^2), bất kể trạng thái ban đầu của mảng?

• A. Sắp xếp chèn
• B. Sắp xếp chọn
• C. Sắp xếp nổi bọt
• D. Cả ba thuật toán.

Câu 25: Giả sử bạn có một mảng chứa các đối tượng phức tạp (ví dụ: hồ sơ sinh viên), và việc hoán đổi toàn bộ đối tượng là một thao tác rất tốn kém. Bạn muốn chọn thuật toán sắp xếp đơn giản nào trong ba thuật toán đã học để giảm thiểu chi phí hoán đổi?

• A. Sắp xếp chèn
• B. Sắp xếp chọn
• C. Sắp xếp nổi bọt
• D. Cả ba đều tốn kém như nhau về hoán đổi.

Câu 26: Cho dãy G = [3, 1, 4, 1, 5, 9, 2, 6]. Sử dụng thuật toán sắp xếp nổi bọt. Sau khi pass thứ hai hoàn thành, phần tử nào sẽ nằm ở vị trí cuối cùng của mảng?

• A. 6
• B. 2
• C. 5
• D. 9

Câu 27: So sánh độ phức tạp thời gian giữa sắp xếp chèn và sắp xếp chọn trong trường hợp xấu nhất.

• A. Sắp xếp chèn là O(n), sắp xếp chọn là O(n^2).
• B. Sắp xếp chèn là O(n^2), sắp xếp chọn là O(n).
• C. Cả hai đều là O(n^2).
• D. Sắp xếp chèn là O(n log n), sắp xếp chọn là O(n^2).

Câu 28: Đâu là một lợi thế của thuật toán sắp xếp chèn so với sắp xếp nổi bọt và sắp xếp chọn?

• A. Rất hiệu quả với dữ liệu gần như đã được sắp xếp.
• B. Luôn thực hiện số lượng hoán đổi tối thiểu.
• C. Độ phức tạp thời gian luôn là O(n).
• D. Dễ dàng triển khai song song.

Câu 29: Cho dãy H = [5, 4, 3, 2, 1]. Sử dụng thuật toán sắp xếp chèn. Phần tử nào sẽ được chèn vào vị trí đầu tiên trong mảng con đã sắp xếp ở cuối quá trình sắp xếp?

• A. 1
• B. 5
• C. 3
• D. 2

Câu 30: Trong thuật toán sắp xếp nổi bọt, sau mỗi pass (lần duyệt) đầy đủ qua mảng (không tính pass cuối cùng khi mảng đã sắp xếp), điều gì chắc chắn xảy ra?

• A. Mảng con ở đầu đã được sắp xếp hoàn toàn.
• B. Không có phần tử nào được hoán đổi trong pass đó.
• C. Phần tử lớn nhất trong phần chưa sắp xếp được đặt vào đúng vị trí của nó.
• D. Độ phức tạp của pass tiếp theo sẽ giảm đi.

Câu 1: Thuật toán sắp xếp chèn (Insertion Sort) hoạt động dựa trên ý tưởng chính nào?

• A. Tìm phần tử nhỏ nhất trong mảng chưa sắp xếp và đưa về đầu.
• B. Xây dựng mảng đã sắp xếp từng bước bằng cách chèn các phần tử vào đúng vị trí.
• C. So sánh và hoán đổi các cặp phần tử liền kề để đưa phần tử lớn hơn về cuối.
• D. Chia mảng thành hai phần và sắp xếp từng phần một cách đệ quy.

Câu 2: Cho mảng A = [5, 2, 8, 1, 9]. Áp dụng thuật toán sắp xếp chèn, trạng thái của mảng sau khi xử lý xong phần tử thứ 3 (giá trị 8) là gì? (Giả sử mảng bắt đầu từ chỉ số 0. Phần tử thứ 1 là 5, thứ 2 là 2, thứ 3 là 8).

• A. [1, 2, 5, 8, 9]
• B. [2, 5, 8, 9, 1]
• C. [2, 5, 8, 1, 9]
• D. [5, 2, 8, 1, 9]

Câu 3: Độ phức tạp thời gian (Time Complexity) trong trường hợp tốt nhất của thuật toán sắp xếp chèn là gì?

• A. O(n)
• B. O(n log n)
• C. O(n^2)
• D. O(1)

Câu 4: Trong thuật toán sắp xếp chèn, nếu một mảng có n phần tử đã được sắp xếp theo thứ tự giảm dần, khi sắp xếp tăng dần, số lượng phép so sánh và dịch chuyển sẽ như thế nào?

• A. Số phép so sánh là O(n), không có dịch chuyển.
• B. Số phép so sánh là O(n), số dịch chuyển là O(n^2).
• C. Số phép so sánh là O(n^2), không có dịch chuyển.
• D. Số phép so sánh và dịch chuyển đều là O(n^2).

Câu 5: Thuật toán sắp xếp chọn (Selection Sort) hoạt động dựa trên ý tưởng chính nào?

• A. Lặp đi lặp lại việc tìm phần tử nhỏ nhất trong phần chưa sắp xếp và đổi chỗ về đúng vị trí.
• B. Chèn từng phần tử vào đúng vị trí trong một mảng con đã sắp xếp.
• C. So sánh và hoán đổi các cặp phần tử liền kề cho đến khi mảng được sắp xếp.
• D. Chia mảng thành các mảng con nhỏ hơn và sắp xếp chúng.

Câu 6: Cho mảng B = [7, 3, 9, 1, 5]. Áp dụng thuật toán sắp xếp chọn, trạng thái của mảng sau khi hoàn thành vòng lặp ngoài thứ nhất là gì?

• A. [3, 7, 9, 1, 5]
• B. [1, 3, 9, 7, 5]
• C. [1, 3, 5, 7, 9]
• D. [7, 3, 9, 1, 5]

Câu 7: Độ phức tạp thời gian trong trường hợp xấu nhất của thuật toán sắp xếp chọn là gì?

• A. O(n)
• B. O(n log n)
• C. O(n^2)
• D. O(n!)

Câu 8: Điểm khác biệt cốt lõi về số lượng phép hoán đổi (swap) giữa thuật toán sắp xếp chèn và sắp xếp chọn trong trường hợp tổng quát là gì?

• A. Sắp xếp chèn luôn ít hoán đổi hơn sắp xếp chọn.
• B. Sắp xếp chọn luôn ít hoán đổi hơn sắp xếp chèn.
• C. Cả hai thuật toán đều thực hiện cùng số lượng hoán đổi trong mọi trường hợp.
• D. Sắp xếp chọn thực hiện số lượng hoán đổi cố định (O(n)), trong khi sắp xếp chèn thực hiện số lượng hoán đổi thay đổi tùy trường hợp (có thể lên tới O(n^2)).

Câu 9: Thuật toán sắp xếp nổi bọt (Bubble Sort) hoạt động dựa trên ý tưởng chính nào?

• A. Chia mảng thành hai phần và sắp xếp từng phần.
• B. Tìm phần tử lớn nhất hoặc nhỏ nhất và đưa về đúng vị trí.
• C. Lặp đi lặp lại việc so sánh và hoán đổi các cặp phần tử liền kề.
• D. Chèn từng phần tử vào phần đã sắp xếp.

Câu 10: Cho mảng C = [4, 1, 6, 3]. Áp dụng thuật toán sắp xếp nổi bọt (để sắp xếp tăng dần), trạng thái của mảng sau khi hoàn thành vòng lặp ngoài thứ nhất là gì?

• A. [1, 4, 3, 6]
• B. [1, 3, 4, 6]
• C. [4, 1, 6, 3]
• D. [1, 6, 4, 3]

Câu 11: Độ phức tạp thời gian trong trường hợp tốt nhất của thuật toán sắp xếp nổi bọt là gì?

• A. O(n)
• B. O(n log n)
• C. O(n^2)
• D. O(1)

Câu 12: Thuật toán nào trong số các thuật toán sắp xếp đơn giản (chèn, chọn, nổi bọt) có số lượng phép hoán đổi ít nhất trong trường hợp xấu nhất?

• A. Sắp xếp chèn
• B. Sắp xếp chọn
• C. Sắp xếp nổi bọt
• D. Cả ba đều có số hoán đổi như nhau trong trường hợp xấu nhất.

Câu 13: Đối với một mảng dữ liệu gần như đã được sắp xếp, thuật toán sắp xếp đơn giản nào có khả năng hoạt động hiệu quả nhất?

• A. Sắp xếp chèn
• B. Sắp xếp chọn
• C. Sắp xếp nổi bọt (không dùng cờ hiệu)
• D. Hiệu quả như nhau đối với cả ba thuật toán.

Câu 14: Đặc điểm nào sau đây là ĐÚNG khi so sánh thuật toán sắp xếp chèn và sắp xếp chọn?

• A. Sắp xếp chọn có trường hợp tốt nhất hiệu quả hơn sắp xếp chèn.
• B. Sắp xếp chèn không phải là thuật toán tại chỗ (in-place).
• C. Sắp xếp chọn là thuật toán ổn định (stable).
• D. Sắp xếp chèn có thể hiệu quả hơn sắp xếp chọn đối với dữ liệu gần sắp xếp.

Câu 15: Đặc điểm nào sau đây là ĐÚNG về thuật toán sắp xếp nổi bọt?

• A. Là thuật toán tại chỗ (in-place).
• B. Có độ phức tạp thời gian trung bình là O(n log n).
• C. Không phải là thuật toán ổn định (stable).
• D. Số lượng phép hoán đổi luôn ít hơn sắp xếp chọn.

Câu 16: Tại sao thuật toán sắp xếp chọn được coi là không ổn định (unstable)?

• A. Vì độ phức tạp thời gian của nó là O(n^2).
• B. Vì nó sử dụng bộ nhớ phụ đáng kể.
• C. Vì nó có thể thay đổi thứ tự tương đối của các phần tử bằng nhau.
• D. Vì nó thực hiện nhiều phép hoán đổi.

Câu 17: Cho mảng D = [6, 4, 2, 8]. Áp dụng thuật toán sắp xếp chèn, trạng thái của mảng sau khi xử lý xong phần tử thứ 2 (giá trị 4) là gì?

• A. [2, 4, 6, 8]
• B. [6, 4, 2, 8]
• C. [4, 2, 6, 8]
• D. [4, 6, 2, 8]

Câu 18: Cho mảng E = [5, 1, 4, 2, 8]. Áp dụng thuật toán sắp xếp chọn, trạng thái của mảng sau khi hoàn thành vòng lặp ngoài thứ hai là gì?

• A. [1, 5, 4, 2, 8]
• B. [1, 2, 5, 4, 8]
• C. [1, 4, 5, 2, 8]
• D. [1, 2, 4, 5, 8]

Câu 19: Cho mảng F = [3, 1, 4, 2]. Áp dụng thuật toán sắp xếp nổi bọt (sắp xếp tăng dần), trạng thái của mảng sau khi kết thúc lần duyệt (pass) thứ hai của vòng lặp ngoài là gì?

• A. [1, 3, 2, 4]
• B. [1, 2, 3, 4]
• C. [1, 4, 2, 3]
• D. [3, 1, 4, 2]

Câu 20: Khi phân tích hiệu quả của thuật toán sắp xếp, yếu tố nào sau đây thường được coi là quan trọng nhất?

• A. Độ phức tạp thời gian (Time Complexity).
• B. Màu sắc của giao diện chương trình.
• C. Tên của lập trình viên.
• D. Số dòng code của thuật toán.

Câu 21: Thuật toán nào trong ba thuật toán đơn giản (chèn, chọn, nổi bọt) yêu cầu nhiều phép so sánh nhất trong trường hợp xấu nhất?

• A. Sắp xếp chèn
• B. Sắp xếp chọn
• C. Sắp xếp nổi bọt
• D. Cả ba đều xấp xỉ như nhau trong trường hợp xấu nhất.

Câu 22: Trong thuật toán sắp xếp chèn, phần đã sắp xếp của mảng được xây dựng từ đâu?

• A. Từ đầu mảng, mở rộng dần về phía cuối.
• B. Từ cuối mảng, thu hẹp dần về phía đầu.
• C. Từ giữa mảng, mở rộng ra hai phía.
• D. Được tạo ra trong một mảng phụ khác.

Câu 23: Trong thuật toán sắp xếp chọn, sau mỗi lần lặp của vòng lặp ngoài, điều gì được đảm bảo?

• A. Mảng con chưa sắp xếp được thu nhỏ lại một nửa.
• B. Tất cả các phần tử đã được so sánh ít nhất một lần.
• C. Một phần tử được đặt vào đúng vị trí cuối cùng của nó trong mảng đã sắp xếp.
• D. Không có cặp phần tử liền kề nào không đúng thứ tự.

Câu 24: Thuật toán sắp xếp nào trong ba thuật toán đơn giản (chèn, chọn, nổi bọt) có thể dừng sớm nhất nếu mảng đã được sắp xếp hoàn toàn ngay từ đầu?

• A. Sắp xếp chọn
• B. Sắp xếp nổi bọt (không dùng cờ hiệu)
• C. Chỉ sắp xếp chèn
• D. Sắp xếp chèn và Sắp xếp nổi bọt (với cờ hiệu)

Câu 25: Một ưu điểm của thuật toán sắp xếp chọn so với sắp xếp chèn và nổi bọt là gì?

• A. Hiệu quả hơn trên dữ liệu gần sắp xếp.
• B. Số lượng phép hoán đổi ít nhất trong mọi trường hợp.
• C. Có độ phức tạp thời gian tốt nhất là O(n).
• D. Là thuật toán ổn định (stable).

Câu 26: Tại sao các thuật toán sắp xếp đơn giản (chèn, chọn, nổi bọt) thường không được sử dụng cho các tập dữ liệu rất lớn trong thực tế?

• A. Độ phức tạp thời gian trung bình và xấu nhất là O(n^2), kém hiệu quả với dữ liệu lớn.
• B. Chúng sử dụng quá nhiều bộ nhớ phụ.
• C. Chúng không phải là thuật toán ổn định.
• D. Chúng chỉ hoạt động với các kiểu dữ liệu số.

Câu 27: Trong thuật toán sắp xếp nổi bọt, sau mỗi lần duyệt qua mảng (pass), phần tử nào được đảm bảo ở đúng vị trí cuối cùng của nó?

• A. Phần tử nhỏ nhất.
• B. Phần tử lớn nhất trong phần chưa sắp xếp.
• C. Phần tử đầu tiên của mảng.
• D. Phần tử ở giữa của mảng.

Câu 28: Cho mảng G = [8, 5, 2, 9, 3]. Áp dụng thuật toán sắp xếp chèn. Sau khi hoàn thành việc chèn phần tử có giá trị 2 vào phần đã sắp xếp, mảng sẽ có trạng thái như thế nào?

• A. [2, 5, 8, 9, 3]
• B. [5, 8, 2, 9, 3]
• C. [2, 8, 5, 9, 3]
• D. [8, 5, 2, 9, 3]

Câu 29: Thuật toán sắp xếp nào trong ba thuật toán đơn giản có thể được triển khai sao cho nó là thuật toán ổn định (stable)?

• A. Chỉ sắp xếp chọn.
• B. Chỉ sắp xếp nổi bọt.
• C. Chỉ sắp xếp chèn.
• D. Sắp xếp chèn và Sắp xếp nổi bọt.

Câu 30: Khi nào thì việc sử dụng một trong các thuật toán sắp xếp đơn giản (chèn, chọn, nổi bọt) có thể được chấp nhận hoặc thậm chí là lựa chọn tốt?

• A. Khi cần sắp xếp tập dữ liệu cực lớn để đạt hiệu quả cao nhất.
• B. Khi cần một thuật toán có độ phức tạp thời gian O(n log n).
• C. Khi tập dữ liệu cần sắp xếp có kích thước nhỏ hoặc khi yêu cầu cài đặt đơn giản.
• D. Khi dữ liệu đầu vào luôn được sắp xếp ngược lại.

Câu 1: Thuật toán sắp xếp chèn (Insertion Sort) hoạt động dựa trên ý tưởng chính nào?

• A. Tìm phần tử nhỏ nhất trong phần chưa sắp xếp và đưa về đầu.
• B. So sánh và hoán đổi các cặp phần tử liền kề nếu sai thứ tự.
• C. Chèn từng phần tử vào đúng vị trí trong phần mảng con đã sắp xếp.
• D. Chia mảng thành hai nửa và sắp xếp độc lập.

Câu 2: Cho mảng A = [7, 3, 8, 1, 5]. Sau khi thực hiện xong pass thứ 2 của vòng lặp chính (tức là sau khi phần tử "8" đã được xử lý) trong thuật toán sắp xếp chèn (sắp xếp tăng dần), mảng A sẽ có trạng thái như thế nào?

• A. [3, 7, 8, 1, 5]
• B. [3, 7, 1, 8, 5]
• C. [1, 3, 5, 7, 8]
• D. [7, 3, 8, 1, 5]

Câu 3: Đối với một mảng có n phần tử đã được sắp xếp theo thứ tự tăng dần, số lượng phép so sánh phần tử cần thiết trong trường hợp tốt nhất của thuật toán sắp xếp chèn là bao nhiêu?

• A. O(n^2)
• B. n*(n-1)/2
• C. 0
• D. n-1

Câu 4: Thuật toán sắp xếp chọn (Selection Sort) hoạt động dựa trên ý tưởng chính nào?

• A. So sánh và hoán đổi các cặp phần tử liền kề nếu sai thứ tự.
• B. Tìm phần tử nhỏ nhất trong phần chưa sắp xếp và đưa về đúng vị trí.
• C. Chèn từng phần tử vào đúng vị trí trong phần mảng con đã sắp xếp.
• D. Chia mảng thành hai nửa và sắp xếp độc lập.

Câu 5: Cho mảng B = [6, 1, 8, 3, 5]. Sau khi thực hiện xong pass thứ 1 của vòng lặp chính trong thuật toán sắp xếp chọn (sắp xếp tăng dần), mảng B sẽ có trạng thái như thế nào?

• A. [1, 3, 5, 6, 8]
• B. [6, 1, 8, 3, 5]
• C. [1, 6, 8, 3, 5]
• D. [1, 3, 8, 6, 5]

Câu 6: Độ phức tạp thời gian trong trường hợp xấu nhất của thuật toán sắp xếp chọn (Selection Sort) là gì?

• A. O(n)
• B. O(n^2)
• C. O(n log n)
• D. O(1)

Câu 7: Thuật toán sắp xếp nổi bọt (Bubble Sort) hoạt động dựa trên ý tưởng chính nào?

• A. So sánh và hoán đổi các cặp phần tử liền kề nếu sai thứ tự.
• B. Tìm phần tử nhỏ nhất trong phần chưa sắp xếp và đưa về đúng vị trí.
• C. Chèn từng phần tử vào đúng vị trí trong phần mảng con đã sắp xếp.
• D. Chia mảng thành hai nửa và sắp xếp độc lập.

Câu 8: Cho mảng C = [4, 2, 7, 1, 5]. Sau khi thực hiện xong pass thứ 1 của vòng lặp chính trong thuật toán sắp xếp nổi bọt (sắp xếp tăng dần), mảng C sẽ có trạng thái như thế nào?

• A. [1, 2, 4, 5, 7]
• B. [2, 4, 1, 5, 7]
• C. [4, 2, 7, 1, 5]
• D. [2, 1, 4, 5, 7]

Câu 9: Trong trường hợp tốt nhất (mảng đã được sắp xếp), độ phức tạp thời gian của thuật toán sắp xếp nổi bọt (Bubble Sort) là gì?

• A. O(n)
• B. O(n^2)
• C. O(n log n)
• D. O(1)

Câu 10: So sánh giữa thuật toán sắp xếp chèn và sắp xếp chọn về số lượng phép hoán đổi (swap). Phát biểu nào sau đây là đúng?

• A. Sắp xếp chèn luôn thực hiện ít phép hoán đổi hơn sắp xếp chọn.
• B. Sắp xếp chọn luôn thực hiện nhiều phép hoán đổi hơn sắp xếp chèn.
• C. Sắp xếp chọn thực hiện số lượng phép hoán đổi ít hơn đáng kể so với sắp xếp chèn và nổi bọt trong hầu hết các trường hợp.
• D. Cả hai thuật toán đều thực hiện cùng số lượng phép hoán đổi.

Câu 11: Thuật toán nào trong ba thuật toán đơn giản (Chèn, Chọn, Nổi bọt) phù hợp nhất để sắp xếp một danh sách dữ liệu gần như đã được sắp xếp?

• A. Sắp xếp chèn
• B. Sắp xếp chọn
• C. Sắp xếp nổi bọt
• D. Cả ba đều có hiệu suất tương đương trong trường hợp này.

Câu 12: Phát biểu nào sau đây là SAI về thuật toán sắp xếp chọn (Selection Sort)?

• A. Luôn có độ phức tạp thời gian O(n^2) trong cả trường hợp tốt nhất và xấu nhất.
• B. Thực hiện số lượng phép hoán đổi tối thiểu so với Chèn và Nổi bọt.
• C. Là một thuật toán sắp xếp tại chỗ (in-place).
• D. Là một thuật toán sắp xếp ổn định (stable).

Câu 13: Thế nào là một thuật toán sắp xếp "ổn định" (stable)?

• A. Thuật toán luôn chạy trong thời gian O(n log n).
• B. Thuật toán giữ nguyên thứ tự ban đầu của các phần tử có giá trị bằng nhau.
• C. Thuật toán chỉ sử dụng một lượng nhỏ bộ nhớ phụ.
• D. Thuật toán hoàn thành việc sắp xếp sau một số pass cố định.

Câu 14: Trong ba thuật toán sắp xếp đơn giản (Chèn, Chọn, Nổi bọt), thuật toán nào KHÔNG đảm bảo tính ổn định?

• A. Sắp xếp chèn
• B. Sắp xếp chọn
• C. Sắp xếp nổi bọt
• D. Cả ba thuật toán đều ổn định.

Câu 15: Một thuật toán sắp xếp được gọi là "tại chỗ" (in-place) nếu...

• A. Nó chỉ sử dụng một lượng bộ nhớ phụ không đáng kể (thường là O(1)).
• B. Nó luôn chạy trong thời gian O(n log n).
• C. Nó giữ nguyên thứ tự ban đầu của các phần tử có giá trị bằng nhau.
• D. Nó chia mảng thành các phần nhỏ hơn để sắp xếp.

Câu 16: Cả ba thuật toán sắp xếp đơn giản (Chèn, Chọn, Nổi bọt) đều là thuật toán "tại chỗ" (in-place). Điều này có ý nghĩa gì đối với việc sử dụng bộ nhớ của chúng?

• A. Chúng cần bộ nhớ phụ tỷ lệ thuận với số lượng phần tử (O(n)).
• B. Chúng cần bộ nhớ phụ tỷ lệ thuận với bình phương số lượng phần tử (O(n^2)).
• C. Chúng chỉ cần một lượng bộ nhớ phụ cố định, không phụ thuộc vào kích thước mảng (O(1)).
• D. Chúng cần bộ nhớ phụ cho việc đệ quy.

Câu 17: Giả sử bạn cần sắp xếp một mảng rất lớn nhưng bạn biết rằng mảng đó chỉ có một vài phần tử bị sai vị trí so với thứ tự đã sắp xếp. Thuật toán nào trong ba thuật toán đơn giản có khả năng cho hiệu suất tốt nhất trong trường hợp này?

• A. Sắp xếp chèn
• B. Sắp xếp chọn
• C. Sắp xếp nổi bọt
• D. Hiệu suất của cả ba đều như nhau trong trường hợp này.

Câu 18: Trong thuật toán sắp xếp chèn, khi chèn một phần tử vào phần mảng đã sắp xếp, các phần tử lớn hơn nó sẽ được dịch chuyển sang phải. Quá trình dịch chuyển này có mục đích gì?

• A. Để hoán đổi vị trí phần tử đang xét với phần tử nhỏ nhất.
• B. Để tạo không gian cho phần tử đang xét được chèn vào đúng vị trí.
• C. Để đưa phần tử lớn nhất về cuối mảng.
• D. Để kiểm tra xem mảng đã được sắp xếp hoàn toàn chưa.

Câu 19: Thuật toán sắp xếp nổi bọt được gọi là "nổi bọt" vì...

• A. Nó sử dụng ít bộ nhớ nhất.
• B. Nó có hiệu suất tốt nhất trong trường hợp tốt nhất.
• C. Nó chèn từng phần tử vào vị trí đúng.
• D. Các phần tử lớn hơn (hoặc nhỏ hơn) dần di chuyển đến vị trí cuối cùng (hoặc đầu tiên) sau mỗi pass.

Câu 20: Cho mảng D = [5, 2, 4, 6, 1, 3]. Áp dụng thuật toán sắp xếp chọn. Sau khi hoàn thành pass thứ 3 (tức là 3 phần tử đầu tiên đã được đặt đúng vị trí), mảng D sẽ trông như thế nào?

• A. [1, 2, 3, 6, 5, 4]
• B. [1, 2, 4, 5, 3, 6]
• C. [1, 2, 3, 4, 5, 6]
• D. [1, 2, 5, 6, 4, 3]

Câu 21: Mặc dù có độ phức tạp thời gian xấu nhất là O(n^2), thuật toán sắp xếp chèn vẫn có thể được ưu tiên sử dụng trong một số trường hợp thực tế. Trường hợp nào sau đây là ví dụ điển hình?

• A. Sắp xếp một mảng rất lớn (hàng triệu phần tử) chưa sắp xếp.
• B. Khi cần đảm bảo độ phức tạp thời gian luôn là O(n log n).
• C. Khi cần sắp xếp dữ liệu trên các hệ thống phân tán.
• D. Sắp xếp một tập dữ liệu nhỏ (ví dụ: dưới 20 phần tử) hoặc một tập dữ liệu gần như đã sắp xếp.

Câu 22: Xét mảng E = [8, 5, 2, 6, 9, 3]. Áp dụng thuật toán sắp xếp nổi bọt (sắp xếp tăng dần). Sau khi hoàn thành pass thứ 2 của vòng lặp chính, mảng E sẽ trông như thế nào?

• A. [2, 3, 5, 6, 8, 9]
• B. [2, 5, 3, 6, 8, 9]
• C. [2, 5, 6, 3, 8, 9]
• D. [5, 2, 6, 8, 3, 9]

Câu 23: Thuật toán nào trong ba thuật toán đơn giản (Chèn, Chọn, Nổi bọt) có số lượng phép so sánh cố định là n(n-1)/2 trong cả trường hợp tốt nhất và xấu nhất?

• A. Sắp xếp chèn
• B. Sắp xếp chọn
• C. Sắp xếp nổi bọt
• D. Không có thuật toán nào trong ba thuật toán này có tính chất đó.

Câu 24: Tại sao thuật toán sắp xếp chọn (Selection Sort) lại thực hiện ít phép hoán đổi hơn so với sắp xếp chèn (Insertion Sort) và sắp xếp nổi bọt (Bubble Sort) trong trường hợp xấu nhất?

• A. Vì nó chỉ thực hiện một phép hoán đổi duy nhất sau khi tìm thấy phần tử nhỏ nhất trong mỗi pass.
• B. Vì nó sử dụng bộ nhớ phụ ít hơn.
• C. Vì nó có độ phức tạp thời gian tốt hơn.
• D. Vì nó không cần so sánh các phần tử liền kề.

Câu 25: Bạn được yêu cầu sắp xếp một mảng dữ liệu có các phần tử trùng lặp và điều quan trọng là thứ tự ban đầu của các phần tử bằng nhau phải được giữ nguyên (tức là cần thuật toán ổn định). Thuật toán nào trong ba thuật toán đơn giản nên được ưu tiên?

• A. Sắp xếp chọn
• B. Cả ba thuật toán đều không đảm bảo tính ổn định.
• C. Sắp xếp chọn hoặc Sắp xếp nổi bọt.
• D. Sắp xếp chèn hoặc Sắp xếp nổi bọt.

Câu 26: Xét thuật toán sắp xếp nổi bọt. Nếu trong một pass của vòng lặp chính, không có bất kỳ cặp phần tử nào được hoán đổi, điều này có ý nghĩa gì?

• A. Phần tử lớn nhất đã được đưa về cuối mảng.
• B. Mảng đã được sắp xếp hoàn toàn và thuật toán có thể dừng lại.
• C. Cần phải thực hiện thêm một pass nữa để kiểm tra.
• D. Thuật toán đang ở trường hợp xấu nhất.

Câu 27: Thuật toán sắp xếp chèn có thể được coi là mô phỏng cách con người sắp xếp bài trong bộ bài khi chơi. Hãy phân tích sự tương đồng này.

• A. Giống như việc cầm một bộ bài đã sắp xếp và lần lượt rút từng lá bài mới để chèn vào đúng vị trí trong bộ bài đang cầm.
• B. Giống như việc tìm lá bài nhỏ nhất trong bộ bài chưa sắp xếp và đặt nó sang một bên.
• C. Giống như việc so sánh từng cặp lá bài liền kề và đổi chỗ nếu cần.
• D. Giống như việc chia bộ bài làm đôi và sắp xếp từng nửa.

Câu 28: Phát biểu nào sau đây là đúng khi so sánh hiệu suất của ba thuật toán sắp xếp đơn giản (Chèn, Chọn, Nổi bọt) trong trường hợp xấu nhất?

• A. Sắp xếp chèn luôn nhanh hơn sắp xếp chọn và nổi bọt.
• B. Cả ba thuật toán đều có độ phức tạp thời gian O(n^2).
• C. Sắp xếp chọn là nhanh nhất trong ba thuật toán.
• D. Sắp xếp nổi bọt là nhanh nhất trong ba thuật toán.

Câu 29: Giả sử bạn cần sắp xếp một mảng các đối tượng phức tạp (ví dụ: các bản ghi sinh viên) và chi phí cho mỗi lần hoán đổi (swap) là rất lớn. Thuật toán nào trong ba thuật toán đơn giản (Chèn, Chọn, Nổi bọt) nên được xem xét ưu tiên để giảm thiểu số lần hoán đổi?

• A. Sắp xếp chèn
• B. Sắp xếp chọn
• C. Sắp xếp nổi bọt
• D. Cả ba đều thực hiện số lượng hoán đổi tương đương.

Câu 30: Đâu là một trong những lý do chính khiến các thuật toán sắp xếp đơn giản như Chèn, Chọn, Nổi bọt ít được sử dụng cho các tập dữ liệu lớn trong thực tế so với các thuật toán phức tạp hơn (ví dụ: Merge Sort, Quick Sort)?

• A. Độ phức tạp thời gian O(n^2) trong trường hợp xấu nhất/trung bình khiến chúng chậm với dữ liệu lớn.
• B. Chúng yêu cầu quá nhiều bộ nhớ phụ.
• C. Chúng không đảm bảo tính ổn định.
• D. Chúng rất khó triển khai trên máy tính.

Câu 1: Khi thực hiện thuật toán sắp xếp chèn (Insertion Sort) trên dãy số [5, 2, 8, 1, 9], sau khi xử lý xong phần tử thứ 3 (số 8), dãy số sẽ có trạng thái như thế nào? (Giả sử dãy con đã sắp xếp ban đầu chỉ gồm phần tử đầu tiên)

• A. [2, 5, 1, 8, 9]
• B. [1, 2, 5, 8, 9]
• C. [2, 5, 8, 1, 9]
• D. [5, 2, 8, 1, 9]

Câu 2: Thuật toán sắp xếp chọn (Selection Sort) hoạt động dựa trên ý tưởng chính nào?

• A. So sánh các phần tử kề nhau và hoán đổi nếu sai thứ tự.
• B. Tìm phần tử nhỏ nhất (hoặc lớn nhất) trong phần chưa được sắp xếp và đưa về đúng vị trí.
• C. Chèn từng phần tử vào vị trí thích hợp trong dãy con đã sắp xếp.
• D. Chia dãy thành hai nửa và sắp xếp đệ quy từng nửa.

Câu 3: Độ phức tạp thời gian trong trường hợp xấu nhất của thuật toán sắp xếp nổi bọt (Bubble Sort) là O(n^2). Điều này có ý nghĩa gì đối với hiệu suất của thuật toán khi xử lý một dãy dữ liệu rất lớn?

• A. Thời gian chạy tăng lên rất nhanh (tỉ lệ với bình phương số lượng phần tử), khiến thuật toán trở nên chậm chạp.
• B. Thời gian chạy tăng tuyến tính với số lượng phần tử, thuật toán vẫn hiệu quả.
• C. Thuật toán đạt hiệu suất cao nhất khi dữ liệu lớn.
• D. Độ phức tạp O(n^2) chỉ xảy ra trong trường hợp dữ liệu đã được sắp xếp.

Câu 4: Giả sử bạn có một dãy dữ liệu gần như đã được sắp xếp. Thuật toán sắp xếp đơn giản nào sau đây có khả năng cho hiệu suất tốt nhất trong trường hợp này?

• A. Sắp xếp chọn (Selection Sort)
• B. Sắp xếp nổi bọt (Bubble Sort) mà không có cờ tối ưu hóa
• C. Sắp xếp chèn (Insertion Sort)
• D. Tất cả đều có hiệu suất tương đương O(n^2).

Câu 5: Khi sắp xếp dãy số [7, 4, 1, 9, 3] bằng thuật toán sắp xếp chọn (Selection Sort) để sắp xếp tăng dần, trạng thái của dãy sau khi hoàn thành vòng lặp ngoài thứ nhất (tức là sau khi phần tử nhỏ nhất được đưa về vị trí đầu tiên) là gì?

• A. [4, 7, 1, 9, 3]
• B. [1, 4, 7, 9, 3]
• C. [1, 7, 4, 9, 3]
• D. [3, 4, 1, 9, 7]

Câu 6: Thuật toán sắp xếp nào trong ba thuật toán đơn giản (Nổi bọt, Chọn, Chèn) được coi là "ổn định" (stable)? (Thuật toán ổn định giữ nguyên thứ tự tương đối của các phần tử bằng nhau).

• 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 chèn (Insertion Sort)
• D. Sắp xếp nổi bọt và Sắp xếp chèn.

Câu 7: Xét thuật toán sắp xếp nổi bọt (Bubble Sort). Phát biểu nào sau đây mô tả đúng nhất công việc của vòng lặp bên trong (inner loop) trong mỗi bước của vòng lặp bên ngoài (outer loop)?

• A. Duyệt qua phần chưa sắp xếp của dãy, so sánh các cặp phần tử liền kề và đưa phần tử lớn nhất về cuối phần chưa sắp xếp.
• B. Tìm phần tử nhỏ nhất trong phần chưa sắp xếp và hoán đổi nó với phần tử đầu tiên của phần chưa sắp xếp.
• C. Chèn phần tử hiện tại vào vị trí đúng trong phần đã sắp xếp.
• D. Chia dãy thành hai nửa và sắp xếp từng nửa.

Câu 8: Tại sao thuật toán sắp xếp chọn (Selection Sort) luôn có độ phức tạp thời gian O(n^2) ở cả trường hợp tốt nhất, xấu nhất và trung bình?

• A. Vì số lần hoán đổi luôn là n-1.
• B. Vì thuật toán sử dụng kỹ thuật chia để trị.
• C. Vì thuật toán luôn phải duyệt qua toàn bộ phần chưa sắp xếp để tìm phần tử nhỏ nhất trong mỗi bước, bất kể trạng thái ban đầu của dãy.
• D. Vì nó là thuật toán ổn định.

Câu 9: Thuật toán sắp xếp chèn (Insertion Sort) có thể được triển khai để dừng sớm nếu dãy đã được sắp xếp. Điều này dẫn đến độ phức tạp thời gian tốt nhất là O(n). Điều kiện để thuật toán dừng sớm (với cờ tối ưu hóa) là gì?

• A. Khi vòng lặp bên ngoài hoàn thành.
• B. Khi trong một lần duyệt qua phần chưa sắp xếp, không có bất kỳ sự dịch chuyển hoặc hoán đổi nào được thực hiện.
• C. Khi phần tử đang chèn nhỏ hơn tất cả các phần tử trong phần đã sắp xếp.
• D. Khi số lần so sánh đạt đến n-1.

Câu 10: So sánh sắp xếp nổi bọt (Bubble Sort) và sắp xếp chèn (Insertion Sort). Điểm khác biệt cơ bản trong cách chúng xử lý các phần tử để đưa về đúng vị trí là gì?

• A. Bubble Sort sử dụng hoán đổi, còn Insertion Sort sử dụng dịch chuyển.
• B. Bubble Sort đưa phần tử lớn nhất về cuối, còn Insertion Sort đưa phần tử nhỏ nhất về đầu.
• C. Bubble Sort tập trung vào việc đẩy phần tử lớn nhất (hoặc nhỏ nhất) đến đúng vị trí bằng cách so sánh kề nhau, trong khi Insertion Sort tập trung vào việc đặt từng phần tử vào vị trí thích hợp trong dãy con đã sắp xếp.
• D. Bubble Sort hiệu quả với dữ liệu gần sắp xếp, còn Insertion Sort không.

Câu 11: Cho dãy số [6, 3, 8, 2]. Áp dụng thuật toán sắp xếp nổi bọt (Bubble Sort) để sắp xếp tăng dần. Trạng thái của dãy sau khi hoàn thành lần duyệt đầu tiên của vòng lặp bên ngoài là gì?

• A. [3, 6, 2, 8]
• B. [6, 3, 8, 2]
• C. [2, 3, 6, 8]
• D. [3, 2, 6, 8]

Câu 12: Thuật toán sắp xếp nào trong ba thuật toán đơn giản (Nổi bọt, Chọn, Chèn) thực hiện số lượng phép hoán đổi (swap) ít nhất trong trường hợp trung bình và xấu nhất?

• 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 chèn (Insertion Sort)
• D. Cả ba đều thực hiện số lượng hoán đổi tương đương.

Câu 13: Tại sao thuật toán sắp xếp chèn (Insertion Sort) lại được coi là hiệu quả cho các dãy dữ liệu có kích thước nhỏ, mặc dù độ phức tạp thời gian xấu nhất là O(n^2)?

• A. Vì nó có độ phức tạp không gian O(1).
• B. Vì số phép so sánh luôn ít hơn các thuật toán khác.
• C. Vì nó luôn ổn định.
• D. Vì hằng số ẩn trong ký hiệu O lớn (big O) nhỏ, và số phép so sánh/dịch chuyển thực tế ít hơn O(n^2) đáng kể trong trường hợp trung bình hoặc gần sắp xếp, làm cho nó nhanh hơn các thuật toán O(n^2) khác trên dữ liệu nhỏ.

Câu 14: Trong thuật toán sắp xếp chèn (Insertion Sort), khi chèn một phần tử vào dãy con đã sắp xếp, các phần tử lớn hơn nó sẽ được xử lý như thế nào để tạo chỗ trống?

• A. Chúng bị loại bỏ.
• B. Chúng được dịch chuyển sang phải một vị trí.
• C. Chúng được hoán đổi với phần tử đang chèn.
• D. Chúng được dịch chuyển sang trái một vị trí.

Câu 15: Một nhà phát triển cần chọn một thuật toán sắp xếp đơn giản để sử dụng trong một ứng dụng nhúng trên thiết bị có bộ nhớ rất hạn chế. Tiêu chí quan trọng nhất là bộ nhớ phụ sử dụng phải tối thiểu. Thuật toán nào trong ba thuật toán đơn giản là phù hợp nhất?

• A. Sắp xếp nổi bọt (Bubble Sort)
• B. Sắp xếp chọn (Selection Sort)
• C. Sắp xếp chèn (Insertion Sort)
• D. Cả ba thuật toán (Nổi bọt, Chọn, Chèn) đều là thuật toán "tại chỗ" (in-place) và sử dụng bộ nhớ phụ O(1), nên đều phù hợp về mặt không gian bộ nhớ.

Câu 16: Xét dãy số [10, 9, 8, 7]. Nếu sử dụng thuật toán sắp xếp nổi bọt (Bubble Sort) có cờ tối ưu hóa để sắp xếp tăng dần, thuật toán sẽ dừng lại sau bao nhiêu lần duyệt qua toàn bộ dãy (vòng lặp bên ngoài)?

• A. 1 lần
• B. 3 lần
• C. 4 lần
• D. 6 lần

Câu 17: Trong thuật toán sắp xếp chọn (Selection Sort), tại sao phần tử nhỏ nhất của phần chưa sắp xếp luôn được đặt ở vị trí đầu tiên của phần đó trong mỗi bước lặp?

• A. Vì nó được so sánh với tất cả các phần tử khác và hoán đổi nếu nhỏ hơn.
• B. Vì nó được chèn vào vị trí đầu tiên của dãy.
• C. Vì vị trí đầu tiên của phần chưa sắp xếp chính là vị trí đúng của phần tử nhỏ nhất trong toàn bộ dãy sau khi hoàn thành bước đó.
• D. Vì thuật toán luôn hoán đổi phần tử đầu tiên với phần tử cuối cùng của phần chưa sắp xếp.

Câu 18: Sự khác biệt chính về hiệu suất giữa sắp xếp chèn (Insertion Sort) và sắp xếp chọn (Selection Sort) nằm ở đâu?

• A. Sắp xếp chèn có thể có hiệu suất tốt hơn đáng kể (O(n)) trong trường hợp tốt nhất (dãy gần sắp xếp), trong khi sắp xếp chọn luôn là O(n^2).
• B. Sắp xếp chọn sử dụng ít bộ nhớ hơn sắp xếp chèn.
• C. Sắp xếp chèn thực hiện ít phép so sánh hơn sắp xếp chọn trong mọi trường hợp.
• D. Sắp xếp chọn là thuật toán ổn định, còn sắp xếp chèn thì không.

Câu 19: Khi phân tích độ phức tạp của thuật toán sắp xếp chèn (Insertion Sort), số lượng phép so sánh trong trường hợp xấu nhất (dãy sắp xếp ngược) là bao nhiêu?

• A. O(n)
• B. Khoảng n(n-1)/2, tức là O(n^2)
• C. O(n log n)
• D. O(1)

Câu 20: Xét dãy số [4, 1, 3, 2]. Sau khi thực hiện 2 lần duyệt đầu tiên của vòng lặp bên ngoài bằng thuật toán sắp xếp nổi bọt (Bubble Sort) để sắp xếp tăng dần, dãy số sẽ trông như thế nào?

• A. [1, 2, 3, 4]
• B. [1, 3, 2, 4]
• C. [1, 3, 2, 4] (sau lần 1: [1, 3, 2, 4], sau lần 2: [1, 3, 2, 4])
• D. [4, 1, 3, 2]

Câu 21: Giả sử bạn cần sắp xếp một danh sách các đối tượng phức tạp (ví dụ: hồ sơ sinh viên), mà việc hoán đổi chúng tốn kém nhiều thời gian và tài nguyên hơn việc so sánh. Thuật toán sắp xếp đơn giản nào trong ba loại có lợi thế hơn về số lượng phép hoán đổi?

• 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 chèn (Insertion Sort)
• D. Cả ba đều thực hiện số lượng hoán đổi tương đương trong trường hợp xấu nhất.

Câu 22: Phát biểu nào sau đây SAI về thuật toán sắp xếp chèn (Insertion Sort)?

• A. Nó là thuật toán ổn định (stable).
• B. Nó là thuật toán tại chỗ (in-place).
• C. Độ phức tạp thời gian tốt nhất là O(n).
• D. Số lượng phép hoán đổi luôn là O(n^2) trong trường hợp xấu nhất.

Câu 23: Khi áp dụng thuật toán sắp xếp chèn (Insertion Sort) trên dãy [5, 1, 4, 2, 8] để sắp xếp tăng dần, sau khi xử lý xong phần tử thứ 4 (số 2), dãy con đã sắp xếp (từ đầu đến vị trí hiện tại) sẽ là:

• A. [1, 4, 5, 2, 8]
• B. [1, 2, 4, 5, 8]
• C. [1, 4, 2, 5, 8]
• D. [2, 1, 4, 5, 8]

Câu 24: Tại sao thuật toán sắp xếp nổi bọt (Bubble Sort) lại được gọi là "nổi bọt"?

• A. Vì các phần tử nhỏ nhất dần "nổi" lên đầu dãy.
• B. Vì nó sử dụng bọt khí để sắp xếp.
• C. Vì các phần tử lớn nhất dần "nổi" (di chuyển) lên vị trí cuối cùng của phần chưa sắp xếp sau mỗi lần duyệt.
• D. Vì nó có độ phức tạp thời gian "nổi" rất nhanh khi dữ liệu lớn.

Câu 25: Trong các trường hợp nào sau đây, thuật toán sắp xếp chèn (Insertion Sort) có thể là lựa chọn tốt hơn so với sắp xếp chọn (Selection Sort) hoặc nổi bọt (Bubble Sort)?

• A. Khi cần đảm bảo số lượng hoán đổi là tối thiểu.
• B. Khi dữ liệu hoàn toàn ngẫu nhiên và kích thước rất lớn.
• C. Khi tốc độ là yếu tố quan trọng nhất và bộ nhớ không hạn chế.
• D. Khi dữ liệu đầu vào được đảm bảo là gần như đã được sắp xếp.

Câu 26: Xét dãy số [9, 5, 2, 7]. Áp dụng thuật toán sắp xếp chọn (Selection Sort) để sắp xếp tăng dần. Trạng thái của dãy sau khi hoàn thành vòng lặp ngoài thứ hai là gì?

• A. [2, 5, 9, 7]
• B. [2, 5, 7, 9]
• C. [2, 9, 5, 7]
• D. [5, 2, 9, 7]

Câu 27: Thuật toán sắp xếp nào trong ba thuật toán đơn giản (Nổi bọt, Chọn, Chèn) có thể được mô tả là xây dựng dần một dãy con đã sắp xếp từ đầu dãy?

• A. Sắp xếp nổi bọt (Bubble Sort)
• B. Sắp xếp chọn (Selection Sort)
• C. Sắp xếp chèn (Insertion Sort)
• D. Cả ba đều làm như vậy.

Câu 28: Phát biểu nào sau đây là một nhược điểm đáng kể của thuật toán sắp xếp nổi bọt (Bubble Sort) so với các thuật toán sắp xếp hiệu quả hơn (như Quick Sort, Merge Sort - dù không thuộc bài này)?

• A. Hiệu suất kém (O(n^2) trong trường hợp xấu nhất và trung bình) trên các tập dữ liệu lớn.
• B. Sử dụng quá nhiều bộ nhớ phụ.
• C. Không phải là thuật toán ổn định.
• D. Rất khó cài đặt.

Câu 29: Khi so sánh thuật toán sắp xếp chọn (Selection Sort) và sắp xếp nổi bọt (Bubble Sort) trên một dãy ngẫu nhiên có kích thước N, số lượng phép so sánh mà chúng thực hiện trong trường hợp trung bình là:

• A. Selection Sort ít hơn Bubble Sort.
• B. Bubble Sort ít hơn Selection Sort.
• C. Cả hai đều thực hiện số lượng phép so sánh tương đương O(N log N).
• D. Cả hai đều thực hiện số lượng phép so sánh tương đương O(N^2).

Câu 30: Thuật toán sắp xếp nào trong ba thuật toán đơn giản (Nổi bọt, Chọn, Chèn) luôn đảm bảo rằng sau mỗi bước lặp của vòng lặp bên ngoài, phần tử ở vị trí cuối cùng của phần đã được xử lý (phần bên trái) là phần tử nhỏ nhất trong toàn bộ dãy?

• A. Sắp xếp nổi bọt (Bubble Sort)
• B. Sắp xếp chọn (Selection Sort)
• C. Sắp xếp chèn (Insertion Sort)
• D. Không có thuật toán nào trong ba loại này đảm bảo điều đó.

Câu 1: Ý tưởng cốt lõi 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 mảng chưa sắp xếp và đổi chỗ với phần tử đầu tiên của mảng chưa sắp xếp.
• B. So sánh các phần tử liền kề và đổi chỗ nếu chúng sai thứ tự, lặp lại cho đến khi không còn cần đổi chỗ.
• C. Xây dựng mảng đã sắp xếp từng bước bằng cách chèn mỗi phần tử từ mảng đầu vào vào đúng vị trí của nó trong phần đã sắp xếp.
• D. Chia mảng thành hai nửa, sắp xếp từng nửa, sau đó trộn hai nửa đã sắp xếp lại.

Câu 2: Khi áp dụng thuật toán sắp xếp chèn cho mảng A = [5, 2, 8, 1, 9], sau khi phần tử "2" được chèn vào đúng vị trí, mảng A sẽ có trạng thái như thế nào?

• A. [2, 5, 8, 1, 9]
• B. [2, 5, 8, 1, 9]
• C. [5, 2, 8, 1, 9]
• D. [1, 2, 5, 8, 9]

Câu 3: Độ phức tạp thời gian trong trường hợp tốt nhất của thuật toán sắp xếp chèn là gì?

• A. O(n)
• B. O(n log n)
• C. O(n^2)
• D. O(1)

Câu 4: Điều kiện nào của mảng đầu vào dẫn đến trường hợp xấu nhất về thời gian thực hiện của thuật toán sắp xếp chèn?

• A. Mảng đã được sắp xếp theo thứ tự tăng dần.
• B. Tất cả các phần tử trong mảng đều giống nhau.
• C. Mảng là ngẫu nhiên hoàn toàn.
• D. Mảng đã được sắp xếp theo thứ tự giảm dần.

Câu 5: Ý tưởng cốt lõi của thuật toán sắp xếp chọn (Selection Sort) là gì?

• A. Tại mỗi bước, tìm phần tử nhỏ nhất trong phần mảng chưa được sắp xếp và đổi chỗ nó với phần tử đầu tiên của phần mảng chưa sắp xếp đó.
• B. Tại mỗi bước, chèn phần tử hiện tại vào đúng vị trí trong phần mảng đã được sắp xếp.
• C. Lặp đi lặp lại việc so sánh và đổi chỗ các phần tử liền kề nếu chúng sai thứ tự.
• D. Chia mảng thành các mảng con nhỏ hơn và sắp xếp chúng một cách đệ quy.

Câu 6: Khi áp dụng thuật toán sắp xếp chọn cho mảng A = [6, 4, 1, 8, 3], sau vòng lặp đầu tiên (khi phần tử nhỏ nhất đã được đưa về đầu mảng), mảng A sẽ có trạng thái như thế nào?

• A. [1, 3, 4, 6, 8]
• B. [6, 4, 1, 8, 3]
• C. [1, 4, 6, 8, 3]
• D. [1, 4, 3, 8, 6]

Câu 7: Độ phức tạp thời gian trong trường hợp xấu nhất của thuật toán sắp xếp chọn là gì?

• A. O(n)
• B. O(n log n)
• C. O(n^2)
• D. O(n!)

Câu 8: Số lượng phép so sánh của thuật toán sắp xếp chọn trên một mảng có n phần tử là bao nhiêu trong trường hợp tổng quát?

• A. n - 1
• B. n * log(n)
• C. n^2
• D. Khoảng n^2 / 2

Câu 9: Ý tưởng cốt lõi của thuật toán sắp xếp nổi bọt (Bubble Sort) là gì?

• A. Tìm phần tử nhỏ nhất và đưa về đầu mảng.
• B. Chèn phần tử vào đúng vị trí trong mảng con đã sắp xếp.
• C. Chia mảng và trộn các mảng con đã sắp xếp.
• D. Lặp đi lặp lại việc so sánh và đổi chỗ các phần tử liền kề sai thứ tự.

Câu 10: Khi áp dụng thuật toán sắp xếp nổi bọt cho mảng A = [7, 1, 5, 2, 4], sau pass (lượt duyệt) đầu tiên, mảng A sẽ có trạng thái như thế nào?

• A. [1, 5, 2, 4, 7]
• B. [1, 2, 4, 5, 7]
• C. [7, 1, 5, 2, 4]
• D. [1, 7, 5, 2, 4]

Câu 11: Độ phức tạp thời gian trong trường hợp tốt nhất của thuật toán sắp xếp nổi bọt có sử dụng cờ hiệu (flag) để dừng sớm là gì?

• A. O(n log n)
• B. O(n)
• C. O(n^2)
• D. O(1)

Câu 12: Thuật toán sắp xếp nào trong số các thuật toán đơn giản (chèn, chọn, nổi bọt) luôn có độ phức tạp thời gian O(n^2) bất kể dữ liệu đầu vào?

• A. Sắp xếp chèn (Insertion Sort)
• B. Sắp xếp chọn (Selection Sort)
• C. Sắp xếp nổi bọt (Bubble Sort)
• D. Cả ba thuật toán.

Câu 13: Thuật toán sắp xếp nào trong ba thuật toán đơn giản được coi là "ổn định" (stable), tức là giữ nguyên thứ tự tương đối của các phần tử bằng nhau?

• A. Chỉ Sắp xếp chọn.
• B. Chỉ Sắp xếp nổi bọt.
• C. Chỉ Sắp xếp chèn.
• D. Sắp xếp chèn và Sắp xếp nổi bọt.

Câu 14: Khi sắp xếp một mảng có kích thước nhỏ (ví dụ n < 20), thuật toán nào trong ba thuật toán đơn giản (chèn, chọn, nổi bọt) thường cho hiệu quả tốt nhất trong thực tế và tại sao?

• A. Sắp xếp chèn, vì chi phí hằng số nhỏ.
• B. Sắp xếp chọn, vì số lần đổi chỗ ít nhất.
• C. Sắp xếp nổi bọt, vì ý tưởng đơn giản dễ cài đặt.
• D. Cả ba đều có hiệu quả tương đương nhau với mảng nhỏ.

Câu 15: Thuật toán sắp xếp nào trong ba thuật toán đơn giản (chèn, chọn, nổi bọt) thực hiện số lượng phép đổi chỗ (swap) ít nhất trong trường hợp tổng quát?

• 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ả ba đều thực hiện số lượng đổi chỗ tương đương.

Câu 16: Cho mảng A = [4, 1, 3, 2]. Hãy mô tả trạng thái của mảng A sau khi thuật toán sắp xếp chèn hoàn thành bước chèn phần tử thứ 3 (giá trị 3) vào đúng vị trí trong phần đã sắp xếp.

• A. [1, 4, 3, 2]
• B. [1, 3, 4, 2]
• C. [3, 1, 4, 2]
• D. [1, 2, 3, 4]

Câu 17: Cho mảng A = [9, 5, 2, 7]. Hãy mô tả trạng thái của mảng A sau khi thuật toán sắp xếp chọn hoàn thành bước thứ hai (tìm phần tử nhỏ nhất trong phần còn lại và đổi chỗ).

• A. [2, 5, 9, 7]
• B. [2, 5, 7, 9]
• C. [2, 9, 5, 7]
• D. [5, 2, 9, 7]