Chủ đề 6. Kĩ thuật lập trình – Bài 21: Các thuật toán sắp xếp đơn giản – sách bài tập trang 69 lớp 11 Khoa học máy tính – Kết Nối Tri Thức, mời các em tham khảo cùng Bumbii.
Chủ đề 6. Kĩ thuật lập trình – Bài 21: Các thuật toán sắp xếp đơn giản
Câu 21.1
Thuật toán sắp xếp chèn có ý tưởng ban đầu như sau:
Nếu công việc chèn tại dòng 2 ở trên được thực hiện như sau:
Thuật toán được mô tả theo cách trên có đúng không?
Trả lời:
Thuật toán được mô tả theo cách trên đúng.
Câu 21.2
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.
Trả lời:
def insertSort(A):
for i in range (1, len(A)):
j = i
while j > 0 and A[j] < A[j-1]:
A[j],A[j-1] = A[j-1],A[j]
j = j - 1Câu 21.3
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?
Trả lời:
Với thuật toán sắp xếp chèn, khi thuật toán thực hiện ít phép so sánh nhất là: Khi dãy ban đầu đã sắp xếp đúng
Câu 21.4
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?
Trả lời:
Với thuật toán sắp xếp chèn, khi thuật toán thực hiện nhiều phép so sánh nhất là: Khi dãy ban đầu đã được sắp xếp theo chiều ngược lại.
Câu 21.5
Quan sát lại ý tưởng của thuật toán sắp xếp chèn:
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.
Trả lời:
Có thể được. Chẳng hạn hàm đó là chen() có thể như sau:
def insertionSort(A):
for i in range(1, len(A)):
chen(A, A[i], i-1)
#Hàm chen(A,x,k) có chức năng chèn x vào vị trí đúng trong dãy A[0], A[1], ....., A[k] như sau:
def chen(A, x, k):
j = k
while j >= 0 and A[j] > x:
A[j+1] = A[j]
j = j - 1
A[j+1] = xCâu 21.6
Ý 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:
Nếu thay dòng 3 bằng A[i + 1], A[i + 2], …, A[n − 1] thì thuật toán còn đúng không?
Trả lời:
Nếu thay dòng 3 bằng A[i + 1], A[i + 2], …, A[n − 1] thì thuật toán không còn đúng. Thuật toán sẽ sai.
Câu 21.7
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.
Trả lời:
Sau đây là một cách thiết lập thuật toán chọn sử dụng hàm min():
def SelectionSort(A):
n = len(A)
for i in range(n-1):
m = min(A[i +1 :])
if A[i]> m:
j = i + A[i: ].index(m)
A[i],A[j] = A[j],A[i]Câu 21.8
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?
Trả lờ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
Ý 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:
Em hãy viết chương trình mô tả đoạn mã giả trên.
Trả lời:
def bubbleSort(A):
n = len(A)
for i in range (1, n-1):
for j in range (n-1, i-1,-1):
if A[j] < A[j-1]:
A[j],A[j-1] = A[j-1],A[j]Câu 21.10*
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].
Trả lời:
Với mỗi phần tử của B được chèn vào đúng vị trí trong dãy A.
def insert(A, B):
for x in B:
A.append(x)
j = len(A) - 2
while j >= 0 and A[j] > x:
A[j + 1] = A[j]
j = j - 1
A[j + 1] = xXem các bài giải khác: Giải Sách Bài Tập Lớp 11 Khoa Học Máy Tính Kết Nối Tri Thức Với Cuộc Sống
Thông tin liên hệ & mạng xã hội:
Website: https://bumbii.com/
Facebook: https://www.facebook.com/bumbiiapp
Pinterest: https://www.pinterest.com/bumbiitech
