数据结构习题
书面作业练习题
习 题 六 树 和 二 叉 树
6.1 单项选择题
1. 下图所示的4棵二叉树，____不是完全二叉树。
2. 下列编码中属前缀码的是( ) （A ）{1,01,000,001} （B ）{1,01,011,010}
（C ）{0,10,110,11} （D ）{0,1,00,11
3. 已知某二叉树的后序遍历序列是dabec ，中序遍历序列是debac ，它的前序遍历序列是____。
A. acbed
B. decab
C. deabc
D. cedba
4．设a,b 为一棵二叉树上的两个结点，在中序遍历时，a 在b 前的条件是 。
A ．a 在b 的右方
B ．a 在b 的左方
C ．a 是b 的祖先
D ．a 是b 的子孙
5. 假定在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为 个。
A ．15
B ．16
C ．17
D ．47
6. 按照二叉树的定义，具有3个结点的二叉树有____种。
A. 3
B. 4
C. 5
D. 6
（A）（B）（C）（D）
图8.7 4棵二叉树
7. 树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。这里，我们把由树转化得到的二叉树叫做这棵数对应的二叉树。结论____是正确的。
A. 树的先根遍历序列与其对应的二叉树的先序遍历序列相同
B. 树的后根遍历序列与其对应的二叉树的后序遍历序列相同
C. 树的先根遍历序列与其对应的二叉树的中序遍历序列相同
D. 以上都不对
8. 深度为5的二叉树至多有____个结点。
A. 16
B. 32
C. 31
D. 10
9. 树最适合用来表示____。
A. 有序数据元素
B. 无序数据元素
C. 元素之间具有分支层次关系的数据
D. 元素之间无联系的数据
10. 设有13个值，用它们组成一棵赫夫曼树，则该赫夫曼树共有( )个结点。
A ．13 B. 12 C. 26 D. 25
6.2 应用题
1. 有一棵树如图8.12所示，回答下面的问题：
⑴ 这棵树的根结点是____；
⑵ 这棵树的叶子结点是____；
⑶ 结点k3的度是____； ⑷ 这棵树的度是____；
⑸ 这棵树的深度是____；
⑹ 结点k3的子女是____； ⑺ 结点k3的父结点是____；
2. 深度为k 的完全二叉树至少有____个结点。至多有____个结点，若按自上而下，从左到右次序给结点编号（从0开始），则编号最小的叶子结点的编号是____。
3. 结点最少的树为____，结点最少的二叉树为____。
4. 由如图8.17所示的二叉树， 该二叉树对应的森林是?。
图8.12 一棵树
图8.17 一棵二叉树
5. 已知一棵树如图8.20所示，画出其转换为的一棵二叉树。
该树的先根遍历序列、后根遍历序列？
图8.20 一棵树
6. 有一份电文中共使用8个字符：a、b、c、d、e、f、g、h，它们出现的频率是5, 29, 7, 8, 14, 23, 3, 11（9分）
（1）试画出对应的哈夫曼树；
（2）每个字符的哈夫曼编码；
（3）求带权外部路径长度(WPL)。
6.3 算法设计题:
试编写算法，统计二叉树的叶子的个数。
6.4 证明题:
证明：在非空二叉树的第i层上，至多有2i个结点（i≥0）。
