湖南大学数据结构第5次作业.doc

1、画出对下列存储于数组中的值执行buildheap后得到的最大值堆： 10 5 12 3 2 1 8 7 9 4先序遍历为12 10 4 1 2 9 5 8 3 7中序遍历为1 4 2 10 5 9 12 3 8 72、假设某字母表各个字母的权如下： Q Z F M T S O E 2 3 10 10 10 15 20 30(a) 按照这个字母表，一个包含n个字母的字符串采用Huffman编码在最差情况下需要多少位？怎样的串会出现最差情况？在最差的情况下需要5*n位，当所有的字母都是Q或者Z的时候。（b）按照这个字母表，包含n个字母的字符串采用Huffman编码在最佳情况下需要多少位？怎样的串会出现最佳情况？在最佳的情况下需要2*n位，当所有的字母都是E或者O的时候。（c）按照一个字母表，一个字母平均需要多少位？ （2*30 + 2*20 + 3*15 + 3*10 + 3*10 + 4*10 + 5*3+ 5*2）/100 =2.7 2.73、 编写一个算法来判断两棵树是否相同。尽可能提高算法效率，并分析算法的运行时间代价。template bool Compare(GTNode* tree1, GTNode* tree2) GTNode *num1, *num2;if (tree1 = NULL) & (tree2 != NULL) |(tree2 = NULL) & (tree1 != NULL)return 0;if (t1 = NULL) & (t2 = NULL) return 1;if (tree1-val() != tree2-val() return 0;Num1 = tree1-left_child();Num2 = tree2-left_child();while(!(num1 = NULL) & (num2 = NULL) if (!Compare(num1, num2) return false;if (num1 != NULL) num1 = num1-right_value();if (num2 != NULL) num2 = num2-right_value();O（n）4、编写出一个函数，以一棵树为输入，返回树的结点数目。要求使用下面给出的GenTree和GTNode ADT。 / General tree node ADT Template class GTNode Public:GTNode (const Elem&); / ConstructorGTNode ( ); / Destructor Elem value ( );Bool isLeaf ( );GTNode * parent ( );GTNode * right_sibling ( ); Void setValue ( Elem &); Void insert_first(GTNode * n); / Insert first childVoid insert_next(GTNode * n); / Insert next sibling Void remove_first ( ); / Remove first child Void remove_next ( ); / Remove right sibling;/General tree ADTTemplate class GenTree Private: Void printhelp ( GTNode *) ; / Print helper functionPublic :GenTree ( ); /ConstructorGenTree ( ); /DestructorVoid clear ( ); / Send nodes to free storeGTNode* root ( ); / Retrun the root / Combine two subtreesVoid newroot (Elem& , GTNode * ,GTNode* );Void print ( ); / print a tree ;template int gencount(GTNode* subroot) if (subroot = NULL) return 0int count = 1;GTNode* temp = rt-leftmost_child();while (temp != NULL) count += gen