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

数据结构第五章习题参考答案一、判断题（在正确说法的题后括号中打“”，错误说法的题后括号中打“”）1、知道一颗树的先序序列和后序序列可唯一确定这颗树。( )2、二叉树的左右子树可任意交换。（ ）3、任何一颗二叉树的叶子节点在先序、中序和后序遍历序列中的相对次序不发生改变。（ ）4、哈夫曼树是带权路径最短的树，路径上权值较大的结点离根较近。（ ）5、用一维数组存储二叉树时，总是以前序遍历顺序存储结点。( )6、完全二叉树中，若一个结点没有左孩子，则它必是叶子结点。( )7、一棵树中的叶子数一定等于与其对应的二叉树的叶子数。（ ）8、度为2的树就是二叉树。（ ）二、单项选择题1具有10个叶结点的二叉树中有（ B ）个度为2的结点。A8 B9 C10 D112树的后根遍历序列等同于该树对应的二叉树的( B )。A. 先序序列 B. 中序序列 C. 后序序列3、二叉树的先序遍历和中序遍历如下： 先序遍历：EFHIGJK；中序遍历：HFIEJKG 。该二叉树根的右子树的根是：( C )A. E B. F C. G D. H04、在下述结论中，正确的是（ D ）。具有n个结点的完全二叉树的深度k必为log2(n+1)； 二叉树的度为2；二叉树的左右子树可任意交换；一棵深度为k(k1)且有2k-1个结点的二叉树称为满二叉树。A B C D5、某二叉树的后序遍历序列与先序遍历序列正好相反，则该二叉树一定是（ D ）。A空或只有一个结点 B完全二叉树C二叉排序树 D高度等于其结点数三、填空题1、对于一棵具有n个结点的二叉树，对应二叉链接表中指针总数为_2n_个，其中_n-1_个用于指向孩子结点，_n+1_个指针空闲着。2、一棵深度为k(k1)的满二叉树有_2k-1_个叶子结点。3、在完全二叉树中，编号为i和j的两个结点处于同一层的条件是_2 i= 2j_ _。？4、某二叉树有20(n0)个叶子结点，有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的功能。void function(BinTree T)Stack 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;else p=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; while (!S.IsEmpty ();(1)DBFGECA(2) 函数function的功能是对二叉树进行后序遍历。2、课本P246 5.2题【解答】1234-156-17-18-1-1-1-19二叉树图略3、课本P246 5.3题【解答】结点个数为n时，深度最小的树的深度为2；它有n-1个叶结点，1个分支结点；深度最大的树的深度为n；它有1个叶结点，n-1个分支结点。4、课本P246 5.4题【解答】总结点数 n = n0 + n1 + n2 + + nm总分支数 e = n-1 = n0 + n1 + n2 + + nm-1 = m*nm + (m-1)*nm-1 + + 2*n2 + n1则有 5、课本P246 5.5题【解答】略6、课本P246 5.6题【解答】(1) 二叉树的前序序列与中序序列相同：空树或缺左子树的单支树；(2) 二叉树的中序序列与后序序列相同：空树或缺右子树的单支树；(3) 二叉树的前序序列与后序序列相同：空树或只有根结点的二叉树。7、课本P246 5.7题123456785-17答（1）（2）（3）（4）8、课本P246 5.8题（1）（2）（3）（4）9、课本P247 5.14题【解答】略10、课本P247 5.17题11、课本P248 5.18题165-19答1791415632ABCDEFIG5-18答JH12、课本P248 5.19题5-20 Huffman树C7C5C6C4C2C1C3C8WPL = （2+3）5+64+（9+14+15）3 +（16+17）2 = 22913、课本P248 5.20题5-20 Huffman树C7C5C6C4C2C1C3C8各字母的Huffman编码：C1: 0110C2: 10C3: 0000C4: 0111C5: 001C6: 010C7: 11C8: 0001电文总码长=4（3+4+5+6）+3（10+11）+2（25+36）=25714、课本P248 5.23题【解答】(1) 统计二叉树中叶结点个数int BinaryTree : leaf ( BinTreeNode * ptr ) if ( ptr = NULL ) return 0;else if ( ptr-leftChild = NULL & ptr-rightChild = NULL ) return 1;else return leaf ( ptr-leftChild ) + leaf ( ptr-rightChild ); (2) 交换每个结点的左子女和右子女void BinaryTree : exchange ( BinTreeNode * ptr ) BinTreeNode * temp;if ( ptr-leftChild != NULL | ptr-rightChild != NULL ) temp = ptr-leftChild;ptr-leftChild = ptr-rightChild;ptr-rightChild = temp;exchange ( ptr-leftChild );exchange ( ptr-rightChild );15、课本P248 5.24题【解答】template void BinaryTree : ConstructTree ( Type T , int n, int i, BinTreeNode *& ptr ) /私有函数 : 将用Tn顺序存储的完全二叉树, 以i为根的子树转换成为用二叉链表表示的/以ptr为根的完全二叉树。利用引用型参数ptr将形参的值带回实参。if ( i = n ) ptr = NULL;else ptr = new BinTreeNode ( Ti ); /建立根结点 ConstructTree ( T, n, 2*i+1, ptr-leftChild ); ConstructTree ( T, n, 2*i+2, ptr-rightChild ); 16、课本P249 5.29题【解答】template void BinaryTree:FullBinTree2Array(Type&* T)QueueBinTreeNode * Q;BinTreeNode * p = GetRoot();Q.EnQueue(p); int index = 0;while(!Q.IsEmpty()p = Q.DeQueue();Tindex+=p-data;if(p-leftChild != NULL) Q.EnQueue(p-leftChild);if(p-rightChild != NULL) Q.EnQueue(p-rightChild);17、课本P250 5.37题/缩格文本显示树template void BinaryTree : FormatDisplay( ) Stack BinTreeNode* S;S.Push(NULL);Stack S1;S1.Push(0); BinTreeNode * p = root; /初始化int level = 0; while(p !=NULL) for(int i = level; i 0; i-) cout ; co