12+ Đề Trắc Nghiệm Tin Học 11 (Kết Nối Tri Thức) Bài 19: Bài Toán Tìm Kiếm

Câu 1: Bài toán sắp xếp là gì?

• A. Tìm kiếm một phần tử trong danh sách.
• B. Sắp xếp các phần tử trong danh sách theo một thứ tự nhất định.
• C. Xóa một phần tử khỏi danh sách.
• D. Thêm một phần tử vào danh sách.

Câu 2: Thuật toán Sắp xếp chọn (Selection Sort) hoạt động theo nguyên tắc nào?

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

Câu 3: Cho dãy số A = [5, 2, 8, 1, 9]. Áp dụng thuật toán Sắp xếp chọn theo thứ tự tăng dần. Dãy A sẽ như thế nào sau lần duyệt (pass) đầu tiên?

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

Câu 4: Thuật toán Sắp xếp nổi bọt (Bubble Sort) hoạt động theo nguyên tắc nào?

• A. So sánh các phần tử kề nhau và đổi chỗ nếu sai thứ tự, lặp lại cho đến khi danh sách được sắp xếp.
• B. Tìm phần tử nhỏ nhất trong phần chưa sắp xếp và đổi chỗ với phần tử đầu tiên của phần chưa sắp xếp.
• C. Chèn từng phần tử vào đúng vị trí trong phần đã sắp xếp.
• D. Chia danh sách thành hai nửa và sắp xếp từng nửa.

Câu 5: Cho dãy số B = [6, 1, 4, 3, 2]. Áp dụng thuật toán Sắp xếp nổi bọt theo thứ tự tăng dần. Dãy B sẽ như thế nào sau lần duyệt (pass) đầu tiên?

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

Câu 6: Thuật toán Sắp xếp chèn (Insertion Sort) hoạt động theo nguyên tắc nào?

• A. So sánh các phần tử kề nhau và đổi chỗ nếu sai thứ tự.
• B. Chèn từng phần tử vào đúng vị trí trong phần đã sắp xếp được xây dựng từ trái sang phải.
• C. Tìm phần tử nhỏ nhất trong phần chưa sắp xếp và đổi chỗ với phần tử đầu tiên của phần chưa sắp xếp.
• D. Chia danh sách thành hai nửa và sắp xếp từng nửa.

Câu 7: Cho dãy số C = [7, 3, 5, 1, 4]. Áp dụng thuật toán Sắp xếp chèn theo thứ tự tăng dần. Dãy C sẽ như thế nào sau khi xử lý xong phần tử có giá trị bằng 5 (tức là sau khi chèn 3 và 5 vào phần đã sắp xếp)?

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

Câu 8: Đối với dãy có n phần tử, thuật toán Sắp xếp chọn (Selection Sort) cần bao nhiêu lượt so sánh trong trường hợp xấu nhất (worst case)?

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

Câu 9: Thuật toán Sắp xếp nổi bọt (Bubble Sort) có thể dừng sớm nếu trong một lượt duyệt (pass) không có bất kỳ cặp phần tử nào được đổi chỗ. Điều này xảy ra khi nào?

• A. Khi danh sách rỗng.
• B. Khi chỉ còn một phần tử trong danh sách.
• C. Khi tất cả các phần tử đều có giá trị giống nhau.
• D. Khi danh sách đã được sắp xếp hoàn toàn.

Câu 10: Trong trường hợp tốt nhất (best case), thuật toán Sắp xếp chèn (Insertion Sort) có độ phức tạp thời gian là bao nhiêu và xảy ra khi nào?

• A. O(n^2) khi danh sách đã sắp xếp.
• B. O(n) khi danh sách đã sắp xếp.
• C. O(n log n) khi danh sách ngược thứ tự.
• D. O(1) khi danh sách chỉ có 2 phần tử.

Câu 11: Thuật toán sắp xếp nào trong các thuật toán đơn giản (Selection, Bubble, Insertion) có số lần đổi chỗ (swap) luôn cố định là n-1 đối với dãy có n phần 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 thuật toán đều có số lần đổi chỗ thay đổi tùy theo dữ liệu đầu vào.

Câu 12: Khi nào thì nên cân nhắc sử dụng thuật toán Sắp xếp chèn (Insertion Sort) thay vì Sắp xếp chọn hoặc Sắp xếp nổi bọt?

• A. Khi danh sách có kích thước rất lớn.
• B. Khi cần đảm bảo số lần so sánh là cố định.
• C. Khi danh sách hoàn toàn ngược thứ tự.
• D. Khi danh sách có kích thước nhỏ hoặc đã gần như được sắp xếp.

Câu 13: Cho dãy số D = [4, 1, 3, 2]. Áp dụng thuật toán Sắp xếp chèn theo thứ tự tăng dần. Dãy D sẽ như thế nào sau khi hoàn thành bước chèn phần tử thứ 3 (giá trị 3)?

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

Câu 14: Độ phức tạp thời gian của các thuật toán sắp xếp đơn giản (Selection, Bubble, Insertion) trong trường hợp xấu nhất đều là O(n^2). Điều này có ý nghĩa gì khi xử lý các danh sách có kích thước rất lớn?

• A. Các thuật toán này rất hiệu quả với danh sách lớn.
• B. Thời gian thực thi tăng tuyến tính với kích thước danh sách.
• C. Thời gian thực thi tăng rất nhanh khi kích thước danh sách lớn, khiến chúng không hiệu quả.
• D. Số lần đổi chỗ không đáng kể với danh sách lớn.

Câu 15: Giả sử bạn đang triển khai một ứng dụng cần sắp xếp dữ liệu "trực tuyến" (online), nghĩa là các phần tử mới được thêm vào danh sách cần sắp xếp liên tục. Thuật toán đơn giản nào phù hợp nhất cho việc này?

• 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 thuật toán đều không phù hợp.

Câu 16: Đặc điểm nào sau đây KHÔNG phải là ưu điểm của các thuật toán sắp xếp đơn giản (Selection, Bubble, Insertion)?

• A. Dễ hiểu và dễ cài đặt.
• B. Yêu cầu ít bộ nhớ phụ (O(1) không gian).
• C. Phù hợp với danh sách nhỏ hoặc gần sắp xếp (đối với Insertion Sort).
• D. Tốc độ xử lý nhanh đối với danh sách có kích thước lớn.

Câu 17: Cho dãy số E = [9, 8, 7, 6, 5]. Áp dụng thuật toán Sắp xếp nổi bọt theo thứ tự tăng dần. Có bao nhiêu lần đổi chỗ (swap) được thực hiện trong lần duyệt (pass) đầu tiên?

• A. 4
• B. 3
• C. 5
• D. 0

Câu 18: Trong Sắp xếp chèn (Insertion Sort), phần nào của danh sách được coi là "đã sắp xếp" sau mỗi bước lặp chính?

• A. Phần tử cuối cùng của danh sách.
• B. Phần đầu của danh sách, bao gồm các phần tử đã được chèn vào đúng vị trí.
• C. Toàn bộ danh sách.
• D. Phần tử nhỏ nhất tìm được trong mỗi bước.

Câu 19: Cho dãy số F = [10, 20, 30, 40, 50]. Áp dụng thuật toán Sắp xếp nổi bọt theo thứ tự tăng dần. Có bao nhiêu lần đổi chỗ (swap) được thực hiện trong toàn bộ quá trình sắp xếp?

• A. 0
• B. N-1
• C. N*(N-1)/2
• D. Thay đổi tùy theo cách triển khai

Câu 20: Thuật toán sắp xếp nào trong các thuật toán đơn giản có số lần so sánh là cố định O(n^2) bất kể dữ liệu đầu vào là gì?

• 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 thuật toán.

Câu 21: Cho dãy số G = [3, 1, 4, 1, 5, 9, 2, 6]. Áp dụng Sắp xếp chọn theo thứ tự tăng dần. Dãy G sẽ như thế nào sau khi hoàn thành hai lần duyệt (pass) đầu tiên?

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

