2014级DS课程设计题目

2014级《数据结构课程设计》题目（共7个题目）

1、集合的运算（难度系数★★）

集合是一种松散的结构，可用其他结构来表示。请使用顺序表或链表，来表示集合并实现其基本操作，相信你会尽量让时间效率高。

（1）一般规定集合中元素彼此相异，故需实现将表中重复元素去掉的操作,使其成为集合。

（2）实现集合A，B的交，并，补，差，补运算（A∩B , A∪B , A-B ,~A） 以及判断A = B ，A ? B ；简单讨论这些基本操作所需时间复杂度 。

（3）设全集为小写字母集合，请编程随机生成集合A、 B、 C （集合的．．基数和元素都随机）；并使用你的基本操作编程求：

B – A 和 （A∪B）∩（A∪B∪C） - （A ∩ (A ∪ ( B- C) ) 判断得到的这两个集合，是否有相等或包含关系；若有，你能证明吗？

（4）其实，用线性表来表示集合并不算好主意。请查询相关资料，并思考在计算机中表示集合，时空效率更高、实现也更简单的方法是什么？请简述或实现之。

2、仓库管理（难度系数★★）

某电子公司仓库中有若干批次的同一种电脑，按价格、数量来存储。

（1） 初始化n批不同价格电脑入库； （2） 出库：销售m台价格为p的电脑； （3） 入库：新到m台价格为p的电脑；

（4） 盘点：电脑的总台数，总金额，最高价，最低价，平均价格。

注：每个数据元素含有价格与数量；同一价格的电脑存储为一个数据元素。

提示：本题可以用

（1） 顺序表； （2） 有序表； （3） 单链表；

（4） 有序循环链表（较好）

1

3、洗车场的调度（难度系数★★★）

某洗车场，洗车车间有若干“洗车位”（编号1,2,3,4…），车间被设计为狭长通道，仅有一个大门供出入。汽车按到达先后次序依次进入各洗车位，若洗车位被占满，则进入洗车场的车辆必须在车间外的“等候区”等候，一旦有车完成洗车驶出车间后，等候区的第一辆车即可进入；

当车欲驶离车间时，因车间狭长，在它之后驶入的车辆必须退出车间为其让路。待其驶出后，这些车辆再按原来的次序进入车间继续洗车。

设计这样一个洗车车间的调度模拟程序。

选作扩展功能：区分VIP客户和普通客户，VIP客户到来后可优先进入车间

要求应有3个必须模块： 【模块1，汽车进入停车场管理】

登记进入洗车场的车牌号并对该车进行调度，其中调度过程要即时反馈。例如(假设有5个洗车位)，洗车位1,2,3,4 正分别被001,002,003,004汽车占有，当牌照为005的汽车到来后，屏幕应显示：

牌照005的汽车进入5号洗车位 再来牌照为006的汽车，屏幕应显示：

牌照006的汽车进入等待区 【模块2：汽车驶离停车场管理】

为离开车间的车辆作调度，并反馈相关车辆状态。例如，洗车位分别占据着001 002 003 004 005 的汽车，等待区顺序为006 007在等候，当003欲驶离时，应给出如下信息：

005暂时退出车间, 004 暂时退出车间； 003驶离洗车场

004重回3号洗车位 005重回4号洗车位 006 进入车间5号洗车位； 【模块3：停车场状态查询】 用来显示各洗车位和等候区的状态；

要求界面设计简洁友好；用户操作有提示，用户操作产生的调度过程要有显示，信息表达精炼准确；测试要求：停车场状态应保持合理，比如不允许出现洗车位空闲而等候区非空的情形。

2

4、字符编码及电文译码（难度系数★★★）

输入一行字符，允许进行修改。当刚输入的一个字符错误时，补进一个退格符“#”，表示前一个字符无效；当错误较多时，键入一个“@”退行符，表示当前行中“@”之前的字符均无效。 例如输入：123@456##789 得到字符串：4789 （1） 统计字符出现的频度（次数） （2） 并对字符进行01编码 （3） 计算带权路径长度 （4） 按照编码，对给定字符串进行编码 （5） 对已有的01编码串进行译码

注：（4）字符串中的字符，应该是（1）中出现过的 提示： （1） 输入一行字符算法参考P50算法3.2

（2） 编码可以为等长码，位数为log2n向上取整，其中n为字符个数 （3） 编码可采取赫夫曼编码（较好）

5、最低投入修高铁（难度系数★★★★）

已知n个城市的地图，顶点为城市，边上的权值为2个城市之间的距离，现在要在n个城市之间建立高铁互通网络，修高铁的成本与城市之间的距离成正比。既保证城市之间互通，又使得修高铁的费用最低，请给出具体要修那些线路。 （1） 利用Prim算法求解 （2） 利用Kruskal算法求解 （3） 比较2个算法的适应性（稀疏图，稠密图） 提示： （1） Prim算法存储结构为邻接矩阵 （2） Kruskal算法存储结构如下：

