数据结构Ch6习题答案

1、Ch6树一、选择题：1下列关于哈夫曼树的叙述，错误的是( C )。A哈夫曼树根结点的权值等于所有叶结点权值之和。B具有n个叶结点的哈夫曼树共有2n-1个结点。C哈夫曼树是一棵二叉树，因此它的结点的度可以为0，1，2。 D哈夫曼树是带权路径长度最短的二叉树。2由3个结点可以构成多少棵不同形态的二叉树( C )。 A3 B4 C5 D6 3如果一棵二叉树结点的前序序列是A，B，C，后序序列是C，B，A，则该二叉树结点的中序序列是( D )。 AA，B，C BA，C，B CB，C，A D不能确定4如图所示的4棵二叉树中，( B )不是完全二叉树。 A B C D5二叉树按某种顺序线索化后，任一结点均

2、有指向其前趋和后继的线索，这种说法( B )A正确 B错误若结点有左子树，则令其lchild指针指示其左孩子；若结点没有左子树，则令其lchild指针指示其前驱；若结点有右子树，则令其rchild指针指示其右孩子；若结点没有右子树，则令其rchild指针指示其后继。6二叉树的前序遍历序列中，任意一个结点均处在其子女结点的前面，这种说法( A )。A正确 B错误7对一棵70个结点的完全二叉树，它有( A )个叶子结点。A35 B40 C30 D448设一棵二叉树中，度为1的结点数为9，则该二叉树的叶子结点的数目为( D )。A10 B11 C12 D不确定n0=n2+19假定根结点的层次为0，含

3、有15个结点的二叉树最小高度为( A )。 A3 B4 C5 D6假定根结点的层次为1，含有15个结点的二叉树最小高度为410若一棵二叉树中，度为2的结点数为9，该二叉树的叶子结点的数目为( A )。A10 B11 C12 D不确定n0=n2+111设根结点的层次为0，则高度为k的二叉树的最大结点数为(C )。 A2k-1 B2k C2k+1-1 D2k+1若设根结点的层次为1，则这棵树的高度为k+1，高度为k+1的二叉树的最大结点数为2k+1-112以知某二叉树的后序遍历序列为abdec，先序遍历序列为cedba，它的中序遍历序列为( D )。 Adebac Bacbed Cdecba D不

4、确定13设高度为h的二叉树上只有度为0和度为2的结点,则此二叉树所包含的结点数至少为( B )。 A2h B2h-1 C2h+1 Dh+114设n,m为一棵二叉树上的两个结点，在中序遍历时，n在m前的条件是( C )。An在m右方 Bn是m祖先 Cn在m左方 Dn是m子孙15将一棵有100个结点的完全二叉树从上到下,从左到右依次对结点进行编号,根结点的编号为49的结点的左孩子编号为( A )。 A98 B99 C50 D4816某二叉树的前序和后序序列正好相反,则该二叉树一定是( B )二叉树。A 空或只有一个结点 B高度等于其结点数 C任一结点无左孩子 D任一结点无右孩子17对于一棵满二叉树

5、，m个树叶，n个结点，深度为h，则( C )。Ah+m=2n Bm=h-1 Cn=2h-1 Dn=h+m18判断线索二叉树中某结p有左孩子的条件是( C )。Ap!=null Bp->lchild!=null Cp->ltag=0 Dp->ltag=119实现任意二叉树的后序非递归算法而不使用堆栈结构，最佳方案是二叉树采用( C )存储结构。A二叉链表 B广义存储结构 C三叉链表 D顺序存储结构20在一棵二叉树结点的先序遍历序列，中序遍历序列和后序遍历序列中，所有的叶子结点的先后顺序( B )。A都不相同 B完全相同 C先序和中序相同，而与后序不同 D中序和后序相同，而与先序

6、不同21下图所示FF是森林F转换而来的二叉树，那么F 一共有( C )个叶子结点。A4 B5 C6 D722在一非空二叉树的中序遍历序列中，根结点的右边( A )。A只有右子树上的所有结点 B只有右子树上的部分结点 C只有左子树上的所有结点 D只有左子树上的部分结点23设森林F中有3棵树，其第一，第二和第三棵树的结点个数分别是n1，n2和n3，则与森林F相对应的二叉树根结点的右子树上的结点个数是( D )。 An1 Bn1+n2 Cn3 Dn2+n324假定一棵二叉树的结点数为18，则它的最小高度为(C )。A18 B8 C5 D4第1层 第2层 第3层 第4层 第5层1 2 4 8 325树