Câu 22: Thuật toán nào trong các thuật toán đơn giản được mô tả bằng các bước sau: "Lặp từ phần tử thứ hai đến hết danh sách. Với mỗi phần tử, so sánh nó với các phần tử trong phần đã sắp xếp ở phía trước và chèn nó vào đúng vị trí bằng cách dịch chuyển các phần tử lớn hơn sang phả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. Không phải thuật toán nào trong số này.

Câu 23: Cho dãy số H = [2, 1, 4, 3]. Áp dụng Sắp xếp nổi bọt theo thứ tự tăng dần. Dãy H sẽ như thế nào sau khi hoàn thành lần duyệt (pass) thứ hai?

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

Câu 24: Thuật toán sắp xếp nào được gọi là "stable" (ổn định) nếu nó duy trì thứ tự tương đối của các phần tử có giá trị bằng nhau?

• A. Sắp xếp chọn (Selection Sort)
• B. Sắp xếp nhanh (Quick Sort)
• C. Sắp xếp chèn (Insertion Sort)
• D. Sắp xếp trộn (Merge Sort)

Câu 25: Một giáo viên yêu cầu học sinh sắp xếp một chồng bài kiểm tra theo điểm từ thấp đến cao. Chồng bài kiểm tra chỉ có 15 bài. Thuật toán đơn giản nào có thể là lựa chọn hợp lý nhất về mặt hiệu quả và dễ hiểu?

• A. Sắp xếp hợp nhất (Merge Sort)
• B. Sắp xếp nhanh (Quick Sort)
• C. Sắp xếp chèn (Insertion Sort)
• D. Sắp xếp đếm (Counting Sort)

Câu 26: Thuật toán sắp xếp đơn giản nào có số lần đổi chỗ (swap) có thể lên tới O(n^2) trong trường hợp xấu nhất (ví dụ: dãy ngược thứ 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. Tất cả các thuật toán trên.

Câu 27: Cho dãy số I = [8, 4, 6, 2]. Áp dụng Sắp xếp chèn theo thứ tự tăng dần. Dãy I sẽ như thế nào sau khi hoàn thành bước chèn phần tử thứ 4 (giá trị 2)?

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

Câu 28: Tại sao Sắp xếp chọn (Selection Sort) lại có số lần đổi chỗ ít hơn đáng kể so với Sắp xếp nổi bọt (Bubble Sort) trong trường hợp xấu nhất?

• A. Vì nó sử dụng kỹ thuật chia để trị.
• B. Vì nó chỉ thực hiện 1 lần đổi chỗ cho mỗi lần duyệt để đưa phần tử nhỏ nhất/lớn nhất về đúng vị trí.
• C. Vì nó chỉ so sánh các phần tử kề nhau.
• D. Vì nó chèn từng phần tử vào đúng vị trí.

Câu 29: Xem xét ba thuật toán Sắp xếp chọn, Sắp xếp nổi bọt và Sắp xếp chèn. Thuật toán nào có thể dừng sớm nhất nếu danh sách đầu vào đã được sắp xếp?

• 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ới cờ hiệu) và Sắp xếp chèn.

Câu 30: Một nhà phát triển cần chọn một thuật toán sắp xếp đơn giản cho một hệ thống nhúng với bộ nhớ rất hạn chế. Yếu tố "in-place" (sắp xếp tại chỗ, không dùng bộ nhớ phụ đáng kể) là rất quan trọng. Thuật toán nào trong số các thuật toán đơn giản đáp ứng yêu cầu này?

• A. Sắp xếp chọn (Selection Sort) và Sắp xếp nổi bọt (Bubble Sort)
• B. Sắp xếp chèn (Insertion Sort) và Sắp xếp hợp nhất (Merge Sort)
• C. Chỉ có Sắp xếp chọn (Selection Sort)
• D. Cả Sắp xếp chọn, Sắp xếp nổi bọt và Sắp xếp chèn.

Câu 1: Bài toán sắp xếp (Sorting Problem) trong Tin học có mục tiêu chính là gì?

• A. Sắp xếp các phần tử của một dãy dữ liệu theo một thứ tự nhất định (tăng dần hoặc giảm dần).
• B. Tìm kiếm một phần tử cụ thể trong một dãy dữ liệu.
• C. Thêm hoặc bớt các phần tử vào một dãy dữ liệu.
• D. Kết hợp hai hoặc nhiều dãy dữ liệu thành một.

Câu 2: 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 cơ bản nào?

• A. Tìm phần tử nhỏ nhất (hoặc lớn nhất) trong phần chưa sắp xếp và đưa nó về đúng vị trí.
• B. Chia dãy thành hai nửa, sắp xếp từng nửa rồi trộn lại.
• C. So sánh và hoán đổi vị trí các cặp phần tử liền kề nếu chúng không đúng thứ tự.
• D. Lấy từng phần tử từ dãy ban đầu và chèn vào đúng vị trí trong phần đã sắp xếp.

Câu 3: Cho dãy số A = [5, 1, 4, 2, 8]. Sau khi thực hiện **một lượt (pass)** đầu tiên của thuật toán Sắp xếp nổi bọt (Bubble Sort) theo thứ tự tăng dần, dãy A sẽ trở thành như thế nào?

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

Câu 4: Thuật toán Sắp xếp chọn (Selection Sort) hoạt động dựa trên nguyên tắc cơ bản nào?

• A. Tìm phần tử nhỏ nhất (hoặc lớn nhất) trong phần chưa sắp xếp và hoán đổi nó với phần tử ở vị trí đầu tiên của phần chưa sắp xếp.
• B. So sánh và hoán đổi vị trí các cặp phần tử liền kề nếu chúng không đúng thứ tự.
• C. Lấy từng phần tử từ dãy ban đầu và chèn vào đúng vị trí trong phần đã sắp xếp.
• D. Chia dãy thành hai nửa, sắp xếp từng nửa rồi trộn lại.

Câu 5: Cho dãy số B = [6, 2, 8, 3, 1]. Sau khi thực hiện **hai lượt (pass)** đầu tiên của thuật toán Sắp xếp chọn (Selection Sort) theo thứ tự tăng dần, dãy B sẽ trở thành như thế nào?

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

Câu 6: Thuật toán Sắp xếp chèn (Insertion Sort) hoạt động dựa trên nguyên tắc cơ bản nào?

• A. Chia dãy thành hai nửa, sắp xếp từng nửa rồi trộn lại.
• B. Tìm phần tử nhỏ nhất (hoặc lớn nhất) trong phần chưa sắp xếp và đưa nó về đúng vị trí.
• C. So sánh và hoán đổi vị trí các cặp phần tử liền kề nếu chúng không đúng thứ tự.
• D. Xây dựng dãy đã sắp xếp bằng cách lần lượt chèn từng phần tử của dãy ban đầu vào đúng vị trí của nó trong phần đã sắp xếp.

Câu 7: Cho dãy số C = [7, 3, 5, 8, 4]. Sau khi thực hiện **bước chèn phần tử thứ 3** (với phần tử thứ nhất và thứ hai đã được xem như phần đã sắp xếp ban đầu) của thuật toán Sắp xếp chèn (Insertion Sort) theo thứ tự tăng dần, dãy C sẽ trở thành như thế nào?

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

Câu 8: Xét độ phức tạp thời gian trong trường hợp xấu nhất (Worst Case) của các thuật toán sắp xếp đơn giản (Bubble Sort, Selection Sort, Insertion Sort) với N phần tử. Độ phức tạp này thường được biểu diễn bằng ký hiệu Big O là gì?

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

Câu 9: Tại sao các thuật toán sắp xếp đơn giản (như Bubble Sort, Selection Sort, Insertion Sort) lại không hiệu quả cho các tập dữ liệu rất lớn?

• A. Chúng yêu cầu quá nhiều bộ nhớ phụ.
• B. Số lượng phép so sánh và hoán đổi tăng rất nhanh (theo bình phương) khi số lượng phần tử lớn.
• C. Chúng chỉ hoạt động trên các kiểu dữ liệu số.
• D. Chúng cần dữ liệu phải được sắp xếp trước khi bắt đầu.

