Dữ liệu đầu vào là danh sách học sinh trong lớp và điểm trung bình các môn

Giảm giá 50% sách VietJack đánh giá năng lực các trường trên Shopee Mall

Giải Chuyên đề Tin 12 Bài 7: Cây tìm kiếm nhị phân - Kết nối tri thức

Vận dụng 1 trang 36 Chuyên đề Tin học 12: Dữ liệu đầu vào là danh sách học sinh trong lớp và điểm trung bình các môn. Danh sách được cho trong tệp văn bản có dạng như bảng bên.

Viết chương trình đọc tập dữ liệu đầu vào trên và liên tục thực hiện các thao tác sau:

a) Nhập thêm vào danh sách học sinh và điểm trung bình.

b) Tìm kiếm với yêu cầu nhập họ tên học sinh và đưa ra kết quả họ tên học sinh, điểm trung bình hoặc thông báo "không tìm thấy".

Chương trình kết thúc khi nhập vào một xâu rỗng. Yêu cầu giải bài này bằng cây tìm kiếm nhị phân.

Dữ liệu đầu vào là danh sách học sinh trong lớp và điểm trung bình các môn

Quảng cáo

Lời giải:

Sử dụng một cây tìm kiếm nhị phân (Binary Search Tree - BST) để lưu trữ và thao tác với danh sách học sinh và điểm trung bình của họ. Chương trình sẽ bao gồm các chức năng sau:

1. Đọc dữ liệu đầu vào từ tệp Data.inp.

2. Thêm học sinh mới vào cây tìm kiếm nhị phân.

3. Tìm kiếm học sinh theo tên và đưa ra điểm trung bình của họ.

4. Chương trình kết thúc khi nhập vào một chuỗi rỗng.

Dưới đây là hướng dẫn các bước triển khai chi tiết:

* Bước 1: Định nghĩa cấu trúc của cây tìm kiếm nhị phân

Chúng ta sẽ tạo một lớp Node để biểu diễn mỗi nút trong cây và một lớp BinarySearchTree để thực hiện các thao tác trên cây.

class Node:

def __init__(self, name, score):

self.name = name

self.score = score

self.left = None

self.right = None

class BinarySearchTree:

def __init__(self):

self.root = None

def insert(self, name, score):

new_node = Node(name, score)

if self.root is None:

self.root = new_node

else:

self._insert(self.root, new_node)

def _insert(self, current, new_node):

if new_node.name < current.name:

if current.left is None:

current.left = new_node

else:

self._insert(current.left, new_node)

elif new_node.name > current.name:

if current.right is None:

current.right = new_node

else:

self._insert(current.right, new_node)

def search(self, name):

return self._search(self.root, name)

def _search(self, current, name):

if current is None:

return None

if name == current.name:

return current

elif name < current.name:

return self._search(current.left, name)

else:

return self._search(current.right, name)

* Bước 2: Đọc dữ liệu từ tệp Data.inp và khởi tạo cây tìm kiếm nhị phân

def load_data(filename):

bst = BinarySearchTree()

with open(filename, 'r', encoding='utf8') as file:

for line in file:

parts = line.strip().split(maxsplit=1)

name = parts[0] + " " + parts[1]

score = float(parts[2])

bst.insert(name, score)

return bst

bst = load_data("Data.inp")

* Bước 3: Thực hiện các thao tác thêm học sinh và tìm kiếm

def main():

bst = load_data("Data.inp")

while True:

print("Chọn thao tác:")

print("1. Thêm học sinh")

print("2. Tìm kiếm học sinh")

print("Nhập chuỗi rỗng để kết thúc chương trình.")

choice = input("Nhập lựa chọn: ").strip()

if choice == "":

break

elif choice == "1":

name = input("Nhập họ tên học sinh: ").strip()

if name == "":

break

try:

score = float(input("Nhập điểm trung bình: ").strip())

bst.insert(name, score)

print(f"Đã thêm học sinh {name} với điểm trung bình {score}")

except ValueError:

print("Điểm trung bình phải là một số.")

elif choice == "2":

name = input("Nhập họ tên học sinh cần tìm: ").strip()

if name == "":

break

result = bst.search(name)

if result:

print(f"Học sinh: {result.name}, Điểm trung bình: {result.score}")

else:

print("Không tìm thấy học sinh này.")

else:

print("Lựa chọn không hợp lệ. Vui lòng chọn lại.")

if __name__ == "__main__":

main()

*Giải thích:

1. Cấu trúc cây tìm kiếm nhị phân:

- Node: Lớp biểu diễn một nút trong cây, bao gồm tên học sinh, điểm trung bình, và các nút con trái/phải.

- BinarySearchTree: Lớp chứa các phương thức để chèn (insert) và tìm kiếm (search) các nút trong cây.

2. Đọc dữ liệu:

- load_data(filename): Hàm này đọc dữ liệu từ tệp Data.inp và chèn từng học sinh vào cây tìm kiếm nhị phân.

3. Thao tác thêm và tìm kiếm:

- main(): Hàm chính thực hiện vòng lặp để cho phép người dùng thêm học sinh và tìm kiếm học sinh theo tên. Khi nhập vào chuỗi rỗng, chương trình sẽ kết thúc.

Quảng cáo

Lời giải bài tập Chuyên đề Tin 12 Bài 7: Cây tìm kiếm nhị phân hay, ngắn gọn khác:

Quảng cáo

Xem thêm lời giải bài tập Chuyên đề học tập Tin học 12 Kết nối tri thức hay, ngắn gọn khác:

Xem thêm các tài liệu học tốt lớp 12 hay khác:

Tài liệu cho giáo viên: Giáo án, powerpoint, đề thi giữa kì cuối kì, đánh giá năng lực, thi thử THPT, HSG, chuyên đề, bài tập cuối tuần..... độc quyền VietJack, giá hợp lí

Sách VietJack thi THPT quốc gia 2025 cho học sinh 2k7:

ĐỀ THI, GIÁO ÁN, GÓI THI ONLINE DÀNH CHO GIÁO VIÊN VÀ PHỤ HUYNH LỚP 12

Bộ giáo án, đề thi, bài giảng powerpoint, khóa học dành cho các thầy cô và học sinh lớp 12, đẩy đủ các bộ sách cánh diều, kết nối tri thức, chân trời sáng tạo tại https://tailieugiaovien.com.vn/ . Hỗ trợ zalo VietJack Official