7、最合适用来表示(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

8、的父亲是(C)，祖先是(A,C)。2二叉树的每一个结点至多有(2)棵子树，且子树有(左右)之分。3树的结点包含一个(数据元素)及若干指向其(子树)的分支，结点拥有的子树数称为(度)，度为0的结点称为(树叶或终端结点)，度不为0的结点称为(非终端结点或分支结点)。 4对二叉树来说，第k层上至多有(2k-1)个结点。5前序遍历序列为abc的不同二叉树有(5)种不同形态。6二叉树的前序遍历序列为I J KL MNO,中序遍历序列为J LK I NMO,则后序遍历序列为(LKJNOMI)。7一棵树转化为一棵二叉树后，二叉树没有(右)子树。8一棵含有n个结点的完全二叉树，它的高度是(log2n+1)。

9、一棵含有n个结点的完全二叉树，它的高度是(log2n+1)。 h-1层最后一个结点的编号2h-1-1 h层第一个结点的编号2h-1 h层最后一个结点的编号2h-1 2h-1n2h-1n2h-1hlogn+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树和二叉树从定义上说是两种不同的数

10、据结构，那么将树转化为二叉树的基本目的是(利用已有的二叉树的算法来解决树的有关问题)。15深度为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

11、=n(结点总数)0*n0+1*n1+2*n2=n-1(边数)所以：n0=n2+1n1=3019用数组A1n顺序存储完全二叉树的各结点，则当i (n-1)/2时，结点Ai的右孩子是结点(A2i+1)。20一棵二叉树结点的前序序列为A，B，D，E，G，C，F，H，I，中序序列为D，B，G，E，A，C，H，F，I，则该二叉树结点的后序序列为(DGEBHIFCA)。21有m个叶子结点的哈夫曼树上的结点数是(2m-1)。22设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1和1，则T中叶子结点的个数为(8)。设度为i的结点有ni个n1=4 n2=2 n3=1 n4=1n0+n1+n2+n3

12、+n4=nn-1=0*n0+1*n1+2*n2+3*n3+4*n4236个结点可构造出 132 种不同形态的二叉树。 高度：6高度：5高度：4高度：324在一棵高度为3的四叉树中，最多含有 21 结点。 1+1*4+1*4*425一棵树的广义表表示为a (b (c, d (e, f), g (h) ), i(j, k (x, y) ) )，结点f的层数为 3 。假定根结点的层数为0。 26一棵树的广义表表示为a (b (c, d (e, f), g (h) ), i(j, k (x, y) ) )，结点k的所有祖先的结点数为 2 个。 27假定一棵三叉树(即度为3的树)的结点个数为50，则它的

13、最小高度为 4 。假定根结点的高度为0。 第一层：30=1个结点第二层：1×3=31=3个结点第三层：1×3×3=32=9个结点第四层：1×3×3×3=33=27个结点-前四层，共40个结点第五层：50-40=10个结点28对于一棵具有n个结点的树，该树中所有结点的度数之和为 n-1 。 即求边数29设二叉树根的高度为1，则：高度为h的完全二叉树的不同二叉树棵数： 2h-1 ，(即最后一层分别有1，2，2h-1个结点的完全二叉树)高度为h的满二叉树的不同二叉树棵数： 1 。三判断题1(×)二叉树是一棵无序树。 2(×

14、;)若有一个结点是二叉树中某个子树的前序遍历结果序列的最后一个结点，则它一定是该子树的中序遍历结果序列的最后一个结点。 3()在一棵二叉树中，假定每个结点只有左子女，没有右子女，对它分别进行中序遍历和后序遍历，则具有相同的遍历结果。 4()在树的存储中，若使每个结点带有指向前驱结点的指针，将在算法中为寻找前驱结点带来方便。 5()二叉树是树的特殊情形。 6(×)对于一棵具有n个结点的任何二叉树，进行前序、中序或后序的任一种次序遍历的空间复杂度为O(log2n)。 7(×)对于一棵具有n个结点，其高度为h的二叉树，进行任一种次序遍历的时间复杂度为O(h)。 8(×)

15、若有一个叶子结点是二叉树中某个子树的前序遍历结果序列的最后一个结点，则它一定是该子树的中序遍历结果序列的最后一个结点。 9()线索化二叉树中的每个结点通常包含有5个数据成员。 10(×)若有一个结点是二叉树中某个子树的中序遍历结果序列的最后一个结点，则它一定是该子树的前序遍历结果序列的最后一个结点。 四其他1二叉树的遍历方法有哪几种，分别简诉其遍历步骤。二叉树的遍历方法有先序遍历、中序遍历、后序遍历三种。(1)先序遍历二叉树算法是：若二叉树为空，则空操作；否则访问根结点(D)；先序遍历左子树(L)；先序遍历右子树(R)。(2)中序遍历二叉树算法是：若二叉树为空，则空操作；否则中序遍历

16、左子树(L)；访问根结点(D)；中序遍历右子树(R)。(3)后序遍历二叉树算法是：若二叉树为空，则空操作；否则后序遍历左子树(L)；后序遍历右子树(R)；访问根结点(D)。2若按中序遍历二叉树的结果为A，C，B。作出所有能得到这一遍历结果的二叉树。3二叉树结点数据采用顺序存储结构，存储数组中，如图所示，画出该二叉树的二叉链式表示形式。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21eafdgcjhib4已知一棵树的双亲表示如下，其中各兄弟结点是从左到右依次出现的，画出该树及对应的二叉树。5写出二叉树的先序，中序和后序遍历序列，并将该二

17、叉树分解为森林。二叉树的先序遍历序列：ABCDEFGHI二叉树的中序遍历序列：BDCAFEHIG二叉树的后序遍历序列：DCBFIHGEA对应的森林：6以知一棵二叉树的先序遍历序列为ABECDFGHIJ，中序遍历序列为EBCDAFHIGJ，试画出这棵二叉树，并写出其后序遍历序列。后序遍历序列为：EDCBIHJGFA7画以数据集4，5，6，7，10，12，18为结点权值所构造的哈夫曼树，并求其带权路径长度WPL。8设用于通讯的电文仅有8个字母组成，字母在电文中出现的频率分别为7，19，2，6，32，3，21，10。试为这8个字母设计哈夫曼编码。9有一棵二叉树，其中序和后序遍历序列分别为dgbaec

18、hif，gdbeihfca。画出该二叉树，对该二叉树进行先序线索化，并求该二叉树所对应的森林。10二叉树以二叉链表结构存储，在下列中序遍历序列算法中填上正确的语句。 Status in_order (BiTree p)if ( p !=NULL) (1)in_order(p->lchild) ; printf ( p->data); (2)in_order(p->rchild) ; 11以二叉链表作为存储结构，试完成下列程序(1)下列函数是中序输出二叉树的各结点，读程序并在每一个空格初填写一个语句或表达式。 void printtree (BiTree BT) BiTnode

19、 *p;InitStack (s ); /构造栈sp=(1) BT ; s.top=0;while (p | s.top!=0) while (2) p!=NULL ) s.elems.top+=p; (3) p=p->lchild ; if (s.top>0)(4)p=s.elem-top ; printf (“%d”, p->data); (5)p=p->rchild ; (2)所谓二叉树T1和T2是等价的，那就是说，或者T1和T2都是空的二叉树；或者T1和T2都是非空的二叉树，且T1和T2的根结点的值相同，同时T1和T2的根结点的左子树是等价的，且T1和T2的根结

20、点的右子树也是等价的。下面给出了判断二叉树T1和T2是否等价的程序。读程序并在每一个空格初填写一个语句或表达式。 int equalbitre (BiTree t1, BiTree t2 ) int equal=0; if (t1= =null &&(1) t2=null ) equal=1; else if (t1!= null &&(2) t2!=null) if (t1->data= =t2->data) if (equalbitre ( t1->lchild, t2->lchild) (3) if (equalbitre ( t1

21、->rchild, t2->rchild)equal=1; return equal; 12一棵用二叉链表表示的二叉树，其根指针为root，试写出求二叉树结点数目的算法。答案一：int Size(BiTree T) if(T=NULL) return 0; else return(1+Size(T->lchild)+Size(T->rchild);答案二：i=0;int in_order (BiTree p)if ( p !=NULL) in_order(p->lchild) ; printf ( p->data); i+; in_order(p->rchild) ; return i;答案三：void printtree (BiTree BT) BiTnode *p; i=0；InitStack (s ); /构造栈sp=(1) BT ; s.top=0;while (p | s.top!=0) while (p!=NULL ) s.elems.top+=p; p=p->lchild ; if (s.top>0)(4)p=s.elem-top ; printf (“%d”, p->data); i+；