《数据结构课后习题答案第六章》由会员分享，可在线阅读，更多相关《数据结构课后习题答案第六章（16页珍藏版）》请在金锄头文库上搜索。
1、第六章树和二叉树（下载后用阅读版式视图或 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 的完全二叉树至少有(
2、)个结点，至多有( )个结点。A. 2h_l B.h C2h-1 D. 2h5.在一棵完全二叉树中，若编号为 f 的结点存在右孩子，则右子结点的编号为( )。A. 2i B. 2i-l C. 2i+l D. 2i+26.一棵二叉树的广义表表示为 a(b(c)，d(e(，g(h)，f)，则该二叉树的高度为 ( )。A.3 B.4 C.5 D.67.深度为 5 的二叉树至多有( )个结点。A. 31 B. 32 C. 16 D. 108.假定在一棵二叉树中，双分支结点数为 15，单分支结点数为 30 个，则叶子结点数为( )个。A. 15 B. 16 C. 17 D. 479.题图 6-1 中，(
3、 )是完全二叉树，( )是满二叉树。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.411.在一棵具有 35 个结点的完全二叉树中，该树的深度为( )
4、。A.5 B.6 C.7 D.812. 一棵有 124 个叶结点的完全二叉树，最多有( )个结点。A247 B248 C 249 D25013.用顺序存储的方法将完全二叉树中所有结点逐层存放在数组 R1n中，结点 Ri若有左子树，则左子树是结点( )。A. R2i+l B. R2i C.Ri/2 D. R2i-114.在一非空二叉树的中序遍历序列中，根结点的右边( )。A.只有右子树上的所有结点 B.只有右子树上的部分结点C.只有左子树上的部分结点 D.只有左子树上的所有结点15一棵度为 m 的树中，有 ni 个度为 1 的结点，有 n2 个度为 2 的结点，有 nm 个度为 m 的结点，则该
5、树的叶结点数为( )。A. n1+n2+.+nm B. (m-l) nm+.+n2+1 C.n1+n2+1 D. nl-n216.已知某二叉树的中序遍历序列是 debac，后序遍历序列是 dabec，它的前序遍历序列是( )。A. acbed B. decab C. deabc D. cedba17.在一棵二叉树的二叉链表中，空指针域等于所有非空指针域数加( )。A.2 B.1 C.0 D.-118.线索二叉树是一种( )结构。A.逻辑 B逻辑和存储 C物理 D.线性19.由权值分别是 8，7，2，5 的叶子结点生成一棵哈夫曼树，它的带权路径长度为( )。A. 23 B. 37 C46 D.
6、4320.设 T 是哈夫曼树，具有 5 个叶结点，树 T 的高度最高可以是( )。A.2 B.3 C.4 D.5二、填空题1.对于一棵具有 n 个结点的树，该树中所有结点的度数之和为_。2.在树型结构中，树根结点没有_结点，其余每个结点有且只有_个前驱结点：叶子结点没有_结点，其余每个结点可以有_后继结点。3.有一棵树如题图 6-3 所示，回答下面的问题。这棵树的根点是_；叶子结点是_；结点 k3 的度是_；结点 k3 的子女是_；结点 k3 的父结点是_；这棵树的度为_；这棵树的深度是_。4.假定一棵树的广义表表示为 A(B(E)，C(F(H ，I ，J，G)，D) ，则该树的度为_，树的深
7、度为_，终端结点的个数为_，单分支结点的个数为_，双分支结点的个数为_，3 分支结点的个数为_，C 结点的双亲结点为_，其孩子结点为_。5.一棵深度为 h 的满 k 叉树有如下性质：第 h 层上的结点都是叶子结点，其余各层上的每个结点都有 k 棵非空子树。如果按层次顺序（同层自左至右）从 1 开始对全部结点编号，则：(1)第 i 层结点数目是_。 (2)编号为 n 的结点的双亲结点（若存在）的编号是_ 。(3)编号为 n 的结点的第 i 个孩子结点（若存在）的编号是_。(4)编号为 n 的结点有右兄弟的条件是_：其右兄弟的编号是 _。6前序遍历一棵树相当于_树中对应的二叉树，后序遍历一棵树则相
8、当于树中对应的二叉树。7二叉树的遍历分为_ ，树与森林的遍历包括_。8一棵二叉树的第 i(i=1)层最多有 _个结点；一棵有 n(n0)个结点的满二叉树共有_ 个叶子和_个非终端结点。9.在一棵二叉树中，假定双分支结点数为 5 个，单分支结点数为 6 个，则叶子结点为_个。10在一棵二叉树中，第五层上的结点数最多为_。11.对于一棵具有 n 个结点的二叉树，当进行链接存储时，其二叉链表中的指针域的总数为_个，其中_个用于链接孩子结点，_个空闲着。12.前序遍历的顺序是 ABDGEHICFJ，则二叉树的根是_。13.从概念上讲，树与二叉树是两种不同的数据结构，将树转化为二叉树的基本目的是_14.
9、结点最少的树为_ ，结点最少的二叉树为_。15.一棵完全二叉树按层次遍历的序列为 ABCDEFGHI，则在前序遍历中结点 E 的直接前驱为_ ，后序遍历中结点 B 的直接后继是_。16.某二叉树的中序遍历序列为 ABCDEFG，后序序列为 BDCAFGE，则该二叉树结点的前序序列为_，该二叉树对应的森林包括_棵树。17.用一维数组存放的一棵完全二叉树如题图 6-4 所示。则后序遍历该二叉树时结点访问的顺序为_。18.由 n 个权值构成的哈夫曼树共有_个结点。19.由带权为 3，9，6，2，5 的 5 个叶子结点构成一棵哈夫曼树，则带权路径长度为_。20.设 F 是一个森林，B 是由 F 转换得
10、到的二叉树，F 中有 n 个非终端结点，则 B 中右指针域为空的结点有_个。21.二叉树的存储结构分为_ ，树的存储结构分为_。三、判断题1树中任意结点的子树不必是有序的。( )2树可以看成特殊的无向图。( )3可以使用双链表表示树型结构。( )4顺序存储方式只能用于存储线性结构。( )5完全二叉树的某结点若无左孩子，则必是叶结点。( )6在叶子数目和权值相同的所有二叉树中，最优二叉树一定是完全二叉树。( )7由于二叉树中每个结点的度最大为 2，所以二叉树是一种特殊的树。( )8二叉树的前序遍历序列中，任意一个结点均处在其子树结点的前面。 ( )9二叉树的前序和后序遍历序列能惟一确定这棵二叉树
11、。 ( )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已知一棵树边的集合为，M，N，I，E，D ，B，J ，K， ，G，F ，L，H，C)，请画出这棵树，并回答下列问题：(1)哪个是根结点？(2)哪些是叶子结点？(3)哪个是结点 G 的
12、双亲？(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
13、；后序遍历该树的结点次序为 CFEABHGIKJDS，请画出这棵树。7已知一棵树如题图 6-5 所示，将其转换为其孩子兄弟表示的二叉树。并画出该二叉树的后序线索二叉树。8试找出分别满足下列条件的所有二叉树： (1)前序遍历序列和中序遍历序列相同。(2)中序遍历序列和后序遍历序列相同。(3)前序遍历序列和后序遍历序列相同。9已知信息为“ABCD BCD CB DB ACB”，请按此信息构造哈夫曼树，求出每一字符的最优编码。10.己知中序线索二叉树采用二叉链表存储结构，链结点的构造为：其中若 ltag 为 0，则 lchild 指向结点的前驱，否则 lchild 指向左孩子结点；若 rtag 为
14、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 所示的二叉树的情况进行跟踪（即给出各阶段栈的变化及输出的结点序列）。栈已经定义：InitStack(S)（初始化）、Empty(S) （判栈空）、 Push(S，p) （入栈）、Pop(S，p)（出栈）等操作。2假设在表示一棵二叉树的二叉链表上增加两个域：双亲域用于指示其双亲结点，标志域 flag（可取 0.2）的值，用以区分在遍历过程中到达该结点时继续向右或向左或访问该结点。试以此存储结构编写不用栈进行后序遍历的递归形式的算法。3一棵具有 n 个结点的完全二叉树，以一维数组作为存储结构，试设计一个对该完全二叉树进行前序遍历的算法。4设中序线索树的结点由 5 个域组成。Info：给出
