15+ Đề Trắc nghiệm Tin học 11 Kết nối tri thức Bài 22: Thực hành bài toán sắp xếp

Câu 1: Trong tình huống nào sau đây, thuật toán sắp xếp chèn (Insertion Sort) được xem là lựa chọn hiệu quả nhất về mặt hiệu suất?

• A. Khi cần sắp xếp một danh sách lớn các số ngẫu nhiên.
• B. Khi danh sách cần sắp xếp đã gần như được sắp xếp hoàn toàn.
• C. Khi yêu cầu bộ nhớ sử dụng phải tối thiểu tuyệt đối.
• D. Khi cần đảm bảo thời gian sắp xếp là nhanh nhất trong mọi trường hợp.

Câu 2: Xét một danh sách [5, 2, 4, 7, 1, 3, 2, 6]. Nếu sử dụng thuật toán sắp xếp chọn (Selection Sort) để sắp xếp danh sách này theo thứ tự tăng dần, thì sau bước duyệt đầu tiên, danh sách sẽ trở thành như thế nào?

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

Câu 3: Trong thuật toán sắp xếp nổi bọt (Bubble Sort), điều gì xảy ra sau khi hoàn thành một lần duyệt qua toàn bộ danh sách?

• A. Danh sách đã được sắp xếp hoàn toàn.
• B. Phần tử nhỏ nhất đã được đưa về vị trí đầu tiên.
• C. Phần tử lớn nhất (hoặc nhỏ nhất, tùy theo thứ tự sắp xếp) đã được đưa về vị trí cuối cùng (hoặc đầu tiên).
• D. Thứ tự của các phần tử trong danh sách không thay đổi.

Câu 4: Giải thích tại sao thuật toán sắp xếp chèn (Insertion Sort) lại có hiệu suất tốt hơn sắp xếp nổi bọt (Bubble Sort) đối với dữ liệu gần như đã sắp xếp.

• A. Vì sắp xếp chèn luôn thực hiện ít phép so sánh hơn sắp xếp nổi bọt.
• B. Vì sắp xếp chèn chỉ dịch chuyển các phần tử đến đúng vị trí của chúng mà không cần nhiều lần hoán đổi như sắp xếp nổi bọt trong trường hợp dữ liệu gần đúng thứ tự.
• C. Vì sắp xếp chèn sử dụng ít bộ nhớ hơn sắp xếp nổi bọt.
• D. Vì sắp xếp chèn dễ dàng song song hóa hơn sắp xếp nổi bọt.

Câu 5: Trong đoạn mã Python sau, dòng lệnh `if arr[j] < arr[j-1]:` đóng vai trò gì trong thuật toán sắp xếp?

• A. Khởi tạo vòng lặp để duyệt qua danh sách.
• B. Hoán đổi vị trí hai phần tử trong danh sách.
• C. Kiểm tra xem danh sách đã được sắp xếp hay chưa.
• D. So sánh hai phần tử liền kề để xác định thứ tự của chúng và chuẩn bị cho việc hoán đổi nếu cần.

Câu 6: Ưu điểm chính của thuật toán sắp xếp chọn (Selection Sort) so với thuật toán sắp xếp nổi bọt (Bubble Sort) là gì?

• A. Sắp xếp chọn dễ cài đặt hơn sắp xếp nổi bọt.
• B. Sắp xếp chọn sử dụng ít bộ nhớ hơn sắp xếp nổi bọt.
• C. Sắp xếp chọn thực hiện ít phép hoán đổi hơn sắp xếp nổi bọt.
• D. Sắp xếp chọn luôn nhanh hơn sắp xếp nổi bọt trong mọi trường hợp.

Câu 7: Nhược điểm lớn nhất của thuật toán sắp xếp nổi bọt (Bubble Sort) khiến nó ít được sử dụng trong thực tế là gì?

• A. Độ phức tạp thời gian lớn, đặc biệt với dữ liệu có kích thước lớn.
• B. Khó cài đặt và dễ gây lỗi lập trình.
• C. Yêu cầu bộ nhớ lớn để lưu trữ dữ liệu tạm thời.
• D. Không ổn định (unstable sort).

Câu 8: Bạn có một danh sách điểm thi của học sinh và muốn sắp xếp chúng theo thứ tự giảm dần để hiển thị bảng xếp hạng. Thuật toán sắp xếp nào trong số các thuật toán đã học (chèn, chọn, nổi bọt) là phù hợp nhất để thực hiện công việc này một cách hiệu quả, nếu số lượng học sinh không quá lớn (ví dụ, dưới 100)?

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

Câu 9: Giả sử bạn cần sắp xếp một chồng bài kiểm tra theo thứ tự bảng chữ cái của tên học sinh. Bạn quyết định sử dụng phương pháp sắp xếp chèn. Mô tả bước đầu tiên bạn sẽ thực hiện.

• A. Chia chồng bài kiểm tra thành hai phần: một phần đã sắp xếp và một phần chưa sắp xếp.
• B. Lấy bài kiểm tra đầu tiên (thứ hai từ đầu nếu coi bài đầu tiên đã "sắp xếp") và so sánh nó với các bài kiểm tra trước đó (trong phần đã sắp xếp, nếu có) để tìm vị trí chèn thích hợp.
• C. Tìm bài kiểm tra có tên đứng đầu bảng chữ cái trong toàn bộ chồng bài.
• D. Đổi chỗ bài kiểm tra đầu tiên với bài kiểm tra cuối cùng.

Câu 10: Xét danh sách [8, 5, 2, 9, 5, 6, 3]. Nếu á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, sau vòng lặp đầu tiên, danh sách sẽ trở thành:

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

Câu 11: Trong thuật toán sắp xếp chọn (Selection Sort) để sắp xếp danh sách theo thứ tự tăng dần, ở mỗi bước lặp, chúng ta thực hiện thao tác chính nào?

• A. So sánh các cặp phần tử liền kề và hoán đổi nếu chúng không đúng thứ tự.
• B. Tìm phần tử nhỏ nhất trong phần chưa được sắp xếp của danh sách 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 đúng vị trí trong phần đã được sắp xếp của danh sách.
• D. Chia danh sách thành các danh sách con và sắp xếp từng danh sách con.

Câu 12: Khi nào thuật toán sắp xếp chèn (Insertion Sort) thể hiện hiệu suất tốt nhất (trường hợp tốt nhất)?

• A. Khi danh sách đã được sắp xếp hoàn toàn.
• B. Khi danh sách được sắp xếp ngược thứ tự.
• C. Khi danh sách chứa nhiều phần tử trùng lặp.
• D. Khi danh sách có kích thước rất lớn.

Câu 13: Giả sử bạn có một ứng dụng quản lý thư viện, và bạn muốn sắp xếp sách theo tiêu đề. Với số lượng sách lớn và thường xuyên có sách mới được thêm vào, thuật toán sắp xếp nào (trong số chèn, chọn, nổi bọt) sẽ là lựa chọn hợp lý hơn cả để duy trì danh sách sách luôn được sắp xếp?

• A. Thuật toán sắp xếp nổi bọt (Bubble Sort)
• B. Thuật toán sắp xếp chọn (Selection Sort)
• C. Cả ba thuật toán đều phù hợp như nhau.
• D. Thuật toán sắp xếp chèn (Insertion Sort), vì nó hiệu quả khi thêm phần tử mới vào danh sách đã sắp xếp.

Câu 14: Cho danh sách [10, 9, 8, 7, 6, 5]. Nếu sử dụng thuật toán sắp xếp chọn (Selection Sort) để sắp xếp theo thứ tự tăng dần, sau khi hoàn thành 3 bước lặp đầu tiên, danh sách sẽ trở thành:

