Tin học · Lớp 12
15 câu · 23 phút · Ngân hàng đề TopStudy. Đáp án và lời giải do TopStudy biên soạn, mở ngay dưới từng câu.
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?
Hướng dẫn chấm do TopStudy biên soạn, mang tính gợi ý
- Tại mỗi nút, dữ liệu của nút của cây con trái nhỏ hơn dữ liệu của cây con phải với nút này.
- Tại mỗi nút, giá trị nút luôn lớn hơn dữ liệu nút con trái của nó và luôn nhỏ hơn dữ liệu nút con phải của nó
Hướng dẫn chấm do TopStudy biên soạn, mang tính gợi ý
a) Tổ chức dữ liệu cây nhị phân:
Có thể tổ chức dữ liệu cây nhị phân theo 2 cách là sử dụng mô hình nút liên kết hoặc mảng 1 chiều. Mô hình nút liên kết bao gồm:
- Cấu trúc nút Node dùng để lưu thông tin của nút.
- Cấu trúc nút Tree có gốc của cây.
b) Cây tìm kiếm nhị phân:
Có 2 tính chất quan trọng:
- Khoá của mỗi nút của cây lớn hơn khoá của tất cả các nút thuộc cây con trái và nhỏ hơn khoá của tất cả các nút thuộc cây con phải của nó.
- Hai nút khác nhau có hai khoá khác nhau.
Trong hình 7.5, em hãy cho biết cây nào là cây tìm kiếm nhị phân.
Hướng dẫn chấm do TopStudy biên soạn, mang tính gợi ý
Hướng dẫn chấm do TopStudy biên soạn, mang tính gợi ý
Có thể tạo 2 cây tìm kiếm như sau:
- Cây 1:
- Cây 2:
Bài toán: cho cây tìm kiếm nhị phân T. Yêu cầu chèn khoá v vào cây T sao cho sau khi cho sau khi chèn khoá v thì cây T vẫn là cây tìm kiếm nhị phân.
Quan sát, thảo luận, tìm hiểu thuật toán tìm kiếm khoá 7 trên cây tìm kiếm nhị phân và cách chèn khoá 7 vào cây này.
Hướng dẫn chấm do TopStudy biên soạn, mang tính gợi ý
Quá trình chèn khoá v = 7 vào cây tìm kiếm nhị phân T ở Hình 7.6a như sau:
Bước 1. Tìm vị trí cần chèn khoá v trên cây T (Hình 7.6b). Khoá v lớn hơn khoá 5, đi đến nút con phải. Khoá y nhỏ khoá 10, đi đến nút con trái. Khoá y nhỏ hơn khoá 8, đi đến nút con trái và gặp nút giả None.
Bước 2. Chèn khoá v vào cây T (Hình 7.6c). Trong trường hợp khoá v không có trong cây T thì chèn khoá v vào cây này bằng cách tạo nút thật mới tại nút giả None và gán khoá y cho nút mới này.
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.
Khi nào việc tìm kiếm trên cây tìm kiếm nhị phân là:
a) nhanh nhất?
b) chậm nhất?
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
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.
Cho trước dãy A bao gồm các số nguyên và các giá trị None. Viết chương trình kiểm tra xem A có phải là biểu diễn của một cây nhị phân hoàn chỉnh đã biến đổi hay không?
Ví dụ:
Dãy [10, 7, 0, 5, None, 3] là biểu diễn của cây nhị phân hoàn chỉnh đã biến đổi. Dãy [1, 6, None, 2, 3, None, 4] không là biểu diễn của cây nhị phân tổng quát nào.
Cho trước dãy A bao gồm các số nguyên và các giá trị None. Viết chương trình kiểm tra xem A có phải là biểu diễn của một cây tìm kiếm nhị phân hay không.
Ví dụ:
Dãy [5, 3, 6, None, 4, None, 10] là biểu diễn của cây tim kiếm nhị phân.
Dãy [2, 1, 5, None, 3, 4, 10] không là biểu diễn của cây tìm kiếm nhị phân (mặc dù dãy này là biểu diễn của cây nhị phân hoàn chỉnh đã biến đổi).
Tất cả đề Chuyên đề 2. Tìm hiểu cây tìm kiếm nhị phân trong sắp xếp và tìm kiếm · Các bộ sách Tin học Lớp 12