数据结构习题与答案--树和二叉树

1、第七章 树和二叉树16一、判断题( t )01、若二叉树用二叉链表作存贮结构，则在n个结点的二叉树链表中只有n1个非空指针域。( f )02、二叉树中每个结点的两棵子树的高度差等于1。(t )03、二叉树中每个结点的两棵子树是有序的。( f )04、二叉树中每个结点有两棵非空子树或有两棵空子树。( f )05、二叉树中所有结点个数是2k-1-1，其中k是树的深度。(f )06、二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。( f )07、对于一棵非空二叉树，它的根结点作为第一层，则它的第i层上最多能有2i1个结点。(t )08、用二叉链表法存储包含n个结点的二叉树，结点的2n个指

2、针区域中有n+1个为空指针。(t)09、具有12个结点的完全二叉树有5个度为2的结点。( f )10、二叉树中每个结点的关键字值大于其左非空子树(若存在的话)所有结点的关键字值，且小于其右非空子树(若存在的话)所有结点的关键字值。( f )11、二叉树按某种顺序线索化后，任一结点均有指向其前驱和后续的线索。( t )12、二叉树的先序遍历序列中，任意一个结点均处在其孩子结点的前面。二、填空题01、由3个结点所构成的二叉树有_5_种形态。 02、一棵深度为6的满二叉树有_个分支结点和_个叶子。03、一棵具有257个结点的完全二叉树，它的高度为_深度为_。04、设一棵完全二叉树有700个结点，则共

3、有_个叶子结点。05、设一棵完全二叉树具有1000个结点，则此完全二叉树有_个叶子结点，有_个度为2的结点，有_个结点只有非空左子树，有_个结点只有非空右子树。06、一棵含有n个结点的k叉树，可能达到的最大深度为_，最小深度为_。07、二叉树的基本组成部分是：根(N)、左子树(L)和右子树(R)。因而二叉树的遍历次序有六种。最常用的是三种：前序法(即按N L R次序)，后序法(即按LRN次序)和中序法(也称对称序法，即按L N R次序)。这三种方法相互之间有关联。若已知一棵二叉树的前序序列是BEFCGDH，中序序列是FEBGCHD，则它的后序序列必是_。08、用5个权值3, 2, 4, 5,

4、1构造的哈夫曼(Huffman)树的带权路径长度是_。三、选择题( )01、树最适合用来表示_。A)有序数据元素B)无序数据元素C)元素之间具有分支层次关系的数据D)元素之间无联系的数据( )02、假定在一棵二叉树中，双分支结点数为15，单分支结点数为30，则叶子结点数为_个。A)15 B)16 C)17 D)47( )03、假定一棵三叉树的结点数为50，则它的最小高度为_。A)3 B)4 C)5 D)6( )04、在一棵二叉树上第5层的结点数最多为_。A)8 B)16 C)15 D)32( )05、用顺序存储方法将完全二叉树中的所有结点逐层存放在数组R1.n中，结点Ri若有子树，则左子树是结

5、点_。A)R2i+1 B)R2i C)Ri/2 D)R2i-1( )06、在一棵具有k层的满三叉树中，结点总数为_。A)(3k-1)/2 B)3k-1 C)(3k-1)/3 D) 3k( )07、由带树为9,2,5,7的四个叶子结点树造一棵哈夫曼树，该树的带权路径长度为_。A)29 B)37 C)46 D)44( )08、具有n(n>0)个结点的完全二叉树的深度为 。A)élog2(n)ù B)ëlog2(n)û C)ëlog2(n)û+1 D)élog2(n)+1ù( )09、由n个数据元素构造的哈夫曼树，

6、共有( )个结点。A)n-1 B)2n-1 C)2n D)2n+1( )10、任何一棵二叉树的叶子结点在先序、中序和后序遍历序列中的相对次序_。A)不发生改变 B)发生改变C)不能确定 D)以上都不对( )11、设a,b为一棵二叉树上的两个结点，在中序遍历中，a在b前面的条件是_。A)a在b的右方 B)a在b的左方C)a是b的祖先 D)a是b的子孙( )12、如图所示，其中_不是完全二叉树。( )13、在线索二叉树中，t所指结点没有左子树的充要条件是_。A)t->lchild=NULLB)t->ltag=1C)t->ltag=1 && t->lchild