• A. [5, 6, 7, 8, 9, 10]
• B. [6, 7, 8, 9, 10, 5]
• C. [8, 9, 10, 7, 6, 5]
• D. [7, 8, 9, 10, 6, 5]

Câu 15: Trong thuật toán sắp xếp nổi bọt (Bubble Sort), số lần so sánh trong trường hợp xấu nhất (worst-case scenario) tỉ lệ như thế nào với số lượng phần tử "n" trong danh sách?

• A. Tuyến tính (tỉ lệ thuận với n)
• B. Logarit (tỉ lệ với log n)
• C. Bình phương (tỉ lệ với n^2)
• D. Hằng số (không đổi theo n)

Câu 16: Để sắp xếp một danh sách các số nguyên theo thứ tự giảm dần bằng thuật toán sắp xếp chèn (Insertion Sort), bạn cần điều chỉnh điều kiện so sánh trong quá trình chèn như thế nào?

• A. Không cần điều chỉnh gì, thuật toán sắp xếp chèn luôn sắp xếp giảm dần.
• B. Thay đổi phép so sánh từ "nhỏ hơn" thành "lớn hơn" khi tìm vị trí chèn.
• C. Đảo ngược danh sách sau khi đã sắp xếp tăng dần.
• D. Sử dụng một thuật toán sắp xếp khác.

Câu 17: Trong một chương trình quản lý sản phẩm, bạn cần sắp xếp sản phẩm theo giá từ cao xuống thấp. Bạn có một danh sách lớn các sản phẩm nhưng giá thường xuyên được cập nhật và sản phẩm mới được thêm vào. Thuật toán sắp xếp nào (chèn, chọn, nổi bọt) sẽ phù hợp nhất để sử dụng định kỳ (ví dụ, mỗi đêm) để cập nhật thứ tự sắp xếp?

• A. Thuật toán sắp xếp nổi bọt (Bubble Sort)
• B. Thuật toán sắp xếp chèn (Insertion Sort)
• C. Thuật toán sắp xếp chọn (Selection Sort)
• D. Cả ba thuật toán đều có hiệu quả tương đương trong trường hợp này.

Câu 18: Giả sử bạn đang xây dựng một chức năng gợi ý tìm kiếm, và bạn muốn sắp xếp các kết quả tìm kiếm theo mức độ liên quan (điểm số). Bạn có một danh sách kết quả tìm kiếm và điểm số tương ứng. Thuật toán sắp xếp nào (chèn, chọn, nổi bọt) sẽ phù hợp nhất nếu bạn muốn hiển thị kết quả theo thứ tự liên quan nhất lên đầu?

• A. Thuật toán sắp xếp nổi bọt (Bubble Sort)
• B. Thuật toán sắp xếp chọn (Selection Sort)
• C. Không cần sắp xếp, chỉ cần hiển thị kết quả theo thứ tự tìm thấy.
• D. Bất kỳ thuật toán sắp xếp nào trong số trên (chèn, chọn, nổi bọt) đều có thể sử dụng để sắp xếp theo điểm số.

Câu 19: So sánh số lượng phép hoán đổi trung bình giữa thuật toán sắp xếp chọn (Selection Sort) và thuật toán sắp xếp nổi bọt (Bubble Sort) khi sắp xếp một danh sách ngẫu nhiên. Thuật toán nào thường thực hiện ít phép hoán đổi hơn?

• A. Sắp xếp chọn (Selection Sort) thường thực hiện ít phép hoán đổi hơn.
• B. Sắp xếp nổi bọt (Bubble Sort) thường thực hiện ít phép hoán đổi hơn.
• C. Cả hai thuật toán thực hiện số lượng phép hoán đổi tương đương nhau.
• D. Số lượng phép hoán đổi phụ thuộc vào kích thước danh sách, không thể so sánh chung.

Câu 20: Bạn có một danh sách các giao dịch ngân hàng cần được sắp xếp theo thời gian giao dịch. Nếu các giao dịch thường đã được sắp xếp gần đúng theo thời gian (chỉ có một vài giao dịch bị lệch thứ tự), thuật toán sắp xếp nào (chèn, chọn, nổi bọt) sẽ là lựa chọn tối ưu để nhanh chóng hoàn thành việc sắp xếp?

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

Câu 21: Trong thuật toán sắp xếp chèn (Insertion Sort), vòng lặp bên ngoài (outer loop) thường bắt đầu từ phần tử thứ hai của danh sách. Giải thích lý do tại sao lại như vậy.

• A. Để giảm số lượng phép so sánh cần thực hiện.
• B. Để đảm bảo phần tử đầu tiên luôn là phần tử nhỏ nhất.
• C. Vì phần tử đầu tiên được coi như là một danh sách con đã được sắp xếp, và thuật toán bắt đầu chèn các phần tử còn lại vào danh sách con đã sắp xếp này.
• D. Đó chỉ là quy ước lập trình, không có lý do cụ thể.

Câu 22: Xét một danh sách gồm 1000 phần tử đã được sắp xếp ngược thứ tự. Thuật toán sắp xếp nào (chèn, chọn, nổi bọt) sẽ mất nhiều thời gian nhất để sắp xếp danh sách này theo thứ tự tăng dần?

• A. Thuật toán sắp xếp chèn (Insertion Sort)
• B. Thuật toán sắp xếp chọn (Selection Sort)
• C. Thuật toán sắp xếp nổi bọt (Bubble Sort)
• D. Cả ba thuật toán sẽ mất thời gian tương đương nhau trong trường hợp này.

Câu 23: Trong quá trình triển khai thuật toán sắp xếp chọn (Selection Sort), biến "min_index" (hoặc tương tự) thường được sử dụng để làm gì?

• A. Đếm số lượng phần tử đã được sắp xếp.
• B. Lưu trữ chỉ số của phần tử nhỏ nhất (hoặc lớn nhất) được tìm thấy trong phần chưa sắp xếp của danh sách.
• C. Xác định vị trí cần chèn phần tử trong thuật toán sắp xếp chèn.
• D. Kiểm soát số lần lặp của vòng lặp.

Câu 24: Giả sử bạn muốn sắp xếp một danh sách các đối tượng phức tạp (ví dụ, các bản ghi thông tin học sinh) dựa trên một thuộc tính cụ thể (ví dụ, điểm trung bình). Các thuật toán sắp xếp chèn, chọn, nổi bọt có thể được áp dụng trực tiếp không, hay cần điều chỉnh gì?

• A. Có thể áp dụng, nhưng cần điều chỉnh phép so sánh để so sánh dựa trên thuộc tính mong muốn (ví dụ, so sánh điểm trung bình thay vì so sánh trực tiếp các đối tượng).
• B. Không thể áp dụng trực tiếp, cần viết thuật toán sắp xếp hoàn toàn mới cho đối tượng phức tạp.
• C. Chỉ có thuật toán sắp xếp nổi bọt là có thể áp dụng cho đối tượng phức tạp.
• D. Cần chuyển đổi đối tượng phức tạp thành dữ liệu đơn giản trước khi sắp xếp.

Câu 25: Trong thuật toán sắp xếp nổi bọt (Bubble Sort) cải tiến, người ta thường sử dụng một biến cờ (flag) để kiểm tra xem có lần hoán đổi nào xảy ra trong một vòng lặp hay không. Mục đích của việc này là gì?

• A. Để tăng tốc độ hoán đổi các phần tử.
• B. Để phát hiện khi danh sách đã được sắp xếp hoàn toàn và dừng thuật toán sớm, tránh các vòng lặp không cần thiết.
• C. Để giảm số lượng phép so sánh trong mỗi vòng lặp.
• D. Để đơn giản hóa việc cài đặt thuật toán.

