第六章树和二叉树（下载后用阅读版式视图或web版式可以看清）
习 题
一、选择题
1．有一“遗传”关系：设x是y的父亲，则x可以把它的属性遗传给y。表示该遗传关系最适合的数据结构为( )。 A.向量 B.树 C图 D.二叉树 2．树最合适用来表示( )。
A.有序数据元素 B元素之间具有分支层次关系的数据 C无序数据元素 D.元素之间无联系的数据
3．树B的层号表示为la，2b，3d，3e，2c，对应于下面选择的( )。 A. la (2b (3d,3e),2c) B. a(b(D,e),c) C. a(b(d,e),c) D. a(b,d(e),c)
4.高度为h的完全二叉树至少有( )个结点，至多有( )个结点。 A. 2h_l B.h C．2h-1 D. 2h
5.在一棵完全二叉树中，若编号为f的结点存在右孩子，则右子结点的编号为( )。 A. 2i B. 2i-l C. 2i+l D. 2i+2
6.一棵二叉树的广义表表示为a(b(c)，d(e(，g(h))，f))，则该二叉树的高度为 ( )。 A.3 B.4 C.5 D.6
7.深度为5的二叉树至多有( )个结点。 A. 31 B. 32 C. 16 D. 10
8.假定在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为( )个。 A. 15 B. 16 C. 17 D. 47
9.题图6-1中，( )是完全二叉树，( )是满二叉树。
1 / 17
10.在题图6-2所示的二叉树中：
(1)A结点是
A.叶结点 B根结点但不是分支结点
C根结点也是分支结点 D.分支结点但不是根结点 (2)J结点是
A.叶结点 B．根结点但不是分支结点 C根结点也是分支结点 D.分支结点但不是根结点 (3)F结点的兄弟结点是 A.E B.D C．空 D.I (4)F结点的双亲结点是 A.A B.B C.C D.D (5)树的深度为
A.1 B.2 C.3 D.4 (6)B结点的深度为
A.1 B.2 C.3 D.4 (7)A结点所在的层是 A.1 B.2 C.3 D.4
11.在一棵具有35个结点的完全二叉树中，该树的深度为( )。 A.5 B.6 C.7 D.8
12. 一棵有124个叶结点的完全二叉树，最多有( )个结点。 A．247 B．248 C．249 D．250
13.用顺序存储的方法将完全二叉树中所有结点逐层存放在数组R[1…n]中，结点R[i]若
有左子树，则左子树是结点( )。
A. R[2i+l] B. R[2i] C.R[i/2] D. R[2i-1]
14.在一非空二叉树的中序遍历序列中，根结点的右边( )。
2 / 17
A.只有右子树上的所有结点 B.只有右子树上的部分结点 C.只有左子树上的部分结点 D.只有左子树上的所有结点
15．一棵度为m的树中，有ni个度为1的结点，有n2个度为2的结点……，有nm个度为m的结点，则该树的叶结点数为( )。 A. n1+n2+...+nm B. (m-l) nm+...+n2+1 C.n1+n2+1 D. nl-n2
16.已知某二叉树的中序遍历序列是debac，后序遍历序列是dabec，它的前序遍历序列
是( )。
A. acbed B. decab C. deabc D. cedba
17.在一棵二叉树的二叉链表中，空指针域等于所有非空指针域数加( )。 A.2 B.1 C.0 D.-1
18.线索二叉树是一种( )结构。
A.逻辑 B．逻辑和存储 C．物理 D.线性
19.由权值分别是8，7，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为( )。 A. 23 B. 37 C．46 D. 43
20.设T是哈夫曼树，具有5个叶结点，树T的高度最高可以是( )。 A.2 B.3 C.4 D.5 二、填空题
1.对于一棵具有n个结点的树，该树中所有结点的度数之和为____。
2.在树型结构中，树根结点没有____结点，其余每个结点有且只有____个前驱 结点：叶子结点没有____结点，其余每个结点可以有____后继结点。 3.有一棵树如题图6-3所示，回答下面的问题。
这棵树的根点是____；叶子结点是____；结点k3的度是____；结点k3的 子女是____；结点k3的父结点是____；这棵树的度为____；这棵树的深度是 ____。
3 / 17
4.假定一棵树的广义表表示为A(B(E)，C(F(H，I，J，G)，D)，则该树的度为____，树的深度为____，终端结点的个数为____，单分支结点的个数为____，双分支结点的个数为____，3分支结点的个数为____，C结点的双亲结点为____，其孩子结点为____。
5.一棵深度为h的满k叉树有如下性质：第h层上的结点都是叶子结点，其余各层上的每个结点都有k棵非空子树。 如果按层次顺序（同层自左至右）从1开始对全部结点编号，则： (1)第i层结点数目是____。
(2)编号为n的结点的双亲结点（若存在）的编号是____。
(3)编号为n的结点的第i个孩子结点（若存在）的编号是____。
(4)编号为n的结点有右兄弟的条件是____：其右兄弟的编号是____。
6．前序遍历一棵树相当于____树中对应的二叉树，后序遍历一棵树则相当于树中对应的二叉树。 7．二叉树的遍历分为____ ，树与森林的遍历包括____。
8．一棵二叉树的第i(i>=1)层最多有____个结点；一棵有n(n>0)个结点的满二叉树共有____ 个叶子和____个非终端结点。 9.在一棵二叉树中，假定双分支结点数为5个，单分支结点数为6个，则叶子结点为____个。 10．在一棵二叉树中，第五层上的结点数最多为____。
11.对于一棵具有n个结点的二叉树，当进行链接存储时，其二叉链表中的指针域的总数为____个，其中____个用于链接孩子结点，____个空闲着。 12.前序遍历的顺序是ABDGEHICFJ，则二叉树的根是____。
13.从概念上讲，树与二叉树是两种不同的数据结构，将树转化为二叉树的基本目的是____ 14.结点最少的树为____ ，结点最少的二叉树为____。
15.一棵完全二叉树按层次遍历的序列为ABCDEFGHI，则在前序遍历中结点E的直接前驱为____ ，后序遍历中结点B的直接后继是____。 16.某二叉树的中序遍历序列为ABCDEFG，后序序列为BDCAFGE，则该二叉树结点的前序序列为____，该二叉树对应的森林包括____棵树。 17.用一维数组存放的一棵完全二叉树如题图6-4所示。
4 / 17
则后序遍历该二叉树时结点访问的顺序为____。 18.由n个权值构成的哈夫曼树共有____个结点。
19.由带权为3，9，6，2，5的5个叶子结点构成一棵哈夫曼树，则带权路径长度为____。
20.设F是一个森林，B是由F转换得到的二叉树，F中有n个非终端结点，则B中右指针域为空的结点有____个。 21.二叉树的存储结构分为____ ，树的存储结构分为____。 三、判断题
1．树中任意结点的子树不必是有序的。( ) 2．树可以看成特殊的无向图。( ) 3．可以使用双链表表示树型结构。( )
4．顺序存储方式只能用于存储线性结构。( )
5．完全二叉树的某结点若无左孩子，则必是叶结点。( )
6．在叶子数目和权值相同的所有二叉树中，最优二叉树一定是完全二叉树。( ) 7．由于二叉树中每个结点的度最大为2，所以二叉树是一种特殊的树。( ) 8．二叉树的前序遍历序列中，任意一个结点均处在其子树结点的前面。 ( ) 9．二叉树的前序和后序遍历序列能惟一确定这棵二叉树。 ( ) 10.中序线索二叉树中，右线索若不为空，则一定指向其父结点。( ) 四、算法和操作题
1．假定一棵二叉树广义表表示为a(b(c)，d(e，D)，分别写出对它进行前序、中序、后序遍历的结果。 前序： 中序： 后序：
2．已知一棵二叉树的中序和后序序列，求该二叉树的高度和双支、单支及叶子结点数。 中根序列：c，b，d，e，a，g，i,h,j，f 后根序列：c，e，d，b，i，j，h，g，fa 高度： 双支： 单支： 叶子：
3．已知一棵树边的集合为{
5 / 17
数据结构课后习题标准答案第六章
