《数据结构》第五章习题参考答案.docx
数据结构第五章习题参考答案一、推断题（在正确说法的题后括号中打“ J "，错误说法的题后括号中打“ X ”） 1、知道一颗树的先序序列和后序序列可唯一确定这颗树。（X ）2、二叉树的左右子树可随意交换。（X ）3、任何一颗二叉树的叶子节点在先序、中序和后序遍历序列中的相对次序不发 生变更。（V ）4、哈夫曼树是带权路径最短的树，路径上权值较大的结点离根较近。（V ）5、用一维数组存储二叉树时，总是以前序遍历依次存储结点。（X ）6、完全二叉树中，若一个结点没有左孩子，则它必是叶子结点。（ V ）7、一棵树中的叶子数肯定等于与其对应的二叉树的叶子数。（ X ）8、度为2的树就是二叉树。（X ）二、单项选择题1 .具有10个叶结点的二叉树中有（B ）个度为2的结点。A. 8B. 9C. 10D. 112 .树的后根遍历序列等同于该树对应的二叉树的（B ）oA.先序序列B.中序序列C.后序序列3、二叉树的先序遍历和中序遍历如下：先序遍历：EFHIGJK；中序遍历：HFIEJKG。该 二叉树根的右子树的根是：（C ）A. EB.F C. G D. H04、在下述结论中，正确的是（ D ）o具有n个结点的完全二叉树的深度k必为log2（n+l）i ；二叉树的度为2；二叉树的左右子树可随意交换；一棵深度为k（kNl）且有2仁1个结点的二叉树称为满二叉树。A.B.C.D.5、某二叉树的后序遍历序列与先序遍历序列正好相反，则该二叉树肯定是（D ）。A.空或只有一个结点B.完全二叉树C.二叉排序树D.高度等于其结点数三、填空题1、对于一棵具有n个结点的二叉树，对应二叉链接表中指针总数为2n个，其中 ml个用于指向孩子结点,n+1个指针空闲着。2、一棵深度为k（kKl）的满二叉树有2匕1个叶子结点。3、在完全二叉树中，编号为i和j的两个结点处于同一层的条件是F Hog 2 i-i二log 2j-!o? 4、某二叉树有20(n0)个叶子结点，有30个结点仅有一个孩子(nl),则该二 叉树的总结点数为69。(n=n0+nl+n2)(而n0=n2+l)5、完全二叉树中，结点个数为n,则编号最大的分支结点的编号为5/2O6、已知二叉树前序为ABDEGCF,中序为DBGEACF,则后序肯定是 DGEBFCAO四、综合题1、设二叉树采纳二叉链表存储结构，结点的数据域data为字符类型。阅读下列 算法，并回答问题：(1)对于如图所示的二叉树，写出执行函数function的输出结果；(2)简述函数function的功能。void function(B inTree T)(Stack< BinTreeNode*> 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« p->data;)if(!S.IsEmpty ()q=S.GetTop();p=q-> rightChild;) while (!S.IsEmpty ();(l)DBFGECA函数function的功能是对二叉树进行后序遍历。2、课本P246 5.2题【解答】1234-156-17-18-1-1-1-19二叉树图略3、课本P246 5.3题【解答】结点个数为时，深度最小的树的深度为2；它有T个叶结点，1个分支结点; 深度最大的树的深度为；它有1个叶结点，个分支结点。4、课本P246 5.4题【解答】总结点数=o+i + 2+ + nm总分支数 e-n- - /?()+ n + ri2+ + ntn-l-m*n,n + (2-1)*机一1 + + 2*2 + n则有 o=之+ 1 3=2)5、课本P246 5.5题【解答】略6、课本P246 5.6题【解答】(1)二叉树的前序序列与中序序列相同：空树或缺左子树的单支树； (2)二叉树的中序序列与后序序列相同：空树或缺右子树的单支树；(3)二叉树的前序序列与后序序列相同：空树或只有根结点的二叉树。7、课本P246 5.7题(1) X (2) V (3) X (4) V8、课本P246 5.8题(1) X (2) X (3) V (4) X9、课本 P247 5. 14 题【解答】略10、课本 P247 5. 17 题11、课本 P248 5. 18 题12、课本 P248 5. 19 题WPL=(2+3) X5+6X4+ (9+14+15) X3+ (16+17) X2 = 22913、课本 P248 5.20 题各字母的Huffman编码：Cl:0110C2: 10C3: 0000C4:0111C5: 001C6:010C7: 11C8: 0001电文总码长=4X (3+4+5+6) +3X (10+11)+2X (25+36)=25714、课本 P248 5.23 题【解答】(1)统计二叉树中叶结点个数int Binar)Tree<Type> : leaf( BinTreeNodeypO * ptr) if (ptr = NULL ) return 0;else if (ptr-yleftChild = NULL && ptr-yrightChild = NULL ) return 1;else return leaf (pti->leftChild) + lea以ptr->rightChild);)(2)交换每个结点的左子女和右子女void Binary'Tree<Type> : exchange ( BinTreeNode<Type> * ptr) BinTreeNode<Type> * temp;if (pti->leftChild != NULL pti-> rightChild != NULL )temp = ptr> leftChild;pti-y leftChild = ptLrightChild; pti'-'>rightChild = temp;exchange (ptr-yleftChild);exchange (ptr>rightChi/d);15、课本 P248 5.24 题【解答】template <class Type>void Binary'Tree<Type> : ConstructTree ( Type T , int ，int z, BbiTreeNode<Type> *& ptr) 私有函数：将用Tn依次存储的完全二叉树，以i为根的子树转换成为用二叉链表表示的 /以疗为根的完全二叉树。利用引用型参数次将形参的值带回实参。if (i >= n ) ptr = NULL：else ptr - new BinTreeNode<Vy> (); 建立根结点ConstructTree ( Tf几,2*z+/, ptr->leftChild);ConstructTree ( T,n,2*i+2, ptr->rightChild);16、课本 P249 5.29 题【解答】template <class Type> void BinaryTree<Type>:FullBinTree2Array(Type&* T)Queue<BinTreeNode<Type> *> Q;BinTreeNode<Type> * p = GetRoot();Q.EnQueue(p);int index = 0;while(! Q.IsEmpty () p = Q.DeQueue();T index+4- |=p->data;if(p->leftChild != NULL) Q.EnQueue(p->leftChild);if(p->rightChild != NULL) Q.EnQueue(p->rightChild);)17、课本 P250 5.37 题缩格文本显示树template <class Type>void BinaryTree<Type> : FormatDisplay() Stack <BinTreeNode<Type>* > S;S.Push(NULL);Stack <int> S1;Sl.Push(O);BinTreeNode<Type> * p = root;初始化int level = 0;while(p !=NULL)for(int i = level; i > 0; i-) cout«n ”；cout « p->data « endl;if( p->rightChild != NULL)S.Push ( p->rightChild ); 预留右子树指针在栈中 Sl.Push(level);)if (p->leftChild !=NULL) level+；p = p->leftChild; /进左子树)else/左子树为空，进右子树(p = S.Pop(); level=Sl.Pop();)