Câu 26: Nếu bạn cần sắp xếp một mảng số nguyên có kích thước rất nhỏ (ví dụ, dưới 10 phần tử), việc lựa chọn thuật toán sắp xếp (chèn, chọn, nổi bọt) có ảnh hưởng đáng kể đến hiệu suất tổng thể của chương trình không?

• A. Có, thuật toán sắp xếp chọn luôn nhanh hơn đáng kể so với các thuật toán khác.
• B. Có, thuật toán sắp xếp nổi bọt luôn chậm hơn đáng kể và nên tránh.
• C. Không, với kích thước nhỏ, sự khác biệt về hiệu suất giữa các thuật toán này thường không đáng kể.
• D. Có, thuật toán sắp xếp chèn luôn là lựa chọn tốt nhất cho mảng nhỏ.

Câu 27: Trong thuật toán sắp xếp chọn (Selection Sort), sau khi vòng lặp đầu tiên kết thúc, bạn có thể chắc chắn điều gì về phần tử đầu tiên của danh sách?

• A. Nó là phần tử lớn nhất trong danh sách.
• B. Nó nằm ở vị trí cuối cùng trong danh sách đã sắp xếp.
• C. Nó đã được so sánh với tất cả các phần tử còn lại trong danh sách.
• D. Nó là phần tử nhỏ nhất trong danh sách (nếu sắp xếp tăng dần) và đã ở đúng vị trí cuối cùng của nó trong danh sách đã sắp xếp.

Câu 28: Để sắp xếp một danh sách các chuỗi ký tự theo thứ tự bảng chữ cái, bạn có thể sử dụng trực tiếp các thuật toán sắp xếp số (chèn, chọn, nổi bọt) không? Nếu có, phép so sánh sẽ được thực hiện như thế nào?

• A. Có, có thể sử dụng trực tiếp. Phép so sánh sẽ được thực hiện dựa trên thứ tự mã ASCII (hoặc Unicode) của các ký tự trong chuỗi.
• B. Không thể sử dụng trực tiếp, cần chuyển đổi chuỗi thành số trước khi sắp xếp.
• C. Chỉ có thuật toán sắp xếp chèn là có thể sử dụng cho chuỗi.
• D. Cần viết hàm so sánh riêng cho chuỗi và tích hợp vào thuật toán sắp xếp.

Câu 29: Bạn muốn sắp xếp một danh sách số nguyên sao cho các số chẵn đứng trước các số lẻ, và trong mỗi nhóm (chẵn và lẻ), các số được sắp xếp tăng dần. Bạn có thể kết hợp các thuật toán sắp xếp cơ bản (chèn, chọn, nổi bọt) như thế nào để đạt được mục tiêu này?

• A. Không thể đạt được mục tiêu này chỉ với các thuật toán sắp xếp cơ bản.
• B. Chỉ cần sắp xếp danh sách bằng một trong các thuật toán (chèn, chọn, nổi bọt) là đủ.
• C. Có thể chia danh sách thành hai phần (chẵn và lẻ), sắp xếp từng phần bằng thuật toán sắp xếp, sau đó ghép lại.
• D. Cần sử dụng thuật toán sắp xếp tùy chỉnh hoàn toàn mới.

Câu 30: Trong bối cảnh thực tế, khi nào việc sử dụng các thuật toán sắp xếp đơn giản như chèn, chọn, nổi bọt vẫn được ưu tiên mặc dù có các thuật toán sắp xếp phức tạp và hiệu quả hơn (ví dụ, sắp xếp nhanh, sắp xếp trộn)?

• A. Khi cần sắp xếp danh sách có kích thước cực lớn.
• B. Khi danh sách có kích thước nhỏ, hoặc khi yêu cầu về độ phức tạp của code và tính dễ bảo trì được ưu tiên hơn hiệu suất tuyệt đối.
• C. Khi cần đảm bảo thời gian sắp xếp là nhanh nhất trong mọi trường hợp.
• D. Các thuật toán sắp xếp đơn giản không bao giờ được ưu tiên trong thực tế.

Câu 1: Trong bài toán quản lý kho hàng, việc sắp xếp các sản phẩm theo thứ tự xuất nhập kho gần nhất mang lại lợi ích nào sau đây?

• A. Giảm thiểu chi phí lưu trữ do hàng hóa được sắp xếp ngăn nắp hơn.
• B. Tăng tốc độ bán hàng nhờ việc ưu tiên hiển thị các sản phẩm mới.
• C. Dễ dàng xác định và quản lý các sản phẩm tồn kho lâu ngày, tránh tình trạng hết hạn hoặc lỗi thời.
• D. Cải thiện tính thẩm mỹ của kho hàng, tạo ấn tượng tốt với khách hàng và đối tác.

Câu 2: Xét thuật toán sắp xếp chèn (Insertion Sort) trên một mảng đã gần như được sắp xếp. Phát biểu nào sau đây mô tả đúng nhất hiệu quả của thuật toán trong trường hợp này?

• A. Thuật toán sắp xếp chèn luôn có hiệu suất kém nhất trên mảng gần như đã sắp xếp.
• B. Thuật toán sắp xếp chèn hoạt động rất hiệu quả, gần như đạt độ phức tạp tuyến tính O(n).
• C. Thuật toán sắp xếp chèn không tận dụng được tính chất gần sắp xếp của mảng.
• D. Hiệu suất của thuật toán sắp xếp chèn không đổi, không phụ thuộc vào trạng thái ban đầu của mảng.

Câu 3: Trong thuật toán sắp xếp chọn (Selection Sort) để sắp xếp một danh sách số theo thứ tự giảm dần, bước nào sau đây được lặp lại cho đến khi danh sách được sắp xếp hoàn chỉnh?

• A. Tìm phần tử lớn nhất trong phần chưa được sắp xếp và đưa về đầu phần chưa sắp xếp.
• B. Tìm phần tử nhỏ nhất trong phần chưa được sắp xếp và đưa về đầu phần chưa sắp xếp.
• 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ự giảm dần.
• D. Chia danh sách thành hai phần, sắp xếp từng phần rồi trộn lại.

Câu 4: Xét một danh sách gồm tên các học sinh. Nếu muốn sắp xếp danh sách này theo thứ tự bảng chữ cái, tiêu chí so sánh chính sẽ dựa trên yếu tố nào?

• A. Chiều dài của chuỗi tên (số lượng ký tự).
• B. Số lượng nguyên âm trong tên.
• C. Thứ tự xuất hiện của tên trong danh sách ban đầu.
• D. Thứ tự chữ cái của ký tự đầu tiên, sau đó là các ký tự tiếp theo nếu cần.

Câu 5: Thuật toán sắp xếp nổi bọt (Bubble Sort) có tên gọi như vậy là do đặc điểm nào trong quá trình sắp xếp?

• A. Các phần tử nhỏ "chìm" xuống đáy danh sách.
• B. Các phần tử lớn bị loại bỏ dần như bọt biển.
• C. Các phần tử lớn "nổi" lên trên như bọt khí trong quá trình so sánh và đổi chỗ.
• D. Thuật toán tạo ra nhiều "bọt" lỗi trong quá trình sắp xếp cần được xử lý.

Câu 6: Trong tình huống nào, thuật toán sắp xếp chèn (Insertion Sort) được xem là lựa chọn phù hợp hơn so với thuật toán sắp xếp chọn (Selection Sort)?

