Câu hỏi:
11/07/2024 348Quan 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,
Sách mới 2k7: Tổng ôn Toán, Lí, Hóa, Văn, Sử, Địa…. kỳ thi tốt nghiệp THPT Quốc gia 2025, đánh giá năng lực (chỉ từ 110k).
Quảng cáo
Trả lời:
Có thể được. Chẳng hạn hàm đó là chen() có thể như sau:
CÂU HỎI HOT CÙNG CHỦ ĐỀ
Câu 1:
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?
Câu 2:
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?
Câu 3:
Ý 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.
Câu 4:
Ý 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?
Câu 5:
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].
Câu 6:
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?
15 câu Trắc nghiệm Tin học 11 KNTT Tin học ứng dụng Bài 11: Cơ sở dữ liệu có đáp án
15 câu Trắc nghiệm Tin học 11 KNTT Tin học ứng dụng Bài 10: Lưu trữ dữ liệu và khai thác thông tin phục vụ quản lí có đáp án
15 câu Trắc nghiệm Tin học 11 KNTT Tin học ứng dụng Bài 12: Hệ quản trị cơ sở dữ liệu và hệ cơ sở dữ liệu có đáp án
Đề thi cuối học kì 1 Tin học 11 Kết nối trí thức có đáp án (Đề 3)
15 câu Trắc nghiệm Tin học 11 KNTT Tin học ứng dụng Bài 13: Cơ sở dữ liệu quan hệ có đáp án
Đề thi cuối học kì 1 Tin học 11 Kết nối trí thức có đáp án (Đề 1)
15 câu Trắc nghiệm Tin học 11 KNTT Tin học ứng dụng Bài 14: SQL – Ngôn ngữ truy vấn có cấu trúc có đáp án
15 câu Trắc nghiệm Tin học 11 Cánh diều Tin học ứng dụng Bài 1: Bài toán quản lý và cơ sở dữ liệu có đáp án
về câu hỏi!