15 câu Trắc nghiệm Tin học 11 Kết nối tri thức Bài 21 có đáp án

Đá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.

Đá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.

Đá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)).

Đá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ó.

Đá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).

Đá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.

Đá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

Đá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).

Đá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.

Đá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.

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.

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.

Đá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.

Đá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ử.

Đá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.