• A. Khi cần sắp xếp một danh sách có kích thước rất lớn.
• B. Khi danh sách cần sắp xếp đã gần như được sắp xếp.
• C. Khi yêu cầu về bộ nhớ sử dụng là yếu tố quan trọng hàng đầu.
• D. Khi cần đảm bảo số lần so sánh giữa các phần tử là ít nhất.

Câu 7: Cho một danh sách số: [5, 2, 8, 1, 9]. Sau bước đầu tiên của thuật toán sắp xếp chọn (Selection Sort) để sắp xếp tăng dần, danh sách sẽ trở thành:

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

Câu 8: Độ phức tạp thời gian trung bình 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ì về hiệu suất của thuật toán khi kích thước dữ liệu tăng lên?

• A. Thời gian thực hiện thuật toán tăng tuyến tính theo kích thước dữ liệu.
• B. Thời gian thực hiện thuật toán giảm khi kích thước dữ liệu tăng lên.
• C. Thời gian thực hiện thuật toán tăng theo lũy thừa bậc hai của kích thước dữ liệu.
• D. Thời gian thực hiện thuật toán không phụ thuộc vào kích thước dữ liệu.

Câu 9: Trong thuật toán sắp xếp chèn (Insertion Sort), thao tác "chèn" một phần tử vào vị trí đúng trong phần đã sắp xếp đòi hỏi kỹ thuật nào?

• A. Chia để trị và trộn (Divide and Conquer).
• B. Hoán đổi trực tiếp các cặp phần tử (Direct Swapping).
• C. Tìm kiếm nhị phân để xác định vị trí chèn (Binary Search).
• D. Dịch chuyển các phần tử lớn hơn sang phải để tạo khoảng trống (Shifting Larger Elements).

Câu 10: Giả sử bạn có một danh sách các số điện thoại cần sắp xếp theo thứ tự tăng dần. Thuật toán sắp xếp nào sẽ phù hợp nhất nếu bạn ưu tiên sự đơn giản và dễ cài đặt, ngay cả khi hiệu suất không phải là tối ưu?

• A. Thuật toán sắp xếp nổi bọt (Bubble Sort).
• B. Thuật toán sắp xếp trộn (Merge Sort).
• C. Thuật toán sắp xếp nhanh (Quick Sort).
• D. Thuật toán sắp xếp vun đống (Heap Sort).

Câu 11: Để sắp xếp một tập hợp lớn các bản ghi dữ liệu phức tạp (ví dụ: thông tin sinh viên bao gồm tên, mã số, điểm trung bình), bạn cần xác định yếu tố nào quan trọng nhất trước khi chọn thuật toán sắp xếp?

• A. Kích thước của bản ghi dữ liệu.
• B. Loại dữ liệu của các trường không phải khóa sắp xếp.
• C. Trường (hoặc các trường) được sử dụng làm khóa sắp xếp.
• D. Ngôn ngữ lập trình được sử dụng để cài đặt thuật toán.

Câu 12: Trong quá trình sắp xếp một danh sách bằng thuật toán sắp xếp chèn (Insertion Sort), tại một thời điểm nhất định, danh sách được chia thành hai phần: phần đã sắp xếp và phần chưa sắp xếp. Phần đã sắp xếp nằm ở vị trí nào trong danh sách?

• A. Luôn nằm ở đầu danh sách.
• B. Luôn nằm ở cuối danh sách.
• C. Nằm xen kẽ với phần chưa sắp xếp.
• D. Vị trí phần đã sắp xếp thay đổi ngẫu nhiên.

Câu 13: Xét tình huống cần sắp xếp điểm thi của học sinh từ cao xuống thấp để xếp hạng. Thuật toán sắp xếp chọn (Selection Sort) thực hiện việc này như thế nào?

• A. Tìm điểm thấp nhất và đưa lên đầu danh sách.
• B. Tìm điểm cao nhất trong phần chưa xếp hạng và đưa lên đầu phần chưa xếp hạng.
• C. So sánh điểm của từng cặp học sinh liền kề và đổi chỗ nếu điểm không giảm dần.
• D. Chia danh sách điểm thành các nhóm nhỏ, sắp xếp từng nhóm rồi ghép lại.

Câu 14: Trong thuật toán sắp xếp nổi bọt (Bubble Sort), sau mỗi lần duyệt qua danh sách, điều gì được đảm bảo về vị trí của các phần tử?

• A. Toàn bộ danh sách đã được sắp xếp hoàn chỉnh.
• B. Phần tử nhỏ nhất đã được đưa về vị trí đầu tiên.
• C. Phần tử ở giữa danh sách đã ở đúng vị trí cuối cùng.
• D. Phần tử lớn nhất (hoặc nhỏ nhất, tùy theo thứ tự sắp xếp) đã được đưa về vị trí đúng cuối cùng (hoặc đầu tiên).

Câu 15: Để đánh giá hiệu quả của một thuật toán sắp xếp, người ta thường sử dụng tiêu chí nào sau đây?

• A. Độ phức tạp thời gian và độ phức tạp không gian.
• B. Số dòng code cần thiết để cài đặt thuật toán.
• C. Tính dễ hiểu và dễ bảo trì của code.
• D. Màu sắc và giao diện người dùng của chương trình sắp xếp.

Câu 16: Cho danh sách [7, 3, 9, 1, 5]. Áp dụng thuật toán sắp xếp chèn (Insertion Sort), sau khi chèn phần tử "9" vào đúng vị trí, danh sách sẽ như thế nào?

• A. [3, 7, 9, 1, 5]
• B. [1, 3, 5, 7, 9]
• C. [7, 3, 9, 1, 5]
• D. [3, 7, 9, 1, 5] (Vì 9 đã đúng vị trí trong phần đã sắp xếp [3, 7])

Câu 17: Trong thuật toán sắp xếp chọn (Selection Sort), số lượng phép so sánh cần thực hiện để sắp xếp một danh sách có n phần tử là bao nhiêu?

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

Câu 18: Thuật toán sắp xếp nào sau đây có độ phức tạp thời gian tốt nhất trong trường hợp trung bình và trường hợp tốt 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. Sắp xếp trộn (Merge Sort)

Câu 19: Trong một ứng dụng quản lý thư viện, bạn cần sắp xếp sách theo tiêu đề. Kiểu sắp xếp nào phù hợp nhất với dữ liệu là chuỗi ký tự (tiêu đề sách)?

• A. Sắp xếp số học.
• B. Sắp xếp từ điển (lexicographical sort).
• C. Sắp xếp theo độ dài chuỗi.
• D. Sắp xếp ngẫu nhiên.

Câu 20: Nếu bạn cần sắp xếp một lượng nhỏ dữ liệu và code cần dễ hiểu, dễ bảo trì, thuật toán nào sau đây có thể là lựa chọn tốt nhất?

• A. Sắp xếp nhanh (Quick Sort).
• B. Sắp xếp trộn (Merge Sort).
• C. Sắp xếp chèn (Insertion Sort).
• D. Sắp xếp vun đống (Heap Sort).

Câu 21: Trong thuật toán sắp xếp nổi bọt (Bubble Sort), số lần duyệt qua danh sách trong trường hợp xấu nhất (danh sách đảo ngược thứ tự) để hoàn thành sắp xếp là bao nhiêu với danh sách n phần tử?

• A. 1
• B. n-1
• C. n
• D. log n

Câu 22: Cho danh sách [4, 2, 1, 3]. Sau bước đầu tiên của thuật toán sắp xếp nổi bọt (Bubble Sort) để sắp xếp tăng dần, danh sách sẽ là:

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

Câu 23: Ưu điểm chính của thuật toán sắp xếp chèn (Insertion Sort) so với sắp xếp chọn (Selection Sort) trong trường hợp danh sách gần như đã được sắp xếp là gì?