7、=NULLD)以上都不对( )14、设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为_。A)2h B)2h-1 C)2h+1 D)h+1( )15、以下说法中错误的是_。A)哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近B) 若一个二叉树的树叶是某子树中序遍历序列中的第一个结点，则它必是该子树后序遍历序列中的第一个结点C)已知二叉树的前序遍历和后序遍历并不能惟一地确定这棵树，因为不知道树的根结点是哪一个D)在前序遍历二叉树的序列中任何结点其子树的结点都是直接跟在该结点之后的( )16、二叉树在线索化后，仍不能有效求解的问题是_。A)先序线索二叉树中

8、求先序后继B)中序线索二叉树中求中序后继C)中序线索二叉树中求中序前驱D)后序线索二叉树中求后序后继( )17、棵有124个叶结点的完全二叉树，最多有_个结点。A)247 B)248 C)249 D)250( )18、在N个结点的线索二叉树中，线索的数目为_。A)N-1 B)N C) N+1 D)2N( )19、设树T的高度为4，其中度为1、2、3和4的结点个数分别为4、2、1、1，则T中的叶子数为_。A)5 B)6 C)7 D)8( )20、下列有关二叉树的说法正确的是_。A)二叉树的度为2B)一棵二叉树可以小于2C)二叉树中至少有一个结点的度为2D)二叉树中任一个结点的度都为2( )21、

9、某二叉树的中序序列为ABCDEFG，后序序列为BDCAFGE，则前序序列是_。A)EGFACDB B)EACBDGFC)EAGCFBD D)上面都不对( )22、设森林F对应的二叉树为B，它有m个结点，B的根为P，P的右子树结点个数为n，森林F中的第一棵树的结点个数是_。A)m-n B)m-n-1 C)n+1 D)条件不充分，无法确定( )23、对二叉排序树进行_遍历，可以得到该二叉树所有结点构成的排序序列。A)先序 B)中序 C)后序 D)按层次( )24、对于一棵具有n个结点、度为4的树来说，_。A)树的高度至多是n-3B)树的高度至多是n-4C)第i层上至多有4*(i-1)个结点D)至少

10、在某一层上正好有4个结点( )25、度为4、高度为h的树，_。A)至少有h+3个结点 B)至多有4h-1个结点C)至多有4h个结点 D)至少有h+4个结点( )26、用双亲数组法表示树，其优点之一是_比较方便。A)找指定结点的双亲 B)找指定结点的孩子C)找指定结点的兄弟 D)判断某结点是不是树叶( )27、用孩子链表法表示树，其优点之一是_比较方便。A)判断两个指定结点是不是兄弟B)找指定结点的双亲C)判断指定结点在第几层D)计算指定结点的度数( )28、如果用孩子链表法来表示树，则_。A)树的高度等于各链表长度的最大值B)树叶的数目和链表的数目成反比C)树的度数等于各链表长度的最大值D)结

11、点的数目等于各链表长度之和( )29、如果在表示树的二叉链表中有6个空的左指针域，7个空的右指针域，5个结点左、右指针域都为空，则该树中叶子结点的个数是_。A)7 B)6 C)5 D)不能确定( )30、如果用二叉链表法来表示一棵具有n (n>1)个结点的树，则在二叉链表中_。A)至多有n-1个非空的右指针域B)至少有2个空的右指针域C)至少有2个非空的左指针域D)至多有n-1个空的右指针域( )31、二叉树和度为2的树的相同之处包括_。A)每个结点都有一个或两个孩子结点B)至少有一个根结点C)至少有一个度为2的结点D)每个结点至多只有一个双亲结点( )32、“二叉树为空”意味着二叉树_