Câu 10: Trong trường hợp tốt nhất (Best Case) của thuật toán Sắp xếp chèn (Insertion Sort) theo thứ tự tăng dần (khi dãy đã được sắp xếp tăng dần), số lượng phép so sánh gần đúng là bao nhiêu với N phần tử?

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

Câu 11: So sánh giữa Sắp xếp nổi bọt (Bubble Sort) và Sắp xếp chọn (Selection Sort) trên một dãy có N phần tử. Thuật toán nào có xu hướng thực hiện ít phép hoán đổi (swap) hơn trong trường hợp trung bình và xấu nhất?

• A. Sắp xếp nổi bọt (Bubble Sort)
• B. Sắp xếp chọn (Selection Sort)
• C. Cả hai đều thực hiện số lượng hoán đổi tương đương.
• D. Không thể so sánh được.

Câu 12: Thuật toán sắp xếp đơn giản nào có thể hiệu quả nhất (về số phép so sánh) trong trường hợp dãy đầu vào đã được sắp xếp gần hoàn toàn?

• 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 có hiệu quả như nhau trong trường hợp này.

Câu 13: Xét dãy số D = [4, 1, 3, 2]. Theo dõi thuật toán Sắp xếp chèn (Insertion Sort) theo thứ tự tăng dần. Sau khi phần tử có giá trị 2 được chèn vào đúng vị trí, dãy D sẽ như thế nào?

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

Câu 14: Cho dãy số E = [9, 7, 5, 3, 1]. Khi áp dụng thuật toán Sắp xếp chọn (Selection Sort) theo thứ tự tăng dần, sau lượt thứ nhất, phần tử nào chắc chắn đã ở đúng vị trí cuối cùng của nó trong dãy đã sắp xếp?

• A. Phần tử nhỏ nhất của dãy ban đầu.
• B. Phần tử ở vị trí cuối cùng của dãy ban đầu.
• C. Phần tử ở vị trí đầu tiên của dãy ban đầu.
• D. Không có phần tử nào chắc chắn ở đúng vị trí cuối cùng của nó sau lượt thứ nhất, trừ khi đó là phần tử nhỏ nhất và nó ở vị trí 0 ngay từ đầu.

Câu 15: Thuật toán sắp xếp nào trong ba thuật toán đơn giản (Bubble, Selection, Insertion) thường được coi là dễ cài đặt nhất cho người mới bắt đầu học?

• A. Sắp xếp nổi bọt (Bubble Sort)
• B. Sắp xếp chèn (Insertion Sort)
• C. Sắp xếp chọn (Selection Sort)
• D. Độ khó cài đặt là như nhau.

Câu 16: Xét thuật toán Sắp xếp nổi bọt (Bubble Sort) trên dãy A = [1, 2, 3, 4, 5] (đã sắp xếp tăng dần). Hỏi cần bao nhiêu phép so sánh và bao nhiêu phép hoán đổi để thuật toán kết thúc nếu nó có cơ chế kiểm tra xem có hoán đổi nào xảy ra trong một lượt không?

• A. (N-1)*N/2 phép so sánh, 0 hoán đổi.
• B. N-1 phép so sánh, 0 hoán đổi.
• C. (N-1)N/2 phép so sánh, (N-1)N/2 hoán đổi.
• D. N-1 phép so sánh, N-1 hoán đổi.

Câu 17: Cho dãy số F = [10, 20, 30, 40, 50]. Khi áp dụng thuật toán Sắp xếp chọn (Selection Sort) theo thứ tự tăng dần, số lượng phép hoán đổi sẽ là bao nhiêu?

• A. 0
• B. N/2
• C. N-1
• D. N*(N-1)/2

Câu 18: Một dãy số được sắp xếp bằng một trong ba thuật toán đơn giản. Sau một số bước, dãy có dạng [1, 3, 5, 8, 2, 4, 6]. Dựa vào cấu trúc "phần đã sắp xếp" và "phần chưa sắp xếp", có thể suy đoán dãy này đang được sắp xếp bằng thuật toán nào?

• A. Sắp xếp chèn (Insertion Sort)
• B. Sắp xếp nổi bọt (Bubble Sort)
• C. Sắp xếp chọn (Selection Sort)
• D. Không thể xác định chỉ với thông tin này.

Câu 19: Cho dãy số G = [7, 1, 5, 12, 3, 8]. Theo dõi thuật toán Sắp xếp nổi bọt (Bubble Sort) theo thứ tự tăng dần. Sau khi phần tử có giá trị 12 được "nổi bọt" đến đúng vị trí cuối cùng của nó, dãy G sẽ như thế nào?

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

Câu 20: Khi nào thì thuật toán Sắp xếp chọn (Selection Sort) và Sắp xếp nổi bọt (Bubble Sort) có cùng độ phức tạp thời gian trong trường hợp tốt nhất (Best Case)?

• A. Khi dãy đã được sắp xếp tăng dần.
• B. Khi dãy được sắp xếp ngược lại (giảm dần).
• C. Khi tất cả các phần tử trong dãy đều bằng nhau.
• D. Không bao giờ có cùng độ phức tạp thời gian trong trường hợp tốt nhất.

Câu 21: Thuật toán sắp xếp nào trong ba thuật toán đơn giản có tính chất là sau mỗi lượt (pass), một phần tử chắc chắn đã được đưa về đúng vị trí cuối cùng của nó trong dãy đã sắp xếp?

• A. Sắp xếp nổi bọt (Bubble Sort)
• B. Sắp xếp chèn (Insertion Sort)
• C. Sắp xếp chọn (Selection Sort)
• D. Cả ba thuật toán đều có tính chất này.

Câu 22: Cho dãy số H = [8, 4, 6, 2]. Theo dõi thuật toán Sắp xếp chọn (Selection Sort) theo thứ tự tăng dần. Sau khi kết thúc lượt thứ 2, dãy H sẽ như thế nào?

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

Câu 23: So sánh Sắp xếp nổi bọt (Bubble Sort) và Sắp xếp chèn (Insertion Sort) về số lượng phép hoán đổi. Thuật toán nào có thể thực hiện ít phép hoán đổi hơn trong trường hợp trung bình?

• A. Sắp xếp nổi bọt (Bubble Sort)
• B. Sắp xếp chèn (Insertion Sort)
• C. Cả hai đều thực hiện số lượng hoán đổi tương đương.
• D. Không thể so sánh được.

Câu 24: Một lập trình viên cần chọn một thuật toán sắp xếp đơn giản để sắp xếp một danh sách rất nhỏ (ví dụ, dưới 20 phần tử) trong một ứng dụng nhúng có bộ nhớ hạn chế. Thuật toán nào trong ba thuật toán đơn giản có thể là lựa chọn hợp lý nhất, xét về sự đơn giản và hiệu quả trên dữ liệu nhỏ?

• 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 phù hợp như nhau.

Câu 25: Cho dãy số I = [5, 3, 1]. Theo dõi thuật toán Sắp xếp nổi bọt (Bubble Sort) theo thứ tự tăng dần. Cần bao nhiêu phép so sánh để dãy được sắp xếp hoàn toàn?

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

Câu 26: Cho dãy số J = [5, 3, 1]. Theo dõi thuật toán Sắp xếp chọn (Selection Sort) theo thứ tự tăng dần. Cần bao nhiêu phép hoán đổi để dãy được sắp xếp hoàn toàn?

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

Câu 27: Cho dãy số K = [5, 3, 1]. Theo dõi thuật toán Sắp xếp chèn (Insertion Sort) theo thứ tự tăng dần. Cần bao nhiêu phép so sánh để dãy được sắp xếp hoàn toàn?

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

Câu 28: Thuật toán sắp xếp nào có thể được mô tả là "chia dãy thành hai phần: một phần đã sắp xếp và một phần chưa sắp xếp, và lần lượt đưa phần tử từ phần chưa sắp xếp sang phần đã sắp xếp sao cho nó vẫn giữ được tính thứ 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.

