数据结构期末复习 第六章树和二叉树
一、选择题
1. 树最适合用来表示（C）。
A. 有序数据元素 B. 无序数据元素
C. 元素之间具有分支层次关系的数据 D. 元素之间无联系的数据
2. 树中所有结点的度等于所有结点数加（D）。
A. 1 B. 0 C. 2 D. -1
3. 对于一个满二叉树，m个树叶，n个结点，深度为h，则（D）。
A. n = h + m B. h + m = 2n C. m = h-1 D. n = 2 h -1
4. 如图所示一棵二叉树中，（C）不是完全二叉树。
5. 深度为5的二叉树至多有（C）个结点。
A. 16 B. 32 C. 31 D. 10
6. 假定一棵二叉树中，双分支结点数为15，单分支结点数为30，则叶子结点数为（B）。
A. 15 B. 16 C. 17 D. 47
7. 二叉树第k层上最多有（B）个结点。
A．2k B．2k-1 C．2k-1 D．2k-1
8.在一棵度具有5层的满二叉树中结点总数为（A）。
A．31 B．32 C．33 D．16
9.在一棵二叉树上，第5层的结点数最多为（C）。
A．8 B．15 C．16 D．32
10.具有127个结点的完全二叉树其深度为（B）。
A．8 B．7 C．6 D．5
11. 设一棵二叉树中没有度为1的结点，已知叶子结点数为n，此树的结点数为（D）。
A．2n+2 B．2n+1 C．2n D．2n-1
12.设二叉树中有n2个度为2的结点，n1个度为1的结点，n0个叶子结点，则此二叉树中空指针域个数为（D）。
A．n0+n1+n2 B．n2+n1+2n0 C．2n2+n1 D．2n0+n1
解析：
结点总数：n= n0+n1+n2。
在二叉链表中，每个结点有 2 个指针域（左孩子和右孩子）。总指针域数 = 2n。
非空指针域数 = 边数 e。在二叉树中，边数：e=n−1。即：除了根结点，每个结点都有一条边。
所以空指针域数：=2n-（n-1）=n+1= n0+n1+n2+1。
根据二叉树的性质：叶子结点数比度为 2 的结点多 1，所以n2可以表示为n0-1，所以
空指针域数= n0+n1+(n0-1)+1=2n0+n1
13.n个结点的二叉树中，用二叉链表做存储，非空指针数目为（C）。
A．n B．2n C．n-1 D．n+1
14. 在一棵二叉树的二叉链表中，空指针域数等于非空指针域数加（C）。
A．0 B．1 C．2 D．-1
15. 在一非空二叉树的中序遍历序列中，根结点的右边（A）。
A. 只有右子树上的所有结点 B. 只有右子树上的部分结点
C. 只有左子树上的所有结点 D. 只有左子树上的部分结点
16. 如图所示二叉树的中序遍历序列是（B）。
A. abdgcefh B. dgbaechf C. gdbehfca D. abcdefgh
17. 设n、m为一棵二叉树上的两个结点，中序遍历时n在m前的条件是（C）。
A. n在m右方 B. n是m祖先 C. n在m左方 D. n是m子孙
18.某二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树一定（D）。
A.空或只有一个结点 B.完全二叉树
C.二叉排序树 D.深度等于其结点数
19.二叉树的先序遍历和中序遍历如下：
先序遍历：EFHIGJK
中序遍历：HFIEJKG
该二叉树根的右子树的根是（C）。
A．E B．F C．G D．H
20. 如果将给定的一组数据作为叶子数值，所构造出的二叉树的带权路径长度最小，则该树称为（A）。
A．哈夫曼树 B．平衡二叉树 C．二叉树 D．完全二叉树
21.利用n个值作为叶结点的权生成的哈夫曼树中共包含有（D）个结点。
A. n B. n+1 C. 2*n D. 2*n-1
22. 利用2、4、5、10这四个值作为叶子结点的权，生成一棵哈夫曼树，该树中所有叶子的最长带权路径长度为（C）。
A. 18 B. 16 C. 38 D. 30
23.哈夫曼树是（D）。
A．满二叉树 B．二叉排序树
C．树的路径长度最短的二叉树 D．带权路径长度最短的二叉树
24.用权值分别为15，2，4，5的四个结点，构造出的哈夫曼树为（ D ）。
25.设哈夫曼树的叶结点数为n，则它的结点总数为（A）。
A．2n-1 B．2n C．2n+1 D．不确定
二、判断题
1．树是一种线性结构。（×）
2．树最适合表示元素之间具有层次关系的数据。（√）
3．如果结点A有 3个兄弟，而且B是A的双亲，则B的度是4。（√）
4. 树中全部结点的度均大于0。（×）
5. 森林是m（m≥0）棵互不相交的树的集合。（√）
6. 深度为k的完全二叉树至少有2k-1个结点。（×）
7. 完全二叉树中没有度为1的结点。（×）
8．若树的度为2时，该数为二叉树。（×）
9．具有三个结点的二叉树有五种。（√）
解析：如下所示：
10．深度为5的二叉树最多有3层。（×）
11．具有256个结点的完全二叉树的深度为9 。（√）
12．具有100个结点的完全二叉树有50 个叶子。（√）
解析：100个结点的完全二叉树，前6层是满的（1、2、4、8、16、32），共63个结点，所以第7层有100-63=37个结点（都是叶子结点），要在第7层产生37个叶子结点，则第6层要有18个双分支结点和1个单分支结点，所以第6层还剩32-19=13个结点没有孩子（即叶结点）。所以总叶结点数=37+13=50.
13. 在二叉树的链接存储中，每个结点设置三个域：值域、左指针域和右指针域。（√）
14．二叉树只能采用二叉链表来存储。（×）
15．具有n个结点的二叉树，采用二叉链表存储，共有n+1个空链域。（√）
16. 二叉树的先序遍历序列中，任意一个结点均处在其子女结点的前面。（√）
17．已知一棵树的先序序列和后序序列，一定能构造出该树。（×）
解析：先序 + 中序 → 可唯一确定二叉树
后序 + 中序 → 可唯一确定二叉树
先序 + 后序 → ❌ 不能唯一确定二叉树（当存在单支结点时产生歧义）
反例：
1 1
/ \\
2 2
上面两种二叉树先序都不1，2；后序都为2，1。
18. 二叉树的遍历就是按照一定次序访问树中所有结点，并且每个结点的值仅被访问一次的过程。（√）
19. 哈夫曼树一定是完全二叉树或满二叉树。（×）
20. 哈夫曼树只存在着双支结点，不存在单支结点。（√）
三、本章综合应用或程序题
1. 有一棵树如图所示，回答下面问题：
（1）这棵树的根结点是（C）；
（2）这棵树的叶子结点是（E）；
（3）这棵树的度是（A）；
（4）这棵树的深度是（B）；
（5）c结点的孩子结点是（D）；
（6）c结点的父母结点是（C）。
A. 3
B. 4
C. a
D. e、f
E. b、e、d、g
2. 由如图所示的二叉树，回答以下问题：
（1）其中序遍历序列（B）；
（2）其先序遍历序列（C）；
（3）其后序遍历序列（A）；
A. gdbeihfca B. dgbaechif C. abdgcefhi
3.以3，4，5，8，9，作为叶结点的权，构造一棵哈夫曼树。该树的带权路径长度为（D）
A. 61 B. 62 C.63 D.65
4.以2，3，4，7，8，9作为叶结点的权，构造一棵哈夫曼树。权重值为4的叶结点的哈夫曼编码为（ABC）
A. 000 B. 001 C.010 D.10
解析：哈夫曼树编码不唯一，ABC都是可能的，参考答案为B不准确。图示如下：
