Đáp án và lời giải
Chuyên đề Tin 12 CTST Bài 2.1. Cây và cây nhị phân
Câu 1
Hướng dẫn chấm do TopStudy biên soạn, mang tính gợi ý
Câu 2
Hướng dẫn chấm do TopStudy biên soạn, mang tính gợi ý
a) Nút gốc, nút nhánh, nút lá ở Hình 3a:
- Nút gốc là: 2
- Nút nhánh là: 24, 11, 20, 8.
- Nút lá là: 83, 3, 10, 15, 9.
b) Mức và chiều cao của cây trong Hình 3b
Mức của cây là: 1, nút gốc ở mức 0.
Chiều cao của cây là: 3
Câu 3
Hướng dẫn chấm do TopStudy biên soạn, mang tính gợi ý
Câu 4
Hướng dẫn chấm do TopStudy biên soạn, mang tính gợi ý
Câu 5
Hướng dẫn chấm do TopStudy biên soạn, mang tính gợi ý
Biểu diễn cấu trúc các tập bao lồng nhau trong Hình 8 dưới dạng cây như sau:
Cây vừa nêu có 2 mấy nút lá là: C, D, E, F.
Câu 6
Hướng dẫn chấm do TopStudy biên soạn, mang tính gợi ý
a) Vẽ một cây nhị phân có chiều cao là 4 như sau:
b) Xây dựng mảng một chiều để biểu diễn cây này:
[A, B, C, D, E, F, G, H, I, K, N, M, L, O, P]
Vận dụng trang 31 Tin học 12: Cho mảng một chiều A biểu diễn cho một cây nhị phân hoàn chỉnh như sau:
2
24
11
8
3
8
9
1
2
3
4
Chỉ ra các nút con của rút có giá trị là 11.
Câu 7
Hướng dẫn chấm do TopStudy biên soạn, mang tính gợi ý
Mảng biểu diễn cây nhị phân như sau:
| Mảng | 2 | 24 | 11 | 8 | 3 | 8 | 9 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| Thứ tự | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
Ta thấy nút có giá trị là 11 nằm ở vị trí thứ 3 trong mảng.
Xác định các nút con của nút tại vị trí 3
- Nút con trái của nút tại vị trí i hay còn gọi là vị trí số 3 sẽ nằm ở vị trí 2*i = 2*3=6
- Nút con phải của nút tại vị trí i hay còn gọi là vị trí số 3 sẽ nằm ở vị trí 2*i + 1=2*3+1=7
Giá trị của các nút con tại vị trí 6 có giá trị là 8. Nút tại vị trí 7 có giá trị là 9.
Vậy, các nút con của nút có giá trị 11 là: Nút con trái: 8. Nút con phải: 9