数据结构课程设计题目(最终版)-2012.doc

数据结构课程设计题目1、 医务室模拟。问题描述：假设只有一位医生，在一段时间内随机地来几位病人；假设病人到达的时间间隔为014分钟之间的某个随机值，每个病人所需处理时间为19分钟之间的某个随机值。试用队列结构进行模拟。实现要求 ： 要求输出医生的总等待时间和病人的平均等待时间。程序设计思路：计算机模拟事件处理时，程序按模拟环境中的事件出现顺序逐一处理，在本程序中体现为医生逐个为到达病人看病。当一个病人就诊完毕而下一位还未到达时，时间立即推进为下一位病人服务，中间时间为医生空闲时间。当一个病人还未结束之前，另有一位病人到达，则这些病人应依次排队，等候就诊。2、 招聘模拟问题描述：某集团公司为发展生产向社会公开招聘m个工种的工作人员，每个工种各有不同的编号（0，1，2，m-1）和计划招聘人数，参加招聘的人数有n个（编号为0，1，2，。，n-1）。每位应聘者可以申报两个工种，并参加公司组织的考试。公司将按应聘者的成绩，从高到低的顺序排队录取。公司的录取原则是：从高分到低分依次对每位应聘者按其第一志愿录取；当不能按第一志愿录取时，便将他的成绩扣去5分后，重新排队，并按其志愿考虑录取。程序为每个工种保留一个录取者的有序队列。录取处理循环直至招聘额满，或已对全部应聘者都做了录用处理。实现要求：要求程序输出每个工种录用者的信息（编号、成绩），以及落选者的信息（编号、成绩）。3、 组织机构问题问题描述：以青岛理工大学为例，实现对我校组织结构的管理。要求把我校的组织结构以树型结构存储，实现要求：（1） 树中每个结点保存部门名称；（2） 假定处级部门（含院系）在树中第二层，科级部门在第三层（即最后一层），软件应该能计算出处级部门有几个，有哪几个？（3） 软件可以查询某部门下面的具体编制？4、 最少换车次数问题问题描述：设某城市有n个车站，并有m条公交线路连接这些车站。设这些公交车站都是单向的，这n个车站被顺序编号为0n-1。编程序，输入该城市的公交线路数，车站个数，以及各公交线路上的各站编号。实现要求：求得从站0出发乘公交车至站n-1的最少换车次数。设计思路：利用输入信息构建一张有向图G（邻接矩阵存储），有向图的顶点表示车站，若某条公交线路经i站能到达j站，就在图G中存在一条有向边，权值为1。因此，从站x至站y的最少上车次数对应于图G中从顶点x到顶点y的最短路径长度。5、 职工工作量统计问题描述：采用随机函数产生职工的工号和他所完成产品个数的数据信息，对同一职工多次完成的产品个数进行累计，按职工完成产品数量的名次、该名次每位职工完成的产品数量、同一名次的职工人数和他们的职工号格式输出。实现要求：输出统计结果，如下所示：Order Quantity Count Number1375 31020214250 2356200 197150 2 1114 程序设计思路：采用链表结构存储有关信息，链表中的每个结点对应于一位职工。在数据采集的同时，形成一个有序链表（按完成的产品数量和工号排序）。当一个职工有新的数据输入，在累计他的完成数量时会改变原来链表的有序性，为此应对链表进行删除、查找和插入等操作。6、航空客运订票系统问题描述：航空客运订票的业务活动包括：查询航线和客票预定的信息、客票预定和办理退票等。设计一个计算机程序，使上述任务能借助计算机来完成。基本要求1）系统必须存储的数据信息（1）航线信息（9个）：飞机抵达城市、航班号、飞机号、起降时间、航班票价、票价折扣、总位置和剩余位置、已定票的客户名单。（2）客户信息（3个）：客户姓名、证件号、座位号2）系统能实现的操作和功能（1）承办订票业务：根据客户提出的要求（飞机抵达城市、起降时间、订票数量）查询该航班信息（包括票价、折扣和剩余位置），若满足要求，则为客户办理订票手续，输出座位号。（2）承办退票业务：根据客户提供的情况（航班号，订票数量），为客户办理退票手续。（3）查询功能：（较高要求）A、查询航线信息：根据飞机降落地点，输出航班号、飞机号、起降时间、航班票价、票价折扣和剩余位置等信息。B、查询客户预订信息：根据客户证件号，输出航班号、飞机号和座位号等信息。7、公园主要游览景点之间最短距离问题问题描述：图的最短路径问题是指从指定的某一点v开始，求得从该地点到图中其它各地点的最短路径。并且给出求得的最短路径的长度及途径的地点。除了完成最短路径的求解外，还能对该图进行修改，如顶点以及边的增删、边上权值的修改等。公园最短路径问题中的数据元素有：（1） 顶点数（2） 边数（3） 边的长度功能需求：要求完成以下功能：(1) 输出顶点信息：将公园内各景点输出。（2）输出边的信息：将公园内每两个位置（若两个位置之间有直接路径）的距离输出。(3) 修改：修改两个位置（若两个位置之间有直接路径）的距离，并重新输出每两个位置（若两个位置之间有直接路径）的距离；(4) 求最短路径：输出给定两点之间的最短路径的长度及途经的地点，输出任意一点与其他各点的最短路径。（较高要求）（5）删除：删除任意一条边。（6）插入：插入任意一条边。8、迷你计算器功能要求：（ 1 ）计算任意一个算术表达式的加法、减法、除法以及乘法。（ 2 ）运算数为整数和小数（ 3 ）人机界面自定义，要友好。如用户输入错误在计算之前可以修改。9、排序算法演示系统【问题描述】设计一个测试程序比较几种内部排序算法的关键字比较次数和移动次数以取得直观感受。【基本要求】(1)实现各种内部排序。包括冒泡排序，直接选择排序，希尔排序，快速排序，堆排序。(2) 待排序的元素的关键字为整数。其中的数据要用随机数产生(如10000个)，至少用5组不同的数据做比较，再使用各种算法对其进行排序，记录其排序时间，再汇总比较。(3) 演示程序以人机对话的形式进行。每次测试完毕显示各种比较指标值的列表，比较各种排序的优劣。(4) 界面友好，易与操作。采用菜单方式进行选择。10、通讯录【问题描述】设计散列表实现通讯录查找系统。【基本要求】(1) 设每个记录有下列数据项：电话号码、用户名、地址；(2) 从键盘输入各记录，分别以电话号码为关键字建立散列表；(3) 采用线性探测再散列法解决冲突；(4) 查找并显示给定电话号码的记录；(5) 通讯录信息文件保存；(6) 要求人机界面友好，使用图形化界面；【实现提示】如果不用界面编程，可用以下函数实现：主函数：根据选单的选项调用各函数，并完成相应的功能。Menu()的功能：显示英文提示选单。Quit()的功能：退出选单。Create()的功能：创建新的通讯录。Append()的功能：在通讯录的末尾写入新的信息，并返回选单。Find()：查询某人的信息，如果找到了，则显示该人的信息，如果没有则提示通讯录中没有此人的信息，并返回选单。Alter()的功能：修改某人的信息，如果未找到要修改的人，则提示通讯录中没有此人的信息，并返回选单。Delete()的功能：删除某人的信息，如果未找到要删除的人，则提示通讯录中没有此人的信息，并返回选单。List()的功能：显示通讯录中的所有记录。Save()的功能：保存通讯录中的所有记录到指定文件中。Load()的功能：从指定文件中读取通讯录中的记录。11、航班信息的查询与检索功能要求：（1）界面友好，易于操作。可采用菜单或其它人机对话方式进行选择。（2）实现对飞机航班信息进行排序与查找。可按航班的航班号、起点站、到达站、起飞时间以及到达时间等信息进行查询。每个航班记录包括八项：航班号、起点站、到达站、班期、起飞时间、到达时间、飞机型号以及票价。除了票价为数值型外，其它的均定义为字符串。航班号起点站终点站班期起飞时间到达时间飞机型号票价CA1544合肥北京1.3.510551240733960MU5341上海广州每日14201615M901280CZ3869重庆深圳2.4.608551035733101012、图书管理系统功能要求：（1）界面友好，易于操作。可采用菜单或其它人机对话方式进行选择。(2) 每种书的登记内容包括书号、书名、著作者、现存量和库存量； (3) 对书号建立索引表（线性表）以提高查找效率；(4) 系统主要功能如下： *采编入库：新购一种书，确定书号后，登记到图书帐目表中，如果表中已有，则只将库存量增加； *借阅：如果一种书的现存量大于0，则借出一本，登记借阅者的书证号和归还期限，改变现存量； *归还：注销对借阅者的登记，改变该书的现存量13、表达式求值功能要求：当用户输入一个合法的表达式后，能够返回正确的结果。能够计算的运算符包括：加、减、乘、除、括号；能够计算的数要求在实数范围内。能执行多重括号嵌套运算。对于异常表达式给出错误提示。（要求使用静态栈数据结构。）14、飞机订票系统功能要求：（1）录入：可以录入航班情况（数据可以存储在一个数据文件中，数据结构、具体数据自定）（2）查询：可以查询某个航线的情况（如，输入航班号，查询起降时间，起飞抵达城市，航班票价，票价折扣，确定航班是否满仓）；可以输入起飞抵达城市，查询飞机航班情况；（3）订票：（订票情况可以存在一个数据文件中，结构自己设定）可以订票，如果该航班已经无票，可以提供相关可选择航班；（4）退票： 可退票，退票后修改相关数据文件；客户资料有姓名，证件号，订票数量及航班情况，订单要有编号。（5）修改航班信息：当航班信息改变可以修改航班数据文件15、多项式运算功能要求：（1）输入并建立多项式；（2）输出多项式，输出形式为整数序列n,c1,e1,c2,e2,cn,en,其中n是多项式的 项数，ci和ei分别是第i项的系数和指数，序列按指数降序排列；（3）多项式a和b相加，建立多项式a+b；输出相加的多项式（4）多项式a和b相减，建立多项式a-b。输出相加的多项式（5）用带表头结点的单链表存储多项式。16、停车场管理问题描述：设停车场是一个可以停放n辆汽车的狭长通道，且只有一个大门可以供车辆进出。车辆按到达停车场时间的早晚依次从停车场最里向大门口处停放（最先到达的第一辆车放在停车场的最里面）。如果停车场已放满n辆车，则后来的车只能在停车场大门外的便道上等待，一旦停车场内有车开走，则排在便道上的第一辆车就进入停车场。停车场内如有某辆车要开走，在它之后进入停车场的车都必须先退出停车场为它让路，待其开出停车场后，这些车辆再依原来的次序进场。每辆车在离开停车场时，都应根据它在停车场内停留的时间长短交费。如果停留在便道上的车未进停车场就要离去