Giải chuyên đề Tin 12 Cánh diều Bài 4: Thực hành tổng hợp: Ứng dụng cây tìm kiếm nhị phân có đáp án
19 người thi tuần này 4.6 168 lượt thi 5 câu hỏi
🔥 Đề thi HOT:
15 câu Trắc nghiệm Tin học 12 Cánh diều Mô hình và các giao thức mạng có đáp án
Bộ 3 đề thi cuối kì 2 Tin 12 Kết nối tri thức có đáp án - Đề 1
15 câu Trắc nghiệm Tin học 12 Kết nối tri thức Bài 19 có đáp án
15 câu Trắc nghiệm Tin học 12 Kết nối tri thức Bài 23 có đáp án
15 câu Trắc nghiệm Tin học 12 Kết nối tri thức Bài 25 có đáp án
Bộ 3 đề thi cuối kì 2 Tin 12 Chân trời sáng tạo có đáp án - Đề 1
15 câu Trắc nghiệm Tin học 12 Kết nối tri thức Bài 24 có đáp án
15 câu Trắc nghiệm Tin học 12 Cánh diều Giới thiệu trí tuệ nhân tạo có đáp án
Nội dung liên quan:
Danh sách câu hỏi:
Lời giải
Đầu vào của bài toán là một tập các phân tử có giá trị là mã các mặt hàng được nhập vào lần lượt. Các yêu cầu của bài toán cần được mô tả chi tiết các bước thực hiện thuật toán dựa theo hướng dẫn như sau:
(1) Đầu tiên, khởi tạo một cây tìm kiếm nhị phân rỗng. Với mỗi mã mặt hàng
được nhập vào, tạo một nút mới có khoá là mã mặt hàng vừa nhập và chèn
nút vào đúng vị trí trên cây tìm kiếm nhị phân như trong Mục 2 của Bài 3.
2) Với một giá trị x nhập vào, thực hiện thao tác tìm kiếm giá trị khoá x trên cây tìm kiếm nhị phân như trong Mục 3 của Bài 3.
3) Thực hiện phép duyệt cây tìm kiếm nhị phân theo thứ tự giữa sẽ thu được danh sách các mã mặt hàng được đưa ra theo thứ tự giá trị khoá tăng dần như trong Mục 4 của Bài 3.
4) Thực hiện phép duyệt cây tìm kiếm nhị phân theo thứ tự giữa. Trong khi duyệt, nếu gặp nút có giá trị khoá nhỏ hơn min hoặc có giá trị khoá lớn hơn max thì dừng việc duyệt đến các nút con của nó và tiếp tục quay lại quá trình duyệt cho các nhánh khác.
Lời giải
Hướng dẫn: Mỗi nhóm chọn một ví dụ cụ thể và mô phỏng chi tiết từng bước trên ví dụ đó, bao gồm:
• Khởi tạo cây tìm kiếm nhị phân.
• Chèn từng mã mặt hàng vào cây.
• Tìm kiếm một mã mặt hàng trên cây.
• Duyệt cây theo thứ tự giữa tìm nút có giá trị khoá t.
• Duyệt cây theo thứ tự giữa đưa ra danh sách các nút có giá trị khoá trong khoảng từ min đến max.
Lời giải
Các nhóm thực hiện theo các bước sau:
Chuẩn bị các bộ dữ liệu đầu vào cho chương trình, mỗi bộ dữ liệu cần lưu trữ trong một mảng một chiều có cấu trúc là một cây nhị phân hoàn chỉnh có tính chất cây tìm kiếm nhị phân. Ví dụ: Mảng A
=[26, 21, 36, 12, None, None, 40]
biểu diễn một cây tìm kiếm nhị phân hoàn chỉnh.
Viết chương trình duyệt cây theo thứ tự giữa sử dụng mảng một chiều và được cài đặt đệ quy.
Lời giải
Với hai bộ dữ liệu mẫu trong Bảng 1 (minh hoạ tại Hình 1 và Hình 2), kết quả thử nghiệm chương trình của mỗi nhóm cần giống với kết quả đầu ra tương ứng trong bảng:
Yêu cầu mỗi nhóm cần tự nhập vào thêm nhiều bộ dữ liệu đầu vào khác nhau và kiểm nghiệm kết quả đầu ra.
Khi áp dụng vào thực tiễn cuộc sống, gia đình Hương Trà cần lưu trữ nhiều thông tin hơn về mỗi mặt hàng như: tên mặt hàng, số lượng, xuất xứ, giá trị nhập vào, giá trị bán ra,... Khi đó, Hương Trà cần mở rộng quản lí cây tìm kiếm nhị phân. Trong bài học này, chưa đề cập đến cách giải quyết vấn đề mở rộng này.
Lời giải
Tên công ty là một chuỗi kí tự không rỗng, ví dụ: Công ty Alphabee, công ty BeatLight, công ty ZentaHome…
Giá trị Min, Max trong thực hành 4 cũng là dạng một chuỗi kí tự.
Cây tìm kiếm nhị phân cần được xây dựng dựa trên việc so sánh chuỗi là giá trị khoá của mỗi nút. Việc so sánh hai chuỗi cần theo quy luật thứ tự từ từ điển của chuỗi kí tự dựa trên thuật toán sau:
1. Khởi tạo biến 1 = 0. Các kí tự trong chuỗi được đánh số từ 0 đến độ dài của chuỗi trừ 1.
2. Bước lặp:
a) So sánh kí tự thứ I của hai chuỗi với nhau.
b) Kí tự nào lớn hơn thì chuỗi chứa kí tự đó sẽ lớn hơn chuỗi còn lại theo thứ tự từ từ điển. Kết thúc quá trình so sánh.
c) i =i +1
d) Bước lặp kết thúc khi i bằng độ dài của một trong hai chuỗi. Nếu độ dài cả hai chuỗi đều bằng i thì hai chuỗi bằng nhau theo thứ tự từ điển. Trái lại, chuỗi nào có độ dài lớn hơn sẽ lớn hơn chuỗi còn lại theo thứ tự từ điển.
Ví dụ “Alphabet” > Aphabee
Sau khi đưa kết quả bài thực hành 3, em nhận xét dãy tên các công ty đưa ra theo phép duyệt thứ tự giữa trên cây tìm kiếm nhị phân có đặc điểm sau: Sử dụng mảng 1 chiều và có sử dụng đệ quy.
34 Đánh giá
50%
40%
0%
0%
0%