数据结构题目 课时6
题目
1、设一棵树的度是 4，其中度为 0, 1, 2, 3, 4 的结点个数分别是 8, 4, 2, 1 和（ ）。
A. 4 B. 3 C. 2 D. 1
2、设一棵 m 叉树中有 N₁个度数为 1 的结点，N₂个度数为 2 的结点，……，Nₘ个度数为 m 的结点，则该树中共有（ ）个叶子结点。
3、树最适合用来表示（ ）。
A. 有序数据元素
B. 无序数据元素
C. 元素之间具有分支层次关系的数据
D. 元素之间无联系的数据
4、设 T 是一棵二叉树，T 中有 n 个叶子结点，且非叶子结点都是具有两个孩子的结点，那么 T 中共有（ ）个结点。
A. 2n - 1
B. 2n
C. 2n + 1
D. 2 (n + 1)
5、深度为 h 的完全二叉树至少有______个结点，至多有______个结点。
6、一个具有 1025 个结点的二叉树的高 h 为（ ）。
A. 11
B. 10
C. 11～1025
D. 12～1025
7、若 10 个结点的完全二叉树采用顺序表存储，下标范围 0～9，根结点下标为 0，则下标为 3 的结点的左孩子的下标是_______。
A. 5 B. 6 C. 7 D. 8
8、一棵二叉树为下图，则后序序列为________，中序序列为_________，先序序列为________。
9、已知某二叉树的后序遍历序列是 dabec，中序遍历序列是 debac，它的前序遍历序列为（ ）。
A. acbed
B. decab
C. deabc
D. cedba
10、已知一棵二叉树的先序遍历为：ABDCEF，中序遍历为：DBAECF，要求：
(1) 画出这棵二叉树；
(2) 写出这棵二叉树的后序遍历序列。
答案
1、D
设度为 4 的结点个数为 x
8 + 4 + 2 + 1 + x = 1×4 + 2×2 + 3×1 + 4x + 1
解得 x = 1
2、D
设叶子结点的个数为 x
N₁ + N₂ + ⋯ + Nₘ + x = 1×N₁ + 2×N₂ + ⋯ + m×Nₘ + 1
x = 1×N₂ + ⋯ + (m - 1)×Nₘ + 1
3、C
4、A
非空二叉树上的叶子结点数等于度为 2 的结点数加 1，即 n₀ = n₂ + 1。
5、2^(h - 1)；2^h - 1
6、C
⌈log₂(n + 1)⌉ = ⌈log₂(1025 + 1)⌉ = 11
7、C
注意，这里的根结点下标是从 0 开始。
8、DECBHGFA；BDCEAFGH；ABCDEFGH
9、D
10、（1）
（2）后序遍历为 DBEFCA
原文地址：https://blog.csdn.net/2301_79046256/article/details/145232019
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！