12、。A)由一些没有赋值的空结点构成B)根结点没有子树C)不存在D)没有结点( )33、在高度为h的完全二叉树中，_。A)度为0的结点都在第h层上B)第i(1i<h)层上的结点都是度为2的结点C)第i(1i<h)层上有2i-1个结点D)不存在度为1的结点( )34、若树中结点的前序序列是abcdef，后序序列是bdecfa，则_。A)结点c有两个孩子B)树有两个度为0的结点C)树的高度为5D)不能唯一确定该树的结构( )35、若树中结点的前序序列是abcdefg，后序序列前面3个结点是bde，则后序序列的后面4个结点有可能是_。A)gcfa B)gacf C)afgc D)cfga(

13、)36、若某棵二叉树结点的前序序列和中序序列相同，则该二叉树_。A)只有一个结点 B)每个结点都没有左孩子C)每个结点都没有右孩子 D)不存在( )37、若某棵二叉树结点的后序序列和层次序列正好相反，则该二叉树_。A)每个结点都没有右孩子 B)不存在度为2的结点C)每个结点都没有左孩子 D)不存在( )38、若某棵二叉树结点的前序序列和后序序列相同，则该二叉树_。A)度为1B)只有一个结点C)每个结点都没有左孩子D)每个结点都没有右孩子( )39、在一棵高度小于4的二叉树中，若结点的前序序列是abcdef，则结点的中序序列有可能是_。A)dcebaf B)bcdafe C)cbdafe D)f

14、cadbe( )40、若二叉树中结点的中序序列是abcdef，则结点的前序序列不可能是_。A)dbacef B)acbedf C)efbacd D)bafdce( )41、在一棵高度小于5的二叉树中，若结点的中序序列是abcdef，则结点的后序序列有可能是_。A)bdfeca B)befdca C)bdefca D)fedcba( )42、在任何一棵二叉树中，如果结点a有左孩子b、右孩子c，则在结点的前序序列、中序序列、后序序列中，_。A)结点b一定在结点a的前面B)结点a一定在结点c的前面C)结点b一定在结点c的前面D)结点a一定在结点b的前面( )43、若二叉树结点的前序序列是abcd，后

15、序序列是dcba，则该二叉树_。A)每个分支结点都没有左孩子B)每个分支结点都只有一个孩子C)每个分支结点都没有右孩子D)高度可能为3( )44、如果二叉树中结点的前序序列是.a.b.，中序序列是.b.a.，则_。A)结点a和结点b分别在某结点的左子树和右子树中B)结点b在结点a的右子树中C)结点b在结点a的左子树中D)结点a和结点b分别在某结点的两棵非空子树中( )45、如果二叉树结点的前序序列和中序序列分别是abcdefgh和bcafegdh，则该二叉树的后序序列是_。A)一定是cbfgehda B)可能是cbgefhdaC)不存在 D)有多种可能( )46、如果完全二叉树结点的后序序列是

16、abcdefgh，则结点的前序序列_。A)不能唯一确定 B)是hgfedcbaC)是abdchegf D)是hdbacgef( )47、二叉树若用顺序方法存储，则下列四种运算中的_最容易实现。A)前序遍历二叉树B)判断两个指定结点是不是在同一层上C)层次遍历二叉树D)根据结点的值查找其存储位置( )48、根据使用频率为五个字符设计的哈夫曼编码不可能是_。A)111，110，10，01，00B)000，001，010，011，1C)100，11，10，1，0D)001，000，01，11，10( )49、用整数1,2,3,4,5作为五个树叶的权值，可构造一棵带树路径长度值为_的哈夫曼树。A)33

17、 B)15 C)34 D)54( )50、树的后根遍历序列等同于该树对应的二叉树的_。A)先序遍历 B)中序遍历C)后序遍历 D)层次遍历( )51、在下列存储形式中，_不是树的存储结构。A)双亲表示法 B)孩子链表表示法C)孩子兄弟表示法 D)顺序存储表示法( )52、利用二叉链表存储树，则根结点的右指针是_。A)指向最左孩子 B)指向最右孩子C)空 D)非空( )53、由树为8,2,5,7的数据元素构造一棵哈夫曼树，该树的带权路径径长度为_。A)23 B)37 C)46 D)43( )54、设T是哈夫曼树，具有5个叶子结点，树T的高度最高可以是_。A)3 B)4 C)5 D)6( )55、

