数据结构-树-考试习题

第五章树11．不含任何结点的空树()A）是一棵树B）是一棵二叉树Ｃ）既不是树也不是二叉树D）是一棵树也是一棵二叉树12．二叉树是非线性数据结构，所以()A）它不能用顺序存储结构存储;B）它不能用链式存储结构存储;C）顺序存储结构和链式存储结构都能存储;D）顺序存储结构和链式存储结构都不能使用13．把一棵树转换为二叉树后，这棵二叉树的形态是()A）唯一的B）有多种C）有多种，但根结点都没有左孩子D）有多种，但根结点都没有右孩子9.11，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（）A)24B)72C)48D)5310.一棵含18个结点的二叉树的高度至少为()A)3B)4C)6D)511.下面的二叉树中，(C)不是完全二叉树。10.设结点x和结点y是二叉树T中的任意两个结点，若在前序序列中x在y之前，而在中序序列中x在y之后，则x和y的关系是（）A）x是y的左兄弟B）x是y的右兄弟C）y是x的祖先D）y是x的孩子11.设二叉树根结点的层次为1，所有含有15个结点的二叉树中，最小高度是（）A）6B）5C）4D）37．下列陈述中正确的是（）A）二叉树是度为2的有序树B）二叉树中结点只有一个孩子时无左右之分C）二叉树中必有度为2的结点D）二叉树中最多只有两棵子树，并且有左右之分8.树最适合用来表示（）A）有序数据元素B）无序数据元素C）元素之间具有分支层次关系的数据D）元素之间无联系的元素9.3个结点有（）不同形态的二叉树A）2B）3C）4D）56．二叉树是非线性数据结构，()A）它不能用顺序存储结构存储;B）它不能用链式存储结构存储;C）顺序存储结构和链式存储结构都能存储;D）顺序存储结构和链式存储结构都不能使用7．二叉树上叶结点数等于()A)分支结点数加1B)单分支结点数加1C)双分支结点数加1D)双分支结点数减18．如将一棵有n个结点的完全二叉树按顺序存放方式，存放在下标编号为0,1,…,n-1的一维数组中，设某结点下标为k(k0)，则其双亲结点的下标是()A)(k-1)/2B)(k+1)/2C)k/2D)k-18.树最适合用来表示（）。A．有序数据元素B．无序数据元素C.元素之间具有分支层次关系的数据D．元素之间无联系的元素10.有64个结点的完全二叉树的深度为()(根的层次为第1层)。A.8B.7C.6D.511.在一棵度为3的树中，度为3的结点有2个，度为2的结点有1个，度为1的结点有２个，那么，该树有（）个叶子结点。A.4B.5C.6D.79.一个二叉树按顺序方式存储在一个维数组中，如图01234567891011121314ABCDEFGHIJ则结点E在二叉树的第（）层。(假设树根所在层为第1层)A、2B、3C、4D、510.由权值分别为11，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（）A24B71C48D538.二叉树上叶结点数等于（）。A．分支结点数加1B．单分支结点数加1C．双分支结点数加1D．双分支结点数减18.某二叉树的先序序列和后序序列正好相同，则该二叉树一定是()的二叉树。A.空或只有一个结点B.高度等于其结点数C.任一结点无左孩子D.任一结点无右孩子9.在有n个结点的二叉链表中，值为空的链域的个数为()A.n-1B.2n-1C.n+1D.2n+110.一棵含18个结点的二叉树的高度至少为()A.8B.7C.6D.511.深度优先遍历类似于二叉树的()A.先序遍历B.中序遍历C.后序遍历D.层次遍历9.一棵124个叶结点的完全二叉树，最多应有()个结点。A.245B.246C.247D.24810.后缀表达式“56*32+-”的值为（）。A.15B.25C.30D.3511.由权值分别为11，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（）A.24B.71C.48D.537.对一个满二叉树，m个树叶,n个结点,深度为为h,则（）。A.n=2h-1B.h+m=2nC.m=h-1D.n=h+m8.在一棵二叉树的二叉链表中，空指针域数等于非空指针域数加()。A.2B.1C.0D.-19.若完全二叉树的结点总个数为100（结点编号从1开始编号，按层序编号），则第58个结点的度为（）A.2B.1C.0D.不确定10.已知完全二叉树的第9层有240个结点，则该完全二叉树的结点数是（）A.494B.495C.496D.497二、填空题1.一棵深度为5的二叉树，至多有_____________个结点。316.图的存储结构有__________________和__________________，遍历图有______________、_____________等方法。邻接矩阵邻接表深度优先广度优先7.深度为ｋ的完全二叉树最多有个结点。12k8.若按层序对深度为ｋ的完全二叉树中全部结点从１开始编号，则叶子结点可能的最小编号为。122k6.设有树如图所示，则结点ｃ的度为___________，层次为___________，树的度为___________，树的高度为___________。结点ｃ的度为２，层次为２，树的度为３，高度为４7.深度为ｋ的完全二叉树至少有___________个结点，最多有___________个结点。12k，12k7.对于一棵具有n个结点的二叉树，当进行链接存储时，其二叉链表中的指针域的总数为_______个，其中_______个用于链接孩子结点，_______个空闲着。2n，n-1，n+12.后缀表达式“210+5*6–9/”的值为。63.由n个权值构成的哈夫曼树共有个结点。2n-16.在一棵树中，____结点没有后继结点。叶4．后缀表达式“210+5*6–9/”的计算结果为。64.一棵深度为7的二叉树，最多有个结点。1275.若一棵树的括号表示为A(B,C(E,F(G)),D),该树的叶子结点个数为________，该树的度为_____________，该树的深度为_____________。4、3、46.在有n个叶子结点的哈夫曼树中，总结点数是_______。2n-11.深度为4的完全二叉树最少有______个结点，最多有_______个结点。8156.假定一棵树的广义表表示为A(B(C(D,E),F,G(H,I,J)),K)，则度为3、2、1、0的结点数分别为______、______、______和______个。22076.若结点A有其他三个兄弟,B是A的双亲结点,B的度是_______________。47.一棵二叉树有67个结点，这些结点的度要么是0，要么是2。这棵二叉树中度为2的结点有_____________个。338.一棵深度为7的二叉树，最多有个结点。127三、应用题1、名词解释：树，子树，结点的度，叶子结点，孩子，双亲，兄弟，深度，有序树，森林，二叉树，遍历二叉树，树的带权路径长度，哈夫曼树。2、描述二叉树的性质。3、从概念上讲，树、森林和二叉树是三种不同的数据结构，将树、森林转换为二叉树的基本目的是什么？指出树和二叉树的主要区别。4、已知一棵树边的结点为{I,M,I,N,E,I,B,E,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）树的深度是多少？5、试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。6、已知一棵度为k的树中有n1个度为1的结点，n2个度为2的结点，……，nk个度为k的结点，问该树中有多少个叶子结点？7、已知在一棵含有n个结点的树中，只有度为k的分支结点和度为0的叶子结点。试求该树含有的叶子结点的数目。8、有n个结点的二叉树，已知叶子结点个数为n0，写出求度为1的结点的个数n1的计算公式；若此树是深度为k的完全二叉树，写出n为最小的公式；若二叉树中仅有度为0和度为2的结点，写出求该二叉树结点个数n的公式。9、假设n和m为二叉树中两结点，用“1”，“0”或“”（分别表示肯定、恰恰相反或者不一定）填写下表：前序遍历时n在m前?中序遍历时n在m前?后序遍历时n在m前?n在m左方n在m右方n是m祖先n是m子孙注：如果（1）离a和b最近的共同祖先p存在，且（2）a在p的左子树中，b在p的右子树中，则称a在b的左方（即b在a的右方）。10、找出所有满足下列条件的二叉树：（a）它们在先序遍历和中序遍历时，得到的结点访问序列相同；（b）它们在后序遍历和中序遍历时，得到的结点访问序列相同；（c）它们在先序遍历和后序遍历时，得到的结点访问序列相同；11、分别画出和下列树对应的各个二叉树：12、画出和下列二叉树相应的森林：13、画出和下列已知序列对应的树T：树的先根次序访问序列为GFKDAIEBCHJ；树的后根次序访问序列为CBEFDGAJIKLH。14、假设一棵二叉树的中序序列为DCBGEAHFIJK和后序序列为DCEGBFHKJIA。请画出该树。15、假设一棵二叉树的层序序列为ABCDEFGHIJ和中序序列为DBGEHJACIF。请画出该树。16、编写递归算法，在二叉树中求位于先序序列中第k个位置的结点的值。17、编写递归算法，计算二叉树中叶子结点的数目。5.用于通信的电文仅由a、b、c、d、e、f、g、h等8个字母组成，字母在电文中出现的频率分别为：007、0.19、0.02、0.06、0.32、0.03、0.21、0.10。试构造相应的哈夫曼树并为这些字母设计哈夫曼编码。（9分）得到的编码如下：a:0010b:10c:00000d:0001e:01f:00001g:11h:0011此题答案不唯一。5.设先序遍历某个树的结点次序为ABDEHCFGI，中序遍历该树的结点次序为DBEHAFCIG,要求画出这个二叉树，并写出此二叉树的后序遍历。（10分）后序：DHFBFIGCA6.给定一组权值（5，9，11，2，7，16），试设计相应的哈夫曼树，并计算带权路径长度.（9分）答案：带权路径长度=（9+11+16）*2+7*3+（2+5）*4=121509203011161477251.已知一组关键字为{25,18,46,2,53,39,32,4,74,67,60,11}。按表中的元素顺序依次插入到一棵初始为空的二叉排序树中,画出该二叉排序树,并求在等概率的情况下查找成功的平均查找长度。（10分）答案：1．设先序遍历某个树的结点次序为ABDEHCFGI，中序遍历该树的结点次序为DBEHAFCIG,要求画出这个二叉树,并写出该树的后序遍历的结点次序。(6分)1..后序:DHEBFIGCA1．已知一棵树二叉如下，请写出按前序、中序、后序和层次遍历时得到的结点序列。（8分）ABCDEFABCDEFGHI5.312615243332211ASL2518463953241132746760GH前序：中序：后序：层次：各遍历次序如下前序：Ａ，Ｂ，Ｄ，Ｇ，Ｃ，Ｅ，Ｆ，Ｈ中序：Ｄ，Ｇ，Ｂ，Ａ，Ｅ，Ｃ，Ｈ，Ｆ后序：Ｇ，Ｄ，Ｂ，Ｅ，Ｈ，Ｆ，Ｃ，Ａ层次：Ａ，Ｂ，Ｃ，Ｄ，Ｅ，Ｆ，Ｇ，Ｈ4.已知一棵完全二叉树共有999个结点，试求：(写出详细的分析过程)（9分）1、树的高度（深度）2、叶子结点的数目3、度为1的结点数目深度：10叶子节点数目：500度为1的节点数目：01.试写出如图所示的二叉树分别按先序、中序、后序遍历时得到的结点序列。答：DLR：ABDFJGKCEHILMLDR:BFJDGKACHELIMLRD：JFKGDBHLMIECA.请将下图所示的森林森林转换为所对应的二叉树。ABDEFCGHJIKNOMLBGDCHKEIFJLMNOA图5-164．将关键码53，78，65，17，87，09，81，45，23依次插入到一棵初始为空的二叉搜索树中，