顶点结点：

typedef struct { char data; //顶点信息 Int jihe; //顶点是否联通 }VEX; 边结点：

typedef struct { int vexh, vext; //边依附的两顶点的下标 Int weight; //边的权值 Int flag; //标志域

}EDGE;

3

6、模拟竞价系统（难度系数★★★★）

大米手机一贯采取饥饿营销，拥有大批“米粉”。该公司欲新推一款产品，宣称因产能所限，首批货将采取客户通过手机号注册后竞拍的形式。当有5万名用户参与竞价后，再根据实际产量来确定中标者，价高者得（若报价相同，先出价者得）。注意：产品数量在竞拍期间未知，竞价完毕根据备货量确定！

为了激励高价，系统即时反馈当前的最高报价。为防止恶意虚报高价，破坏竞拍，管理员不定时地监控当前最高价，并与可疑虚报者确认，若确认虚报，则删除当前最高价。竞价结束后，备货数量可能是1台也许是100万台。

请您为该公司设计这样一个系统，来模拟竞拍过程。

考虑到实际运行的规模，请选择合适的数据结构和算法以保证系统即时性。 模拟系统应至少有如下模块：

接受报价模块：添加一条报价信息，并显示当前最高价； 删除报价模块：删除当前最高报价信息；

输出竞拍结果：根据给定产品数量，列出中标客户的信息（手机号及报价）； 例如，准备测试数据如左；

运行时，输入A(添加一条报价)或D(删除当前最大报价)，运行情况如右 （红色为用户输入，蓝色为系统的输出）：

13469987555 13971845666 18945334222 15943789000 13478922444 13567779999 13289887777 15678878888 15717121141 13565341668 13478907764

报

800 最高价：

价 报

1340 A 13971845666 1340 最高价：

价 报

880 A 18945334222 880 最高价：

价 报

1500 A 15943789000 1500 最高价：

价 报

99900 A 13478922444 99900 最高价：

价 报

1551 A 13567779999 1551 最高价：

价 被

1280 D 13478922444

删 报

1666 A 13289887777 1280 最高价：

价 报

1340 A 15678878888 1666 最高价：

价 报

1456 A 15717121141 1340 最高价：

价 报

1000 A 13565341668 1456 最高价：

价 报

A 13478907764 1000 最高价：

价

有效报价：9 输入手机数量：5 竞标结果如下： 800

A 13469987555

4

800 1340 1340 1500 99900 99900 1551 1666 1666 1666 1666

15678878888 13567779999 15943789000 13565341668 15717121141

1666 1551 1500 1456 1340

经测试，保证系统的正确性后，请简单修改系统以进行压力测试（比如3000人竞争600部产品）：随机生成测试数据（报价信息或删除命令）保存在文本文件中（为方便生成数据，以顺序的ID流水号代替手机号；并手动在文件中插入一些D（删除）操作），系统将数据文件作为输入（用fread函数重定向输入设备到指定文件）。并统计系统整个运行过程中的比较、移动（赋值） 操作的次数。

请与其他同课题小组商定数据格式，用统一数据文件来PK系统效率吧！

7、小镇导航（难度系数★★★★★）

某小镇路口众多，拥堵严重，每个路口有专门交警负责。于是，各交警对各自负责路口的转向进行限制：在路口的各入口前都设置指示牌，不同方向进入的车辆只能对应指示牌转向。于是，小镇开车出行不怎么费油，然而特别费智商！

请你设计一个程序，帮助悲催的司机们找到出行的最短路径吧（即经过的路．．．．口最少），当然也可能根本就不存在路径。

交通图的设置格式：进入路口的方向（N E W S 分别代表 北 东 西 南，即上右左下 ）不同，允许转向也不同（L R F 分别代表允许左 右 直行）。

例如，下左图第一行第二列的路口的字符串： 1 2 WLF NR ER # 代表 1行2列路口的三个路标：若从W(西，左)进入路口，可以L(左拐)，F(直行)；若从N（北上）或者E(西右)进入，则只能R(右拐)。（#只是分隔标志）。

5

输入：道路数据 3 1 N 3 3 (向N上进入3,1; 终点为3,3) 1 1 WL NR # 1 2 WLF NR ER # 1 3 NL ER # 2 1 SL WR NF # 2 2 SL WF ELF # 2 3 SFR EL # （此为上左图的交通图） 试一试上面的右图吧！！！！小明欲从4,2到4,3去约会，苦思三个月也没头绪

，

输出：最短路径或者无解 (3,1) (2,1) (1,1) (1,2) (2,2) (2,3) (1,3) (1,2) (1,1) (2,1) (2,2) (1,2) (1,3) (2,3) (3,3) 小明说：“深度优先搜索（DFS）能找到路径，广度优先搜索（BFS）能找到最短路径；找到最短路径最好，但如果您只熟悉DFS，随便找条路径也行啊！”

6

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库2014级DS课程设计题目在线全文阅读。