发布时间 : 星期六 文章浙大远程教育数据结构与算法离线作业参考答案更新完毕开始阅读
int main() {
string mdata,res; cin>>mdata;
res=middletolast(mdata); for(int i=0;i if(i==0) cout< cout<<' '< cout< 【11，4，3】设二叉树的存储结构如下： data 1 J 2 0 H 0 3 2 F 0 4 3 D 9 5 7 B 4 6 5 A 0 7 8 C 0 8 0 E 0 9 10 G 0 10 1 I 0 Lchild 0 Rchild 0 其中根结点的指针值为6，Lchild，Rchild分别为结点的左、右孩子指针域，data为数据域。 （1） 画出二叉树的逻辑结构。 21 答： J E H F C B A D G I （2） 写出该树的前序、中序和后序遍历的序列。 答： 前序序列： ABCEDFHGI 中序序列： ECBHFDJIGA 后序序列： ECHFJIGDBA 【12，4，4】可以生成如下二叉排序树的关键字的初始排列有几种？请写出其中的任意4个。 答： 可以生成如上二叉排序树的关键字的初始排列有30种 任写4个序列如下： （5， 7， 6，4，2，1，3） （5， 7， 6，4，2，3，1） 22 （5， 4， 2，3，7，6，1） （5， 4， 2，1，7，6，3） 【13，4，5】给定关键字序列（11、7、16、4、22、13、5），请回答： （1） 画出依次插入到一棵空的二叉排序树后的最终二叉树（6分）； 答： 11 7 13 4 16 22 5 （2）画出依次把给定序列关键字插入一棵空的平衡二叉树后的结果（4分）； 11 5 16 4 7 13 22 【14，4，6】 假设一个文本使用的字符集为{a,b,c,d,e,f,g}, 字符的哈夫曼编码依次为{0110，10，110，111，00，0111，010}。 （1） 请根据哈夫曼编码画出此哈夫曼树，并在叶子结点中标注相应的字符； 答： 0 0 e g 1 0 1 b 1 1 0 c 1 d 1 0 （2） 若这些字符在文本中出现的频率分别为：{3,35,13,15,20,5,9}，求该哈夫曼树的带权路径 长度。 23 答： WPL=4*(3+5)+3*(9+13+15)+2*(20+35)=253 【15，5，3】用公式5.6计算一下你的身份证号码的散列值是多少。 答： 924300 【16，5，4】设有一组关键字{29，01，13，15，56，20，87，27，69，9，10，74}，散列函数为：H(key) = key % 17，采用平方探测方法解决冲突。试在0到18的散列地址空间中对该关键字序列构造散列表。 答： 首先将各个数除以17取余数：（6,2,7,1,2,7,7,6）可见20,85与46冲突，58与71冲突。将7+1再对13取余，直到无冲突，类似的6+1对13取余，最后可得H(71)=6；H（28）=2；H（46）=7；H(14)=1；H(2)=3；H(20)=8；H(85)=9；H(58)=10；哈希表存储结构： 0 1 2 3 4 5 6 7 8 9 10 14 28 2 71 46 20 85 58 平均查找长度=（1×4+2×2+3×1+4×1）/8=15/8 【17，5，4】将关键字序列（7，8，30，11，18，9，14）散列存储到散列列表中，散列表的存储空间是一个下标从0开始的一个一维数组。处理冲突采用线性探测法，散列函数为：H（key）=（key×3）mod TableSize，要求装入因子为0.7。 答： （1）由装载因子0.7，数据总数7个→存储空间长度为10→P=10 所以，构造的散列表为： 0 1 2 3 4 5 24 6 7 8 9