“数据结构”作业
作业应按时独立完成，在本次作业的截止日期之前交给你的辅导老师。 超过截止日期一周以内按照50％计入成绩，超过日期一周以上不计成绩。 平时作业和上机的情况在整个课程的最终成绩中占30％。
作业写在作业本或者纸上，标明姓名学号。算法请尽可能写得清晰规整，加上必要的注释。
最好在上机时交给你的辅导老师，其他情况请自己与辅导老师联系（参考主页里的教学小组信息）。
序号 布置日期 截止日期 作业内容
5 12.12 12.18 教科书第一版第208页第19, 20题，第237第9题

即第二版：244页第12、13题；另一题如下：
9）（第8章习题），请根据堆的定义判断下述序列是否为堆。若不是，请按堆的构造方法将其调整为堆：
1）{50, 36, 41, 19, 23, 4, 20, 18, 12, 22}
2）{86, 5, 47, 1, 41, 11, 59, 15, 48, 19}

4 11.18 12.4 第207-208页第3、6、14、17、18题
（第二版，198页算法第3题，复习第4题；243页复习第4、7、8、9题）
3 11.14 11.21 第155-156页，第5，6，9，11，12，13，18题
（第2版，166-167页，第1，14，2，7，8，9，6题）

补充：给出下面一组字符及其出现频率，请求出相应的哈夫曼编码：a:12，b:10，c:7，e:35，f:14，g:20，h:3，i:16，j:2，k:4。（字符后的数是其出现频率）

2 10.17 10.24 字符串模式匹配：教科书（第一版）64页第6题的(b)和(c)，第7题（第二版83页“复习题”2题的(b)和(c)，第3题）。

算法：（第1版）64页3，5题（第二版83页算法2题，84页4题）

1 9.21 9.28 1，教材48页第2题（新版教材67页第3题）。注意，对两种表的操作都不允许另外分配空间。也就是说，对顺序表的逆序算法应通过在数组里调整元素位置的方式实现，对链接表的逆序算法应通过修改表中链接指针的方式实现。

2，教材48页第9题（新版68页第12题）。

3，请对线性表的顺序实现和链接实现做详细对比，从存储使用，各种操作的时间复杂性和实现的难度等方面加以比较。请提出两种情况，你认为在一种情况中更应该采用顺序实现，另一种情况中更应该采用链接实现，并请说明为什么。

写上述算法时可以假定已经有了书上定义的数据类型，只需定义适当的C函数。

本页及相关页面（除另声明者外）由裘宗燕创建维护，可自由用于各种学习活动。其他使用需得到作者许可。