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

《《数据结构》第五章习题参考答案.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《数据结构》第五章习题参考答案一、判断题（在正确说法的题后括号中打“√”，错误说法的题后括号中打“×”）1、知道一颗树的先序序列和后序序列可唯一确定这颗树。(×)2、二叉树的左右子树可任意交换。（×）3、任何一颗二叉树的叶子节点在先序、中序和后序遍历序列中的相对次序不发生改变。（√）4、哈夫曼树是带权路径最短的树，路径上权值较大的结点离根较近。（√）5、用一维数组存储二叉树时，总是以前序遍历顺序存储结点。(×)6、完全二叉树中，若一个结点没有左孩子，则它必是叶子结点。(√)7、一棵树中的叶子数一定等于与其对应的二叉树的叶子数。（×）8、度为2的树就是二

2、叉树。（×）二、单项选择题1．具有10个叶结点的二叉树中有（B）个度为2的结点。A．8B．9C．10D．112．树的后根遍历序列等同于该树对应的二叉树的(B)。A.先序序列B.中序序列C.后序序列3、二叉树的先序遍历和中序遍历如下：先序遍历：EFHIGJK；中序遍历：HFIEJKG。该二叉树根的右子树的根是：(C)A.EB.FC.GD.H04、在下述结论中，正确的是（D）。①具有n个结点的完全二叉树的深度k必为┌log2(n+1)┐；②二叉树的度为2；③二叉树的左右子树可任意交换；④一棵深度为k(k≥1)且有2k-1个结点的二叉树称为满二叉树。A．①②

3、③B．②③④C．①②④D．①④5、某二叉树的后序遍历序列与先序遍历序列正好相反，则该二叉树一定是（D）。A．空或只有一个结点B．完全二叉树C．二叉排序树D．高度等于其结点数三、填空题1、对于一棵具有n个结点的二叉树，对应二叉链接表中指针总数为__2n____个，其中___n-1_____个用于指向孩子结点，___n+1___个指针空闲着。2、一棵深度为k(k≥1)的满二叉树有_____2k-1______个叶子结点。3、在完全二叉树中，编号为i和j的两个结点处于同一层的条件是「_┌㏒2i┐=┌㏒2j┐____。？4、某二叉树有20(n0)个叶子结点，有

4、30个结点仅有一个孩子(n1)，则该二叉树的总结点数为69_。（n=n0+n1+n2）(而n0=n2+1)5、完全二叉树中，结点个数为n，则编号最大的分支结点的编号为__└n/2┘____。6、已知二叉树前序为ABDEGCF，中序为DBGEACF，则后序一定是_DGEBFCA___。四、综合题1、设二叉树采用二叉链表存储结构，结点的数据域data为字符类型。阅读下列算法，并回答问题：（1）对于如图所示的二叉树，写出执行函数function的输出结果；1（2）简述函数function的功能。voidfunction(BinTreeT){Stack

5、TreeNode*>S;BinTreeNode*p=T.GetRoot();BinTreeNode*q;if(p==NULL)return;do{while(p!=NULL){S.Push(p);if(p->leftChild!=NULL)p=p->leftChild;elsep=p->rightChild;}while(!S.IsEmpty()&&q=S.GetTop()&&q->rightChild==p){p=S.Pop();cout<data;}if(!S.IsEmpty()){q=S.GetTop();p=q->rightChild;

6、}}while(!S.IsEmpty());}(1)DBFGECA(2)函数function的功能是对二叉树进行后序遍历。2、课本P2465.2题【解答】1234-156-17-18-1-1-1-19二叉树图略3、课本P2465.3题【解答】结点个数为n时，深度最小的树的深度为2；它有n-1个叶结点，1个分支结点；深度最大的树的深度为n；它有1个叶结点，n-1个分支结点。4、课本P2465.4题【解答】总结点数n=n0+n1+n2+…+nm总分支数e=n-1=n0+n1+n2+…+nm-1=m*nm+(m-1)*nm-1+…+2*n2+n1则有5、课本

7、P2465.5题【解答】略6、课本P2465.6题【解答】(1)二叉树的前序序列与中序序列相同：空树或缺左子树的单支树；(2)二叉树的中序序列与后序序列相同：空树或缺右子树的单支树；(3)二叉树的前序序列与后序序列相同：空树或只有根结点的二叉树。7、课本P2465.7题123456785-17答（1）×（2）√（3）×（4）√8、课本P2465.8题（1）×（2）×（3）√（4）×9、课本P2475.14题【解答】略10、课本P2475.17题11、课本P2485.18题165-19答1791415632ABCDEFIG5-18答JH12、课本P248

8、5.19题5-20Huffman树C7C5C6C4C2C1C3C8WPL=（2+3）×5+6×