第5章树与二叉树习题解析.docx
《第5章树与二叉树习题解析.docx》由会员分享，可在线阅读，更多相关《第5章树与二叉树习题解析.docx（10页珍藏版）》请在冰点文库上搜索。
第5章树与二叉树习题解析
习题五树与二叉树1
一、选择题
1、一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足 。
A、所有的结点均无左孩子 B、所有的结点均无右孩子
C、只有一个叶子结点 D、是任意一棵二叉树
2、一棵完全二叉树上有1001个结点，其中叶子结点的个数是 。
A、250 B、500 C、254 D、505 E、以上答案都不对
3、以下说确的是 。
A、若一个树叶是某二叉树前序遍历序列中的最后一个结点，则它必是该子树后序遍历序列中的最后一个结点
B、若一个树叶是某二叉树前序遍历序列中的最后一个结点，则它必是该子树中序遍历序列中的最后一个结点
C、在二叉树中，具有两个子女的父结点，在中序遍历序列中，它的后继结点最多只能有一个子女结点
D、在二叉树中，具有一个子女的父结点，在中序遍历序列中，它没有后继子女结点
4、以下说法错误的是 C 。
A、哈夫曼树是带权路径长度最短得数，路径上权值较大的结点离根较近
B、若一个二叉树的树叶是某子树中序遍历序列中的第一个结点，则它必是该子树后序遍历序列中的第一个结点
C、已知二叉树的前序遍历和后序遍历并不能唯一地确定这棵树,因为不知道树的根结点是哪一个
D、在前序遍历二叉树的序列中,任何结点其子树的所有结点都是直接跟在该结点之后的
5、一棵有124个叶结点的完全二叉树，最多有 个结点。
A、247 B、248 C、249 D、250 E、251
6、任何一棵二叉树的叶结点在前（先）序、中序和后序遍历序列中的相对次序 。
A、不发生变化 B、发生变化 C、不能确定
7、设a、b为一棵二叉树上的两个结点。
在中序遍历时，a在b前面的条件是 。
A、a在b的右方 B、a在b的左方C、a是b的祖先 D、a是b的子
8、设深度为k的二叉树上只有度为0和度为2的结点，则这类二叉树上所含的结点总数为 。
A、k+1 B、2k C、2k-1 D、2k+1
9、设有13个值，用它们组成一棵哈夫曼树，则该哈夫曼树共有 个结点。
A、13 B、12 C、26 D、25
10、下面几个符号串编码集合中，不是前缀编码的是 。
A、{0，10，110，1111} B、{11，10，001，101，0001}
C、{00，010，0110，1000} D、{b,c,aa,ac,aba,abb,abc}
11、欲实现任意二叉树的后序遍历的非递归算法而不使用栈结构，最佳的方案是二叉树采用 存储结构。
A、三叉链表 B、广义表 C、二叉链表 D、顺序表
12、以下说法错误的是 。
A、存在这样的二叉树，对它采用任何次序遍历其结点访问序列均相同
B、二叉树是树的特殊情形
C、由树转换成二叉树，其根结点的右子树总是空的
D、在二叉树只有一棵子树的情况下也要明确指出该子树是左子树还是右子树
13、树的基本遍历策略可分为先根遍历和后根遍历，二叉树的基本遍历策略可分为先序、中序和后序三种遍历。
我们把由树转化得到的二叉树称该树对应的二叉树，则下面 是正确的。
A、树的先根遍历序列与其对应的二叉树先序遍历序列相同
B、树的后根遍历序列与其对应的二叉树后序遍历序列相同
C、树的先根遍历序列与其对应的二叉树中序遍历序列相同
D、以上都不对
14、若以二叉树的任一结点出发到根的路径上所经过的结点序列按其关键字有序。
则该二叉树是 。
A、二叉排序树 B、哈夫曼树 C、堆
15、下列有关二叉树的说确的是 。
A、二叉树的度为2 B、一棵二叉树度可以小于2
C、二叉树中至少有一个结点的度为2 D、二叉树中任一个结点的度都为2
16、某二叉树中序序列为ABCDEFG，后序序列为BDCAFGE，则前序序列是 。
A、EGFACDB B、EACBDGF
C、EAGCFBD D、上面的都不对
17、对二叉排序树进行 遍历，可以得到该二叉树所有结点构成的排序序列。
A、前序 B、中序 C、后序 D、按层次
18、由二叉树的前序和后序遍历序列 唯一地确定这棵二叉树。
A、能 B、不能
19、在一棵度为3的树中，度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为 个。
A、4 B、5 C、6 D、7
20、在一棵深度为h的完全二叉树中，所含结点的个数不小于 。
A、2h B、2h+1 C、2h-1 D、2h-1
21、在一棵具有n个结点的二叉树第i层上，最多具有 个结点。
A、2i B、2i+1 C、2i-1 D、2n
22、在下列情况中，可称为二叉树的是 。
A、每个结点至多有两棵子树的树 B、哈夫曼树
C、每个结点至多有两棵子树的有序树 D、每个结点只有一棵右子树
E、以上答案都不对
二、填空题
1、8层完全二叉树至少有 128 个结点，拥有100个结点的完全二叉树的最大层数为 7 。
2、树在计算机的表示方式有 双亲表示法 、 孩子表示法 、孩子兄弟表示法 。
3、一棵有n个结点的满二叉树有 0 个度为1的结点，有 ┕n/2┛ 个分支（非终端）结点和┕n/2┛+1 个叶子，该满二叉树的深度为 ┕log2n┛+1 。
4、若一个二叉树的叶子结点是某子树的中序遍历序列中的最后一个结点，则它必是孩子树的 前序遍历 序列中的最后一个结点。
5、一棵共有n个结点的树，其中所有分支结点的度均为k，则该树中的叶子结点个数为（n×（k-1）+1）/k。
6、深度为k（设根的层数为1）的完全二叉树至少有2k-1个结点，至多有 2k-1 个结点。
7、设只包含根结点的二叉树高度为0，则高度为k的二叉树最大结点数为 2k+1-1，最小结点数为k+1。
8、一棵完全二叉树有999个结点，它的深度为10。
9、对于一棵具有n个结点的树，该树中所有结点的度数之和为 n-1。
10、有n个结点并且其高度为n的二叉树有2n-1个。
11、一棵具有n个结点的二叉树，若它有n0个叶子结点，则该二叉树上度为1的结点n1= n-2n0+1。
12、若一棵二叉树的叶子数为n0，则该二叉树中左、右子树皆非空的结点个数为n0-1。
13、设n0为哈夫曼树的叶子结点数目，则该哈夫曼树共有2n0-1个结点。
14、若以{4、5、6、7、8}作为叶子结点的权值构造哈夫曼树，则其带权路径长度是69。
三、判断题
1、完全二叉树的某结点若无左孩子，则它必是叶结点。
（对 ）
2、存在这样的二叉树，对它采用任何次序的遍历，结果相同。
（ 对 ）
3、二叉树就是结点度为2的树。
（ 错 ）
4、二叉树中不存在度大于2的结点，当某个结点只有一棵子树时无所谓左、右子树。
（ 错 ）
5、已知二叉树的前序遍历序列和后序遍历序列并不能唯一地确定这棵树，因为不知道树的根结点是哪一个。
（错 ）
6、在哈夫曼编码中，当两个字符出现的频率相同时，其编码也相同，对于这种情况应作特殊处理。
（错 ）
7、中序遍历一棵二叉排序树的结点就可得到排好序的结点序列。
（对 ）
8、将一棵树转换成二叉树后，根结点没有左子树。
（错 ）
9、用树的前序遍历和中序遍历可以导出树的后序遍历。
（对 ）
10、哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。
（ 对 ）
11、不使用递归也能实现二叉树前序、中序和后序遍历。
（ 对 ）
习题五树与二叉树2
1.填空题
⑴树是n（n≥0）结点的有限集合，在一棵非空树中，有（）个根结点，其余的结点分成m（m＞0）个（）的集合，每个集合都是根结点的子树。
【解答】有且仅有一个，互不相交
⑵树中某结点的子树的个数称为该结点的（），子树的根结点称为该结点的（），该结点称为其子树根结点的（）。
【解答】度，孩子，双亲
⑶一棵二叉树的第i（i≥1）层最多有（）个结点；一棵有n（n>0）个结点的满二叉树共有（）个叶子结点和（）个非终端结点。
【解答】2i-1，（n+1）/2，（n-1）/2
【分析】设满二叉树中叶子结点的个数为n0，度为2的结点个数为n2，由于满二叉树中不存在度为1的结点，所以n=n0+n2；由二叉树的性质n0=n2+1，得n0=（n+1）/2，n2=（n-1）/2。
⑷设高度为h的二叉树上只有度为0和度为2的结点，该二叉树的结点数可能达到的最大值是（），最小值是（）。
【解答】2h-1，2h-1
【分析】最小结点个数的情况是第1层有1个结点，其他层上都只有2个结点。
⑸深度为k的二叉树中，所含叶子的个数最多为（）。
【解答】2k-1
【分析】在满二叉树中叶子结点的个数达到最多。
⑹具有100个结点的完全二叉树的叶子结点数为（）。
【解答】50
【分析】100个结点的完全二叉树中最后一个结点的编号为100，其双亲即最后一个分支结点的编号为50，也就是说，从编号51开始均为叶子。
⑺已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点。
则该树中有（）个叶子结点。
【解答】12
【分析】根据二叉树性质3的证明过程，有n0=n2+2n3+1（n0、n2、n3分别为叶子结点、度为2的结点和度为3的结点的个数）。
⑻某二叉树的前序遍历序列是ABCDEFG，中序遍历序列是CBDAFGE，则其后序遍历序列是（）。
【解答】CDBGFEA
【分析】根据前序遍历序列和后序遍历序列将该二叉树构造出来。
⑼在具有n个结点的二叉链表中，共有（）个指针域，其中（）个指针域用于指向其左右孩子，剩下的（）个指针域则是空的。
【解答】2n，n-1，n+1
⑽在有n个叶子的哈夫曼树中，叶子结点总数为（），分支结点总数为（）。
【解答】n，n-1
【分析】n-1个分支结点是经过n-1次合并后得到的。
已知二叉树的中序和后序序列分别为CBEDAFIGH和CEDBIFHGA，试构造该二叉树。
对给定的一组权值W＝（5，2，9，11，8，3，7），试构造相应的哈夫曼树，并计算它的带权路径长度。
【解答】构造的哈夫曼树如图5-13所示。
树的带权路径长度为：
WPL=2×4+3×4+5×3+7×3+8×3+9×2+11×2
=120
二叉树先根序、后根序、中根序遍历的速算法（解题技巧）
经过研究我找出了一种不用画图，由先（后）根序遍历和中根序遍历迅速确定遍历结果的办法。
谨以此文献给智商与我同级而又不得不研究算法的朋友。
抽象思维太差，用例子来说明吧。
下面这个是后根遍历的算法。
例1：
已知某二叉树的先根序遍历为ABCDEFG,中根序遍历为CDBAFEG，则它的后根序遍历为_________
解法如下：
1、确定树根。
由先序遍历知道，树根为A。
2、分离左、右子树。
由中根序遍历知，A左面的为CDB左子树结点，右面的FEG为右子树结点。
把先根序遍历也分成左、右子树结点，BCD、EFG。
前根序遍历 BCD EFG
中根序遍历 CDB FEG
3、分别把先根序遍历左、右子树结点抄过来，写的时候要从右往左写，本例中，依次写下B、C、D、，E、F、G，结果是DCBGFE。
当然不是简单到这种程序。
上面只是个原理。
抄的过程应该是这样的：
盯着前根序的，瞅着中根序的。
如果要抄的先根序中的结点在中根序中是最左/右边，则直接抄过来；如果不是，则把这个结点左边的结点先放记在右根序的最左边，然后继续抄。
本题的结果是DCB,FGE,A,即DCBFGEA。
上面这个例子太短，看不出“猫腻”来。
再举个结点多一点儿的。
例2：
已知某二叉树的先根序遍历为ABCDEFGHIJK,中根序遍历为CEDFBAHKJIG，则它的后根序遍历为_________
按上面的方法：
前根序遍历 BCDEF GHIJK
中根序遍历 CEDFB HKJIG
依次抄得前根序的结点：
F、E（E在中根序遍历中不靠边，所以先放在后根遍序历中左子树结点最左边）、D、C
同理，把右子树也抄过来。
因此，写下结点的过程依次是：
如果还是不太懂，你可以试着做一下下面的例子：
已知二叉树前序遍历ABCDEFGHIJK，中序遍历CEDFBAHGKJI，求后序遍历。
解：
（1）以根结点A分左、右子树结点，
BCDEFGHIJK
CEDFBHGKJI
（2） 写左子树，盯着前序，从右到左开始写
DCB （在中序中，B靠右边，C靠左边，D不靠边。
写一个，从中序中抹一个。
）
因为D在中序遍历中不靠边，所以下一个结点E先搁到最左边（注意，是“搁”，也就是说，不能把E从中序抹去。
E DCB
因为B已经抹了，F靠右边。
于是F仍然按照从右到左的规则，写在D的的左边。
E FDCB
最后把E加上，左子树OK。
右子树仍然从右到写
G
因为G不靠边，所以下一个结点H先搁在最左边
H G
然后继续
H KJIG
于是，结果是
EFDCBHKJIGA
前根序遍历类似。
以上的方法只适用于三层以的二叉树（含三层）。
在选择题中，三层以上二叉树也可用以上方法初步判断正确答案。
升级会员 