数据结构课程设计题目（最终版）.pdfVIP

数据结构课程设计题目（最终版）

数据结构课程设计题目

1、医务室模拟。

问题描述：假设只有一位医生，在一段时间内随机地来几位病人；

假设病人到达的时间间隔为0~14分钟之间的某个随机值，每个病人

所需处理时间为1~9分钟之间的某个随机值。试用队列结构进行模拟。

实现要求：要求输出医生的总等待时间和病人的平均等待时间。

程序设计思路：计算机模拟事件处理时，程序按模拟环境中的事

件出现顺序逐一处理，在本程序中体现为医生逐个为到达病人看病。

当一个病人就诊完毕而下一位还未到达时，时间立即推进为下一位病

人服务，中间时间为医生空闲时间。当一个病人还未结束之前，另有

一位病人到达，则这些病人应依次排队，等候就诊。

2、招聘模拟

问题描述：某集团公司为发展生产向社会公开招聘m个工种的工

作人员，每个工种各有不同的编号（0，1，2，…，m-1）和计划招聘

人数，参加招聘的人数有n个（编号为0，1，2，。。。，n-1）。每

位应聘者可以申报两个工种，并参加公司组织的考试。公司将按应聘

者的成绩，从高到低的顺序排队录取。公司的录取原则是：从高分到

低分依次对每位应聘者按其第一志愿录取；当不能按第一志愿录取时，

便将他的成绩扣去5分后，重新排队，并按其志愿考虑录取。

程序为每个工种保留一个录取者的有序队列。录取处理循环直至

招聘额满，或已对全部应聘者都做了录用处理。

实现要求：要求程序输出每个工种录用者的信息（编号、成绩），

以及落选者的信息（编号、成绩）。

3、组织机构问题

问题描述：以青岛理工大学为例，实现对我校组织结构的管理。

要求把我校的组织结构以树型结构存储，实现要求：

（1）树中每个结点保存部门名称；

（2）假定处级部门（含院系）在树中第二层，科级部门在第三层

（即最后一层），软件应该能计算出处级部门有几个，有哪几个？

（3）软件可以查询某部门下面的具体编制？

4、最少换车次数问题

问题描述：设某城市有n个车站，并有m条公交线路连接这些车

站。设这些公交车站都是单向的，这n个车站被顺序编号为0~n-1。

编程序，输入该城市的公交线路数，车站个数，以及各公交线路上的

各站编号。

实现要求：求得从站0出发乘公交车至站n-1的最少换车次数。

设计思路：利用输入信息构建一张有向图G（邻接矩阵存储），

有向图的顶点表示车站，若某条公交线路经i站能到达j站，就在图G

中存在一条有向边，权值为1。因此，从站x至站y的最少上车次数对

应于图G中从顶点x到顶点y的最短路径长度。

5、职工工作量统计

问题描述：采用随机函数产生职工的工号和他所完成产品个数的

数据信息，对同一职工多次完成的产品个数进行累计，按职工完成产

品数量的名次、该名次每位职工完成的产品数量、同一名次的职工人

数和他们的职工号格式输出。

实现要求：输出统计结果，如下所示：

OrderQuantityCountNumber

137****2021

4250235

620019

715021114

……………

程序设计思路：采用链表结构存储有关信息，链表中的每个结点

对应于一位职工。在数据采集的同时，形成一个有序链表（按完成的

产品数量和工号排序）。当一个职工有新的数据输入，在累计他的完

成数量时会改变原来链表的有序性，为此应对链表进行删除、查找和

插入等操作。

6、航空客运订票系统

问题描述：航空客运订票的业务活动包括：查询航线和客票预定

的信息、客票预定和办理退票等。设计一个计算机程序，使上述任务

能借助计算机来完成。

基本要求

1）系统必须存储的数据信息

（1）航线信息（9个）：飞机抵达城市、航班号、飞机号、起降

时间、航班票价、票价折扣、总位