数据结构Ch6习题答案

Ch6树一、选择题：1.下列关于哈夫曼树的叙述，错误的是(C)。A.哈夫曼树根结点的权值等于所有叶结点权值之和。B.具有n个叶结点的哈夫曼树共有2n-1个结点。C.哈夫曼树是一棵二叉树，因此它的结点的度可以为0,1,2。D.哈夫曼树是带权路径长度最短的二叉树。.由3个结点可以构成多少棵不同形态的二叉树(C)。A.3B.4 C.5D.6(.如果一棵二叉树结点的前序序列是A,B,C,后序序列是C,B,A,则该二叉树结点的中序序列是(D)。A.A,B,C B.A,C,BC.B,C,AD.不能确定.二叉树按某种顺序线索化后，任一结点均有指向其前趋和后继的线索，这种说滔B)A.正确 B.错误若结点有左子树，则令其Ichild指针指示其左孩子；若结点没有左子树，则令其Ichild指针指示其前驱;若结点有右子树，则令其rchild指针指示其右孩子；若结点没有右子树，则令其rchild指针指示其后继。).二叉树的前序遍历序列中，任意一个结点均处在其子女结点的前面，这种说/A)。A.正确 B.错误.对一棵70个结点的完全二叉树，它有(A)个叶子结点。A.35B.40 C.30D.44

第1层,1个结点、第2层12个结点第3层第1层,1个结点、第2层12个结点第3层14个结点第4层18个结点＞与6房.山63个空点।引个结.辽第6层：32个结点上第7层;7个结点——8.设一棵二叉树中，度为1的结点数为9,则该二叉树的叶子结点的数目为(D)。A.10B.11C.12D.不确定n0=n2+1.假定根结点的层次为0,含有15个结点的二叉树最小高度为(A)。A.3 B.4C.5D.6)假定根结点的层次为1,含有15个结点的二叉树最小高度为4.若一棵二叉树中，度为2的结点数为9,该二叉树的叶子结点的数目为(A)。A.10 B.11 C.12 D.不确定n0=n2+1.设根结点的层次为0,则高度为k的二叉树的最大结点数为(C)。A.2k-1B.2kC.2k+1-1 D.2k+1若设根结点的层次为1,则这棵树的高度为k+1,高度为k+1的二叉树的最大结点数为2k+1-1.以知某二叉树的后序遍历序列为abdec,先序遍历序列为cedba,它的中序遍历序列为(D)。A.debac B.acbed C.decba D.不确定⑥®©©&13.设高度为h的二叉树上只有度为0和度为2的结点，则此二叉树所包含的结点数至少为(B)。A.2h B.2h-1 C.2h+1 D.h+1

除第除第1层外,每层只有两个结点，且这两个结点为兄弟14.设n,m为一棵二叉树上的两个结点，在中序遍历时，n在m前的条件是（C）。A.n在m右方 B.n是m祖先 C.n在m左方 D.n是m子孙.将一棵有100个结点的完全二叉树从上到下，从左到右依次对结点进行编号，根结点的编号为49的结点的左孩子编号为（A）。A.98B.99C.50 D.48.某二叉树的前序和后序序列正好相反则该二叉树一定是（B）二叉树。A.空或只有一个结点 B.高度等于其结点数 C.任一结点无左孩子 D.任一结点无右孩子.对于一棵满二叉树，m个树叶，n个结点，深度为足则（C）。A.h+m=2n B.m=h-1 C.n=2h-1 D.n=h+m.判断线索二叉树中某结p有左孩子的条件是（C）。A.p!=nullB.p->lchild!=nullC.p->ltag=0 D.p->ltag=1.实现任意二叉树的后序非递归算法而不使用堆栈结构，最佳方案是二叉树采用（C）存储结构。A.二叉链表B.广义存储结构C.三叉链表D.顺序存储结构.在一棵二叉树结点的先序遍历序列，中序遍历序列和后序遍历序列中，所有的叶子结点的先后顺用B）。A.都不相同B.完全相同 C.先序和中序相同，而与后序不同 D.中序和后序相同，而与先序不同.下图所示FF是森林F转换而来的二叉树，那么F一共有（C）个叶子结点。A.4 B.5 C.6 D.7