• A. Sắp xếp chèn có độ phức tạp không gian tốt hơn.
• B. Sắp xếp chèn có thể kết thúc sớm hơn khi danh sách đã được sắp xếp một phần.
• C. Sắp xếp chèn dễ cài đặt hơn sắp xếp chọn.
• D. Sắp xếp chèn luôn ổn định hơn sắp xếp chọn.

Câu 24: Trong thuật toán sắp xếp chọn (Selection Sort), số lần hoán đổi vị trí các phần tử trong trường hợp xấu nhất là bao nhiêu với danh sách n phần tử?

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

Câu 25: Để sắp xếp danh sách các sản phẩm theo giá từ thấp đến cao trong một trang web bán hàng trực tuyến, thuật toán nào có thể được sử dụng?

• A. Thuật toán tìm kiếm tuyến tính.
• B. Thuật toán tìm kiếm nhị phân.
• C. Thuật toán duyệt đồ thị.
• D. Thuật toán sắp xếp (ví dụ: sắp xếp chèn, sắp xếp chọn, sắp xếp nổi bọt).

Câu 26: Trong thuật toán sắp xếp chèn (Insertion Sort), khi nào thì số phép so sánh và số phép gán (di chuyển phần tử) là ít nhất?

• A. Khi danh sách được sắp xếp ngược thứ tự.
• B. Khi danh sách đã được sắp xếp.
• C. Khi danh sách chứa các phần tử trùng lặp.
• D. Khi danh sách có kích thước rất lớn.

Câu 27: Phát biểu nào sau đây mô tả đúng nhất về tính ổn định (stability) của thuật toán sắp xếp?

• A. Thuật toán luôn cho kết quả đúng sau một số hữu hạn bước.
• B. Thuật toán có hiệu suất không đổi với mọi loại dữ liệu đầu vào.
• C. Thuật toán giữ nguyên thứ tự tương đối của các phần tử có khóa bằng nhau.
• D. Thuật toán dễ dàng thích nghi với các thay đổi của dữ liệu đầu vào.

Câu 28: Thuật toán sắp xếp nào sau đây thường được sử dụng làm thuật toán con (subroutine) trong các thuật toán sắp xếp phức tạp hơn, như sắp xếp trộn (Merge Sort)?

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

Câu 29: Trong ngôn ngữ lập trình Python, hàm `sort()` và hàm `sorted()` được sử dụng để sắp xếp danh sách. Sự khác biệt chính giữa hai hàm này là gì?

• A. `sort()` sắp xếp theo thứ tự giảm dần, `sorted()` sắp xếp theo thứ tự tăng dần.
• B. `sort()` chỉ sắp xếp số, `sorted()` có thể sắp xếp cả chuỗi.
• C. `sort()` nhanh hơn `sorted()`.
• D. `sort()` sắp xếp trực tiếp trên danh sách ban đầu (in-place), `sorted()` trả về một danh sách mới đã sắp xếp.

Câu 30: Khi lựa chọn thuật toán sắp xếp cho một ứng dụng cụ thể, yếu tố nào sau đây thường được cân nhắc đầu tiên?

• A. Hiệu suất (độ phức tạp thời gian và không gian) của thuật toán.
• B. Sự đơn giản và dễ cài đặt của thuật toán.
• C. Tính ổn định của thuật toán.
• D. Ngôn ngữ lập trình và thư viện hỗ trợ sẵn có.

Câu 1: Trong các thuật toán sắp xếp cơ bản, thuật toán nào hoạt động hiệu quả nhất trên một danh sách đã gần như được sắp xếp hoàn chỉnh?

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

Câu 2: Xét danh sách số [5, 2, 8, 1, 9]. Sau bước đầu tiên của thuật toán sắp xếp chọn (Selection Sort) để sắp xếp tăng dần, danh sách sẽ trở thành:

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

Câu 3: Trong thuật toán sắp xếp nổi bọt (Bubble Sort), điều kiện dừng của thuật toán là gì?

• A. Khi duyệt qua danh sách một lần
• B. Khi danh sách chỉ còn một phần tử
• C. Khi không có phép hoán đổi nào được thực hiện trong một lần duyệt
• D. Khi số lần so sánh đạt đến một ngưỡng nhất định

Câu 4: Giả sử bạn có một danh sách tên học sinh cần sắp xếp theo thứ tự bảng chữ cái. Thuật toán sắp xếp nào sau đây phù hợp nhất nếu bạn muốn đảm bảo tính ổn định (stable sort), tức là các học sinh có cùng tên (ví dụ trùng họ và tên) vẫn giữ nguyên thứ tự ban đầu?

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

Câu 5: Cho đoạn mã Python sau:
```python
def mystery_sort(arr):
n = len(arr)
for i in range(1, n):
key = arr[i]
j = i - 1
while j >= 0 and key < arr[j]: arr[j + 1] = arr[j] j -= 1 arr[j + 1] = key ``` Đoạn mã trên cài đặt thuật toán sắp xếp nào?

• 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ông phải thuật toán sắp xếp nào trong các thuật toán trên

Câu 6: Trong thuật toán sắp xếp chọn (Selection Sort) để sắp xếp một danh sách có N phần tử, số lượng phép so sánh tối thiểu và tối đa luôn là:

• A. Tối thiểu N, tối đa N^2
• B. Tối thiểu log N, tối đa N log N
• C. Luôn là N*(N-1)/2
• D. Tối thiểu N, tối đa 2N

Câu 7: Khi nào thuật toán sắp xếp nổi bọt (Bubble Sort) được coi là lựa chọn phù hợp, mặc dù nó thường không hiệu quả với danh sách lớn?

• A. Khi cần sắp xếp danh sách có số lượng phần tử cực lớn
• B. Khi yêu cầu hiệu suất sắp xếp là tối quan trọng
• C. Khi cần sắp xếp dữ liệu ngẫu nhiên
• D. Khi cần một thuật toán đơn giản, dễ hiểu và cài đặt, ngay cả khi không tối ưu về hiệu suất

Câu 8: Để sắp xếp một danh sách các số nguyên theo thứ tự giảm dần bằng thuật toán sắp xếp chèn (Insertion Sort), bạn cần sửa đổi điều kiện so sánh nào trong quá trình chèn phần tử vào vị trí đúng?

• A. Thay đổi từ so sánh "nhỏ hơn" (<) thành "lớn hơn" (>)
• B. Thay đổi từ so sánh "nhỏ hơn hoặc bằng" (<=) thành "lớn hơn hoặc bằng" (>=)
• C. Không cần thay đổi điều kiện so sánh, chỉ cần đảo ngược danh sách sau khi sắp xếp
• D. Thay đổi vòng lặp từ tăng dần sang giảm dần

Câu 9: Xét danh sách ban đầu: [7, 3, 1, 8, 5]. Nếu áp dụng thuật toán sắp xếp nổi bọt (Bubble Sort), danh sách sẽ trở thành [1, 3, 5, 7, 8] sau bao nhiêu lần duyệt qua toàn bộ danh sách (outer loop)?

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

Câu 10: Bạn có một tệp văn bản chứa điểm thi của học sinh, mỗi dòng là một điểm. Bạn muốn đọc các điểm này vào một danh sách và sắp xếp chúng theo thứ tự tăng dần. Thao tác nào sau đây là cần thiết trước khi sắp xếp?

• A. Kiểm tra xem danh sách có bị trùng lặp dữ liệu không
• B. Chuyển đổi dữ liệu từ kiểu chuỗi sang kiểu số
• C. Loại bỏ các dòng trống trong tệp
• D. Đảm bảo tên tệp đúng định dạng