Câu 29: Xét một dãy số có N phần tử. Trong trường hợp xấu nhất, thuật toán Sắp xếp chọn (Selection Sort) sẽ thực hiện khoảng bao nhiêu phép so sánh?

• A. N
• B. N log N
• C. N-1
• D. N*(N-1)/2

Câu 30: Đặc điểm nào sau đây là điểm chung của cả ba thuật toán sắp xếp đơn giản (Bubble Sort, Selection Sort, Insertion Sort) khi nói về yêu cầu bộ nhớ?

• A. Chúng đều là các thuật toán "tại chỗ" (in-place) và chỉ cần một lượng bộ nhớ phụ cố định.
• B. Chúng đều yêu cầu một mảng phụ có kích thước bằng mảng ban đầu.
• C. Yêu cầu bộ nhớ của chúng phụ thuộc tuyến tính vào số lượng phần tử (O(N)).
• D. Chúng yêu cầu bộ nhớ phụ theo cấp logarit (O(log N)).

Câu 1: Khi bạn sử dụng công cụ tìm kiếm trên một website thương mại điện tử để tìm một sản phẩm cụ thể (ví dụ: "điện thoại Samsung Galaxy S23"), "miền dữ liệu" của bài toán tìm kiếm này là gì?

• A. Chỉ các từ khóa bạn gõ vào ô tìm kiếm.
• B. Toàn bộ danh mục sản phẩm và thông tin liên quan có trên website.
• C. Các kết quả tìm kiếm được hiển thị trên màn hình.
• D. Tất cả các website bán hàng trên internet.

Câu 2: Thuật toán tìm kiếm tuần tự (Sequential Search) hoạt động dựa trên nguyên tắc cơ bản nào?

• A. Chia đôi danh sách và tìm kiếm trong một nửa.
• B. Sắp xếp danh sách trước khi tìm kiếm.
• C. Duyệt qua từng phần tử của danh sách theo thứ tự.
• D. So sánh phần tử cần tìm với phần tử ở giữa danh sách.

Câu 3: Cho dãy số A = [4, 12, 7, 25, 18, 31, 9]. Nếu bạn tìm kiếm giá trị K = 18 bằng thuật toán tìm kiếm tuần tự, bạn sẽ cần duyệt qua bao nhiêu phần tử trước khi tìm thấy K?

• A. 3
• B. 4
• C. 6
• D. 5

Câu 4: Trong trường hợp nào, thuật toán tìm kiếm tuần tự đạt hiệu suất tốt nhất (số bước duyệt ít nhất)?

• A. Phần tử cần tìm là phần tử đầu tiên của dãy.
• B. Phần tử cần tìm là phần tử cuối cùng của dãy.
• C. Phần tử cần tìm không tồn tại trong dãy.
• D. Dãy dữ liệu có kích thước nhỏ.

Câu 5: Thuật toán tìm kiếm nhị phân (Binary Search) chỉ có thể áp dụng trực tiếp một cách hiệu quả khi dữ liệu đầu vào có đặc điểm gì?

• A. Dữ liệu có kích thước nhỏ.
• B. Dữ liệu chứa các số nguyên dương.
• C. Dữ liệu đã được sắp xếp theo một thứ tự.
• D. Dữ liệu không chứa các phần tử trùng lặp.

Câu 6: Cho dãy số đã sắp xếp tăng dần A = [10, 20, 30, 40, 50, 60, 70, 80, 90]. Bạn cần tìm giá trị K = 70 bằng thuật toán tìm kiếm nhị phân. Giá trị của phần tử được kiểm tra ở bước **thứ hai** là bao nhiêu?

• A. 30
• B. 50
• C. 60
• D. 70

Câu 7: Với một dãy số đã sắp xếp có N phần tử, số bước duyệt tối đa (trong trường hợp xấu nhất) của thuật toán tìm kiếm nhị phân xấp xỉ là bao nhiêu?

• A. N
• B. log₂(N)
• C. N/2
• D. N * log₂(N)

Câu 8: Bạn có một tệp văn bản chứa hàng triệu dòng dữ liệu, mỗi dòng là một giao dịch bán hàng. Các giao dịch này được lưu trữ theo thứ tự thời gian (không sắp xếp theo bất kỳ trường nào khác). Bạn cần tìm tất cả các giao dịch của một khách hàng cụ thể dựa trên ID khách hàng. Thuật toán tìm kiếm nào phù hợp nhất để thực hiện công việc này?

• A. Tìm kiếm tuần tự.
• B. Tìm kiếm nhị phân (vì dữ liệu lớn).
• C. Cần phải sắp xếp lại dữ liệu theo ID khách hàng rồi mới tìm.
• D. Cả hai thuật toán đều không phù hợp.

Câu 9: So sánh tốc độ giữa tìm kiếm tuần tự và tìm kiếm nhị phân trên một dãy dữ liệu rất lớn (ví dụ 1 tỷ phần tử) đã được sắp xếp. Nhận định nào sau đây là đúng nhất?

• A. Tìm kiếm tuần tự nhanh hơn tìm kiếm nhị phân vì nó đơn giản hơn.
• B. Tìm kiếm nhị phân nhanh hơn đáng kể so với tìm kiếm tuần tự.
• C. Tốc độ của cả hai thuật toán là tương đương.
• D. Tốc độ phụ thuộc vào phần tử cần tìm, đôi khi tuần tự nhanh hơn.

Câu 10: Khi sử dụng thuật toán tìm kiếm tuần tự để tìm một phần tử K trong dãy A mà K không có trong A, thuật toán sẽ dừng lại khi nào?

• A. Ngay lập tức khi nhận ra K không tồn tại.
• B. Sau khi duyệt đến cuối dãy mà không tìm thấy K.
• C. Khi số bước duyệt vượt quá số lượng phần tử của dãy.
• D. Khi tìm thấy một phần tử khác có giá trị gần K nhất.

Câu 11: Khi sử dụng thuật toán tìm kiếm nhị phân để tìm một phần tử K trong dãy A (đã sắp xếp) mà K không có trong A, thuật toán sẽ dừng lại khi nào?

• A. Khi phạm vi tìm kiếm (khoảng giữa low và high) trở thành rỗng.
• B. Sau khi duyệt hết toàn bộ dãy.
• C. Khi số bước duyệt vượt quá log₂(N).
• D. Khi tìm thấy một phần tử khác có giá trị gần K nhất.

Câu 12: Giả sử bạn có một danh sách rất lớn (hàng trăm nghìn mục) các hồ sơ bệnh nhân, được lưu trữ theo thứ tự alphabet của tên. Bạn cần thường xuyên tìm kiếm hồ sơ của một bệnh nhân cụ thể. Thuật toán tìm kiếm nào là lựa chọn tối ưu nhất cho tác vụ này?

• A. Tìm kiếm tuần tự.
• B. Tìm kiếm nhị phân.
• C. Cả hai đều có hiệu quả tương đương.
• D. Cần sử dụng một cấu trúc dữ liệu khác không phải danh sách.

Câu 13: Bạn có một bộ sưu tập các bức ảnh kỹ thuật số được lưu trữ trong một thư mục trên máy tính. Các tệp ảnh không được sắp xếp theo bất kỳ thứ tự nào cụ thể (ví dụ: theo tên, ngày chụp). Bạn muốn tìm một bức ảnh cụ thể dựa trên tên tệp mà bạn nhớ mang máng. Hệ thống tệp của máy tính nhiều khả năng sẽ sử dụng nguyên tắc tìm kiếm nào để duyệt qua các tệp trong thư mục?

• A. Tìm kiếm tuần tự.
• B. Tìm kiếm nhị phân.
• C. Tìm kiếm theo chỉ mục băm (Hashing).
• D. Một thuật toán sắp xếp trước khi tìm kiếm.

Câu 14: Khi một dãy dữ liệu đã sắp xếp chứa nhiều phần tử có giá trị giống nhau, nếu tìm kiếm nhị phân tìm thấy phần tử cần tìm K tại một vị trí, vị trí đó có đảm bảo là vị trí xuất hiện **đầu tiên** của K trong dãy không?