22.在一非空二叉树的中序遍历序列中，根结点的右边(A）22.在一非空二叉树的中序遍历序列中，根结点的右边(A）。A.只有右子树上的所有结点B.只有右子树上的部分结点C.只有左子树上的所有结点 D.只有左子树上的部分结点.设森林F中有3棵树，其第一，第二和第三棵树的结点个数分别是n1,n2和n3,则与森林F相对应的二叉树根结点的右子树上的结点个数是(D)。A.n1B.n1+n2 C.n3 D.n2+n3.假定一棵二叉树的结点数为18,则它的最小高度为(C)。A.18 B.8C.5D.4第1层第2层第3层第4层第5层1 2 4 8 3.树最合适用来表示(C)。A.有序数据元素B.无序数据元素 C.元素之间具有分支层次关系的数据 D.元素之间无联系的数据.以下有关数据结构的叙述正确的是(C)。A.线性表的线性存储结构优于链式存储结构B.二叉树的第i层上有2i-i个结点，深度为k的二叉树上有2k-i个结点。C.二维数组是其数据元素为线性表的线性表。 D.栈的操作方式是先进先出。二.填空题.有一棵树如图示，回答下面问题：(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)。.二叉树的每一个结点至多有⑵棵子树，且子树有(左右)之分。.树的结点包含一个(数据元素)及若干指向其(子树)的分支，结点拥有的子树数称为(度)，度为0的结点称为(树叶或终端结点)，度不为0的结点称为(非终端结点或分支结点)。.对二叉树来说，第k层上至多有(2k-i)个结点。.前序遍历序列为abc的不同二叉树有(5)种不同形态。6.二叉树的前序遍历序列为IJKLMNO,中序遍历序列为JLKINMO,则后序遍历序列为(LKJNOMI)。.一棵树转化为一棵二叉树后，二叉树没有(右)子树。.一棵含有n个结点的完全二叉树，它的高度是([log2n]+1)。一棵含有n个结点的完全二叉树，它的高度是([log2n]+1)。h-1层最后一个结点的编号2h-i-1h层第一个结点的编号2h-ih层最后一个结点的编号2h-12h-12n22h-in22h-ihWlogn+1h=[logn]+1n=2k-1=>k=log2(n+1).深度为k的二叉树至多有(2k-1)个结点。.含有n个结点的二叉树用二叉链表表示，有(n+1)个空链域。,有2n个链域有n-1个非空链域.哈夫曼树是带权路径长度(最短)的二叉树。.具有m个叶子结点的哈夫曼树共(2m-1)个结点。

解决树的有关问题)。15解决树的有关问题)。15.深度为k的完全二叉树至多有(2k-1)个结点；至少有(2k-i)个结点，若按自上而下，从左到右的次序给结点编号从1开始)，则编号最小的叶子结点的编号是(2k-2+1)。第k层 O第1个叶结点,即编号最小的一个结点16.已知完全二叉树的第8层有8个结点，则其叶子结点数为(68)个。第7层的叶结点总数：26-4第8层的叶结点总数：817.已知完全二叉树的第7层有10个叶子结点，则整个二叉树的结点个数最多为(235)个。.已知二叉树有50个叶子结点，且仅有一个孩子的结点数为30,则总结点数为(129)。设度为i的结点有n.个，共n个结点有叫+叫+%5(结点总数)0*n0+1*n1+2*n2=n-1(边数)所以：n0=n2+1[n1=30.用数组A[1...n]顺序存储完全二叉树的各结点，则当i<(n-1)/2时，结点A[i]的右孩子是结点(A[2i+1])。.一棵二叉树结点的前序序列为A,B,D,E,G,C,F,H,I,中序序列为D,B,G,E,A,C,H,F,I,则该二

叉树结点的后序序列为(DGEBHIFCA)。.有m个叶子结点的哈夫曼树上的结点数是(2m-1)。.设树T的度为4,其中度为1,2,3和4的结点个数分别为4,2,1和1,则T中叶子结点的个数为(8)。设度为i的结点有n.个n1=4n2=2n3=1n4=1no+ni+n2+n3+n4=nn-1=0*n0+1*n1+2*n2+3*n3+4*n4.6个结点可构造出_132种不同形态的二叉树。高度：6高度：5高度：4高度：3.在一棵高度为3的四叉树中，最多含有_^1结点。1+1*4+1*4*4.假定一棵三叉树(即度为3的树)的结点个数为50,则它的最小高度为4。假定根结点的高度为0。第一层：3o=1个结点第二层：1X3=31=3个结点第三层：1X3X3=32=9个结点第四层：1X3X3X3=33=27个结点 前四层，共40个结点第五层：50-40=10个结点.对于一棵具有n个结点的树，该树中所有结点的度数之和为n-1即求边数.设二叉树根的高度为1,则：高度为h的完全二叉树的不同二叉树棵数：，(即最后一层分别有1,2,…，2h-i个结点的完全二叉树)高度为h的满二叉树的不同二叉树棵数：1三.判断题)(X)二叉树是一棵无序树。(X)若有一个结点是二叉树中某个子树的前序遍历结果序列的最后一个结点，则它一定是该子树的中序遍历结果序列的最后一个结点。(J)在一棵二叉树中，假定每个结点只有左子女，没有右子女，对它分别进行中序遍历和后序遍历，则具有相同的遍历结果。(J)在树的存储中，若使每个结点带有指向前驱结点的指针，将在算法中为寻找前驱结点带来方便。(J)二叉树是树的特殊情形。(X)对于一棵具有n个结点，其高度为h的二叉树，进行任一种次序遍历的时间复杂度为0(h)。(X)若有一个叶子结点是二叉树中某个子树的前序遍历结果序列的最后一个结点，则它一定是该子树的中序遍历结果序列的最后一个结点。(J)线索化二叉树中的每个结点通常包含有5个数据成员。,(X)若有一个结点是二叉树中某个子树的中序遍历结果序列的最后一个结点，则它一定是该子树的前序遍历结果序列的最后一个结点。四.其他.二叉树的遍历方法有哪几种，分别简诉其遍历步骤。二叉树的遍历方法有先序遍历、中序遍历、后序遍历三种。(1)先序遍历二叉树算法是：若二叉树为空，则空操作；否则访问根结点(D)；先序遍历左子树(L)；

