Giải SBT Tin học 11 Kết nối tri thức bài 21
Chúng tôi xin giới thiệu bài Giải sách bài tập Tin học 11 bài 21: Các thuật toán sắp xếp đơn giản sách Kết nối tri thức hay, chi tiết giúp học sinh dễ dàng xem và so sánh lời giải từ đó biết cách làm bài tập trong SBT Tin học 11.
Bài: Các thuật toán sắp xếp đơn giản
Câu 21.1 trang 69 SBT Tin học 11: Thuật toán sắp xếp chèn có ý tưởng ban đầu như sau:
1 Cho chỉ số i chạy từ phần từ thứ hai đến cuối dây
2 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 công việc chèn tại dòng 2 ở trên được thực hiện như sau:
j = i
while j>e and A[j] < A[j-1]:
đổi chỗ Aljl, Aj-1]
j = j - 1
Thuật toán được mô tả theo cách trên có đúng không?
Lời giải:
Thuật toán sắp xếp chèn có ý tưởng ban đầu như sau:
1 Cho chỉ số i chạy từ phần từ thứ hai đến cuối dây
2 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 công việc chèn tại dòng 2 ở trên được thực hiện như sau:
j = i
while j>e and A[j] < A[j-1]:
đổi chỗ Aljl, Aj-1]
j = j - 1
Thuật toán được mô tả theo cách trên là đúng.
Câu 21.2 trang 69 SBT Tin học 11: Viết lại thuật toán chèn theo cách đã mô tả trong câu trên khác cách mô tả trong sách giáo khoa.
Lời giải:
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?
Lời giải:
Với thuật toán sắp xếp chèn, khi dãy ban đầu đã sắp xếp đúng thì thuật toán thực hiện ít phép so sánh nhất.
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?
Lời giải:
Khi dãy ban đầu đã được sắp xếp theo chiều ngược lại.
Câu 21.5 trang 69 SBT Tin học 11: Quan sát lại ý tưởng của thuật toán sắp xếp chèn
1 Cho chỉ số i chạy từ phần tử thứ hai đến cuối dày
2 Chèn phần tử A[i] vào vị trí đúng của dây đã sắp xếp A[e], A[1], ..., A[i-1]
Có thể viết riêng các lệnh của thao tác “chèn” trong dòng 2 ở trên thành một hàm độc lập được không? Nếu được thì viết lại thuật toán này theo cách mới,
Lời giải:
Có thể được. Chẳng hạn hàm đó là chen() có thể như sau:
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 đã được mô tả trong sách giáo khoa như sau:
1 def SelectionSort(A):
2 for i in range(n-1):
3 Chọn phần tử nhỏ nhất trong dây A[i], A[i+1], A[n-1]
4 Đồi chỗ phần từ này với A[i]
Nếu thay dòng 3 bằng A + 1] A + 2]. ... An – 1] thì thuật toán còn đúng không?
Lời giải:
Nếu thay dòng 3 bằng A + 1] A + 2]. ... An – 1] thì thuật toán sẽ sai.
Câu 21.7 trang 70 SBT Tin học 11: Viết lại chương trình mô tả thuật toán sắp xếp chọn đã mô tả trong Câu 21.6 sử dụng hàm min() của Python.
Lời giải:
Sau đây là một cách thiết lập thuật toán chọn sử dụng hàm min().
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 theo cách trên sẽ không cần thực hiện lệnh đổi chỗ hai phần tử tại dòng 8 của mô tả thuật toán trong sách giáo khoa?
Lời giải:
Trong trường hợp khi dãy ban đầu đã sắp xếp đúng thì thuật toán sắp xếp chọn theo cách trên sẽ không cần thực hiện lệnh đổi chỗ hai phần tử tại dòng 8 của mô tả thuật toán trong sách giáo khoa.
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ả bao gồm hai vòng lặp. Ý vòng lặp bên trong sẽ duyệt từng phần tử từ bên phải sang và đổi chỗ hai phần tử cạnh nhau nếu chúng sắp xếp không đúng. Sau mỗi vòng lặp bên trong thì phần tử nhỏ nhất sẽ được đưa lên vị trí đúng ở phía đầu dãy.
Ý tưởng này được mô tả bằng đoạn mã giả sau:
1 Lặp n - 1 lần
2 Cho chỉ số j chạy từ phải sang đến vị trí thứ 2 của dãy
3 Nếu A[j] < A[j-1] thì đổi chỗ 2 phần tử A[j], A[j-1]
Em hãy viết chương trình mô tả đoạn mã giả trên.
Lời giải:
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. Viết chương trình mô tả hàm insert(A, B) đưa tất cả các phần tử của B vào A mà vẫn phải giữ đúng thứ tự sắp xếp đúng của A.
Ví dụ: A = [1, 4], B = [5, 2, 3] thì sau khi thực hiện hàm insert(A, B), được dãy A = [1, 2, 3, 4, 5].
Lời giải:
Với mỗi phần tử của B được chèn vào đúng vị trí trong dãy A.
>>> Bài tiếp theo: Giải SBT Tin học 11 Kết nối tri thức bài 22
Trên đây là toàn bộ lời giải Giải SBT Tin học lớp 11 bài 21: Các thuật toán sắp xếp đơn giản sách Kết nối tri thức. Các em học sinh tham khảo thêm Trắc nghiệm Toán 11 Kết nối tri thức, Tin học lớp 11 Cánh Diều. VnDoc liên tục cập nhật lời giải cũng như đáp án sách mới của SGK cũng như SBT các môn cho các bạn cùng tham khảo.