• A. Luôn luôn là vị trí đầu tiên.
• B. Luôn luôn là vị trí cuối cùng.
• C. Có thể là bất kỳ vị trí nào của K trong dãy.
• D. Thuật toán tìm kiếm nhị phân không hoạt động với dữ liệu trùng lặp.

Câu 15: Giả sử bạn cần thực hiện 1000 lần tìm kiếm trên một danh sách dữ liệu lớn (1 triệu phần tử) chưa được sắp xếp. Chi phí để sắp xếp danh sách này là đáng kể (ví dụ: tương đương 100.000 bước duyệt tuần tự). Chiến lược nào sau đây có khả năng mang lại tổng thời gian thực hiện (sắp xếp + tìm kiếm) hiệu quả nhất?

• A. Sử dụng tìm kiếm tuần tự cho cả 1000 lần tìm kiếm.
• B. Sắp xếp danh sách một lần rồi sử dụng tìm kiếm nhị phân cho 1000 lần tìm kiếm.
• C. Sử dụng tìm kiếm nhị phân trực tiếp trên danh sách chưa sắp xếp.
• D. Chia danh sách thành các phần nhỏ hơn và tìm kiếm tuần tự trên từng phần.

Câu 16: Trong thuật toán tìm kiếm nhị phân, nếu giá trị cần tìm K lớn hơn giá trị của phần tử ở giữa dãy con hiện tại, thuật toán sẽ tiếp tục tìm kiếm ở phần nào của dãy con đó?

• A. Nửa bên phải của phần tử giữa (bao gồm cả phần tử ngay sau phần tử giữa).
• B. Nửa bên trái của phần tử giữa (bao gồm cả phần tử ngay trước phần tử giữa).
• C. Toàn bộ dãy con hiện tại.
• D. Chỉ phần tử ở giữa đó.

Câu 17: Cho dãy A = [1, 5, 8, 12, 16, 19, 23]. Tìm giá trị K = 15 bằng thuật toán tìm kiếm nhị phân. Các phần tử nào sẽ được kiểm tra theo thứ tự cho đến khi thuật toán dừng lại?

• A. 12, 16, 19
• B. 16, 12, 19
• C. 12, 19, 16
• D. 15

Câu 18: Điều gì xảy ra trong thuật toán tìm kiếm nhị phân khi giá trị cần tìm K bằng giá trị của phần tử ở giữa dãy con hiện tại?

• A. Thuật toán tiếp tục tìm kiếm ở cả hai nửa của dãy con.
• B. Thuật toán dừng lại và báo cáo không tìm thấy.
• C. Thuật toán tiếp tục tìm kiếm ở nửa bên phải.
• D. Thuật toán dừng lại và báo cáo tìm thấy phần tử tại vị trí đó.

Câu 19: Khi tìm kiếm thông tin trên Internet bằng các công cụ tìm kiếm (ví dụ: Google, Bing), "miền dữ liệu" được tìm kiếm là gì?

• A. Tập hợp các trang web và nội dung đã được các công cụ tìm kiếm lập chỉ mục.
• B. Chỉ các trang web có chứa chính xác các từ khóa bạn tìm.
• C. Toàn bộ thông tin có trên tất cả các máy tính kết nối Internet.
• D. Các kết quả được hiển thị trên trang kết quả tìm kiếm.

Câu 20: Thuật toán tìm kiếm nào sau đây có thể được áp dụng hiệu quả nhất để tìm kiếm một từ khóa trong một văn bản dài (ví dụ: một cuốn sách điện tử) mà không cần bất kỳ quá trình tiền xử lý (như sắp xếp) nào trên văn bản đó?

• A. Tìm kiếm tuần tự.
• B. Tìm kiếm nhị phân.
• C. Cả hai đều không phù hợp.
• D. Một thuật toán sắp xếp kết hợp tìm kiếm.

Câu 21: Độ phức tạp thời gian của thuật toán tìm kiếm tuần tự trong trường hợp xấu nhất là O(N), trong đó N là số lượng phần tử. Điều này có nghĩa là gì?

• A. Số bước thực hiện tăng theo logarit của N.
• B. Số bước thực hiện không phụ thuộc vào N.
• C. Số bước thực hiện tăng tỉ lệ thuận với N.
• D. Số bước thực hiện giảm khi N tăng.

Câu 22: So với tìm kiếm tuần tự, ưu điểm chính của tìm kiếm nhị phân khi áp dụng trên dữ liệu phù hợp là gì?

• A. Đơn giản hơn trong cài đặt.
• B. Có thể áp dụng cho mọi loại dữ liệu (đã sắp xếp hoặc chưa sắp xếp).
• C. Đảm bảo tìm thấy tất cả các vị trí của phần tử trùng lặp.
• D. Tốc độ tìm kiếm nhanh hơn đáng kể với dữ liệu lớn đã được sắp xếp.

Câu 23: Cho dãy số A = [5, 12, 8, 20, 15]. Bạn muốn tìm tất cả các phần tử lớn hơn 10 bằng tìm kiếm tuần tự. Các phần tử nào sẽ được tìm thấy?

• A. 5, 12, 20, 15
• B. 12, 20, 15
• C. 12, 20
• D. Chỉ 20

Câu 24: Một hệ thống quản lý kho hàng lưu trữ thông tin về hàng triệu sản phẩm theo mã sản phẩm (một chuỗi ký tự duy nhất cho mỗi sản phẩm). Mã sản phẩm được gán ngẫu nhiên và không theo bất kỳ thứ tự nào. Khi nhân viên muốn tìm kiếm thông tin chi tiết của một sản phẩm dựa vào mã, hệ thống nên sử dụng thuật toán tìm kiếm nào trên danh sách mã sản phẩm?

• A. Tìm kiếm tuần tự.
• B. Tìm kiếm nhị phân.
• C. Cần sắp xếp lại danh sách mã sản phẩm trước.
• D. Một thuật toán sắp xếp nhanh.

Câu 25: Khái niệm "miền dữ liệu" trong bài toán tìm kiếm giúp chúng ta xác định điều gì?

• A. Tốc độ thực hiện của thuật toán tìm kiếm.
• B. Số lượng phần tử cần tìm.
• C. Tập hợp tất cả các đối tượng hoặc thông tin có thể được tìm kiếm.
• D. Vị trí của phần tử cần tìm trong dữ liệu đầu vào.

Câu 26: Tìm kiếm nhị phân hoạt động bằng cách liên tục loại bỏ một nửa phạm vi tìm kiếm. Điều này đạt được nhờ vào việc so sánh phần tử cần tìm K với phần tử nào trong dãy con hiện tại?

• A. Phần tử nằm chính giữa dãy con hiện tại.
• B. Phần tử đầu tiên của dãy con hiện tại.
• C. Phần tử cuối cùng của dãy con hiện tại.
• D. Một phần tử ngẫu nhiên trong dãy con hiện tại.

Câu 27: Cho dãy số đã sắp xếp tăng dần A = [2, 5, 8, 12, 16]. Tìm giá trị K = 6 bằng thuật toán tìm kiếm nhị phân. Các giá trị của các biến "low" và "high" sẽ thay đổi như thế nào cho đến khi thuật toán dừng lại?

• A. (0,4) -> (2,4) -> (3,4)
• B. (0,4) -> (0,1) -> (0,0)
• C. (0,4) -> (0,1) -> (1,1) -> (2,1)
• D. (0,4) -> (2,4) -> (3,4) -> (4,4)

Câu 28: Nhận định nào sau đây là **sai** khi so sánh tìm kiếm tuần tự và tìm kiếm nhị phân?

• A. Tìm kiếm nhị phân yêu cầu dữ liệu phải được sắp xếp.
• B. Tìm kiếm nhị phân thường nhanh hơn tìm kiếm tuần tự trên dữ liệu lớn đã sắp xếp.
• C. Tìm kiếm tuần tự có thể áp dụng cho dữ liệu chưa được sắp xếp.
• D. Tìm kiếm tuần tự chỉ hiệu quả khi dữ liệu có kích thước rất lớn.

