《数据结构》第五章习题参考答案.doc
-作者xxxx-日期xxxx数据结构第五章习题参考答案【精品文档】数据结构第五章习题参考答案一、判断题（在正确说法的题后括号中打“”，错误说法的题后括号中打“×”）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< 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 ();(1)DBFGECA(2) 函数function的功能是对二叉树进行后序遍历。2、课本P246 5.2题【解答】1234-156-17-18-1-1-1-19二叉树图略3、课本P246题【解答】结点个数为n时，深度最小的树的深度为2；它有n-1个叶结点，1个分支结点；深度最大的树的深度为n；它有1个叶结点，n-1个分支结点。4、课本P246题【解答】总结点数 n = n0 + n1 + n2 + + nm总分支数 e = n-1 = n0 + n1 + n2 + + nm-1 = m*nm + (m-1)*nm-1 + + 2*n2 + n1则有 5、课本P246题【解答】略6、课本P246【解答】(1) 二叉树的前序序列与中序序列相同：空树或缺左子树的单支树；(2) 二叉树的中序序列与后序序列相同：空树或缺右子树的单支树；(3) 二叉树的前序序列与后序序列相同：空树或只有根结点的二叉树。7、课本P246123456785-17答（1）×（2）（3）×（4）8、课本P246（1）×（2）×（3）（4）×9、课本P247【解答】略10、课本P24711、课本P248165-19答1791415632ABCDEFIG5-18答JH12、课本P2485-20 Huffman树C7C5C6C4C2C1C3C8WPL = （2+3）×5+6×4+（9+14+15）×3 +（16+17）×2 = 22913、课本P2485-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<Type> : leaf ( BinTreeNode<Type> * 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<Type> : exchange ( BinTreeNode<Type> * ptr ) BinTreeNode<Type> * 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【解答】template <class Type> void BinaryTree<Type> : ConstructTree ( Type T , int n, int i, BinTreeNode<Type> *& ptr ) /私有函数 : 将用Tn顺序存储的完全二叉树, 以i为根的子树转换成为用二叉链表表示的/以ptr为根的完全二叉树。利用引用型参数ptr将形参的值带回实参。if ( i >= n ) ptr = NULL;else ptr = new BinTreeNode<Type> ( Ti ); /建立根结点 ConstructTree ( T, n, 2*i+1, ptr->leftChild ); ConstructTree ( T, n, 2*i+2, ptr->rightChild ); 16、课本P249【解答】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();Tindex+=p->data;if(p->leftChild != NULL) Q.EnQueue(p->leftChild);if(p->rightChild != NULL) Q.EnQueue(p->rightChild);17、课本P250/缩格文本显示树template <class Type> void BinaryTree<Type> : FormatDisplay( ) Stack <BinTreeNode<Type>* > S;S.Push(NULL);Stack <int> S1;S1.Push(0); BinTreeNode<Type> * p = root; /初始化int level = 0; while(p !=NULL) for(int i = level; i > 0; i-) cout<<" " cout << p->data << endl; if ( p->rightChild != NULL ) S.Push ( p->rightChild ); /预留右子树指针在栈中 S1.Push(level);if ( p->leftChild != NULL )level+; p = p->leftChild; /进左子树 else /左子树为空, 进右子树 p = S.Pop(); level=S1.Pop(); 【精品文档】
