Câu hỏi:

13/07/2024 82

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.  (ảnh 1)

 

 

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).

Tổng ôn toán Tổng ôn sử Các môn khác

Quảng cáo

Trả lời:

verified
Giải bởi Vietjack

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.

CÂU HỎI HOT CÙNG CHỦ ĐỀ

Câu 1:

Cho trước dãy các số A = [10, 1, 2, 11, 8, 15, 20, 9, 0]. 

Hãy mô tả và vẽ sơ đồ cây nhị phân biểu diễn dãy số trên sau khi thực hiện thao tác chèn như đã mô tả trong hoạt động. 

Xem đáp án » 13/07/2024 202

Câu 2:

Nếu dãy số được đưa vào cây tìm kiếm nhị phân là tăng dần (hoặc giảm dần) thì cây tìm kiếm nhị phân tương ứng có dạng như thế nào?

Xem đáp án » 13/07/2024 143

Câu 3:

Viết hàm chèn khoá v vào cây tìm kiếm nhị phân T sử dụng kĩ thuật đệ quy.

Xem đáp án » 13/07/2024 102

Câu 4:

Quan sát các cây nhị phân sau, em có nhận xét gì về giá trị của các nút trên cây?

Quan sát các cây nhị phân sau, em có nhận xét gì về giá trị của các nút trên cây? (ảnh 1)

Xem đáp án » 13/07/2024 100

Câu 5:

Cây tìm kiếm nhị phân T được thiết lập bằng cách chèn lần lượt các phần tử 3, 1, 6, 5, 0, 2, 4. Dùng sơ đồ mô tả các bước tìm kiếm giá trị khóa là:

a) 4                                   b) 10                                 c) 0

Xem đáp án » 13/07/2024 100

Câu 6:

Từ các khóa 1, 2, 3 có thể tạo ra được bao nhiêu cây tìm kiếm nhị phân? Hãy vẽ sơ đồ mô tả các cây này.

Xem đáp án » 13/07/2024 96

Câu 7:

Thay đổi thứ tự chèn các phần tử vào cây nhị phân có tạo ra các cây tìm kiếm nhị phân khác nhau hay không? Cho ví dụ minh họa.

Xem đáp án » 13/07/2024 95

Bình luận


Bình luận
Đăng ký gói thi VIP

VIP 1 - Luyện thi tất cả các đề có trên Website trong 1 tháng

  • Được thi tất cả các đề của các lớp có trên Khoahoc.vietjack.com
  • Ngân hàng câu hỏi trắc nghiệm theo các mức độ Nhận biết, Thông hiểu, Vận dụng, Vận dụng cao.
  • Luyện chuyên sâu, rèn tốc độ với trọn bộ đề thi thử, đề minh họa, chính thức các năm.
  • Hỏi bài tập với đội ngũ chuyên môn cao của chúng tôi.

Đặt mua

VIP 2 - Luyện thi tất cả các đề có trên Website trong 3 tháng

  • Được thi tất cả các đề của các lớp có trên Khoahoc.vietjack.com
  • Ngân hàng câu hỏi trắc nghiệm theo các mức độ Nhận biết, Thông hiểu, Vận dụng, Vận dụng cao.
  • Luyện chuyên sâu, rèn tốc độ với trọn bộ đề thi thử, đề minh họa, chính thức các năm.
  • Hỏi bài tập với đội ngũ chuyên môn cao của chúng tôi.

Đặt mua

VIP 3 - Luyện thi tất cả các đề có trên Website trong 6 tháng

  • Được thi tất cả các đề của các lớp có trên Khoahoc.vietjack.com
  • Ngân hàng câu hỏi trắc nghiệm theo các mức độ Nhận biết, Thông hiểu, Vận dụng, Vận dụng cao.
  • Luyện chuyên sâu, rèn tốc độ với trọn bộ đề thi thử, đề minh họa, chính thức các năm.
  • Hỏi bài tập với đội ngũ chuyên môn cao của chúng tôi.

Đặt mua

VIP 4 - Luyện thi tất cả các đề có trên Website trong 12 tháng

  • Siêu tiết kiệm - Được thi tất cả các đề của các lớp có trên Khoahoc.vietjack.com
  • Ngân hàng câu hỏi trắc nghiệm theo các mức độ Nhận biết, Thông hiểu, Vận dụng, Vận dụng cao.
  • Luyện chuyên sâu, rèn tốc độ với trọn bộ đề thi thử, đề minh họa, chính thức các năm.
  • Hỏi bài tập với đội ngũ chuyên môn cao của chúng tôi.

Đặt mua

Vietjack official store