Câu 11: Trong thuật toán sắp xếp chèn (Insertion Sort), khi chèn một phần tử vào vị trí đúng trong phần đã sắp xếp, các phần tử lớn hơn phần tử đang xét sẽ được dịch chuyển về phía nào?

• A. Về phía đầu danh sách
• B. Không dịch chuyển, mà hoán đổi trực tiếp
• C. Về phía cuối danh sách
• D. Dịch chuyển ngẫu nhiên sang trái hoặc phải

Câu 12: Thuật toán sắp xếp nào sau đây có số lượng phép hoán đổi (swaps) ít nhất 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 (Selection Sort)
• C. Sắp xếp chèn (Insertion Sort)
• D. Cả ba thuật toán đều có số lượng hoán đổi tương đương

Câu 13: Giả sử bạn cần sắp xếp điểm thi của 1000 học sinh. Bạn muốn chọn một thuật toán sắp xếp có độ phức tạp thời gian trung bình tốt nhất. Thuật toán nào sau đây nên được ưu tiê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. Sắp xếp nhanh (Quick Sort - mặc dù không được đề cập trực tiếp trong bài 22, nhưng là thuật toán hiệu quả hơn)

Câu 14: Trong quá trình thực hiện thuật toán sắp xếp chọn (Selection Sort), sau khi vòng lặp ngoài cùng thứ nhất kết thúc, điều gì đảm bảo về phần tử đầu tiên của danh sách?

• A. Phần tử đầu tiên là phần tử nhỏ nhất trong toàn bộ danh sách
• B. Phần tử đầu tiên lớn hơn phần tử thứ hai
• C. Phần tử đầu tiên đã được sắp xếp đúng vị trí cuối cùng
• D. Không có gì đảm bảo về phần tử đầu tiên sau vòng lặp thứ nhất

Câu 15: Để kiểm tra tính đúng đắn của chương trình sắp xếp, bạn nên sử dụng bộ dữ liệu kiểm thử (test data) như thế nào?

• A. Chỉ sử dụng dữ liệu đã được sắp xếp sẵn
• B. Chỉ sử dụng dữ liệu ngẫu nhiên
• C. Sử dụng dữ liệu đa dạng: đã sắp xếp, đảo ngược, ngẫu nhiên, biên (rỗng, một phần tử, trùng lặp)
• D. Chỉ cần kiểm tra với một vài trường hợp dữ liệu nhỏ

Câu 16: Trong ngữ cảnh sắp xếp dữ liệu lớn trên đĩa cứng, thuật toán nào ít bị ảnh hưởng bởi việc truy cập bộ nhớ chậm hơ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. Sắp xếp trộn (Merge Sort - mặc dù không được đề cập trực tiếp trong bài 22, nhưng liên quan đến hiệu suất trong thực tế)

Câu 17: Giả sử bạn có danh sách [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]. Thuật toán sắp xếp nào sẽ thực hiện nhiều phép hoán đổi nhất để sắp xếp danh sách này theo thứ tự tăng dầ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 thuật toán đều thực hiện số lượng hoán đổi tương đương trong trường hợp này

Câu 18: Trong thuật toán sắp xếp chèn (Insertion Sort), phần danh sách đã được sắp xếp luôn nằm ở phía nào của danh sách đang xét?

• A. Phía đầu danh sách
• B. Phía cuối danh sách
• C. Ở giữa danh sách
• D. Phân tán ngẫu nhiên trong danh sách

Câu 19: Nếu bạn muốn sắp xếp một mảng các đối tượng phức tạp dựa trên một thuộc tính khóa (key) nào đó, thuật toán sắp xếp nào dễ dàng tùy chỉnh để thực hiện việc này 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 đều dễ dàng tùy chỉnh tương đương

Câu 20: Để sắp xếp danh sách [6, 4, 1, 8, 5, 3] bằng thuật toán sắp xếp chọn (Selection Sort) theo thứ tự tăng dần, sau vòng lặp đầu tiên, phần tử nào sẽ được đưa về vị trí đầu tiên?

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

Câu 21: Xét đoạn mã Python sau:
```python
def mystery_function(data):
for i in range(len(data) - 1):
for j in range(len(data) - i - 1):
if data[j] > data[j + 1]:
data[j], data[j + 1] = data[j + 1], data[j]
return data
```
Đoạn mã này thực hiện thuật toán sắp xếp nào?

• 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ông phải thuật toán sắp xếp nào trong các thuật toán trên

Câu 22: Trong thuật toán sắp xếp chọn (Selection Sort), sau mỗi lần tìm phần tử nhỏ nhất (hoặc lớn nhất), phần tử đó được đặt vào vị trí nào trong danh sách?

• A. Vị trí cuối cùng của danh sách
• B. Vị trí đầu tiên của phần chưa được sắp xếp
• C. Vị trí giữa của danh sách
• D. Vị trí ngẫu nhiên trong danh sách

Câu 23: Để sắp xếp một danh sách giảm dần bằng thuật toán sắp xếp nổi bọt (Bubble Sort), bạn cần thay đổi phép so sánh như thế nào?

• A. Thay đổi phép so sánh từ "lớn hơn" (>) thành "nhỏ hơn" (<)
• B. Thay đổi phép so sánh từ "nhỏ hơn" (<) thành "lớn hơn" (>)
• C. Không cần thay đổi phép so sánh, chỉ cần đảo ngược danh sách sau khi sắp xếp
• D. Loại bỏ phép so sánh và chỉ thực hiện hoán đổi

Câu 24: Trong các thuật toán sắp xếp đã học, thuật toán nào có thể hoạt động "tại chỗ" (in-place), nghĩa là không cần sử dụng thêm bộ nhớ đáng kể ngoài danh sách ban đầu?

• A. Sắp xếp trộn (Merge Sort)
• B. Sắp xếp nhanh (Quick Sort)
• C. Heap Sort
• D. Sắp xếp nổi bọt, Sắp xếp chọn và Sắp xếp chèn

Câu 25: Giả sử bạn có một danh sách các sản phẩm cần sắp xếp theo giá. Nếu bạn muốn sắp xếp nhanh chóng và không quá quan trọng về tính ổn định, thuật toán nào có thể là lựa chọn tố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. Sắp xếp nhanh (Quick Sort - mặc dù không được đề cập trực tiếp trong bài 22, nhưng là thuật toán hiệu quả hơn về tốc độ)

Câu 26: Để đọc dữ liệu số từ một file văn bản "numbers.txt" và lưu vào danh sách numbers trong Python, bạn sử dụng đoạn mã nào sau đây?

• A. numbers = list(open("numbers.txt"))
• B. numbers = [int(line.strip()) for line in open("numbers.txt", "r")]
• C. numbers = readlines("numbers.txt")
• D. numbers = importdata("numbers.txt")

Câu 27: Trong thuật toán sắp xếp nổi bọt, sau mỗi lần duyệt qua danh sách, phần tử lớn nhất (hoặc nhỏ nhất, tùy theo thứ tự sắp xếp) sẽ "nổi" lên vị trí nào?

• A. Vị trí đầu tiên
• B. Vị trí giữa
• C. Vị trí cuối cùng của phần chưa sắp xếp
• D. Vị trí ngẫu nhiên

Câu 28: Thuật toán sắp xếp nào có thể được tối ưu hóa để "dừng sớm" nếu danh sách đã được sắp xếp một phần hoặc hoàn toàn trong quá trình thực hiệ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 thuật toán đều không thể tối ưu hóa để dừng sớm

