15 câu Trắc nghiệm Tin học 11 Kết nối tri thức Bài 21 có đáp án
15 câu hỏi
PHẦN I. Câu trắc nghiệm nhiều phương án lựa chọn. Thí sinh trả lời từ câu 1 đến câu 10. Mỗi câu hỏi thí sinh chỉ lựa chọn một phương án.
Ý tưởng chính của thuật toán sắp xếp chèn là gì?
Tìm phần tử nhỏ nhất và chuyển nó vào vị trí đầu tiên.
So sánh từng cặp phần tử liền kề và hoán đổi nếu chúng không đúng thứ tự.
Chèn từng phần tử vào đúng vị trí trong một mảng con đã sắp xếp.
Chia mảng thành hai phần và sắp xếp từng phần đệ quy.
Đáp án: C
Giải thích: Thuật toán sắp xếp chèn hoạt động bằng cách lấy các phần tử từ phần chưa sắp xếp và chèn chúng vào đúng vị trí trong một mảng con đã sắp xếp, mảng con này sẽ lớn dần sau mỗi lần lặp.
Trong thuật toán sắp xếp chèn, có bao nhiêu phép so sánh trong trường hợp tốt nhất (khi mảng đã được sắp xếp)?
0
n−1n-1n−1
n(n−1)2\frac{n(n-1)}{2}2n(n−1)
n2n^2n2
Đáp án: B
Giải thích: Trong trường hợp tốt nhất, mỗi phần tử chỉ cần so sánh một lần với phần tử đứng trước nó, do đó số phép so sánh là n−1n-1n−1.
Độ phức tạp thời gian trong trường hợp xấu nhất của thuật toán sắp xếp chèn là gì?
O(n)
O(n \log n)
O(n^2)
O(1)
Đáp án: C
Giải thích: Trong trường hợp xấu nhất (khi mảng được sắp xếp ngược), mỗi phần tử cần được so sánh với tất cả các phần tử trước nó, dẫn đến số lượng phép so sánh là bậc hai (O(n^2)).
Trong thuật toán sắp xếp chọn, điều gì xảy ra trong mỗi lần lặp?
Phần tử lớn nhất được chuyển về cuối mảng.
Phần tử nhỏ nhất được đưa vào đúng vị trí.
Mỗi phần tử được chèn vào đúng vị trí của nó.
Các phần tử liền kề được hoán đổi để sắp xếp.
Đáp án: B
Giải thích: Trong mỗi lần lặp của thuật toán sắp xếp chọn, thuật toán chọn phần tử nhỏ nhất trong phần chưa sắp xếp và đặt nó vào đúng vị trí của nó.
Độ phức tạp thời gian trong trường hợp tốt nhất của thuật toán sắp xếp chọn là gì?
O(n)
O(n^2)
O(n \log n)
O(1)
Đáp án: B
Giải thích: Thuật toán sắp xếp chọn luôn thực hiện O(n^2) phép so sánh, bất kể dữ liệu ban đầu được sắp xếp như thế nào, do đó độ phức tạp thời gian trong trường hợp tốt nhất là O(n^2).
Thuật toán nào sau đây không sử dụng so sánh giữa các phần tử?
Sắp xếp chèn
Sắp xếp chọn
Sắp xếp đếm
Sắp xếp nổi bọt
Đáp án: C
Giải thích: Sắp xếp đếm là một thuật toán sắp xếp không dựa trên việc so sánh các phần tử, mà dựa trên việc đếm số lần xuất hiện của mỗi phần tử trong một phạm vi.
Mục đích của vòng lặp bên trong trong thuật toán sắp xếp nổi bọt là gì?
Tìm phần tử lớn nhất và đưa nó về đúng vị trí.
Tìm phần tử nhỏ nhất và đưa nó về đúng vị trí.
So sánh và hoán đổi các phần tử liền kề nếu chúng không đúng thứ tự.
Chia mảng thành các phần nhỏ hơn để sắp xếp.
Đáp án: C
Giải thích: Trong sắp xếp nổi bọt, vòng lặp bên trong so sánh các phần tử liền kề và hoán đổi chúng nếu chúng không đúng thứ tự, điều này làm cho phần tử lớn nhất trong phần chưa sắp xếp "nổi" lên cuối mảng
Trường hợp tốt nhất của thuật toán sắp xếp nổi bọt là gì?
Mảng được sắp xếp ngược lại.
Mảng đã được sắp xếp.
Mảng chứa tất cả các phần tử giống nhau.
Mảng chỉ có hai phần tử.
Đáp án: B
Giải thích: Trường hợp tốt nhất của sắp xếp nổi bọt là khi mảng đã được sắp xếp, khi đó chỉ cần một lần duyệt qua với không cần hoán đổi, dẫn đến độ phức tạp thời gian O(n).
Phát biểu nào sai về thuật toán sắp xếp nổi bọt?
Nó là thuật toán ổn định, có nghĩa là nó giữ nguyên thứ tự của các phần tử bằng nhau.
Nó là thuật toán tại chỗ, tức là nó sử dụng bộ nhớ phụ không đáng kể.
Nó luôn thực hiện số lượng so sánh giống nhau, bất kể thứ tự của đầu vào.
Độ phức tạp thời gian xấu nhất của nó là O(n^2).
Đáp án: C
Giải thích: Số lượng so sánh trong sắp xếp nổi bọt có thể thay đổi tùy thuộc vào mức độ sắp xếp của mảng đầu vào. Trong trường hợp tốt nhất, ít so sánh hơn so với trường hợp xấu nhất.
Trong thuật toán sắp xếp chèn, thuật toán xác định vị trí để chèn phần tử như thế nào trong mỗi lần lặp?
Bằng cách tìm phần tử ở giữa và chèn vào đó.
Bằng cách dịch chuyển các phần tử lớn hơn phần tử hiện tại sang bên phải.
Bằng cách hoán đổi các phần tử liền kề cho đến khi phần tử hiện tại ở đúng vị trí.
Bằng cách chia mảng ra đệ quy.
Đáp án: B
Giải thích: Thuật toán sắp xếp chèn chèn phần tử hiện tại vào đúng vị trí của nó bằng cách dịch chuyển các phần tử lớn hơn nó sang bên phải, tạo ra khoảng trống để chèn.
PHẦN II. Câu trắc nghiệm đúng sai. Thí sinh trả lời từ câu 1 đến câu 2. Trong mỗi ý a), b), c), d) ở mỗi câu, thí sinh chọn đúng hoặc sai
Cho dãy A = [5, 8, 1, 0, 10, 4, 3], thuật toán sắp xếp chèn sẽ hoạt động như thế nào?
a) Sắp xếp từng phần tử vào vị trí đúng trong dãy con đã sắp xếp.
b) Đổi chỗ phần tử nhỏ nhất trong dãy còn lại với phần tử đang xét.
c) Kiểm tra từng cặp phần tử liền kề và đổi chỗ nếu không đúng thứ tự.
d) So sánh từng phần tử và hoán đổi nếu chúng không đúng vị trí.
a) Đúng. Đây chính là cách hoạt động của thuật toán sắp xếp chèn. Sau mỗi vòng lặp, phần tử đang xét sẽ được chèn vào vị trí đúng trong dãy con đã sắp xếp, từ trái sang phải.
b) Sai. Đây là mô tả của thuật toán sắp xếp chọn, không phải sắp xếp chèn.
c) Sai. Đây là cách hoạt động của thuật toán sắp xếp nổi bọt, không phải sắp xếp chèn.
d) Sai. Mô tả này không phản ánh đúng thuật toán sắp xếp chèn, mà là mô tả một cách khác, giống như thuật toán sắp xếp nổi bọt.
Trong thuật toán sắp xếp chọn, điều gì sẽ xảy ra ở mỗi bước lặp?
a) Tìm phần tử lớn nhất trong dãy chưa sắp xếp và đổi chỗ với phần tử cuối cùng.
b) Tìm phần tử nhỏ nhất trong dãy chưa sắp xếp và đổi chỗ với phần tử đang xét.
c) So sánh từng cặp phần tử liền kề và đổi chỗ nếu cần thiết.
d) Chèn phần tử đang xét vào vị trí đúng trong dãy con đã sắp xếp.
a) Sai. Thuật toán sắp xếp chọn tìm phần tử nhỏ nhất trong dãy chưa sắp xếp, không phải phần tử lớn nhất.
b) Đúng. Đây chính là ý tưởng chính của thuật toán sắp xếp chọn, tìm phần tử nhỏ nhất trong dãy còn lại và đổi chỗ với phần tử hiện tại.
c) Sai. Đây là cách hoạt động của thuật toán sắp xếp nổi bọt, không phải sắp xếp chọn.
d) Sai. Đây là mô tả của thuật toán sắp xếp chèn, không phải sắp xếp chọn.
PHẦN III. Câu trả lời ngắn. Thí sinh trả lời từ câu 1 đến câu 3
Nếu dãy ban đầu đã được sắp xếp, thuật toán sắp xếp chèn sẽ thực hiện như thế nào?
Đáp án: Nếu dãy đã được sắp xếp, thuật toán sắp xếp chèn vẫn thực hiện tất cả các bước lặp, nhưng không có sự hoán đổi nào xảy ra.
Giải thích: Thuật toán sắp xếp chèn kiểm tra mỗi phần tử từ trái sang phải và chèn nó vào vị trí đúng trong dãy con đã được sắp xếp. Nếu dãy đã sắp xếp, tất cả các phần tử đều ở vị trí đúng của nó, do đó không cần hoán đổi, nhưng các bước kiểm tra vẫn được thực hiện.
Tại mỗi bước của thuật toán sắp xếp chọn, phần tử nào sẽ được đổi chỗ?
Đáp án: Phần tử nhỏ nhất trong đoạn chưa được sắp xếp sẽ được đổi chỗ với phần tử đầu tiên của đoạn đó.
Giải thích: Thuật toán sắp xếp chọn tìm phần tử nhỏ nhất trong đoạn chưa sắp xếp và hoán đổi nó với phần tử đầu tiên của đoạn đó. Sau mỗi bước, phần tử nhỏ nhất sẽ ở đúng vị trí và đoạn chưa sắp xếp sẽ giảm đi một phần tử.
Trong thuật toán sắp xếp nổi bọt, sau mỗi vòng lặp, điều gì xảy ra với các phần tử?
Đáp án: Sau mỗi vòng lặp, phần tử lớn nhất trong đoạn chưa sắp xếp sẽ được đưa về cuối dãy.
Giải thích: Thuật toán sắp xếp nổi bọt hoạt động bằng cách so sánh từng cặp phần tử liền kề và hoán đổi chúng nếu cần thiết. Sau mỗi vòng lặp, phần tử lớn nhất "nổi" lên và được đặt đúng vị trí ở cuối dãy. Quá trình này tiếp tục cho đến khi dãy được sắp xếp hoàn toàn.