Câu 29: Trong một danh sách gồm 1024 phần tử đã sắp xếp, trong trường hợp xấu nhất, thuật toán tìm kiếm nhị phân cần tối đa bao nhiêu bước so sánh để xác định một phần tử có tồn tại trong danh sách hay không?

• A. 1024
• B. 512
• C. 10
• D. 1

Câu 30: Bạn đang viết chương trình tìm kiếm một từ trong một từ điển điện tử có hàng trăm nghìn từ đã được sắp xếp theo thứ tự alphabet. Kiểu dữ liệu và yêu cầu tìm kiếm này phù hợp nhất với thuật toán nào?

• A. Tìm kiếm tuần tự.
• B. Tìm kiếm nhị phân.
• C. Cả hai đều có hiệu quả tương đương.
• D. Một thuật toán sắp xếp.

Câu 1: Thuật toán sắp xếp nào sau đây hoạt động bằng cách lặp đi lặp lại việc so sánh các cặp phần tử liền kề và đổi chỗ nếu chúng không đúng thứ tự?

• A. Thuật toán sắp xếp chọn (Selection Sort)
• B. Thuật toán sắp xếp nổi bọt (Bubble Sort)
• C. Thuật toán sắp xếp chèn (Insertion Sort)
• D. Thuật toán sắp xếp nhanh (Quick Sort)

Câu 2: Khi sử dụng thuật toán sắp xếp chọn (Selection Sort) để sắp xếp dãy số [5, 2, 8, 1, 9] theo thứ tự tăng dần, dãy số sẽ trông như thế nào sau khi hoàn thành **lượt duyệt đầu tiên** (tìm phần tử nhỏ nhất và đưa về đầu)?

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

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

• A. Chia dãy thành hai nửa và sắp xếp riêng lẻ
• B. Tìm phần tử nhỏ nhất và đặt vào đúng vị trí
• C. So sánh các cặp phần tử liền kề và đổi chỗ
• D. Xây dựng dãy đã sắp xếp từng bước bằng cách chèn phần tử vào đúng vị trí trong phần đã sắp xếp

Câu 4: Cho dãy số [7, 4, 1, 9, 3]. Khi áp dụng thuật toán sắp xếp nổi bọt (Bubble Sort) theo thứ tự tăng dần, dãy số sẽ như thế nào sau khi kết thúc **lượt duyệt thứ hai**?

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

Câu 5: Thuật toán sắp xếp nào sau đây có hiệu suất tốt nhất (trung bình) khi áp dụng cho một dãy số **gần như đã được sắp xếp**?

• A. Thuật toán sắp xếp chọn (Selection Sort)
• B. Thuật toán sắp xếp nổi bọt (Bubble Sort)
• C. Thuật toán sắp xếp chèn (Insertion Sort)
• D. Tất cả đều như nhau với dãy gần sắp xếp

Câu 6: Độ phức tạp thời gian trong trường hợp xấu nhất của các thuật toán sắp xếp đơn giản như Sắp xếp nổi bọt, Sắp xếp chọn, Sắp xếp chèn là bao nhiêu?

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

Câu 7: Khi sử dụng thuật toán sắp xếp chọn (Selection Sort) để sắp xếp một dãy gồm N phần tử, số lần **đổi chỗ** (swap) tối đa có thể xảy ra là bao nhiêu?

• A. N * (N-1) / 2
• B. N * (N-1)
• C. N^2
• D. N - 1

Câu 8: Dãy số [3, 1, 4, 1, 5, 9, 2, 6]. Áp dụng thuật toán sắp xếp chèn (Insertion Sort) theo thứ tự tăng dần. Dãy số sẽ như thế nào sau khi phần tử có giá trị 5 được chèn vào đúng vị trí của nó?

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

Câu 9: Đặc điểm nào sau đây là **không đúng** về thuật toán sắp xếp nổi bọt (Bubble Sort)?

• A. So sánh và đổi chỗ các phần tử liền kề.
• B. Trong mỗi lượt, phần tử lớn nhất (hoặc nhỏ nhất) chưa được sắp xếp sẽ "nổi" lên cuối dãy chưa sắp xếp.
• C. Hiệu quả nhất khi dãy số đã được sắp xếp ngược.
• D. Có thể dừng sớm nếu không có cặp phần tử nào được đổi chỗ trong một lượt duyệt.

Câu 10: Giả sử bạn có một danh sách rất lớn các bản ghi cần sắp xếp, và bộ nhớ là một hạn chế nghiêm trọng. Thuật toán sắp xếp nào trong các thuật toán đơn giản sau đây thường được ưu tiên vì nó thực hiện sắp xếp **tại chỗ** (in-place) và không yêu cầu thêm không gian bộ nhớ đáng kể?

• A. Merge Sort
• B. Quick Sort
• C. Heap Sort
• D. Cả Sắp xếp nổi bọt, Sắp xếp chọn và Sắp xếp chèn đều là thuật toán tại chỗ.

Câu 11: Cho dãy số [10, 5, 3, 8, 1]. Khi sử dụng thuật toán sắp xếp chọn (Selection Sort) để sắp xếp tăng dần, phần tử nào sẽ nằm ở vị trí đầu tiên sau khi hoàn thành **lượt duyệt thứ hai**?

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

Câu 12: Trong thuật toán sắp xếp chèn (Insertion Sort), sau khi phần tử thứ `i` được chèn vào đúng vị trí trong dãy con đã sắp xếp `A[0...i-1]`, dãy con `A[0...i]` sẽ có đặc điểm gì?

• A. Tất cả các phần tử nhỏ hơn `A[i]` đều nằm ở bên trái nó.
• B. Dãy con `A[0...i]` đã được sắp xếp hoàn chỉnh.
• C. Phần tử `A[i]` chắc chắn là phần tử lớn nhất trong dãy con `A[0...i]`.
• D. Số lần đổi chỗ luôn bằng `i`.

Câu 13: Xét thuật toán sắp xếp nổi bọt (Bubble Sort) trên dãy [6, 5, 4, 3, 2, 1]. Trong **lượt duyệt đầu tiên**, có bao nhiêu cặp phần tử liền kề được so sánh và đổi chỗ?

• A. 3
• B. 4
• C. 5
• D. 5

Câu 14: Tại sao thuật toán sắp xếp chọn (Selection Sort) lại có số lần đổi chỗ (swap) ít hơn đáng kể so với Sắp xếp nổi bọt (Bubble Sort) hoặc Sắp xếp chèn (Insertion Sort) trong trường hợp xấu nhất?

• A. Nó chỉ thực hiện một lần đổi chỗ cho mỗi lượt duyệt chính (đưa phần tử nhỏ nhất về đúng vị trí).
• B. Nó không bao giờ thực hiện đổi chỗ.
• C. Nó chỉ so sánh các phần tử ở xa nhau.
• D. Nó sử dụng thêm bộ nhớ để lưu trữ vị trí cần đổi chỗ.

Câu 15: Trong trường hợp tốt nhất (dãy đã được sắp xếp tăng dần), thuật toán sắp xếp nào trong các thuật toán đơn giản sau đây có thể kết thúc với số bước ít nhất (hoặc độ phức tạp thời gian tốt nhất)?

• A. Thuật toán sắp xếp chọn (Selection Sort)
• B. Thuật toán sắp xếp nổi bọt (Bubble Sort)
• C. Thuật toán sắp xếp chèn (Insertion Sort)
• D. Cả Sắp xếp nổi bọt (với cờ hiệu) và Sắp xếp chèn

Câu 16: Một lập trình viên cần sắp xếp một danh sách nhỏ (dưới 20 phần tử). Anh ta nên chọn thuật toán sắp xếp đơn giản nào để tối ưu hóa tốc độ lập trình và dễ hiểu, thay vì hiệu quả chạy chương trình trên dữ liệu lớn?

• A. Quick Sort
• B. Merge Sort
• C. Heap Sort
• D. Bất kỳ thuật toán đơn giản nào như Bubble, Selection, hoặc Insertion Sort đều phù hợp.

