浙大远程教育数据结构与算法离线作业参考答案

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