第六章树和二叉树（下载后用阅读版式视图或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_lB.h C．2h-1 D. 2h5.在一棵完全二叉树中，若编号为f的结点存在右孩子，则右子结点的编号为( )。

A. 2iB. 2i-lC. 2i+lD. 2i+26.一棵二叉树的广义表表示为a(b(c)，d(e(，g(h))，f))，则该二叉树的高度为( )。

A.3B.4C.5D.67.深度为5的二叉树至多有( )个结点。

A. 31B. 32C. 16D. 108.假定在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为( )个。

A. 15B. 16C. 17D. 479.题图6-1中，( )是完全二叉树，( )是满二叉树。

10.在题图6-2所示的二叉树中：(1)A结点是A.叶结点 B根结点但不是分支结点C根结点也是分支结点 D.分支结点但不是根结点(2)J结点是A.叶结点 B．根结点但不是分支结点C根结点也是分支结点 D.分支结点但不是根结点(3)F结点的兄弟结点是A.EB.D C．空 D.I(4)F结点的双亲结点是A.AB.BC.CD.D(5)树的深度为A.1B.2C.3D.4(6)B结点的深度为A.1B.2C.3D.4(7)A结点所在的层是A.1B.2C.3D.411.在一棵具有35个结点的完全二叉树中，该树的深度为( )。

A.5B.6C.7D.812. 一棵有124个叶结点的完全二叉树，最多有( )个结点。

A．247 B．248 C．249 D．25013.用顺序存储的方法将完全二叉树中所有结点逐层存放在数组R[1…n]中，结点R[i]若有左子树，则左子树是结点( )。

A. R[2i+l]B. R[2i]C.R[i/2]D. R[2i-1]14.在一非空二叉树的中序遍历序列中，根结点的右边( )。

A.只有右子树上的所有结点B.只有右子树上的部分结点C.只有左子树上的部分结点D.只有左子树上的所有结点15．一棵度为m的树中，有n i个度为1的结点，有n2个度为2的结点……，有n m个度为m的结点，则该树的叶结点数为( )。

A. n1+n2+...+n mB. (m-l) n m+...+n2+1C.n1+n2+1D. n l-n216.已知某二叉树的中序遍历序列是debac，后序遍历序列是dabec，它的前序遍历序列是( )。

A. acbedB. decabC. deabcD. cedba17.在一棵二叉树的二叉链表中，空指针域等于所有非空指针域数加( )。

A.2B.1C.0D.-118.线索二叉树是一种( )结构。

A.逻辑B．逻辑和存储C．物理 D.线性19.由权值分别是8，7，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为( )。

A. 23B. 37 C．46 D. 4320.设T是哈夫曼树，具有5个叶结点，树T的高度最高可以是( )。

A.2B.3C.4D.5二、填空题1.对于一棵具有n个结点的树，该树中所有结点的度数之和为____。

2.在树型结构中，树根结点没有____结点，其余每个结点有且只有____个前驱结点：叶子结点没有____结点，其余每个结点可以有____后继结点。

3.有一棵树如题图6-3所示，回答下面的问题。

这棵树的根点是____；叶子结点是____；结点k3的度是____；结点k3的子女是____；结点k3的父结点是____；这棵树的度为____；这棵树的深度是____。

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所示。

则后序遍历该二叉树时结点访问的顺序为____。

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．已知一棵树边的集合为{<I< SPAN>，M>，<I< SPAN>，N>，<E< SPAN>，I>，<B< SPAN>，E>，<B< SPAN>，D>，<A< SPAN>，B>，<G< S PAN>，J>，<G< SPAN>，K>，<C< SPAN>，G>，<C< SPAN>，F>，<H< SPAN>，L>，<C< SPAN>，H>，<A< SPAN>，C>)，请画出这棵树，并回答下列问题：(1)哪个是根结点？(2)哪些是叶子结点？(3)哪个是结点G的双亲？(4)哪些是结点G的祖先？(5)哪些是结点G的孩子？(6)哪些是结点E的子孙？(7)哪些是结点E的兄弟？哪些是结点F的兄弟？(8)结点B和N的层次号分别是什么？(9)树的深度是多少？(10)以结点C为根的子树的深度是多少？4．将算术表达式((a+b)+c*(d+e)+f*(g+h)转化为二叉树。

5. 一棵二叉树的结点数据采用顺序存储结构，存储于数组BT中，如题表6-1所示。

画出该二叉树的链接表示形式。

数组BT的存放形式是相对于满二叉树中编号为数组下标值的结点值。

若该结点不存在，则取0值。

6．假设前序遍历某棵树的结点次序为SACEFBDGHIJK；后序遍历该树的结点次序为CFEABHGIKJDS，请画出这棵树。

7．已知一棵树如题图6-5所示，将其转换为其孩子兄弟表示的二叉树。

并画出该二叉树的后序线索二叉树。

8．试找出分别满足下列条件的所有二叉树：(1)前序遍历序列和中序遍历序列相同。

(2)中序遍历序列和后序遍历序列相同。

(3)前序遍历序列和后序遍历序列相同。

9．已知信息为“ABCD BCD CB DB ACB”，请按此信息构造哈夫曼树，求出每一字符的最优编码。

10.己知中序线索二叉树采用二叉链表存储结构，链结点的构造为：其中若ltag为0，则lchild指向结点的前驱，否则lchild指向左孩子结点；若rtag为0，则rchild指向结点的后继，否则rchild指向右孩子结点。

下面的算法返回x所指结点的直接后继结点的位置。

若该算法有错，则请改正错误；若无错，请写“正确”二字。

BiTree INSUCC (BiTree x){ s=X->rchild;if（s->rtag）while （s->ltag）s=s->rchild;return s；)五、算法设计题1．编写对二叉树进行中序遍历的非递归算法，并对算法执行题图6-6所示的二叉树的情况进行跟踪（即给出各阶段栈的变化及输出的结点序列）。