数据结构课程作业汇总

第一个分组项目：**号码本。

创建**号码本可以存储每个人的（姓名，地址，**号码），一个人可以有多个**号码，但所有**号码不能有重复；

可以根据**号码对人的信息进行排序；

可以根据姓名查询这个人的所有**号码和地址；如果查询失败，则询问是否添加这个人的信息到**号码本中，如果”yes”,则根据输入的姓名，**号码，地址等信息添加到**号码本程序中；

可以根据**号码查询对应的人的信息：姓名和地址，并删除或修改该人的信息；要求查询和排序速度尽量快。

第一次独立项目：不重复随机数。

假设要生成前n个自然数的一个随机置换，如和就是一个合法置换；但就不是，因为1出现2次而3没有。假设我们有一个随机数生成器randint(i,j),它以相同概率生成i到j之间的整数，下面是三个算法。

1）如下填入从a[0]到a[n-1]的数组a:为了填入a[i],生成不同于a[0],a[1],.a[i-1]之间的随机数时，才将其填入a[i]

2）同算法1，但保留一个称为used数组的附加数组，当一个随机数ram最初被放入数组a的时候，used[ram]=1.这就是说，当用一个随机数填入a[i]时，用used数组来测试该随机数是否已经被使用。

3）首先填写数组使得a[i]=i+1;然后for(i=1;iswap(&a[i],&a[randint(0,i)])输入与输出要求。

输入为一个整数n；

输出为前n个自然数的一个随机置换，用，号分隔，最后一个输出为当前算法的运行时间，然后回车换行用同样格式输出下一个算法。一共有3组算法，所以一共输出3次。注意：

1、逗号为英文输入法中逗号；2、程序检测到错误，输出error3、任意多余输出视为错误。例子：输入5输出为1,2,3,4,5,02,1,3,4,5,03,2,1,4,5,0

第一次课后作业：

1.证明o(f)+o(g)=o(f+g)

2.将下列5个函数按渐近增长率由低至高进行排序，要求写出比较过程。（各log函数的底数都为。

第二个分组项目：走迷宫。

基本要求：从文件中读出迷宫数据，寻找并打印路径通路；存储迷宫数据到文件。文件中迷宫地图数据格式为：长宽入口出口迷宫地图数据。

迷宫地图数据由01二进制组成，1表示墙壁，0表示通路可以采用字符显示迷宫地图和路径，比如□表示通路，▇表示墙壁，※表示找到的路径，如图1所示。

也可以采用windows窗体设计和绘制迷宫地图和路径中级要求：寻找多入口多出口地图的所有通路高级要求：自动生成迷宫地图。

第二次作业：课本244页简答题

第二次独立项目：聪明的推销员一公司有n位推销员，预将公司的产品推销给n为顾客。由于顾客对公司产品的喜爱程度不一样，推销难度也是不一样的，因此公司根据顾客对公司的喜爱程度对每位顾客的推销难度进行了评分并将平分结果发给每位推销员。

同时根据推销员的经验也对每位推销员进行了评分，位数越大的推销员经验越多。公司要求经验越多的推销员负责越难推销的顾客。各位推销员都是电脑高手，设计了程序最快的找到要推销的目标进行产品推销。

现你扮演第k位推销员，当你拿到公司给你的各位顾客的推销难度平分后，设计程序要求查询速度尽量快的找到你要推销的目标进行推销。分析算法复杂度。

第三次分组项目：旅游背包问题。

第i个物体大小为si,箱子尺寸为c（maxsi（具体的描述见ppt：4-2第三个项目旅游背包解决思路）

第三个独立项目：实现以上的表达式树类。

1）能够根据任一一中缀表达式构建表达式树。

2）能够通过对树进行遍历获得表达式树所表示的中缀表达式（来自ppt4-4二叉树的遍历）

第三次作业：

第二章习题：选择题填空题简答题算法设计题4

第三章习题：选择题填空题

第四个分组项目：路由协议设计详见ppt5-1第四个项目分析。

第四个独立项目：如何编程实现将一个文件利用霍夫曼最优编码进行压缩和解压缩？（ppt4-7哈夫曼编码）

第四次作业：

4.7习题（p175）一、填空题二、选择题

三、简答题4：（1）（3）四、算法设计题（ppt没找到）