《数据结构》第五章习题参考答案

《数据结构》第五章习题参考答案

一、推断题（在正确说法的题后括号中打“J，错误说法的题后括号中打“X”）

1、知道一颗树的先序序列和后序序列可唯一确定这颗树（）X

2、二叉树的左右子树可随意交换（）X

3、任何一颗二叉树的叶子节点在先序、中序和后序遍历序列中的相对次序不发生变更（V）

4、哈夫曼树是带权路径最短的树，路径上权值较大的结点离根较近（V）

5、用一维数组存储二叉树时，总是以前序遍历依次存储结点（）X

6、完全二叉树中，若一个结点没有左孩子，则它必是叶子结点（V）

7、一棵树中的叶子数肯定等于与其对应的二叉树的叶子数（）X

8、度为2的树就是二叉树（）X

二、单项选择题具有个叶结点的二叉树中有（）个度为的结点

1.10B2A.8B.9C.10D.11树的后根遍历序列等同于该树对应的二叉树的（）

2.B o先序序列中序序列后序序列A.B.C.

3、二叉树的先序遍历和中序遍历如下先序遍历EFHIGJK；中序遍历HFIEJKG该二叉树根的右子树的根是（）CA.E B.F C.G D.H

0、在下述结论中，正确的是（）4D o

①具有n个结点的完全二叉树的深度k必为「log2（n+l）i；

②二叉树的度为2；

③二叉树的左右子树可随意交换；

④一棵深度为（）且有仁个结点的二叉树称为满二叉树k kNl21A.

①②③B.

②③④C.

①②④D.

①④、某二叉树的后序遍历序列与先序遍历序列正好相反，则该二叉树肯定是（）5D空或只有一个结点完全二叉树A.B.二叉排序树高度等于其结点数C.D.

三、填空题

1、对于一棵具有n个结点的二叉树，对应二叉链接表中指针总数为2n个，其中ml个用于指向孩子结点,n+1个指针空闲着

2、一棵深度为k（kKl）的满二叉树有2匕1个叶子结点

3、在完全二叉树中，编号为i和j的两个结点处于同一层的条件是F Hog2i-i二「log2j-!o

4、某二叉树有20n0个叶子结点，有30个结点仅有一个孩子nl,则该二叉树的总结点数为69n=n0+nl+n2而n0=n2+l

5、完全二叉树中，结点个数为n,则编号最大的分支结点的编号为5/2」O

6、已知二叉树前序为ABDEGCF,中序为DBGEACF,则后序肯定是DGEBFCAO

四、综合题

1、设二叉树采纳二叉链表存储结构，结点的数据域data为字符类型阅读下列算法，并回答问题1对于如图所示的二叉树，写出执行函数function的输出结果；2简述函数function的功能void functionBinTree TStackBinTreeNode*S;BinTreeNode*p=T.GetRoot;BinTreeNode*q;if p==NULL return;do{while p!=NULL{S.Pushp;ifp-leftChild!=NULL p=p-leftChild;else p=p-rightChild;while!S.IsEmptyq=S.GetTopq-rightChild==p{p=S.Pop;cout«p-data;if!S.IsEmpty{q=S.GetTop;p=q-rightChild;}while!S.IsEmpty;lDBFGECA⑵函数function的功能是对二叉树进行后序遍历

2、课本P

2465.2题【解答】1234-156-17-18-1-1-1-19二叉树图略

3、课本P

2465.3题【解答】结点个数为〃时，深度最小的树的深度为2；它有〃T个叶结点，1个分支结点;深度最大的树的深度为〃；它有个叶结点，个分支结点

14、课本P

2465.4题【解答】总结点数〃=〃o+〃i+〃2+…+nm总分支数e-n-{-/+n\+ri2++n-ltn-m*n,+〃2-1*〃机一1+・・・+2*〃2+n\n则有〃o=之+13=

25、课本P

2465.5题【解答】略

6、课本P

2465.6题【解答】二叉树的前序序列与中序序列相同空树或缺左子树的单支树；二叉树的中序序列与后序12序列相同空树或缺右子树的单支树；二叉树的前序序列与后序序列相同空树或只有根结点的二叉树

37、课本P

2465.7题1X2V3X4V

8、课本P

2465.8题1X2X3V4X

9、课本P

2475.14题【解答】略

10、课本P

2475.17题

11、课本P

2485.18题

12、课本P

2485.19题WPL=2+3X5+6X4+9+14+15X3X2=229+16+

1713、课本P

2485.20题各字母的编码HuffmanCl:0110C2:10C3:0000C4:0111C5:001C6:010C7:11C8:0001电文总码长=4X3+4+5+6+3X10+11+2X25+36=

25714、课本P

2485.23题【解答】统计二叉树中叶结点个数1int Binar^TreeType::leaf BinTreeNode^ypO*ptr{if ptr==NULLreturn0;else if ptr-yleftChild==NULLptr-yrightChild==NULLreturn1;以else returnleaf pti-leftChild+lea ptr-rightChild;交换每个结点的左子女和右子女2void BinaryTreeType::exchangeBinTreeNodeType*ptr{BinTreeNodeType*temp;if pti-leftChild!=NULL\\pti-rightChild!=NULL{temp=ptr~leftChild;〉pti-y leftChild=ptL rightChild;pti-rightChild=temp;exchange ptr-yleftChild;exchange ptr~rightChi/d;

15、课本P

2485.24题【解答】template classType〃，〃私有函数将用void BinaryTreeType::ConstructTreeType T[],int intz,BbiTreeNodeType*ptr{T[n]依次存储的完全二叉树，以为根的子树转换成为用二叉链表表示的//以〃疗为根的完全二叉树利用引用型参i数〃次将形参的值带回实参if i=nptr=NULLelse{;〃建立根结点ptr-new BinTreeNodeVy^几ConstructTreeT,2*z+/,ptr-leftChild;fConstructTreeT,n,2*i+2,ptr-rightChild;

16、课本P

2495.29题【解答】template classType voidBinaryTreeType::FullBinTree2ArrayType*T{QueueBinTreeNodeType*Q;BinTreeNodeType*p=GetRoot;Q.EnQueuep;int index=0;while!Q.IsEmpty{p=Q.DeQueue;T[index+4-|=p-data;ifp-leftChild!=NULL Q.EnQueuep-leftChild;ifp-rightChild!=NULL Q.EnQueuep-rightChild;

17、课本P

2505.37题〃缩格文本显示树template classTypevoid BinaryTreeType::FormatDisplay{Stack BinTreeNodeType*S;S.PushNULL;Stack intS1;Sl.PushO;〃初始化BinTreeNodeType*p=root;int level=0;whilep!=NULL{forint i=level;i0;i-cout«n”；cout«p-data«endl;if p-rightChild!=NULL{〃预留右子树指针在栈中S.Pushp-rightChild;Sl.Pushlevel;ifp-leftChild!=NULL{level++；进左子树p=p-leftChild;//左子树为空，进右子树else//p=S.Pop;level=Sl.Pop;。