搜索
1Ch6树一、选择题：1．下列关于哈夫曼树的叙述，错误的是(C)。A．哈夫曼树根结点的权值等于所有叶结点权值之和。B．具有n个叶结点的哈夫曼树共有2n-1个结点。C．哈夫曼树是一棵二叉树，因此它的结点的度可以为0，1，2。D．哈夫曼树是带权路径长度最短的二叉树。2．由3个结点可以构成多少棵不同形态的二叉树(C)。A．3B．4C．5D．63．如果一棵二叉树结点的前序序列是A，B，C，后序序列是C，B，A，则该二叉树结点的中序序列是(D)。A．A，B，CB．A，C，BC．B，C，AD．不能确定4．如图所示的4棵二叉树中，(B)不是完全二叉树。A．B．C．D．5．二叉树按某种顺序线索化后，任一结点均有指向其前趋和后继的线索，这种说法(B)A．正确B．错误若结点有左子树，则令其lchild指针指示其左孩子；若结点没有左子树，则令其lchild指针指示其前驱；若结点有右子树，则令其rchild指针指示其右孩子；若结点没有右子树，则令其rchild指针指示其后继。6．二叉树的前序遍历序列中，任意一个结点均处在其子女结点的前面，这种说法(A)。A．正确B．错误7．对一棵70个结点的完全二叉树，它有(A)个叶子结点。A．35B．40C．30D．4428．设一棵二叉树中，度为1的结点数为9，则该二叉树的叶子结点的数目为(D)。A．10B．11C．12D．不确定n0=n2+19．假定根结点的层次为0，含有15个结点的二叉树最小高度为(A)。A．3B．4C．5D．6假定根结点的层次为1，含有15个结点的二叉树最小高度为410．若一棵二叉树中，度为2的结点数为9，该二叉树的叶子结点的数目为(A)。A．10B．11C．12D．不确定n0=n2+111．设根结点的层次为0，则高度为k的二叉树的最大结点数为(C)。A．2k-1B．2kC．2k+1-1D．2k+1若设根结点的层次为1，则这棵树的高度为k+1，高度为k+1的二叉树的最大结点数为2k+1-112．以知某二叉树的后序遍历序列为abdec，先序遍历序列为cedba，它的中序遍历序列为(D)。A．debacB．acbedC．decbaD．不确定13．设高度为h的二叉树上只有度为0和度为2的结点,则此二叉树所包含的结点数至少为(B)。A．2hB．2h-1C．2h+1D．h+1314．设n,m为一棵二叉树上的两个结点，在中序遍历时，n在m前的条件是(C)。A．n在m右方B．n是m祖先C．n在m左方D．n是m子孙15．将一棵有100个结点的完全二叉树从上到下,从左到右依次对结点进行编号,根结点的编号为49的结点的左孩子编号为(A)。A．98B．99C．50D．4816．某二叉树的前序和后序序列正好相反,则该二叉树一定是(B)二叉树。A．空或只有一个结点B．高度等于其结点数C．任一结点无左孩子D．任一结点无右孩子17．对于一棵满二叉树，m个树叶，n个结点，深度为h，则(C)。A．h+m=2nB．m=h-1C．n=2h-1D．n=h+m18．判断线索二叉树中某结p有左孩子的条件是(C)。A．p!=nullB．p-lchild!=nullC．p-ltag=0D．p-ltag=119．实现任意二叉树的后序非递归算法而不使用堆栈结构，最佳方案是二叉树采用(C)存储结构。A．二叉链表B．广义存储结构C．三叉链表D．顺序存储结构20．在一棵二叉树结点的先序遍历序列，中序遍历序列和后序遍历序列中，所有的叶子结点的先后顺序(B)。A．都不相同B．完全相同C．先序和中序相同，而与后序不同D．中序和后序相同，而与先序不同21．下图所示FF是森林F转换而来的二叉树，那么F一共有(C)个叶子结点。A．4B．5C．6D．7422．在一非空二叉树的中序遍历序列中，根结点的右边(A)。A．只有右子树上的所有结点B．只有右子树上的部分结点C．只有左子树上的所有结点D．只有左子树上的部分结点23．设森林F中有3棵树，其第一，第二和第三棵树的结点个数分别是n1，n2和n3，则与森林F相对应的二叉树根结点的右子树上的结点个数是(D)。A．n1B．n1+n2C．n3D．n2+n324．假定一棵二叉树的结点数为18，则它的最小高度为(C)。A．18B．8C．5D．4第1层第2层第3层第4层第5层1248325．树最合适用来表示(C)。A．有序数据元素B．无序数据元素C．元素之间具有分支层次关系的数据D．元素之间无联系的数据26．以下有关数据结构的叙述正确的是(C)。A．线性表的线性存储结构优于链式存储结构B．二叉树的第i层上有2i-1个结点，深度为k的二叉树上有2k-1个结点。C．二维数组是其数据元素为线性表的线性表。D．栈的操作方式是先进先出。二．填空题1．有一棵树如图示，回答下面问题：(1)这棵树的根结点是(A)；(2)这棵树的叶子结点是(B,E,H,G)；(3)结点C的度是(2)；(4)这棵树的度是(3)；(5)这棵树的深度是(4)；(6)结点C的孩子是(E,F),子孙是(E,F,H);(7)结点F的父亲是(C)，祖先是(A,C)。2．二叉树的每一个结点至多有(2)棵子树，且子树有(左右)之分。3．树的结点包含一个(数据元素)及若干指向其(子树)的分支，结点拥有的子树数称为(度)，度为0的结点称为(树叶或终端结点)，度不为0的结点称为(非终端结点或分支结点)。4．对二叉树来说，第k层上至多有(2k-1)个结点。55．前序遍历序列为abc的不同二叉树有(5)种不同形态。6．二叉树的前序遍历序列为IJKLMNO,中序遍历序列为JLKINMO,则后序遍历序列为(LKJNOMI)。7．一棵树转化为一棵二叉树后，二叉树没有(右)子树。8．一棵含有n个结点的完全二叉树，它的高度是([log2n]+1)。一棵含有n个结点的完全二叉树，它的高度是([log2n]+1)。h-1层最后一个结点的编号2h-1-1h层第一个结点的编号2h-1h层最后一个结点的编号2h-12h-1≥n≥2h-1n≥2h-1h≤logn+1h=[logn]+1n=2k-1=k=log2(n+1)9．深度为k的二叉树至多有(2k-1)个结点。10．含有n个结点的二叉树用二叉链表表示，有(n+1)个空链域。有2n个链域有n-1个非空链域11．哈夫曼树是带权路径长度(最短)的二叉树。12．具有m个叶子结点的哈夫曼树共(2m-1)个结点。13．前序为a，b，c且后序为c，b，a的二叉树有(4)棵。14．树和二叉树从定义上说是两种不同的数据结构，那么将树转化为二叉树的基本目的是(利用已有的二叉树的算法来解决树的有关问题)。615．深度为k的完全二叉树至多有(2k-1)个结点；至少有(2k-1)个结点，若按自上而下，从左到右的次序给结点编号(从1开始)，则编号最小的叶子结点的编号是(2k-2+1)。16．已知完全二叉树的第8层有8个结点，则其叶子结点数为(68)个。第7层的叶结点总数：26-4第8层的叶结点总数：817．已知完全二叉树的第7层有10个叶子结点，则整个二叉树的结点个数最多为(235)个。18．已知二叉树有50个叶子结点，且仅有一个孩子的结点数为30，则总结点数为(129)。设度为i的结点有ni个，共n个结点有n0+n1+n2=n(结点总数)0*n0+1*n1+2*n2=n-1(边数)所以：n0=n2+1n1=3019．用数组A[1…n]顺序存储完全二叉树的各结点，则当i≤(n-1)/2时，结点A[i]的右孩子是结点(A[2i+1])。20．一棵二叉树结点的前序序列为A，B，D，E，G，C，F，H，I，中序序列为D，B，G，E，A，C，H，F，I，则该二叉树结点的后序序列为(DGEBHIFCA)。721．设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1和1，则T中叶子结点的个数为(8)。设度为i的结点有ni个n1=4n2=2n3=1n4=1n0+n1+n2+n3+n4=nn-1=0*n0+1*n1+2*n2+3*n3+4*n422．6个结点可构造出132种不同形态的二叉树。高度：6高度：5高度：4高度：323．在一棵高度为3的四叉树中，最多含有21结点。1+1*4+1*4*424．一棵树的广义表表示为a(b(c,d(e,f),g(h)),i(j,k(x,y)))，假定根结点的层数为0，结点f的层数为3，结点k的所有祖先的结点数为2个。25．假定一棵三叉树(即度为3的树)的结点个数为50，则它的最小高度为4。假定根结点的高度为0。第一层：30=1个结点第二层：1×3=31=3个结点第三层：1×3×3=32=9个结点第四层：1×3×3×3=33=27个结点------------前四层，共40个结点8第五层：50-40=10个结点26．对于一棵具有n个结点的树，该树中所有结点的度数之和为n-1。即求边数29．设二叉树根的高度为1，则：高度为h的完全二叉树的不同二叉树棵数：2h-1，(即最后一层分别有1，2，…，2h-1个结点的完全二叉树)高度为h的满二叉树的不同二叉树棵数：1。三．判断题1．(×)二叉树是一棵无序树。2．(×)若有一个结点是二叉树中某个子树的前序遍历结果序列的最后一个结点，则它一定是该子树的中序遍历结果序列的最后一个结点。3．(√)在一棵二叉树中，假定每个结点只有左子女，没有右子女，对它分别进行中序遍历和后序遍历，则具有相同的遍历结果。4．(√)在树的存储中，若使每个结点带有指向前驱结点的指针，将在算法中为寻找前驱结点带来方便。5．(√)二叉树是树的特殊情形。6．(×)对于一棵具有n个结点的任何二叉树，进行前序、中序或后序的任一种次序遍历的空间复杂度为O(log2n)。7．(×)对于一棵具有n个结点，其高度为h的二叉树，进行任一种次序遍历的时间复杂度为O(h)。8．(×)若有一个叶子结点是二叉树中某个子树的前序遍历结果序列的最后一个结点，则它一定是该子树的中序遍历结果序列的最后一个结点。9．(√)线索化二叉树中的每个结点通常包含有5个数据成员。10．(×)若有一个结点是二叉树中某个子树的中序遍历结果序列的最后一个结点，则它一定是该子树的前序遍历结果序列的最后一个结点。四．其他1．二叉树的遍历方法有哪几种，分别简诉其遍历步骤。二叉树的遍历方法有先序遍历、中序遍历、后序遍历三种。(1)先序遍历二叉树算法是：若二叉树为空，则空操作；否则访问根结点(D)；先序遍历左子树(L)；先序遍历右子树(R)。(2)中序遍历二叉树算法是：若二叉树为空，则空操作；9否则中序遍历左子树(L)；访问根结点(D)；中序遍历右子树(R)。(3)后序遍历二叉树算法是：若二叉树为空，则空操作；否则后序遍历左子树(L)；后序遍历右子树(R)；访问根结点(D)。2．若按中序遍历二叉树的结果为A，C，B。作出所有能得到这一遍历结果的二叉树。3．二叉树结点数据采用顺序存储结构，存储数组中，如图所示，画出该二叉树的二叉链式表示形式。123456789101112131415161718192021eafdgcjhib4．已知一棵树的双亲表示如下，其中各兄弟结点是从左到右依次出现的，画出该树及对应的二叉树。105．写出二叉树的先序，中序和后序遍历序列，并将该二叉树分解为森林。二叉树的先序遍历序列：ABCDEFGHI二叉树的中序遍历序列：BDCAFEHIG二叉树的后序遍历序列：DCBFIHGEA对应的森林：6．以知一棵二叉树的先序遍历序列为ABECDFGHIJ，中序遍历序列为EBCDAFHIGJ，试画出这棵二叉树，并写出其后序遍历序列。11后序遍历序列为：EDCBIHJGFA7．画以数据集{4，5，6，7，10，12，18}为结点权值所构造的哈夫曼树，并求其带权路径长度WPL。8．设用于通讯的电文仅有8个字母组成，字母在电文中出现的频率分别为7，19，2，6，32，3，21，10。试为这8个字母设计哈夫曼编码。9．有一棵二叉树，其中序和后序遍历序列分别为dgbaechif，gdbeihfca。画出该二叉树，对该二叉树进行先序线索化，并求该二叉树所对应的森林。1210．二叉树以二叉链