Bài 21 Các thuật toán sắp xếp đơn giản
Lớp 11Tin Học12 câu hỏiBài tập
Phần 1
Câu 1
(Câu 21.1 trang 69 SBT Tin học 11) Thuật toán sắp xếp chèn có ý tưởng: cho chỉ số i chạy từ phần tử thứ hai đến cuối dãy; chèn phần tử A[i] vào vị trí đúng của dãy đã sắp xếp A[0], A[1], ..., A[i-1]. Nếu thao tác chèn được thực hiện bằng cách gán j = i, sau đó lặp khi j > 0 và A[j] < A[j-1] thì đổi chỗ A[j] và A[j-1], rồi giảm j đi 1, thuật toán được mô tả như vậy có đúng không?
AĐúng, vì phần tử A[i] được dịch dần sang trái đến vị trí phù hợp trong đoạn đã sắp xếp.
BSai, vì sắp xếp chèn không được phép đổi chỗ các phần tử liền kề.
CSai, vì cần cho j tăng dần từ trái sang phải.
DSai, vì thuật toán chỉ đúng với dãy đã được sắp xếp sẵn.
Câu 2
(Câu 21.3 trang 69 SBT Tin học 11) Với thuật toán sắp xếp chèn, khi nào thuật toán thực hiện ít phép so sánh nhất?
AKhi dãy ban đầu đã được sắp xếp đúng thứ tự.
BKhi dãy ban đầu được sắp xếp theo chiều ngược lại.
CKhi dãy ban đầu có các phần tử hoàn toàn ngẫu nhiên.
DKhi dãy ban đầu chỉ gồm các số âm.
Câu 3
(Câu 21.4 trang 69 SBT Tin học 11) Với thuật toán sắp xếp chèn, khi nào thuật toán thực hiện nhiều phép so sánh nhất?
AKhi dãy ban đầu đã được sắp xếp theo chiều ngược lại.
BKhi dãy ban đầu đã được sắp xếp đúng thứ tự.
CKhi dãy chỉ có một phần tử.
DKhi tất cả các phần tử trong dãy đều bằng nhau.
Câu 4
(Câu 21.6 trang 69 SBT Tin học 11) Ý tưởng của thuật toán sắp xếp chọn là: với mỗi vị trí i, chọn phần tử nhỏ nhất trong dãy A[i], A[i+1], ..., A[n-1] rồi đổi chỗ phần tử đó với A[i]. Nếu thay bước chọn phần tử nhỏ nhất trong A[i], A[i+1], ..., A[n-1] bằng việc chỉ xét A[i+1], A[i+2], ..., A[n-1] thì thuật toán còn đúng không?
AKhông đúng, vì bỏ qua A[i] nên có thể chọn sai phần tử nhỏ nhất của đoạn cần xét.
BVẫn đúng, vì A[i] luôn là phần tử nhỏ nhất.
CVẫn đúng, vì chỉ cần xét các phần tử đứng sau A[i].
DKhông đúng, vì thuật toán sắp xếp chọn không sử dụng thao tác đổi chỗ.
Câu 5
(Câu 21.8 trang 70 SBT Tin học 11) Trong trường hợp nào thuật toán sắp xếp chọn sẽ không cần thực hiện lệnh đổi chỗ hai phần tử?
AKhi dãy ban đầu đã được sắp xếp đúng thứ tự.
BKhi dãy ban đầu được sắp xếp theo chiều ngược lại.
CKhi dãy ban đầu có nhiều phần tử trùng nhau nhưng chưa sắp xếp.
DKhi phần tử nhỏ nhất luôn nằm ở cuối dãy.
Phần 2
Câu 1
(Câu 21.2 trang 69 SBT Tin học 11) Viết lại thuật toán sắp xếp chèn theo cách đã mô tả ở Câu 21.1.
a)Có thể dùng vòng lặp for i in range(1, len(A)) để duyệt từ phần tử thứ hai đến cuối dãy.
b)Với mỗi i, có thể gán j = i để bắt đầu xét vị trí chèn.
c)Khi j > 0 và A[j] < A[j-1], cần đổi chỗ A[j] với A[j-1] rồi giảm j đi 1.
d)Khi A[j] nhỏ hơn A[j-1], cần tăng j lên 1 để đưa phần tử sang phải.
Câu 2
(Câu 21.5 trang 69 SBT Tin học 11) Có thể viết riêng các lệnh của thao tác “chèn” trong thuật toán sắp xếp chèn thành một hàm độc lập.
a)Có thể viết hàm chen(A, i) để chèn phần tử A[i] vào đúng vị trí trong đoạn A[0], A[1], ..., A[i].
b)Trong hàm chen(A, i), có thể dùng biến j = i rồi dịch phần tử sang trái bằng cách đổi chỗ các phần tử liền kề.
c)Thuật toán sắp xếp chèn có thể gọi hàm chen(A, i) với i chạy từ 1 đến len(A) - 1.
d)Khi đã viết hàm chen(A, i), không cần vòng lặp duyệt các vị trí i trong dãy.
Câu 3
(Câu 21.7 trang 70 SBT Tin học 11) Viết lại thuật toán sắp xếp chọn sử dụng hàm min() của Python.
a)Ở mỗi bước i, cần tìm giá trị nhỏ nhất trong đoạn A[i], A[i+1], ..., A[n-1].
b)Có thể dùng m = min(A[i:]) để tìm giá trị nhỏ nhất trong đoạn chưa sắp xếp.
c)Sau khi tìm được giá trị nhỏ nhất, cần xác định vị trí của giá trị đó để đổi chỗ với A[i].
d)Thuật toán sắp xếp chọn dùng min() không cần xét từng đoạn chưa sắp xếp của dãy.
Câu 4
(Câu 21.9 trang 70 SBT Tin học 11) Ý tưởng của thuật toán sắp xếp nổi bọt được mô tả bằng hai vòng lặp: vòng lặp bên trong duyệt từng phần tử từ bên phải sang trái và đổi chỗ hai phần tử cạnh nhau nếu chúng chưa đúng thứ tự.
a)Sau mỗi lượt duyệt từ phải sang trái, phần tử nhỏ nhất trong đoạn đang xét được đưa dần về phía đầu dãy.
b)Có thể dùng vòng lặp ngoài lặp n - 1 lần.
c)Trong vòng lặp trong, nếu A[j] < A[j-1] thì đổi chỗ A[j] và A[j-1].
d)Thuật toán nổi bọt không bao giờ cần so sánh hai phần tử liền kề.
Câu 5
(Câu 21.9 trang 70 SBT Tin học 11) Xét cách cài đặt thuật toán sắp xếp nổi bọt từ phải sang trái.
a)Có thể dùng vòng lặp for i in range(n-1) cho vòng lặp ngoài.
b)Có thể dùng vòng lặp for j in range(n-1, i, -1) để duyệt từ phải sang trái.
c)Nếu A[j] < A[j-1] thì thực hiện A[j], A[j-1] = A[j-1], A[j].
d)Sau mỗi vòng lặp ngoài, phần tử lớn nhất luôn được đưa về đầu dãy.
Câu 6
(Câu 21.10 trang 70 SBT Tin học 11) Cho trước hai dãy số A, B, trong đó dãy A đã được sắp xếp đúng. Cần viết hàm insert(A, B) đưa tất cả các phần tử của B vào A mà vẫn giữ đúng thứ tự sắp xếp của A.
a)Có thể lần lượt lấy từng phần tử của B để chèn vào vị trí thích hợp trong A.
b)Sau mỗi lần chèn một phần tử của B, dãy A vẫn cần được giữ đúng thứ tự sắp xếp.
c)Với A = [1, 4], B = [5, 2, 3], sau khi thực hiện insert(A, B), có thể thu được A = [1, 2, 3, 4, 5].
d)Chỉ cần nối A và B bằng A = A + B thì chắc chắn A vẫn được sắp xếp đúng trong mọi trường hợp.
Câu 7
(Câu 21.10 trang 70 SBT Tin học 11) Tìm hiểu cách chèn các phần tử của B vào dãy A đã sắp xếp.
a)Khi chèn một phần tử x của B vào A, cần tìm vị trí đầu tiên trong A mà tại đó phần tử đang xét lớn hơn x.
b)Nếu không có phần tử nào trong A lớn hơn x, có thể chèn x vào cuối A.
c)Có thể dùng thao tác insert của list trong Python để chèn x vào vị trí tìm được.
d)Khi chèn phần tử x vào A, luôn phải chèn x vào đầu A dù giá trị của x là bao nhiêu.