Câu 17: Xét dãy số [4, 2, 7, 1, 5]. Sử dụng Sắp xếp nổi bọt (Bubble Sort) tăng dần. Dãy số sau khi kết thúc **lượt duyệt thứ nhất** (bubble up phần tử lớn nhất) là:

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

Câu 18: Thuật toán sắp xếp nào có cách tiếp cận tương tự như cách con người sắp xếp một bộ bài (cầm từng lá bài lên và chèn vào đúng vị trí trong phần bài đã xếp)?

• 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. Sắp xếp nhanh (Quick Sort)

Câu 19: Dãy số [8, 3, 6, 1, 4]. Sử dụng Sắp xếp chọn (Selection Sort) tăng dần. Dãy số sau khi kết thúc **lượt duyệt thứ ba** (đã sắp xếp 3 phần tử đầu tiên) là:

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

Câu 20: Thuật toán sắp xếp đơn giản nào sau đây có số lần **so sánh** là cố định, không phụ thuộc vào trạng thái ban đầu của dãy (dù đã sắp xếp hay chưa)?

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

Câu 21: Khi nào thì nên cân nhắc sử dụng các thuật toán sắp xếp đơn giản như Sắp xếp nổi bọt, Sắp xếp chọn hoặc Sắp xếp chèn thay vì các thuật toán phức tạp hơn như Quick Sort hay Merge Sort?

• A. Khi cần sắp xếp một lượng dữ liệu rất lớn.
• B. Khi yêu cầu hiệu suất chạy chương trình cực kỳ cao trên mọi loại dữ liệu.
• C. Khi kích thước dữ liệu nhỏ hoặc cần triển khai thuật toán một cách nhanh chóng và đơn giản.
• D. Khi dữ liệu luôn ở trạng thái sắp xếp ngược hoàn toàn.

Câu 22: Dãy số [5, 2, 4, 6, 1, 3]. Sử dụng Sắp xếp chèn (Insertion Sort) tăng dần. Dãy số sau khi hoàn thành việc chèn phần tử có giá trị 6 (phần tử thứ 4 ban đầu) là:

• A. [1, 2, 4, 5, 6, 3]
• B. [2, 4, 5, 6, 1, 3]
• C. [2, 4, 5, 1, 6, 3]
• D. [2, 4, 5, 6, 1, 3] (Phần tử 6 đã ở đúng vị trí so với dãy con [2, 4, 5])

Câu 23: Phát biểu nào sau đây mô tả đúng về việc "sắp xếp tại chỗ" (in-place sorting)?

• A. Thuật toán chỉ sử dụng một lượng không gian bộ nhớ phụ trợ cố định, không phụ thuộc vào kích thước của dữ liệu đầu vào (hoặc chỉ một lượng rất nhỏ so với dữ liệu).
• B. Thuật toán yêu cầu tạo một bản sao hoàn chỉnh của dữ liệu gốc.
• C. Thứ tự tương đối của các phần tử có giá trị bằng nhau được giữ nguyên sau khi sắp xếp.
• D. Thuật toán chỉ hoạt động trên dữ liệu đã được lưu trữ trên đĩa cứng.

Câu 24: Đối với một dãy số có N phần tử, trong trường hợp xấu nhất, thuật toán sắp xếp nổi bọt (Bubble Sort) sẽ thực hiện khoảng bao nhiêu phép so sánh?

• A. N
• B. N * log(N)
• C. N * (N-1) / 2
• D. N - 1

Câu 25: Dãy số [9, 7, 5, 3, 1]. Sử dụng Sắp xếp chèn (Insertion Sort) tăng dần. Dãy số sẽ như thế nào sau khi hoàn thành việc chèn phần tử có giá trị 3 (phần tử thứ 4 ban đầu)?

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

Câu 26: Sự khác biệt cơ bản trong cách tìm phần tử để đưa về đúng vị trí giữa Sắp xếp chọn (Selection Sort) và Sắp xếp chèn (Insertion Sort) là gì?

• A. Selection Sort tìm phần tử lớn nhất, còn Insertion Sort tìm phần tử nhỏ nhất.
• B. Selection Sort tìm phần tử nhỏ nhất trong phần chưa sắp xếp và đổi chỗ về đầu phần chưa sắp xếp; Insertion Sort lấy phần tử đầu tiên của phần chưa sắp xếp và chèn vào đúng vị trí trong phần đã sắp xếp.
• C. Selection Sort chỉ hoạt động với số nguyên, còn Insertion Sort hoạt động với mọi loại dữ liệu.
• D. Selection Sort sử dụng đệ quy, còn Insertion Sort sử dụng vòng lặp.

Câu 27: Một thuật toán sắp xếp được gọi là "ổn định" (stable) nếu nó giữ nguyên thứ tự tương đối của các phần tử có giá trị bằng nhau. Trong các thuật toán đơn giản, thuật toán nào sau đây là **không** ổn định?

• A. Thuật toán sắp xếp chọn (Selection Sort)
• B. Thuật toán sắp xếp nổi bọt (Bubble Sort)
• C. Thuật toán sắp xếp chèn (Insertion Sort)
• D. Cả ba thuật toán đều ổn định.

Câu 28: Xét dãy số [2, 8, 3, 5]. Sử dụng Sắp xếp nổi bọt (Bubble Sort) tăng dần. Sau lượt duyệt thứ nhất, dãy số là [2, 3, 5, 8]. Có thể kết luận gì về trạng thái sắp xếp của dãy tại thời điểm này?

• A. Dãy đã được sắp xếp hoàn chỉnh.
• B. Phần tử đầu tiên đã ở đúng vị trí cuối cùng của nó.
• C. Tất cả các phần tử đã di chuyển đến vị trí cuối cùng của chúng.
• D. Phần tử cuối cùng (8) đã ở đúng vị trí cuối cùng của nó.

Câu 29: Khi sắp xếp một danh sách gồm các đối tượng phức tạp (ví dụ: danh sách sinh viên, mỗi sinh viên có nhiều thuộc tính), việc sử dụng thuật toán sắp xếp chọn (Selection Sort) có thể có một ưu điểm nhỏ so với Sắp xếp nổi bọt hoặc Sắp xếp chèn trong một số trường hợp thực tế. Ưu điểm đó là gì?

• A. Số lần so sánh ít hơn.
• B. Độ phức tạp thời gian tốt hơn.
• C. Số lần đổi chỗ (swap) ít hơn, điều này có thể quan trọng nếu việc đổi chỗ các đối tượng lớn tốn kém.
• D. Luôn ổn định (stable).

Câu 30: Cho dãy số [1, 2, 3, 4, 5]. Khi áp dụng thuật toán sắp xếp chèn (Insertion Sort) tăng dần, số lần đổi chỗ (swap) xảy ra là bao nhiêu?

• A. 0
• B. N
• C. N * (N-1) / 2
• D. Không thể xác định được.

Câu 1: Trong bài toán tìm kiếm, khái niệm "miền dữ liệu" (hay không gian tìm kiếm) được hiểu là gì?

• A. Tập hợp các thuật toán có thể sử dụng để giải quyết bài toán.
• B. Kết quả mong muốn mà thuật toán tìm kiếm trả về.
• C. Tập hợp tất cả các đối tượng hoặc thông tin có thể chứa đối tượng cần tìm.
• D. Số lượng bước thực hiện của thuật toán tìm kiếm.

Câu 2: Một người muốn tìm số điện thoại của một cửa hàng trong danh bạ điện thoại được sắp xếp theo tên. Thuật toán tìm kiếm nào sau đây không phù hợp nhất cho tình huống này nếu danh bạ rất lớn?

• A. Tìm kiếm tuần tự (Sequential Search)
• B. Tìm kiếm nhị phân (Binary Search)
• C. Cả hai thuật toán đều phù hợp như nhau.
• D. Tùy thuộc vào số lượng chữ cái trong tên cửa hàng.

Câu 3: Cho dãy số A = [15, 8, 22, 5, 12, 35, 18] và cần tìm giá trị K = 12 bằng thuật toán tìm kiếm tuần tự. Thuật toán sẽ thực hiện bao nhiêu phép so sánh tối đa với các phần tử trong dãy để tìm thấy K?