先序遍历右子树(R)。]⑵中序遍历二叉树算法是：若二叉树为空，则空操作；否则中序遍历左子树(L)；访问根结点(D)；中序遍历右子树(R)。⑶后序遍历二叉树算法是：若二叉树为空，则空操作；否则后序遍历左子树(L)；、后序遍历右子树(R)；访问根结点(D)。.若按中序遍历二叉树的结果为A,C,B。作出所有能得到这一遍历结果的二叉树。3.二叉树结点数据采用顺序存储结构，存储数组中，如图所示，画出该二叉树的二叉链式表示形式。1 2 3 4 5 6 7 8 9 101112131415161718192021eaf》d3.二叉树结点数据采用顺序存储结构，存储数组中，如图所示，画出该二叉树的二叉链式表示形式。1 2 3 4 5 6 7 8 9 101112131415161718192021eaf》dgcjh(ibAa\cAAbA4.已知一棵树的双亲表示如下，其中各兄弟结点是从左到右依次出现的，画出该树及对应的二叉树。，5.写出二叉树的先序中序和后序遍历序列，并将该二叉树分解为森林。，5.写出二叉树的先序中序和后序遍历序列，并将该二叉树分解为森林。01234567891011121314DATAABCDEFGHIJKLMN0PARENT-10D011223345567二叉树的先序遍历序列：ABCDEFGHI二叉树的中序遍历序列：BDCAFEHIG二叉树的后序遍历序列：DCBFIHGEA对应的森林：.以知一棵二叉树的先序遍历序列为ABECDFGHIJ,中序遍历序列为EBCDAFHIGJ,试画出这棵二叉树，并写出其后序遍历序列。后序遍历序列为：EDCBIHJGFA.画以数据集｛4,5,6,7,10,12,18｝为结点权值所构造的哈夫曼树，并求其带权路径长度WPL。4 52*2+6*3+7*3+18*2+4*4+5*4+10*3=165.设用于通讯的电文仅有8个字母组成，字母在电文中出现的频率分别为7,19,2,6,32,3,21,10。试为这8.有一棵二叉树，其中序和后序遍历序列分别为dgbaechif,gdbeihfca。画出该二叉树，对该二叉树进行先序线索化，并求该二叉树所对应的森林。

10.二叉树以二叉链表结构存储，10.二叉树以二叉链表结构存储，在下列中序遍历序列算法中填上正确的语句。Statusin_order(BiTreep){if(p!=NULL)]{(1)inorder(p->lchild);printf(p->data);(2)inorder(p->rchild);})11.以二叉链表作为存储结构，试完成下列程序(1)下列函数是中序输出二叉树的各结点，读程序