Câu 29: Để sắp xếp danh sách các đối tượng học sinh theo tên và sau đó theo điểm nếu tên trùng nhau, bạn cần thực hiện sắp xếp theo tiêu chí nào?

• A. Sắp xếp ngẫu nhiên
• B. Sắp xếp thứ cấp (secondary sort)
• C. Sắp xếp song song
• D. Sắp xếp phân tán

Câu 30: Trong tình huống nào, bạn nên ưu tiên sử dụng thuật toán sắp xếp chèn (Insertion Sort) thay vì sắp xếp chọn (Selection Sort) hoặc nổi bọt (Bubble Sort)?

• A. Khi cần sắp xếp danh sách có kích thước lớn và dữ liệu hoàn toàn ngẫu nhiên
• B. Khi số lượng hoán đổi cần thực hiện phải là ít nhất
• C. Khi danh sách có kích thước nhỏ hoặc gần như đã được sắp xếp
• D. Khi yêu cầu thuật toán phải dễ cài đặt nhưng không cần quan tâm đến hiệu suất

Câu 1: Trong bài toán sắp xếp danh sách điểm thi của học sinh theo thứ tự giảm dần, thuật toán sắp xếp chọn (Selection Sort) sẽ hoạt động như thế nào trong lần lặp đầu tiên?

• A. Tìm phần tử nhỏ nhất và đặt nó ở đầu danh sách.
• B. Tìm phần tử lớn nhất và hoán đổi nó với phần tử đầu tiên của danh sách.
• C. So sánh hai phần tử đầu tiên và hoán đổi nếu chúng không đúng thứ tự.
• D. Chia danh sách thành hai phần và sắp xếp từng phần riêng biệt.

Câu 2: Xét đoạn mã Python sau để sắp xếp danh sách `A = [5, 2, 8, 1, 9]`:

```python
for i in range(len(A)):
min_idx = i
for j in range(i+1, len(A)):
if A[j] < A[min_idx]: min_idx = j A[i], A[min_idx] = A[min_idx], A[i] ``` Đoạn mã này minh họa thuật toán sắp xếp 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. Sắp xếp nhanh (Quick Sort)

Câu 3: Trong thuật toán sắp xếp chèn (Insertion Sort), khi nào thì số lượng phép so sánh là ít nhất?

• A. Khi danh sách đã được sắp xếp theo thứ tự tăng dần.
• B. Khi danh sách được sắp xếp theo thứ tự giảm dần.
• C. Khi danh sách chứa các phần tử giống nhau.
• D. Số phép so sánh không phụ thuộc vào trạng thái ban đầu của danh sách.

Câu 4: Giả sử bạn có một danh sách gần như đã được sắp xếp, chỉ có một vài phần tử nằm sai vị trí. Thuật toán sắp xếp nào sau đây có khả năng hoạt động hiệu quả nhất trong trường hợp này?

• 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 trên đều có hiệu quả tương đương.

Câu 5: Trong thuật toán sắp xếp nổi bọt (Bubble Sort), sau mỗi lần duyệt qua danh sách, điều gì được đảm bảo?

• A. Toàn bộ danh sách đã được sắp xếp hoàn chỉnh.
• B. Phần tử nhỏ nhất đã được đặt ở đầu danh sách.
• C. Phần tử lớn nhất (hoặc nhỏ nhất) đã được đặt đúng vị trí ở cuối (hoặc đầu) phần chưa sắp xếp.
• D. Không có gì được đảm bảo sau mỗi lần duyệt.

Câu 6: Bạn cần sắp xếp một danh sách các số nguyên theo thứ tự tăng dần. Yếu tố nào sau đây không ảnh hưởng trực tiếp đến thời gian thực hiện của thuật toán sắp xếp?

• A. Số lượng phần tử trong danh sách.
• B. Thứ tự ban đầu của các phần tử trong danh sách.
• C. Ngôn ngữ lập trình được sử dụng để cài đặt thuật toán.
• D. Màu sắc của các số trong danh sách.

Câu 7: Cho danh sách `B = [3, 7, 1, 9, 4]`. Nếu sử dụng thuật toán sắp xếp chèn (Insertion Sort) để sắp xếp danh sách này theo thứ tự tăng dần, danh sách sẽ có dạng như thế nào sau bước chèn phần tử thứ hai (số 7)?

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

Câu 8: Trong bài thực hành sắp xếp điểm trung bình học sinh, tại sao chúng ta cần đọc dữ liệu điểm từ tệp tin thay vì nhập trực tiếp từ bàn phím khi số lượng học sinh lớn?

• A. Để tăng tính bảo mật cho dữ liệu điểm.
• B. Để thuật toán sắp xếp hoạt động nhanh hơn.
• C. Để dễ dàng nhập và quản lý dữ liệu điểm số lượng lớn, tránh sai sót khi nhập bằng tay.
• D. Việc đọc từ tệp tin là yêu cầu bắt buộc của thuật toán sắp xếp.

Câu 9: Khi cài đặt thuật toán sắp xếp chọn (Selection Sort) để sắp xếp giảm dần, điều kiện so sánh trong vòng lặp để tìm phần tử lớn nhất cần thay đổi như thế nào so với sắp xếp tăng dần?

• A. Không cần thay đổi, thuật toán sắp xếp chọn luôn sắp xếp giảm dần.
• B. Thay đổi điều kiện so sánh từ nhỏ hơn (`<`) thành lớn hơn (`>`).
• C. Thay đổi điều kiện so sánh từ lớn hơn (`>`) thành nhỏ hơn hoặc bằng (`<=`).
• D. Thêm một điều kiện kiểm tra xem phần tử đã được sắp xếp hay chưa.

Câu 10: Cho đoạn mã Python sau:
```python
def bubble_sort(arr):
n = len(arr)
for i in range(n-1):
for j in range(n-i-1):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
return arr
```
Đoạn mã này thực hiện sắp xếp theo thứ tự nào?

• A. Tăng dần
• B. Giảm dần
• C. Ngẫu nhiên
• D. Không xác định

Câu 11: Trong thực tế, khi nào thì thuật toán sắp xếp nổi bọt (Bubble Sort) vẫn được sử dụng mặc dù nó không phải là thuật toán hiệu quả nhất?

• A. Khi cần sắp xếp danh sách có kích thước rất lớn.
• B. Khi yêu cầu tốc độ sắp xếp là ưu tiên hàng đầu.
• C. Khi cần một thuật toán đơn giản, dễ hiểu và dễ cài đặt cho mục đích giáo dục hoặc danh sách nhỏ.
• D. Khi danh sách đã được sắp xếp hoàn toàn.

Câu 12: Để sắp xếp danh sách tên học sinh theo bảng chữ cái, bạn sẽ sử dụng tiêu chí so sánh nào?

• A. So sánh độ dài của tên.
• B. So sánh thứ tự chữ cái của từng ký tự trong tên từ trái sang phải.
• C. So sánh số lượng nguyên âm trong tên.
• D. Sắp xếp ngẫu nhiên tên học sinh.

Câu 13: Xét danh sách sau: `[7, 2, 5, 1, 8, 3]`. Nếu áp 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ẽ được đặt đúng vị trí đầu tiên sau vòng lặp thứ nhất?

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

Câu 14: Trong thuật toán sắp xếp chèn (Insertion Sort), quá trình "chèn" một phần tử vào vị trí đúng trong phần đã sắp xếp thực chất là việc thực hiện thao tác nào?

• A. Hoán đổi vị trí của phần tử với phần tử cuối cùng của phần đã sắp xếp.
• B. Xóa phần tử đó và thêm nó vào vị trí đúng.
• C. Dịch chuyển các phần tử lớn hơn sang phải để tạo khoảng trống và đặt phần tử vào khoảng trống đó.
• D. Sao chép phần tử đó sang vị trí đúng và giữ nguyên vị trí cũ.

