2014级DS课程设计题目

《2014级DS课程设计题目》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、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∪

2、B）∩（A∪B∪C）-（A∩(A∪(B-C))判断得到的这两个集合，是否有相等或包含关系；若有，你能证明吗？（4）其实，用线性表来表示集合并不算好主意。请查询相关资料，并思考在计算机中表示集合，时空效率更高、实现也更简单的方法是什么？请简述或实现之。2、仓库管理（难度系数★★）某电子公司仓库中有若干批次的同一种电脑，按价格、数量来存储。（1）初始化n批不同价格电脑入库；（2）出库：销售m台价格为p的电脑；（3）入库：新到m台价格为p的电脑；（4）盘点：电脑的总台数，总金额，最高价，最低价，平均价格。注：每个数据元素含有价格与数量；

3、同一价格的电脑存储为一个数据元素。提示：本题可以用（1）顺序表；（2）有序表；（3）单链表；（4）有序循环链表（较好）63、洗车场的调度（难度系数★★★）某洗车场，洗车车间有若干“洗车位”（编号1,2,3,4…），车间被设计为狭长通道，仅有一个大门供出入。汽车按到达先后次序依次进入各洗车位，若洗车位被占满，则进入洗车场的车辆必须在车间外的“等候区”等候，一旦有车完成洗车驶出车间后，等候区的第一辆车即可进入；当车欲驶离车间时，因车间狭长，在它之后驶入的车辆必须退出车间为其让路。待其驶出后，这些车辆再按原来的次序进入车间继续洗车。设计

4、这样一个洗车车间的调度模拟程序。选作扩展功能：区分VIP客户和普通客户，VIP客户到来后可优先进入车间要求应有3个必须模块：【模块1，汽车进入停车场管理】登记进入洗车场的车牌号并对该车进行调度，其中调度过程要即时反馈。例如(假设有5个洗车位)，洗车位1,2,3,4正分别被001,002,003,004汽车占有，当牌照为005的汽车到来后，屏幕应显示：牌照005的汽车进入5号洗车位再来牌照为006的汽车，屏幕应显示：牌照006的汽车进入等待区【模块2：汽车驶离停车场管理】为离开车间的车辆作调度，并反馈相关车辆状态。例如，洗车位分别占

5、据着001002003004005的汽车，等待区顺序为006007在等候，当003欲驶离时，应给出如下信息：005暂时退出车间,004暂时退出车间；003驶离洗车场004重回3号洗车位005重回4号洗车位006进入车间5号洗车位；【模块3：停车场状态查询】用来显示各洗车位和等候区的状态；要求界面设计简洁友好；用户操作有提示，用户操作产生的调度过程要有显示，信息表达精炼准确；测试要求：停车场状态应保持合理，比如不允许出现洗车位空闲而等候区非空的情形。64、字符编码及电文译码（难度系数★★★）输入一行字符，允许进行修改。当刚输入的一个

6、字符错误时，补进一个退格符“#”，表示前一个字符无效；当错误较多时，键入一个“@”退行符，表示当前行中“@”之前的字符均无效。例如输入：123@456##789得到字符串：4789（1）统计字符出现的频度（次数）（2）并对字符进行01编码（3）计算带权路径长度（4）按照编码，对给定字符串进行编码（5）对已有的01编码串进行译码注：（4）字符串中的字符，应该是（1）中出现过的提示：（1）输入一行字符算法参考P50算法3.2（2）编码可以为等长码，位数为log2n向上取整，其中n为字符个数（3）编码可采取赫夫曼编码（较好）5、最低投入

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

8、pedefstruct{intvexh,vext;//边依附的两顶点的下标Intweight;//边的权值Intflag;//标志域}EDGE;66、模拟竞价系统（难度系数★★★★）大米手机一贯采取饥饿营销，拥有大批“米粉”。该公司欲新推一款产品，