• A. 3
• B. 4
• C. 5
• D. 5

Câu 4: Thuật toán tìm kiếm nhị phân yêu cầu dữ liệu đầu vào phải có đặc điểm gì để hoạt động hiệu quả?

• A. Chỉ chứa các số nguyên dương.
• B. Đã được sắp xếp theo một thứ tự nhất định (tăng dần hoặc giảm dần).
• C. Có số lượng phần tử là lũy thừa của 2.
• D. Các phần tử có giá trị duy nhất, không trùng lặp.

Câu 5: Cho dãy số đã sắp xếp tăng dần: A = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]. Sử dụng tìm kiếm nhị phân để tìm giá trị K = 23. Chỉ số của phần tử được so sánh trong lần lặp thứ hai của thuật toán là bao nhiêu? (Giả sử chỉ số bắt đầu từ 0).

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

Câu 6: Xét trường hợp tốt nhất (best-case scenario) cho thuật toán tìm kiếm tuần tự trên một danh sách gồm N phần tử. Số phép so sánh cần thực hiện là bao nhiêu?

• A. 1
• B. N/2
• C. N
• D. log₂N

Câu 7: Xét trường hợp xấu nhất (worst-case scenario) cho thuật toán tìm kiếm nhị phân trên một danh sách gồm N phần tử đã được sắp xếp. Độ phức tạp thời gian (số phép so sánh) thường được biểu diễn bằng ký hiệu Big O là gì?

• A. O(1)
• B. O(N)
• C. O(log N)
• D. O(N²)

Câu 8: Ưu điểm chính của thuật toán tìm kiếm nhị phân so với tìm kiếm tuần tự khi áp dụng cho danh sách lớn và đã được sắp xếp là gì?

• A. Không cần biết trước kích thước của danh sách.
• B. Tốc độ tìm kiếm nhanh hơn đáng kể.
• C. Đơn giản hơn trong cài đặt.
• D. Có thể tìm kiếm trên dữ liệu chưa sắp xếp.

Câu 9: Khi nào thì thuật toán tìm kiếm tuần tự có thể là lựa chọn tốt hơn hoặc duy nhất có thể áp dụng so với tìm kiếm nhị phân?

• A. Khi cần tìm nhiều phần tử cùng lúc.
• B. Khi danh sách dữ liệu rất lớn.
• C. Khi cần tìm phần tử ở cuối danh sách.
• D. Khi danh sách dữ liệu chưa được sắp xếp.

Câu 10: Cho dãy số A = [10, 20, 30, 40, 50] và cần tìm K = 25 bằng tìm kiếm nhị phân. Sau khi thuật toán kết thúc, điều gì sẽ xảy ra?

• A. Thuật toán sẽ báo lỗi vì K không phải là bội số của 10.
• B. Thuật toán sẽ trả về chỉ số của phần tử gần nhất với 25 (ví dụ 20 hoặc 30).
• C. Thuật toán sẽ kết thúc và báo rằng không tìm thấy phần tử K trong dãy.
• D. Thuật toán sẽ tiếp tục lặp vô hạn.

Câu 11: Giả sử bạn có một danh sách 1024 phần tử đã được sắp xếp. Trong trường hợp xấu nhất, tìm kiếm nhị phân cần tối đa bao nhiêu lần so sánh để xác định một phần tử có tồn tại trong danh sách hay không?

• A. 10
• B. 11
• C. 512
• D. 1024

Câu 12: Trong thuật toán tìm kiếm nhị phân, nếu phần tử tại vị trí giữa lớn hơn giá trị cần tìm, thì phạm vi tìm kiếm tiếp theo sẽ được giới hạn ở đâu?

• A. Nửa bên trái của danh sách (bao gồm cả phần tử giữa nếu bằng giá trị cần tìm).
• B. Nửa bên phải của danh sách (không bao gồm phần tử giữa).
• C. Toàn bộ danh sách lại từ đầu.
• D. Chỉ phần tử tại vị trí giữa.

Câu 13: Bài toán "Tìm tất cả các bài viết về biến đổi khí hậu trên một trang web tin tức" có thể được coi là một bài toán tìm kiếm. Miền dữ liệu trong trường hợp này là gì?

• A. Chỉ các bài viết có tiêu đề chứa cụm từ "biến đổi khí hậu".
• B. Số lượng bài viết về biến đổi khí hậu.
• C. Các trang web khác nói về biến đổi khí hậu.
• D. Tất cả các bài viết có trên trang web tin tức đó.

Câu 14: Thuật toán tìm kiếm tuần tự hoạt động dựa trên nguyên tắc cơ bản nào?

• A. Chia danh sách thành hai nửa.
• B. So sánh phần tử cần tìm với phần tử ở giữa danh sách.
• C. Duyệt qua từng phần tử trong danh sách từ đầu đến cuối cho đến khi tìm thấy hoặc hết danh sách.
• D. Sử dụng chỉ mục để truy cập trực tiếp phần tử.

Câu 15: So sánh độ phức tạp thời gian trung bình của tìm kiếm tuần tự và tìm kiếm nhị phân trên một danh sách N phần tử (tìm kiếm thành công).

• A. Tìm kiếm tuần tự là O(N), tìm kiếm nhị phân là O(log N).
• B. Tìm kiếm tuần tự là O(log N), tìm kiếm nhị phân là O(N).
• C. Cả hai đều là O(N).
• D. Cả hai đều là O(log N).

Câu 16: Giả sử bạn có một danh sách 100 phần tử chưa được sắp xếp. Bạn muốn tìm một giá trị cụ thể. Thuật toán nào sau đây là lựa chọn phù hợp ngay lập tức mà không cần thao tác tiền xử lý?

• A. Tìm kiếm tuần tự.
• B. Tìm kiếm nhị phân.
• C. Cả hai đều cần sắp xếp trước.
• D. Không có thuật toán nào phù hợp.

Câu 17: Trong tìm kiếm nhị phân trên dãy A = [5, 10, 15, 20, 25, 30, 35], tìm K = 30. Lần so sánh đầu tiên sẽ kiểm tra phần tử nào? (Giả sử chỉ số từ 0)

• A. 5 (chỉ số 0)
• B. 15 (chỉ số 2)
• C. 20 (chỉ số 3)
• D. 35 (chỉ số 6)

Câu 18: Tiếp theo Câu 17, sau lần so sánh đầu tiên, phạm vi tìm kiếm tiếp theo cho K = 30 sẽ là các chỉ số nào?

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

Câu 19: Mục tiêu cuối cùng của bài toán tìm kiếm là gì?

• A. Sắp xếp dữ liệu.
• B. Xác định xem một đối tượng cụ thể có tồn tại trong miền dữ liệu hay không và, nếu có, trả về thông tin về nó (ví dụ: vị trí).
• C. Đếm số lượng đối tượng trong miền dữ liệu.
• D. Thay đổi giá trị của các đối tượng trong miền dữ liệu.

Câu 20: Tại sao việc sắp xếp dữ liệu lại là bước tiền xử lý quan trọng đối với thuật toán tìm kiếm nhị phân?

• A. Để có thể loại bỏ một nửa miền tìm kiếm sau mỗi lần so sánh với phần tử giữa.
• B. Để đảm bảo các phần tử có giá trị duy nhất.
• C. Để giảm số lượng phần tử trong danh sách.
• D. Để dễ dàng cài đặt thuật toán hơn.

Câu 21: Độ phức tạp thời gian của thuật toán tìm kiếm tuần tự trong trường hợp xấu nhất trên danh sách N phần tử là O(N). Điều này có nghĩa là gì?

• A. Thời gian thực hiện tăng gấp đôi khi số lượng phần tử tăng gấp đôi.
• B. Thời gian thực hiện không phụ thuộc vào số lượng phần tử.
• C. Thời gian thực hiện tăng tỷ lệ thuận với số lượng phần tử N.
• D. Thời gian thực hiện tăng rất nhanh khi số lượng phần tử tăng.