数据结构5-6章测试题(带答案)

第1页共4页《数据结构》第2教学单元测试练习题一．选择1．将一棵有100个结点的完全二叉树从根结点这一层开始，每一层上从左到右依次对结点编号，根结点的编号为1，则编号为49的结点的左孩子编号为（）根?右孩子?A.98B.99C.50D.482．以下说法错误的是()A.一般在赫夫曼树中，权值越大的叶子离根结点越近B.赫夫曼树中没有度数为1的分支结点C.若初始森林中共有n棵二叉树，最终求得的赫夫曼树共有2n-1个结点D.若初始森林中共有n棵二叉树，进行2n-1次合并后才能剩下一棵最终的赫夫曼树3．深度为6的二叉树最多有()个结点A．64B.63C.32D.314．以下说法正确的是()A.任何一棵二叉树中至少有一个结点的度为2B.任何一棵二叉树中每个结点的度都为2C.任何一棵二叉树的度肯定等于2D.任何一棵二叉树的度可以小于25．设森林T中有4棵树，第一、二、三、四棵树的结点个数分别是n1,n2,n3,n4,那么当把森林T转换成一棵二叉树后，且根结点的右子树上有(d)个结点。根结点的左孩子上有(a)个结点。A.n1-1B.n1C.n1+n2+n3D.n2+n3+n46.对含有()个结点的非空二叉树，采用任何一种遍历方式，其结点访问序列均相同。A.0B.1C.2D.不存在这样的二叉树7．讨论树、森林和二叉树的关系，目的是为了()A.借助二叉树上的运算方法去实现对树的一些运算B.将树、森林按二叉树的存储方式进行存储C.将树、森林转换成二叉树D.体现一种技巧，没有什么实际意义8.已知某二叉树的后续遍历序列是dabec,中序遍历序列是deabc,它的前序遍历序列是()A.acbedB.deabcC.decabD.cedba9.如果T2是由有序树T转化而来的二叉树，那么T中结点的前序就是T2中结点的(a),后序就是T2中结点的(b)A.前序B.中序C.后序D.层次序10．深度为5的二叉树至多有()个结点。A.16B.32C.31D.1011．以下说法错误的是()A.存在这样的二叉树，对它采用任何次序的遍历，其结点访问序列均相同B.二叉树是树的特殊情形C.由树转换成二叉树，根结点右子树总是空的D.在二叉树只有一棵子树的情况下也要明确指出该子树是左子树还是右子树12．下列序列中，符合堆定义的是（）A.(100,80,55,60,50,40,58,35,20)B.(100,80,55,60,50,40,35,58,20)C.(100,80,55,58,50,40,60,35,20)D.(100,70,55,60,50,40,58,35,20)13．算术表达式a+b*（c+d/e）转为后缀表达式后为()A.ab+cde/*B.abcde/+*+C.abcde/*++D.abcde*/++14．设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1则T中的叶子数为()A.5B.6C.7D.8解析：总分支=1*4+2*2+3*1+4*1=15，则总结点=15+1=16不为零的结点个数=4+2+1+1=8为零的结点=总的-不为零的=16-8=815．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是()A.9B.11C.15D.不确定16．设有13个值,用它们组成一棵哈夫曼树,则该哈夫曼树共有()个结点.A.13B.12C.26D.2517．设给定权值总数有n个,其哈夫曼树的结点总数为()A.不确定B.2nC.2n+1D.2n-118．二叉树的第I层上最多含有结点数为()A.2IB.2I-1-1C.2I-1D.2I-119．一个具有1025个结点的二叉树的高h为()A.11B．10C.11至1025之间D.10至1024之间20．一棵二叉树高度为h,所有结点的度或为0，或为2，则这棵二叉树最少有()结点A.2hB.2h-1C.2h+1D.h+121．对于有n个结点的二叉树,其高度为()A.nlog2nB.log2nC.log2n|+1D.不确定22．在一棵高度为k的满二叉树中，结点总数为()A.2k-1B.2kC.2k-1D.log2k+123．高度为K的二叉树最大的结点数为()A.2kB.2k-1C.2k-1D.2k-1-124．一棵树高为K的完全二叉树至少有()个结点A.2k–1B.2k-1–1C.2k-1D.2k25．利用二叉链表存储树，则根结点的右指针是()A.指向最左孩子B.指向最右孩子C.空D.非空26．二叉树先序遍历：EFHIGJK；中序遍历:HFIEJKG。该二叉树根的右子树的根是()A.EB.FC.GD.H27．一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足()A.所有的结点均无左孩子B.所有的结点均无右孩子C.只有一个叶子结点D.是任意一棵二叉树前序序列是“根左右”，后序序列是“左右根”，若要这两个序列相反，只有单支树，所以本题的A和B均对，单支树的特点是只有一个叶子结点，故C是最合适的，选C。A或B都不全。由本题可解答44题。28．n个结点的线索二叉树上含有的线索数为()A.2nB.n－lC.n＋lD.n线索二叉树是利用二叉树的空链域加上线索，n个结点的二叉树有n+1个空链域。29．由3个结点可以构造出(a)棵不同的树,(d)棵不同的二叉树A.2B.3C.4D.530.分别以下列序列构造二叉查找树，与用其它三个序列所构造的结果不同的是()A．（100，80，90，60，120，110，130）B.（100，120，110，130，80，60，90）第2页共4页C.（100，60，80，90，120，110，130）D.(100，80，60，90，120，130，110)二．填空1．二叉树由_(1)根结点__，__(2)左子树_，_(3)右子树__三个基本单元组成。2．在二叉树中，指针p所指结点为叶子结点的条件是_p-lchild==null&&p-rchlid==null_____。3．在一棵二叉树中，度为零的结点的个数为N0,度为2的结点的个数为N2,则有N0=__N2+1____4．高度为8的完全二叉树至少有___64___个叶子结点。5．已知二叉树有50个叶子结点，则该二叉树的总结点数至少是_99_____。6．一个有2001个结点的完全二叉树的高度为_11__。7．如某二叉树有20个叶子结点，有30个结点仅有一个孩子，则该二叉树的总结点数为___69___。8．如果结点A有3个兄弟，而且B是A的双亲，则B的度是_4_____。9．完全二叉树中，结点个数为n，则编号最大的分支结点的编号为__n/2____。10．8层完全二叉树至少有_128(第七层满，加第八层１个)_____个结点，拥有100个结点的完全二叉树的最大层数为__7__。11．一棵树T中，包括一个度为1的结点，两个度为2的结点，三个度为3的结点，四个度为4的结点和若干叶子结点，则T的叶结点数为__21____。12．n（n1）个结点的各棵树中，其深度最小的那棵树的深度是_(1)2__。它共有_(2)n-1__个叶子结点和_(3)1__个非叶子结点，其中深度最大的那棵树的深度是_(4)n__，它共有_(5)_1_个叶子结点和_(6)n-1__个非叶子结点。(思考：二叉树呢？)13．每一棵树都能唯一的转换为它所对应的二叉树。若已知一棵二叉树的前序序列是BEFCGDH，中序序列是FEBGCHD，则它的后序序列是_(1)FEGHDCB__。设上述二叉树是由某棵树（或森林）转换而成，则第一棵树的先根次序序列是_(2)_BEF14．二叉树结点的中序序列为ABCDEFG,后序序列为BDCAFGE,则该二叉树结点的前序序列为_(1)EACBDGF__,则该二叉树对应的树林包括_(2)2__棵树。15．二叉树的先序序列和中序序列相同的条件是_任何结点至多只有右子女的二叉树_____。16．具有n个结点的满二叉树，其叶结点的个数是__(n+1)/2____。17．若以{4，5，6，7，8}作为叶子结点的权值构造哈夫曼树，则其带权路径长度是__69____。18．有一份电文中共使用6个字符:a,b,c,d,e,f,它们的出现频率依次为2,3,4,7,8,9，试构造一棵哈夫曼树，则其加权路径长度WPL为_(1)80__，字符c的编码是_(2)001（不唯一）__。19．线索二叉树的左线索指向其(1)前驱,右线索指向其(2)后继.20．设n0为哈夫曼树的叶子结点数目，则该哈夫曼树共有2n0-1个结点。21.由2012个结点构造完全二叉树，所得叶子有1006个，2013个结点构造完全二叉树，所得叶子有1007个三．判断1．若一棵二叉树的任一非叶子结点的度为2，则该二叉树为满二叉树(X)2．如果二叉树中某结点的度为1，则说该结点只有一棵子树(√)3．已知一棵树的先序序列和后序序列，一定能构造出该树(√)二叉树的先序和后序不可4．设与一棵树T所对应的二叉树为BT，则与T中的叶子结点所对应的BT中的结点也一定是叶子结点(X)5．若某二叉树的叶子结点数为1，则其先序序列和后序序列一定相反(√)6．二叉树的前序遍历序列中，任意一个结点均处在其孩子结点的前面，这种说法(√)7．由于二叉树中每个结点的度最大为2，所以二叉树是一种特殊的树，这种说法(X)8．在叶子数目和权值相同的所有二叉树中，最优二叉树一定是完全二叉树，该说法（X）。9．二叉树是度为2的有序树。×10．完全二叉树一定存在度为1的结点。×11．对于有N个结点的二叉树，其高度为log2n。×12．深度为K的二叉树中结点总数≤2k-1。√13．二叉树的遍历结果不是唯一的.√只有在确定何序（前序、中序、后序或层次）遍历后，遍历结果才唯一。14．二叉树的遍历只是为了在应用中找到一种线性次序。√15．完全二叉树中，若一个结点没有左孩子，则它必是树叶。√16．树形结构中元素之间存在一个对多个的关系。√17．完全二叉树的存储结构通常采用顺序存储结构。√18．将一棵树转成二叉树，根结点没有左子树；×右孩子19．在二叉树中插入结点，则它不再是二叉树了。×20．树与二叉树是两种不同的树型结构。√四．解答应用题1.一棵二叉树中的结点的度或为0或为2，则二叉树的枝数为2(n0-1)，其中n0是度为0的结点的个数。证明：设二叉树度为0和2的结点数及总的结点数分别为n0，n2和n，则n=n0+n2…(1)再设二叉树的分支数为B,除根结点外，每个结点都有一个分支所指，第3页共4页则n=B+1………(2)度为零的结点是叶子，没有分支，而度为2的结点有两个分支，因此（2）式可写为n=2*n2+1……………(3)由（1）、（3）得n2=n0-1,代入（1），并由（1）和（2）得B=2*(n0-1)。证毕。2．任意一个有n个结点的二叉树，已知它有m个叶子结点，试证明非叶子结点有（m-1）个度为2，其余度为1。证明：设度为1和2的结点数是n1和n2，则二叉树结点数n为n=m+n1+n2…………(1)由于二叉树根结点没有分枝所指，度为1和2的结点各有1个和2个分枝，度为0的结点没有分枝，故二叉树的结点数n与分枝数B有如下关系n=B+1=n1+2*n2+1……………………….(2)由（1）和（2），得n2=m-1。即n个结点的二叉树，若叶子结点数是m，则非叶子结点中有（m-1）个度为2，其余度为1。3．画出同时满足下列两条件的两棵不同的二叉树。(1)按先根序遍历二叉树顺序为ABCDE。(2)高度为5其对应的树（森林）的高度最大为4。4．已知二叉树的先序、中序和后序遍历序列分别如下(但其中一些模糊不清)先序：ABC__EF____中序：BDE__AG__H后序：_DC__GH____y6fvq1`要求：（1）补充模糊的地方，并重新写出先序、中序和后序遍历序列（2）画出该二叉树（3）画出该二叉树的中序线索树（4）画出该二叉树对应的森林（5）画出森林中第一棵树的孩子兄弟表示法答案：（1）先序：ABCDEFGH;中序BDECAGFH;EDCBGHFA（2）二叉树:（4）森林：BDCEAABCDEA