[实验目的] 培养学生综合运用所学理论知识求解问题的能力和协作精神。
[实验原理] 针对相对复杂问题，综合数据结构、算法和相关数学知识，给出解决问题的方
案，应用相关的数据结构和算法知识设计并编写代码，给出测试数据和测试方
案，完成上机测试和运行结果分析。
[实验要求]
1. 第一、二题一人独立完成，第三题以小组为单位协作完成（每组3-4 人）；
2. 第一周内须完成一、二题，第二周完成第三题；
3. 检查程序前须提交设计报告（按提交报告的先后顺序检查程序）；
4. 每人每周提交一份设计报告（第一、二题一份，三题一份，三题重点描述自己的分工）；
5. 检查第三题时小组成员都要参与讲解（每人侧重讲自己完成部分）；
6. 每次上机必须出席，如不能到需事先提交辅导员签字的假条；
题目一: 内排序算法比较
1) 对以下6 种常用的内部排序算法进行比较：冒泡排序，直接插入排序，直接选择排
序，快速排序，希尔排序，堆排序。
2) 待排序文件中记录个数不小于10000( 其数据用伪随机数产生 )，至少采用5 组不
同的待排序文件文件作比较；比较的指标为关键字的比较次数和记录的移动次数
(一次记录交换计为3 次移动)。
3) 统计在完全正序、完全逆序情况下的关键字比较次数和记录移动次数。
4) 对结果作简单分析，包括对各组数据得出结果波动大小的解释。
题目二: 银行业务模拟系统
设计一个银行业务模拟系统，模拟银行的业务运行并计算一天中客户在银行逗留的平均
时间。银行有N 个窗口对外接待客户，从早晨银行开门起不断有客户进入银行。由于每个
窗口在某个时刻只能接待一个客户，因此在客户人数多时需在窗口前排队，对于刚进入银行
的客户，如果某个窗口的业务员正空闲，则可上任意空闲窗口前办理业务；反之，若N 个
窗口均有客户占用，他便会排在人数最少的队伍后面。
1) 用户通过人机交互的方式设定程序所需参数：银行的开门时间、关门时间；营业窗
口数目。
2) 客户的到达时间可通过人机交互、文件导入或随机生成的方式来输入。
3) 保存银行营业的工作记录：存储客户的到达时间、离开时间。
4) 显示出在某一天中整个银行系统中客户在银行逗留的平均时间。
题目三: 校园导游系统
[实验目的] 综合运用图、线性表、查找等数据结构知识，掌握、提高分析、设计、实现及
测试程序的综合能力。
[实验内容及要求]
设计校园导游程序，完成校园信息的维护以及为来访的客人提供服务。
（1） 记录校内各景点信息：景点名称、代号、简介等；
（2） 记录景点之间道路信息包括：两点距离、所需时间等相关信息；
（3） 数据的输入可以是键盘输入或文件导入；
（4） 提供对校园景点信息的编辑（如：添加、删除、修改等）的功能；
（5） 为来访客人提供图中任意景点相关信息的查询；
（6） 为来访客人提供从校门口到图中任意景点的问路查询，查询出距离最短的往返方案；
（7） 为来访客人提供图中任意景点间的问路查询，查询出距离最短的行走方案
[测试数据]
自行设计校园平面图，所含景点不少于10 个。至少有2 个节点间路径数量大于1 且路
径长度不等。
[实现提示]
以无向图表示校园平面图，顶点表示各景点、边表示道路，边上的权值为距离。问路查
询过程即为查找指定任意两点间的最短路径。