Câu hỏi:
13/07/2024 69
Viết lại hàm BSTSort(A) thực hiện sắp xếp dãy số A theo thứ tự tăng dần nhưng kết quả không cập nhật vào A. Hàm trả lại dãy số mới là dãy vừa được sắp xếp (gồm các phần tử của dãy A).
Viết lại hàm BSTSort(A) thực hiện sắp xếp dãy số A theo thứ tự tăng dần nhưng kết quả không cập nhật vào A. Hàm trả lại dãy số mới là dãy vừa được sắp xếp (gồm các phần tử của dãy A).
Sách mới 2k7: Bộ 20 đề minh họa Toán, Lí, Hóa, Văn, Sử, Địa…. form chuẩn 2025 của Bộ giáo dục (chỉ từ 110k).
Quảng cáo
Trả lời:
Giải bởi Vietjack
1. Định nghĩa cấu trúc nút cây BST:
class TreeNode:
def __init__(self, key):
self.left = None
self.right = None
self.val = key
2. Hàm chèn một phần tử vào BST
def insert(root, key):
if root is None:
return TreeNode(key)
else:
if root.val < key:
root.right = insert(root.right, key)
else:
root.left = insert(root.left, key)
return root
3. Hàm duyệt giữa để lấy thứ tự tăng dần
def in_order_traversal(root, result):
if root:
in_order_traversal(root.left, result)
result.append(root.val)
in_order_traversal(root.right, result)
4. Hàm chính để sắp xếp dãy A
def BSTSort(A):
if not A:
return []
# Bước 1: Tạo cây tìm kiếm nhị phân từ dãy A
root = None
for key in A:
root = insert(root, key)
# Bước 2: Duyệt cây để lấy kết quả sắp xếp
sorted_result = []
in_order_traversal(root, sorted_result)
return sorted_result
Nhà sách VIETJACK:
CÂU HỎI HOT CÙNG CHỦ ĐỀ
Câu 1:
Thuật toán sắp xếp dãy sử dụng cây tìm kiếm nhị phân có độ phức tạp thời gian là bao nhiêu?
Thuật toán sắp xếp dãy sử dụng cây tìm kiếm nhị phân có độ phức tạp thời gian là bao nhiêu?
Xem đáp án »
13/07/2024
418
Câu 3:
Cho trước dãy số A = [2,1,9,0,2,1,5]. Tạo cây tìm kiếm nhị phân T từ dãy A và thực hiện thuật toán duyệt giữa trên cây T. Em hãy cho biết kết quả duyệt là dãy các khoá có thứ tự như thế nào.
Cho trước dãy số A = [2,1,9,0,2,1,5]. Tạo cây tìm kiếm nhị phân T từ dãy A và thực hiện thuật toán duyệt giữa trên cây T. Em hãy cho biết kết quả duyệt là dãy các khoá có thứ tự như thế nào.
Xem đáp án »
13/07/2024
190
Câu 4:
Trao đổi, thảo luận để giải bài toán sau:
Cho trước dãy số A. Thiết kế thuật toán sắp xếp lại dãy A theo thứ tự tăng dần hoặc giảm dần.
Trao đổi, thảo luận để giải bài toán sau:
Cho trước dãy số A. Thiết kế thuật toán sắp xếp lại dãy A theo thứ tự tăng dần hoặc giảm dần.
Xem đáp án »
13/07/2024
117
Câu 5:
Quan sát cây tìm kiếm nhị phân trong hình 9.1, cùng trao đổi, thảo luận các câu hỏi sau:
a) Nếu thực hiện thuật toán duyệt giữa (trái – gốc – phải) thì nút đầu tiên được duyệt là nút nào?
b) Nút cuối cùng được duyệt là nút nào?
c) Thứ tự các nút được duyệt theo thuật toán duyệt giữa sẽ theo thứ tự nào? Em có nhận xét gì về kết quả đạt được? Giải thích vì sao.
Quan sát cây tìm kiếm nhị phân trong hình 9.1, cùng trao đổi, thảo luận các câu hỏi sau:
a) Nếu thực hiện thuật toán duyệt giữa (trái – gốc – phải) thì nút đầu tiên được duyệt là nút nào?
b) Nút cuối cùng được duyệt là nút nào?
c) Thứ tự các nút được duyệt theo thuật toán duyệt giữa sẽ theo thứ tự nào? Em có nhận xét gì về kết quả đạt được? Giải thích vì sao.
Xem đáp án »
13/07/2024
90
Câu 6:
Dựa trên hàm BSTSort(A) đã biết, viết chương trình sắp xếp dãy số giảm dần theo kĩ thuật sử dụng cây tìm kiếm nhị phân.
Dựa trên hàm BSTSort(A) đã biết, viết chương trình sắp xếp dãy số giảm dần theo kĩ thuật sử dụng cây tìm kiếm nhị phân.
Xem đáp án »
13/07/2024
83
Câu 7:
Quan sát cách cài đặt các thuật toán duyệt trên cây tìm kiếm nhị phân và trao đổi về ý nghĩa và sự khác biệt khi thực hiện các thuật toán này so với các thuật toán duyệt cây nhị phân đã học trong Bài 6.
Quan sát cách cài đặt các thuật toán duyệt trên cây tìm kiếm nhị phân và trao đổi về ý nghĩa và sự khác biệt khi thực hiện các thuật toán này so với các thuật toán duyệt cây nhị phân đã học trong Bài 6.
Xem đáp án »
13/07/2024
70
Bình luận
🔥 Đề thi HOT:
-
Đề thi học kì 1 Tin học 12 Kết nối tri thức có đáp án- Đề 1
-
263 câu Trắc nghiệm tổng hợp ôn thi tốt nghiệp THPT môn Tin học Chủ đề F. Giải quyết vấn đề với sự trợ giúp của máy tính có đáp án
-
15 câu Trắc nghiệm Tin học 12 Kết nối tri thức Bài 7 có đáp án
-
15 câu Trắc nghiệm Tin học 12 Kết nối tri thức Bài 10 có đáp án
-
Đề thi học kì 1 Tin học 12 Kết nối tri thức có đáp án- Đề 2
-
15 câu Trắc nghiệm Tin học 12 Kết nối tri thức Bài 8 có đáp án
-
Đề thi học kì 1 Tin học 12 Kết nối tri thức có đáp án- Đề 3
-
15 câu Trắc nghiệm Tin học 12 Kết nối tri thức Bài 9 có đáp án
về câu hỏi!