2020/4/191数据结构复习(习题)22020/4/19第六章树和二叉树(选择题)1.已知一算术表达式的中缀形式为A+B*C-D/E,后缀形式为ABC*+DE/-,其前缀形式为()A.-A+B*C/DEB.-A+B*CD/EC.-+*ABC/DED.-+A*BC/DE2.算术表达式a+b*(c+d/e)转为后缀表达式后为()A.ab+cde/*B.abcde/+*+C.abcde/*++D.abcde*/++√√32020/4/193.设树T的度为4,其中度为1,2,3和4的结点个数分别为4,2,1,1则T中的叶子数为()A.5B.6C.7D.84.在下述结论中,正确的是()①只有一个结点的二叉树的度为0;②二叉树的度为2;③二叉树的左右子树可任意交换;④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。A.①②③B.②③④C.②④D.①④√因为每个结点都有一条枝指向它,分支数为1*4+2*2*3*1+4*1所有结点数为分支数+1,所以1*4+2*2*3*1+4*1=4+2+1+1+xx=8√42020/4/196.若一棵二叉树具有10个度为2的结点,5个度为1的结点,则度为0的结点个数是()A.9B.11C.15D.不确定7.设森林F对应的二叉树为B,它有m个结点,B的根为p,p的右子树结点个数为n,森林F中第一棵树的结点个数是()A.m-nB.m-n-1C.n+1D.条件不足,无法确定8.设森林F中有三棵树,第一,第二,第三棵树的结点个数分别为M1,M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是()。A.M1B.M1+M2C.M3D.M2+M3√√森林转换得到的二叉树中,其左子树加根为森林的第一棵树√52020/4/199.一棵完全二叉树上有1001个结点,其中叶子结点的个数是()A.250B.500C.254D.50110.设给定权值总数有n个,其哈夫曼树的结点总数为()A.不确定B.2nC.2n+1D.2n-1完全二叉树中度为1的结点最多只有1个,由二叉树的度和结点的关系n=n0+n1+n2n=n1+2n2+1得n=2n0+n1-1√哈夫曼树中没有度为1的节点,叶子节点个数为n√62020/4/1911.有关二叉树下列说法正确的是()A.二叉树的度为2B.一棵二叉树的度可以小于2C.二叉树中至少有一个结点的度为2D.二叉树中任何一个结点的度都为212.一个具有1025个结点的二叉树的高h为()A.11B.10C.11至1025之间D.10至1024之间13.一棵二叉树高度为h,所有结点的度或为0,或为2,则这棵二叉树最少有()结点A.2hB.2h-1C.2h+1D.h+1√√完全二叉树和单枝树之间√72020/4/1914.对于有n个结点的二叉树,其高度为()A.nlog2nB.log2nC.log2n|+1D.不确定15.一棵具有n个结点的完全二叉树的树高度(深度)是()A.logn+1B.logn+1C.lognD.logn-116.深度为h的满m叉树的第k层有()个结点。(1=k=h)A.mk-1B.mk-1C.mh-1D.mh-1√√完全二叉树可以确定,一般二叉树不能确定√82020/4/1917.一棵树高为K的完全二叉树至少有()个结点A.2k–1B.2k-1–1C.2k-1D.2k18.将有关二叉树的概念推广到三叉树,则一棵有244个结点的完全三叉树的高度()A.4B.5C.6D.719.利用二叉链表存储树,则根结点的右指针是()A.指向最左孩子B.指向最右孩子C.空D.非空2k-1-1+1=2k-1√h=log3n+1√√92020/4/1920.对二叉树的结点从1开始进行连续编号,要求每个结点的编号大于其左、右孩子的编号,同一结点的左右孩子中,其左孩子的编号小于其右孩子的编号,可采用()次序的遍历实现编号。A.先序B.中序C.后序D.从根开始按层次遍历21.树的后根遍历序列等同于该树对应的二叉树的().A.先序序列B.中序序列C.后序序列22.一棵二叉树的前序遍历序列为ABCDEFG,它的中序遍历序列可能是()A.CABDEFGB.ABCDEFGC.DACEFBGD.ADCFEG√√√当该二叉树所有结点的左子树为空时,先序遍历序列和中序遍历序列相同。102020/4/1923.已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结果为()。A.CBEFDAB.FEDCBAC.CBEDFAD.不定24.某二叉树中序序列为A,B,C,D,E,F,G,后序序列为B,D,C,A,F,G,E则前序序列是:A.E,G,F,A,C,D,BB.E,A,C,B,D,G,FC.E,A,G,C,F,B,DD.上面的都不对25.上题的二叉树对应的森林包括多少棵树()A.1B.2C.3D.概念上是错误的√√√左孩子,右兄弟112020/4/1926.二叉树的先序遍历和中序遍历如下:先序遍历:EFHIGJK;中序遍历:HFIEJKG。该二叉树根的右子树的根是:A、EB、FC、GD、H27.某二叉树T有n个结点,设按某种顺序对T中的每个结点进行编号,编号为1,2,…,n,且有如下性质:T中任一结点V,其编号等于左子树上的最小编号减1,而V的右子树的结点中,其最小编号等于V左子树上结点的最大编号加1。这时是按()编号的。A.中序遍历序列B.前序遍历序列C.后序遍历序列D.层次顺序√√122020/4/1928.对于前序遍历与中序遍历结果相同的二叉树为(1);对于前序遍历和后序遍历结果相同的二叉树为(2)。A.一般二叉树B.只有根结点的二叉树C.根结点无左孩子的二叉树D.根结点无右孩子的二叉树E.所有结点只有左子数的二叉树F.所有结点只有右子树的二叉树29.一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反,则该二叉树一定满足()A.所有的结点均无左孩子B.所有的结点均无右孩子C.只有一个叶子结点D.是任意一棵二叉树FB√前序序列是“根左右”,后序序列是“左右根”,若要这两个序列相反,只有单支树,所以本题的A和B均对,单支树的特点是只有一个叶子结点132020/4/1930.在二叉树结点的先序序列,中序序列和后序序列中,所有叶子结点的先后顺序()A.都不相同B.完全相同C.先序和中序相同,而与后序不同D.中序和后序相同,而与先序不同31.某二叉树的前序序列和后序序列正好相反,则该二叉树一定是()的二叉树。A.空或只有一个结点B.任一结点无左子树C.高度等于其结点数D.任一结点无右子树√√142020/4/1932.一棵左子树为空的二叉树在先序线索化后,其中空的链域的个数是:()A.不确定B.0C.1D.233.一棵左右子树均不空的二叉树在先序线索化后,其中空的链域的个数是:()。A.0B.1C.2D.不确定√左子树为空的二叉树的根结点的左线索为空(无前驱),先序序列的最后结点的右线索为空(无后继),共2个空链域√只有最后一个叶结点没有后继152020/4/1934.线索二叉树是一种()结构。A.逻辑B.逻辑和存储C.物理D.线性35.n个结点的线索二叉树上含有的线索数为()A.2nB.n-1C.n+1D.n36.设F是一个森林,B是由F变换得的二叉树。若F中有n个非终端结点,则B中右指针域为空的结点有()个。A.n-1B.nC.n+1D.n+2√√N个结点共有2n个指针域,二叉链表用了n-1个,剩下n+1个√每一个终端结点的孩子中都会贡献出一个空的右指针162020/4/1937.下述编码中哪一个不是前缀码()。A.(00,01,10,11)B.(0,1,00,11)C.(0,10,110,111)D.(1,01,000,001)38.由3个结点可以构造出多少种不同的二叉树?()A.2B.3C.4D.539.引入二叉线索树的目的是()A.加快查找结点的前驱或后继的速度B.为了能在二叉树中方便的进行插入与删除C.为了能方便的找到双亲D.使二叉树的遍历结果唯一√√√172020/4/19第六章树和二叉树(判断题)1.二叉树的遍历结果不是唯一的.2.二叉树的遍历只是为了在应用中找到一种线性次序。3.采用二叉链表作存储结构,树的前序遍历和其相应的二叉树的前序遍历的结果是一样的。4.完全二叉树中,若一个结点没有左孩子,则它必是树叶。√√√√182020/4/195.给定一棵树,可以找到唯一的一棵二叉树与之对应。6.霍夫曼树的结点个数不能是偶数。7.哈夫曼树是带权路径长度最短的树,路径上权值较大的结点离根较近。8.线索二叉树的优点是便于是在中序下查找前驱结点和后继结点。9.完全二叉树的存储结构通常采用顺序存储结构。√√√√√192020/4/19第六章树和二叉树(填空题)1.二叉树由三个基本单元组成。2.在二叉树中,指针p所指结点为叶子结点的条件是3.已知一棵度为3的树有2个度为1的结点,3个度为2的结点,4个度为3的结点,则该树有______个叶子结点。根结点,左子树,右子树p-lchild==null&&p-rchlid==null12202020/4/194.在完全二叉树中,编号为i和j的两个结点处于同一层的条件是5.在顺序存储的二叉树中,编号为i和j的两个结点处在同一层的条件是。6.一棵有n个结点的满二叉树有___个度为1的结点、有___个分支(非终端)结点和___个叶子,该满二叉树的深度为___。log2i=log2jlog2s=log2t用顺序存储二叉树时,要按完全二叉树的形式存储,非完全二叉树存储时,要加“虚结点”。设编号为i和j的结点在顺序存储中的下标为s和t,则结点i和j在同一层上的条件是log2s=log2t。0(n-1)/2(n+1)/2log2n+1212020/4/197.设有N个结点的完全二叉树顺序存放在向量A[1:N]中,其下标值最大的分支结点为______。8.高度为K的完全二叉树至少有_____个叶子结点。9.已知二叉树有50个叶子结点,则该二叉树的总结点数至少是______。10.一个有2001个结点的完全二叉树的高度为____。11.如果结点A有3个兄弟,而且B是A的双亲,则B的度是______。N/22k-299114222020/4/1912.设F是由T1,T2,T3三棵树组成的森林,与F对应的二叉树为B,已知T1,T2,T3的结点数分别为n1,n2和n3则二叉树B的左子树中有___个结点,右子树中有___个结点13.对于一个具有n个结点的二元树,当它为一棵__二元树时具有最小高度,当它为一棵__时,具有最大高度。14.含4个度为2的结点和5个叶子结点的二叉树,可有______个度为1的结点。n1-1n2+n3完全二叉树单枝树0至多个任意二叉树,度为1的结点个数没限制。只有完全二叉树,度为1的结点个数才至多为1。232020/4/1915.利用树的孩子兄弟表示法存储,可以将一棵树转换为______16.有一份电文中共使用6个字符:a,b,c,d,e,f,它们的出现频率依次为2,3,4,7,8,9,试构造一棵哈夫曼树,则其加权路径长度WPL为___,字符c的编码是___。17.将二叉树bt中每一个结点的左右子树互换的C语言算法如下,其中ADDQ(Q,bt),DELQ(Q),EMPTY(Q)分别为进队,出队和判别队列是否为空的函数,请填写算法中得空白处,完成其功能。80二叉树001242020/4/19typedefstructnode{intdata;structnode*lchild,*rchild;}btnode;voidEXCHANGE(btnode*bt){btnode*p,*q;if(bt){ADDQ(Q,bt);while(!EMPTY(Q)){p=DELQ(Q);q=___;p-rchild=(2)___(3)___=q;if(p-lchild)(4)___;if(p-rchild)(5)___;}}}//p-rchildp-lchildp-lchi