第章_树与二叉树习题解析.docx

习题五树与二叉树1一、选择题1、一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足。A、所有的结点均无左孩子B、所有的结点均无右孩子C、只有一个叶子结点D、是任意一棵二叉树2、一棵完全二叉树上有1001.个结点，其中叶子结点的个数是oA、250B、500C、254D、505E、以上答案都不对3、以下说法正确的是oA、若一个树叶是某二叉树前序遍历序列中的最后一个结点，则它必是该子树后序遍历序列中的最后一个结点B、若一个树叶是某二叉树前序遍历序列中的最后一个结点，则它必是该子树中序遍历序列中的最后一个结点C、在二叉树中，具有两个子女的父结点，在中序遍历序列中，它的后继结点最多只能有一个子女结点D、在二叉树中，具有一个子女的父结点，在中序遍历序列中，它没有后继子女结点4、以下说法错误的是CoA、哈夫曼树是带权路径长度最短得数，路径上权值较大的结点离根较近B、若一个二叉树的树叶是某子树中序遍历序列中的第一个结点，则它必是该子树后序遍历序列中的第一个结点C、已知二叉树的前序遍历和后序遍历并不能唯一地确定这棵树,因为不知道树的根结点是哪一个D、在前序遍历二叉树的序列中，任何结点其子树的所有结点都是直接跟在该结点之后的5、一棵有124个叶结点的完全二叉树，最多有个结点。A、247B、248C、249D、250E、2516、任何一棵二叉树的叶结点在前（先）序、中序和后序遍历序列中的相对次序OA、不发生变化B、发生变化C、不能确定7、设a、b为一棵二叉树上的两个结点。在中序遍历时，a在b前面的条件是OA、a在b的右方B、a在b的左方C、a是b的祖先D、a是b的子孙8、设深度为k的二叉树上只有度为0和度为2的结点，则这类二叉树上所含的结点总数为OA、k+1B、2kC、2k-1.D、2k+1.9、设有13个值，用它们组成一棵哈夫曼树，则该哈夫曼树共有个结点。A、13B、12C、26D、2510、下面几个符号串编码集合中，不是前缀编码的是oA、0,10,110,1111B、11,10,001,101,0001C、00,O1.O,0110,1000D、b,c,aa,ac,aba,abb,abc)11、欲实现任意二叉树的后序遍历的非递归算法而不使用栈结构，最佳的方案是二叉树采用存储结构。A、三叉链表B、广义表C、二叉链表D、顺序表12、以下说法错误的是oA、存在这样的二叉树，对它采用任何次序遍历其结点访问序列均相同B、二叉树是树的特殊情形C、由树转换成二叉树，其根结点的右子树总是空的D、在二叉树只有一棵子树的情况下也要明确指出该子树是左子树还是右子树13、树的基本遍历策略可分为先根遍历和后根遍历，二叉树的基本遍历策略可分为先序、中序和后序三种遍历。我们把由树转化得到的二叉树称该树对应的二叉树，则下面是正确的。A、树的先根遍历序列与其对应的二叉树先序遍历序列相同B、树的后根遍历序列与其对应的二叉树后序遍历序列相同C、树的先根遍历序列与其对应的二叉树中序遍历序列相同D、以上都不对14、若以二叉树的任一结点出发到根的路径上所经过的结点序列按其关键字有序。则该二叉树是OA、二叉排序树B、哈夫曼树C、堆15、下列有关二叉树的说法正确的是。A、二叉树的度为2B、一棵二叉树度可以小于2C、二叉树中至少有一个结点的度为2D、二叉树中任一个结点的度都为216、某二叉树中序序列为ABCDEFG,后序序列为BDCAFGE,则前序序列是A、EGFACDBC、EAGCFBDB、EACBDGF17、对二叉排序树进行遍历，可以得到该二叉树所有结点构成的排序序列。A、前序B、中序C、后序D、按D、上面的都不对层次18、由二叉树的前序和后序遍历序列唯一地确定这棵二叉树。A、能B、不能19、在一棵度为3的树中，度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为O的结点数为个。D、720、在一棵深度为h的完全二叉树中，所含结点的个数不小于A、2hB、 2h+1.C、 2h-1.D、2h-1.21、在一棵具有n个结点的二叉树第i层上，最多具有个结点。A、2iB、2i+1C、2i1.D、2n22、在下列情况中，可称为二叉树的是A、每个结点至多有两棵子树的树B、哈夫曼树C、每个结点至多有两棵子树的有序树D、每个结点只有一棵右子树E、以上答案都不对二、填空题1、8层完全二叉树至少有128个结点，拥有100个结点的完全二叉树的最大层数为7o2、树在计算机内的表示方式有双亲表示法、孩子表示法、孩子兄弟表示法。3、一棵有n个结点的满二叉树有0个度为1的结点，有1.112->个分支（非终端）结点和1.112-+1个叶子，该满二叉树的深度为1.IOg2n+1O4、若一个二叉树的叶子结点是某子树的中序遍历序列中的最后一个结点，则它必是孩子树的前序遍历序列中的最后一个结点。5、一棵共有n个结点的树，其中所有分支结点的度均为k,则该树中的叶子结点个数为（n×（k-1.）+1）/ko6、深度为k（设根的层数为1）的完全二叉树至少有2k-1.个结点，至多有2k-1.个结点。7、设只包含根结点的二叉树高度为0,则高度为k的二叉树最大结点数为2k+1-1.,最小结点数为k+1o8、一棵完全二叉树有999个结点，它的深度为10o9、对于一棵具有n个结点的树，该树中所有结点的度数之和为n-1o10、有n个结点并且其高度为n的二叉树有2n-1.个。口、一棵具有n个结点的二叉树，若它有n个叶子结点，则该二叉树上度为1的结点n1.=n-2n+1.。12、若一棵二叉树的叶子数为n,则该二叉树中左、右子树皆非空的结点个数为n-1.013、设n为哈夫曼树的叶子结点数目，则该哈夫曼树共有2n0-1.个结点。14、若以4、5、6、7、8作为叶子结点的权值构造哈夫曼树，则其带权路径长度是69。三、判断题1、完全二叉树的某结点若无左孩子，则它必是叶结点。（对）2、存在这样的二叉树，对它采用任何次序的遍历，结果相同。（对）3、二叉树就是结点度为2的树。（错）4、二叉树中不存在度大于2的结点，当某个结点只有一棵子树时无所谓左、右子树。（错）5、已知二叉树的前序遍历序列和后序遍历序列并不能唯一地确定这棵树，因为不知道树的根结点是哪一个。（错）6、在哈夫曼编码中，当两个字符出现的频率相同时，其编码也相同，对于这种情况应作特殊处理。（错）7、中序遍历一棵二叉排序树的结点就可得到排好序的结点序列。（对）8、将一棵树转换成二叉树后，根结点没有左子树。（错）9、用树的前序遍历和中序遍历可以导出树的后序遍历。（对）10、哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。（对）11、不使用递归也能实现二叉树前序、中序和后序遍历。（对）习题五树与二叉树21.填空题树是n（n0）结点的有限集合，在一棵非空树中，有（）个根结点，其余的结点分成In（m>0）个（）的集合，每个集合都是根结点的子树。【解答】有且仅有一个，互不相交树中某结点的子树的个数称为该结点的（），子树的根结点称为该结点的（），该结点称为其子树根结点的（）o【解答】度，孩子，双亲一棵二叉树的第i(i21.)层最多有()个结点；一棵有n(n>0)个结点的满二叉树共有()个叶子结点和()个非终端结点。【解答】2i-1.,(n+1.)2,(n-1.)2【分析】设满二叉树中叶子结点的个数为n,度为2的结点个数为n2,由于满二叉树中不存在度为1的结点，所以n=n+n2;由二叉树的性质n=n2+1.,得n=(n+1.)2,n2=(n-1.)2o(4)设高度为h的二叉树上只有度为0和度为2的结点，该二叉树的结点数可能达到的最大值是(),最小值是()o【解答】2h-1,2h-1.【分析】最小结点个数的情况是第1层有1个结点，其他层上都只有2个结点。深度为k的二叉树中，所含叶子的个数最多为()o【解答】2k-1.【分析】在满二叉树中叶子结点的个数达到最多。(6)具有100个结点的完全二叉树的叶子结点数为()o【解答】50【分析】100个结点的完全二叉树中最后一个结点的编号为100,其双亲即最后一个分支结点的编号为50,也就是说，从编号51开始均为叶子。(7)已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点。则该树中有()个叶子结点。【解答】12【分析】根据二叉树性质3的证明过程，有n=n2+2n3+1.(n0、n2、n3分别为叶子结点、度为2的结点和度为3的结点的个数)。(8)某二叉树的前序遍历序列是ABCDEFG,中序遍历序列是CBDAFGE,则其后序遍历序列是（）。【解答】CDBGFEA【分析】根据前序遍历序列和后序遍历序列将该二叉树构造出来。（9）在具有n个结点的二叉链表中，共有（）个指针域，其中（）个指针域用于指向其左右孩子，剩下的（）个指针域则是空的。【解答】2n,n-1.,n+1在有n个叶子的哈夫曼树中，叶子结点总数为（），分支结点总数为（）o【解答】n,n-1【分析】n-1个分支结点是经过n-1.次合并后得到的。已知二叉树的中序和后序序列分别为Cbedafigh和Cedbifhga,试构造该二叉树。对给定的一组权值W=（5,2,9,11,8,3,7）,试构造相应的哈夫曼树，并计算它的带权路径长度。【解答】构造的哈夫曼树如图5-13所示。图5-13构造的哈夫曼树及带权路径长度树的带权路径长度为：WP1.=2X4+3×4+5X3+7×3+8X3+9×2+1.1.×2=120二叉树先根序、后根序、中根序遍历的速算法（解题技巧）经过研究我找出了一种不用画图，由先（后）根序遍历和中根序遍历迅速确定遍历结果的办法。谨以此文献给智商与我同级而又不得不研究算法的朋友。抽象思维太差，用例子来说明吧。下面这个是后根遍历的算法。例1：已知某二叉树的先根序遍历为ABCDEFG,中根序遍历为CDBAFEG,则它的后根序遍历为解法如下：1、确定树根。由先序遍历知道，树根为A。2、分离左、右子树。由中根序遍历知，A左面的为CDB左子树结点，右面的FEG为右子树结点。把先根序遍历也分成左、右子树结点，BCD、EFGo前根序遍历BCDEFG中根序遍历CDBFEG3、分别把先根序遍历左、右子树结点抄过来，写的时候要从右往左写，本例中，依次写下B、C、D、，E、F、G,结果是DCBGFEo当然不是简单到这种程序。上面只是个原理。抄的过程应该是这样的：盯着前根序的，瞅着中根序的。如果要抄的先根序中的结点在中根序中是最左/右边，则直接抄过来；如果不是，则把这个结点左边的结点先放记在右根序的最左边，然后继续抄。本题的结果是DCB,FGE,A,即DCBFGEA。上面这个例子太短，看不出“猫腻”来。再举个结点多一点儿的。例2：已知某二叉树的先根序遍历为ABCDEFGHIJK,中根序遍历为CEDFBAHKJIG,则它的后根序遍历为按上面的方法：前根序遍历BCDEFGHIJK中根序遍历CEDFBHKJIG依次抄得前根序的结点：F、E（E在中根序遍历中不靠边，所以先放在后根遍序历中左子树结点最左边）、D、C同理，把右子树也抄过来。因此，写下结点的过程依次是：如果还是不太懂，你可以试着做一下下面的例子：已知二叉树前序遍历Abcdefghijk,中序遍历Cedfbahgkj1.求后序遍历。解：（1）以根结点A分左、右子树结点，BCDEFGHIJKCEDFBHGKJI（2）写左子树，盯着前序，从右到左开始写DCB（在中序中，B靠右边，C靠左边,D不靠边。写一个，从中序中抹一个。）因为D在中序遍历中不靠边，所以下一个结点E先搁到最左边（注意，是“搁”，也就是说,不能把E从中序抹去。EDCB因为B已经抹了，F靠右边。于是F仍然按照从右到左的规则，写在D的的左边。EFDCB最后把E加上，左子树0K。右子树仍然从右到写G因为G不靠边，所以下一个结点H先搁在最左边HG然后继续HKJIG于是，结果是Efdcbhkjiga前根序遍历类似。以上的方法只适用于三层以内的二叉树（含三层）。在选择题中，三层以上二叉树也可用以上方法初步判断正确答案。