.. . . ..
第六章树和二叉树（下载后用阅读版式视图或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中，( )是完全二叉树，( )是满二叉树。
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.在一非空二叉树的中序遍历序列中，根结点的右边( )。 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的父结点是____；这棵树的度为____；这棵树的深度是 ____。
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．可以使用双链表表示树型结构。( )
. 学习帮手 .
数据结构课后习题答案第六章