Câu 15: Giả sử bạn có 1000 học sinh và cần sắp xếp họ theo điểm trung bình để xếp hạng. Bạn nên ưu tiên tiêu chí nào khi lựa chọn thuật toán sắp xếp?

• A. Hiệu quả về thời gian (độ phức tạp thuật toán).
• B. Sự đơn giản và dễ cài đặt của thuật toán.
• C. Yêu cầu bộ nhớ thấp của thuật toán.
• D. Tính ổn định của thuật toán (stable sort).

Câu 16: Trong thuật toán sắp xếp chọn (Selection Sort), số lượng phép hoán đổi vị trí phần tử trong trường hợp xấu nhất là bao nhiêu?

• A. Bằng số lượng phần tử trong danh sách.
• B. Ít hơn số lượng phần tử trong danh sách (n-1).
• C. Phụ thuộc vào thứ tự ban đầu của danh sách.
• D. Không có phép hoán đổi nào trong thuật toán sắp xếp chọn.

Câu 17: Bạn có một danh sách các sản phẩm trong kho và muốn sắp xếp chúng theo thứ tự ưu tiên, với các sản phẩm có số lượng lớn hơn được ưu tiên hơn. Tiêu chí sắp xếp nào phù hợp nhất?

• A. Sắp xếp theo tên sản phẩm (bảng chữ cái).
• B. Sắp xếp theo mã sản phẩm (tăng dần).
• C. Sắp xếp theo số lượng sản phẩm (giảm dần).
• D. Sắp xếp ngẫu nhiên các sản phẩm.

Câu 18: Để đọc dữ liệu số lượng mặt hàng từ tệp "kho.txt" và lưu vào danh sách trong Python, bạn sử dụng cấu trúc lệnh nào sau đây?

• A. `with open("kho.txt", "w") as f: soluong_ds = f.readlines()`
• B. `soluong_ds = []
  with open("kho.txt", "r") as f:
  for line in f:
  soluong_ds.append(int(line.strip()))`
• C. `import kho.txt
  soluong_ds = kho.txt.data`
• D. `soluong_ds = read_from_file("kho.txt")`

Câu 19: Trong thuật toán sắp xếp nổi bọt (Bubble Sort), điều gì xảy ra nếu trong một lần duyệt qua danh sách không có bất kỳ phép hoán đổi nào?

• A. Thuật toán tiếp tục duyệt thêm một lần nữa.
• B. Thuật toán sẽ báo lỗi vì không thể sắp xếp được nữa.
• C. Thuật toán kết thúc vì danh sách đã được sắp xếp.
• D. Thuật toán sẽ sắp xếp theo thứ tự ngược lại.

Câu 20: Để sắp xếp một danh sách có kích thước lớn (hàng triệu phần tử), thuật toán sắp xếp nào sau đây thường được ưu tiên sử dụng vì có độ phức tạp thời gian trung bình tốt nhất?

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

Câu 21: Trong bài toán sắp xếp điểm học sinh, giả sử có hai học sinh có điểm trung bình bằng nhau. Nếu bạn muốn duy trì thứ tự ban đầu của hai học sinh này trong danh sách đã sắp xếp, bạn cần sử dụng thuật toán sắp xếp có tính chất gì?

• A. Tính hiệu quả về thời gian.
• B. Tính ổn định (stable sort).
• C. Tính đơn giản trong cài đặt.
• D. Tính tiết kiệm bộ nhớ.

Câu 22: Cho danh sách `C = [10, 5, 8, 2, 7]`. Nếu sử dụng thuật toán sắp xếp nổi bọt (Bubble Sort) để sắp xếp danh sách này theo thứ tự tăng dần, danh sách sẽ có dạng như thế nào sau hai lần duyệt qua?

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

Câu 23: Trong thuật toán sắp xếp chèn (Insertion Sort), tại sao chúng ta lại duyệt từ phần tử thứ hai trở đi (tức là từ index 1)?

• A. Vì phần tử đầu tiên được coi là một danh sách con đã được sắp xếp.
• B. Để giảm số lượng phép so sánh cần thực hiện.
• C. Vì thuật toán sắp xếp chèn chỉ hoạt động với danh sách có ít nhất hai phần tử.
• D. Để đảm bảo tính ổn định của thuật toán.

Câu 24: Xét tình huống bạn cần sắp xếp một chồng bài kiểm tra theo thứ tự điểm số từ cao xuống thấp. Bạn thực hiện việc này bằng cách tìm bài có điểm cao nhất, đặt lên trên cùng, sau đó tìm bài cao nhất trong số còn lại và đặt tiếp theo, và cứ tiếp tục như vậy. Phương pháp này tương ứng với thuật toán sắp xếp nà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. Sắp xếp trộn (Merge Sort)

Câu 25: Trong ngôn ngữ lập trình Python, hàm `sort()` và hàm `sorted()` khác nhau cơ bản ở điểm nào?

• A. `sort()` chỉ sắp xếp số, `sorted()` sắp xếp được mọi kiểu dữ liệu.
• B. `sorted()` nhanh hơn `sort()` đối với danh sách lớn.
• C. `sort()` sắp xếp danh sách tại chỗ (in-place), `sorted()` trả về một danh sách mới đã sắp xếp.
• D. `sort()` sắp xếp tăng dần, `sorted()` sắp xếp giảm dần.

Câu 26: Độ phức tạp thời gian trung bình của thuật toán sắp xếp chèn (Insertion Sort) là O(n^2). Điều này có ý nghĩa gì về thời gian thực hiện của thuật toán khi kích thước danh sách tăng lên?

• A. Thời gian thực hiện tăng tuyến tính với kích thước danh sách.
• B. Thời gian thực hiện tăng theo cấp số nhân (bình phương) của kích thước danh sách.
• C. Thời gian thực hiện giảm khi kích thước danh sách tăng lên.
• D. Thời gian thực hiện không phụ thuộc vào kích thước danh sách.

Câu 27: Để sắp xếp danh sách các đối tượng phức tạp (ví dụ: danh sách sinh viên với nhiều thuộc tính như tên, tuổi, điểm), bạn cần cung cấp thêm thông tin gì cho thuật toán sắp xếp?

• A. Dung lượng bộ nhớ tối đa được phép sử dụng.
• B. Ngôn ngữ lập trình được sử dụng.
• C. Tiêu chí so sánh (khóa sắp xếp) để xác định thứ tự giữa các đối tượng.
• D. Số lượng bộ xử lý của máy tính.

Câu 28: Trong thuật toán sắp xếp chọn (Selection Sort), số lượng phép so sánh trong trường hợp xấu nhất là bao nhiêu đối với danh sách có n phần tử?

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

Câu 29: Thuật toán sắp xếp nào sau đây có thể được cải tiến để đạt độ phức tạp thời gian trung bình O(n log n) trong trường hợp tốt nhất và trung bình, nhưng vẫn giữ độ phức tạp O(n^2) trong trường hợp xấu nhất?

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

Câu 30: Khi nào việc sử dụng thuật toán sắp xếp chèn (Insertion Sort) sẽ hiệu quả hơn so với thuật toán sắp xếp chọn (Selection Sort)?

• A. Khi cần sắp xếp danh sách có kích thước lớn.
• B. Khi danh sách đã gần như được sắp xếp.
• C. Khi yêu cầu tính ổn định của thuật toán sắp xếp.
• D. Sắp xếp chọn luôn hiệu quả hơn sắp xếp chèn trong mọi trường hợp.