18、把一棵树转换为二叉树后，这棵二叉树的形态是 。A)唯一的B)有多种C)有多种，但根结点都没有左孩子D)有多种，但根结点都没有右孩子( )56、如果T2是由有序树T1转换而来的二叉树，那么T1中结点的先序就是T2中结点的_。A)先序 B)中序 C)后序 D)层次序( )57、如果T2是由有序树T1转换而来的二叉树，那么T1中结点的后序就是T2中结点的_。A)先序 B)中序 C)后序 D)层次序( )58、某二叉树的先序遍历和后序遍历序列正好相反，则该二叉树一定是_。A)空或只有一个结点 B)完全二叉树C)二叉排序树 D)高度等于其结点的树( )59、如图所示的T2是由森林T1转换而来的二叉树，那

19、么森林T1有_个叶子结点。A)4 B)5 C)6 D)7( )60、设n、m为一棵二叉树上的两个结点，在中序遍历时，n在m前的条件是_。A)n在m右方 B)n是m祖先C)n在m左方 D)n是m子孙四、简答题01、给定二叉树的两种遍历序列，前序遍历序列：DACEBHFGI；中序遍历序列：DCBEHAGIF。试画出二叉树B，并简述由任意二叉树B的前序遍历序列和中序遍历序列求二叉树B的思想方法。02、若根据右面图中所示的二叉树建立线索二叉树，请在图中画出其中表示前驱的线索，并写出求结点后继的规律。03、如图所示，一棵二叉树的结点数据采用顺序存储结构存储于数组中，请画出该二叉树的链式存储表示。1234

20、56789101112131415161718192021eafdgcjihb04、试写出下图所示二叉树的“先序、中序、后序”遍功时得到的结点序列。05、把下图所示的树转换成二叉树。06、画出和下列二叉树相应的森林。07、证明题a)课本中“性质2、性质3、性质4”的证明。b)证明在有n个结点的二叉链表中必定有n+1个空链域。c)试证明在huffman树中共有2n-1个结点。d)任意一个有n个结点的二叉树，已知它有m个叶子结点，试证明非叶子结点有(m-1)个度数为2。08、若以数据集4,5,6,7,10,12,18为结点的权值构造huffman树，试画出该huffman树，并计算带权路径长度WP

21、L。五、算法设计题01、编写递归算法，计算二叉树中叶子结点的数目。02、编写递归算法，求二叉树中以元素值为x的结点为根的子树的深度。03、编写按层次顺序(同一层自左至右)遍历二叉树的算法。04、已知一棵具有n个结点的完全二叉树被顺序存储于一维数组A中，试编写一个算法打印出编号为i的结点的双亲和所有的孩子。05、假设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。试为这8个字母设计哈夫曼编码。第七章 树和二叉树一、判断题： 01-05××× 06-10××

22、× 11-12×二、填空题：(01)5 (02)31、32 (03)9 (04)350 (05)500、499、1、0 (06)n、2 (07)FEGHDCB (08)33三、选择题：01-05 CBCBB 06-10 ADCBA 11-15 BCBBA 16-20 DBCDB 21-25 BBAAA 26-30 ADCBB 31-35 DDCAD 36-40 BBBCC 41-45 ACCCA 46-50 DCCAB 51-55 DCDCA 56-60 ABDCC 四、简答题01、由前序先确定root，由中序可确定root的左、右子树。然后由其左子树的元素集合和右子树的集合对应前序遍历序列中的元素集合，可继续确定root的左右孩子。将他们分别作为新的root，不断递归，则所有元素都将被唯一确定，问题得解。02、中序线索二叉链树 求后继的规律：“终端结点”的后继为线索直接指向的结点；“非终端结点”的后继为右子树下的最左结点。03、04、先序：A B D F J G K C E H I L M中序：B F J D G K A C H E L I M后序：J F K G D B H L M I E C A05、06、07、证明题a)见课本P124页b)