ch6习题及答案

1习题6解答判断题：1.二叉树中每个结点有两个子女结点，而对一般的树则无此限制，因此二叉树是树的特殊情形。(╳)2.二叉树就是结点度为2的树。(╳)((哈工大2000年研究生试题)3.二叉树中不存在度大于2的结点，当某个结点只有一棵子树时无所谓左、右子树之分。(╳)(陕西省1998年自考试题)4.当k≥1时，高度为k的二叉树至多有21k个结点。(╳)5.完全二叉树的某结点若无左孩子，则它必是叶结点。(√)(中科院软件所1997年研究生试题)6.用一维数组存放二叉树时，总是以前序遍历顺序存储结点。(╳)7.若有一个结点是某二叉树子树的中序遍历序列中的最后一个结点，则它必是该子树的前序遍历序列中的最后一个结点。(╳)8.存在这样的二叉树，对它采用任何次序的遍历，结果相同。(√)(哈工大2000年研究生试题)9.中序线索二叉树的优点之一是便于在中序下查找前驱结点和后继结点。(√)10.将一棵树转换成二叉树后，根结点没有左子树，(╳)(北邮1999年研究生试题。)11.由树转换成二叉树，其根结点的右子树总是空的。(√)12.前序遍历森林和前序遍历与该森林对应的二叉树其结果不同。(╳)13.在叶子数目和权值相同的所有二叉树中，最优二叉树一定是完全二叉树。(╳)14.在哈夫曼编码中，当两个字符出现的频率相同时，其编码也相同，对于这种情况应作特殊处理。(╳)15.霍夫曼树一定是满二叉树。(╳)16.树的度是树内各结点的度之和。(╳)17.由二叉树的结点构成的集合可以是空集合。(√)18.一棵树中的叶子结点数一定等于与其对应的二叉树中的叶子结点数。(╳)选择题：19.树最适合用来表示(C)。A．有序数据元素B.无序数据元素C．元素之间具有分支层次关系的数据D.元素之间无联系的数据20.如果结点A有3个兄弟，而且B是A的双亲，则B的度是(D)。A.4B.5C.1D.321.下列有关二叉树的说法正确的是(B)。(南京理工大学2000年研究生试题。)A．二叉树的度为2B.一棵二叉树度可以小于2C．二叉树中至少有一个结点的度为2D.二叉树中任一个结点的度都为222.以下说法错误的是(B)。A．二叉树可以是空集B.二叉树的任一结点都可以有两棵子树C．二叉树与树具有相同的树形结构D.二叉树中任一结点的两棵子树有次序之分223.假定在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为(B)个。A．15B.16C.17D.4724.用顺序存储的方法将完全二叉树中的所有结点逐层存放在数组R[1..n]中，结点R[i]若有左子女，则左子女是结点(B)。A．R[2i+1]B.R[2i]C.R[i/2]D.R[2i-1](参见严蔚敏《(c语言版)数据结构》P.124~125,二叉树的性质,性质5)25.设a、b为一棵二叉树上的两个结点。在中序遍历时，a在b前面的条件是(B)。A．a在b的右方B.a在b的左方C.a是b的祖先D.a是b的子孙26.以下说法正确的是(C)。A．若一个树叶是某二叉树前序遍历序列中的最后一个结点，则它必是该子树后序遍历序列中的最后一个结点。B．若一个树叶是某二叉树前序遍历序列中的最后一个结点，则它必是该子树中序遍历序列中的最后一个结点。C．在二叉树中，具有两个子女的父结点，在中序遍历序列中，它的后继结点最多只能有一个子女结点。(提示：后继结点应为遍历右子树时访问的第一个结点，该后继结点或为叶子结点，则其无子女；或为仅有右子树，则其也是最多只能有一个子女；若有两个子女，则它本身已不是后继。)D．在二叉树中，具有一个子女的父结点，在中序遍历序列中，它没有后继子女结点。27.以下说法错误的是(B)。A．存在这样的二叉树，对它采用任何次序遍历其结点访问序列均相同。B.二叉树是树的特殊情形。C.由树转换成二叉树，其根结点的右子树总是空的。D.在二叉树只有一棵子树的情况与也要明确指出该子树是左子树还是右子树。28.将下图的二叉树按中序线索化，结点X的右指针和Y的左指针分别指向(C)。A．A，DB.B，CC.D，AD.C，A29.在N个结点的线索二叉树中，线索的数目为(C)。A．N-1B.NC.N+1D.2N(参见严蔚敏《(c语言版)数据结构》P.126&P.132)30.设有13个值，用它们组成一棵赫夫曼树，则该赫夫曼树共有(D)个结点。(全国2001年自考题)A．13B.12C.26D.25(参见严蔚敏《(c语言版)数据结构》P.147)31.下面几个符号串编码集合中，不是前缀编码的是(B)。ABDCXEY3A．{0，10，110，1111}B.{11，10，001，101，0001}C．{00，010，0110，1000}D.{b，c，aa，ac，aba，abb，abc}32.由带权为9,2,5,7的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为(D)。A.23B.37C.46D.4433.树的基本遍历策略可分为先根遍历和后根遍历，二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。这里，我们把由树转化得到的二叉树叫做这棵树对应的二叉树。结论(A)是正确的。A．树的先根遍历序列与其对应的二叉树先序遍历序列相同。B.树的后序遍历序列与其对应的二叉树后序遍历序列相同。C.树的先根遍历序列与其对应的二叉树中序遍历序列相同。D.以上都不对34.在一棵具有n个结点的二叉树第i层上，最多具有(C)个结点。A．2iB.21iC.21iD.2n(参见严蔚敏《(c语言版)数据结构》P.123)35.给定一个整数集合{3，5，6，9，12}，下列二叉树哪个是该整数集合对应的霍夫曼（Huffman）树。（C）填空题：36.具有n个结点的二叉树，采用二叉链表存储，共有n+1个空链域。(重庆大学2000年研究生试题)37.对于一棵具有n个结点的二叉树，当进行链接存储时，其二叉链表中指针域总数为2n个，其中n-1个用于链接孩子结点，n+1个空闲着。38.二叉树的线索化实质是将二叉链表中的___空指针____改为___线索___________。(陕西省1998年自考题)39.一棵共有n个结点的树，其中所有分支结点的度均为k，则该树中的叶子结点个数为n-(n-1)/k。40.在下图所示的树中，结点H的祖先为A、D、G。441.从概念上讲，树与二叉树是两种不同的数据结构，将树转化为二叉树的基本目的是借用二叉树的有关算法实现树的有关操作。42.对于一个具有n个结点的二叉树，当它为一棵完全二叉树时具有最小高度，即为1log2n，当它为一棵单支树具有最大高度，即为n。(注：树的深度有时称为高度，不同的体系所用的名词可能会有差别。)43.设只包含根结点的二叉树高度为0，则高度为k的二叉树最大结点数为2k+1-1，最小结点数为k+1。(提示：请注意，这里关于树的高度的定义与通常的高度定义有不同！)44.8层完全二叉树至少有128个结点，拥有100个结点的完全二叉树的最大层数为7。(西南交大2000年研究生试题。)45.二叉树通常有顺序存储结构和链式存储结构。46.二叉树有不同的链式存储结构，其中最常用的是二叉链表与三叉链表。47.一棵左右子树均不空的二叉树在先序线索化后，其空指针域有1个。48.线索二叉树的左线索指向其前驱，右线索指向其后继。(哈工大2000年研究生试题)49.用树的孩子兄弟表示法存储，可以将一棵树转换成二叉树。(重庆大学2000年研究生试题)50.遍历一棵二叉树包括访问根结点、遍历左子树和遍历右子树三个方面。51.已知树的广义表形式为A{B[E，F]，C，D[G（H，I）]}，则该树的度为__3____，从根开始的前序遍历所得序列为_A、B、E、F、C、D、G、H、I____.52.森林定义为m(m=0)棵互不相交的树的集合。简答题53.分别画出具有3个结点的树和具有3个结点的二叉树的所有不同形态。并判断下列论述是否正确，为什么？ABDEFGCHI5(1)二叉树是一种特殊的树；(2)度为2的树是一棵二叉树；(3)度为2的有序树是一棵二叉树。一、3个结点的树二、3个结点的二叉树(注：由此可以看出两个问题。1.二叉树与树的重要区别:(1)二叉树的一个结点至多有两个子树，树则不然。(2)二叉树的一个结点的子树有左右之分，而树则没有此要求。2.度为2的树有两个分支,没有左、右之分；一棵二叉树也可以有两个分支,但有左、右之分,且左、右不能交换。)54.对于如图所示的森林，要求：(1)将其转换为相应的二叉树；(2)写出该森林的先序遍历序列和中序遍历序列。ABCDEFGIHJKL6（1）相应二叉树（2）该森林的先序遍历序列：A、B、D、E、F、C、G、H、I、J、K、L该森林的中序遍历序列：D、E、F、B、C、A、H、I、J、G、L、K55.设有一段正文是由字符集{A,B,C,D,E,F}组成的，正文长度为100个字符，其中每个字符要正文中出现的次数分别为17,12,5,28,35,3。若采用哈夫曼编码对这段正文进行压缩存储，请完成如下的工作：(1)构造哈夫曼树(规定权值较小的结点为左子树)；(2)写出每个字符的哈夫曼编码；(3)若有某一段正文的二进制编码序列为01101010110011，请按(2)的哈夫曼编码将它翻译成所对应的正文。（1）哈夫曼树：ABGDCEFHKIJL1003763172081235283500000111117（2）每个字符哈夫曼编码：A：00，B：011，C：0101，D：10，E：11，F：0100（3）正文：BCBAE56.假定一棵二叉树广义表表示为a(b(c),d(e,f))，分别写出对它进行先序、中序、后序、按层遍历的结果。先序：abcdef中序：cbaedf后序：cbefda按层：abdcef57.设在树中，结点x是结点y的双亲时，用(x,y)来表示树变。已知一棵树边的集合为：{(i,m),(i,n),(b,e),(e,i),(b,d),(a,b),(g,j),(g,k),(c,g),(c,f),(h,l),(c,h),(a,c)}用树形表示法画出此树，并回答下列问题：（1）哪个是根结点？（2）哪些是叶结点？（3）哪个是g的双亲？（4）哪些是g的祖先？（5）哪些是g的孩子？（6）哪些是e的子孙？（7）哪些是e的兄弟？哪些是f的兄弟？（8）结点b和n的层次各是多少？（9）树的深度是多少？（10）以结点c为根的子树的深度是多少？（11）树的度数是多少？3、解：树图略（1）根结点是a（2）叶子结点是:d,m,n,f,j,k,l（3）g的双亲是：c（4）g的祖先是：a,c（5）g的孩子是：j,k（6）e的子孙是：i,m,n（7）e的兄弟是d,f的兄弟是g,h（8）b的层次是2,n的层次是5（9）树的深度是5（10）以结点c为根的子树的深度是3（11）树的度数是358.已知一棵二叉树的前序遍历的结果序列是ABECDFGHIJ,中序遍历的结果序列是EBCDAFHIGJ,试画出这棵二叉树。859.已知二叉树的二叉链表t如下图所示，写出该二叉树的后序遍历序列，并将二叉链表改为后序线索链表该二叉树的后序遍历序列:F,H,C,D,G,K,A,B,E后序线索链表:ABFECDGHIJ960.设二叉树以二叉链表形式存储，请编写一个求叶子结点总数的算法。解：可以用两种方法解决这个问题。方法一：设置一个初始值为0的变量leafNum进行计数，在对二叉树进行遍历过程中判断当前访问的结点是否为叶子结点，若为叶子结点，则leafNum加一。因此当遍历完成整个二叉树后，leafNum的值即为叶子结点的数目。算法如下：intleafNum=0;voidcountLeaf(BinTreet){if(t==Null)return;if(t-Lchild==Null&&t-Rchild==Null)leafNum++;else{countLeaf(t-Lchild);countLeaf(t-Rchild);}}方法二：根据二叉树的特点可知：当二叉树为空时，叶子结点总数为0；当二叉树只有一个结点时，叶子结点数为1；否则，叶子结点