资源描述：
《数据课程设计-实验指导书》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、实验三课程设计题选选题一：图基本操作的实现【问题描述】很多涉及图上的操作的算法都是以图的遍历操作为基础的。试编写一个程序，完成在连通无向图上访问图中全部顶点及相关基本操作。【基本要求】以图的邻接表为存储结构实现连通无向图的深度优先和广度优先遍历。以川户指定的顶点为起点，分别输出每种遍历下的结点访问序列各相应生成树的边集。【测试数据】自行设计一个至少含10个顶点、14条边的无相连通途。【实现提示】设图的顶点不超过30个，每个顶点用一个编号表示（如果一个图有n个顶点，则它们的编号分别为1,2,…,n）。通过输入图
2、的全部边输入一个图，每条边为一个数对，可以对边的顺序作出某种限制。注意，生成树的边是冇向的，顶点顺序不能颠倒。【选做内容】借助于栈类型，用非递归算法实现深度优先遍历。以邻接多重表为存储结构，建立深度优先牛成树和广度优先牛成树，再按树形输出牛成树。图的路径遍历要比顶点遍历具冇更为广泛的应用。试写一个图的路径遍历算法，求从武汉到北京中途不经过郑州的所有简单路径及其里程。选题二教学计划编排问题【问题描述】大学的每个专业都要制定教学计划。假设任何专业都有固定的学习年限，每学年含两个学期，每学期的时间长度和学分上限值均
3、和等。每个专业开设的课程都是确定的，而且课程开设时间的安排必须满足先修关系。每门课程冇哪些先修课程是确定的，可以冇任意多门,也可以没有。每门课恰好占一个学期。试在这样的前捉下设计一个教学计划编制程序。【基本要求】（1）输出参数包括：学期总数、一学期的学分上限、每门课的课程号（固定为占3位的字母和数字串）、学分和直接先修课程的课程号。（2）允许用户制定下列两种编排策略之一：一是使学牛在各学期中的学习负担尽量均匀;二是使课程尽量地集中在前儿个学期屮。（3）若根据给定的条件无解，则报告适当的信息；否则将教学计划输出
4、到用户指定的文件中。教学计划的表格格式自行设计。【测试数据】学期总数：8；学分上限：10；该专业共开设16门课，课程号从C01-C16,学分顺序为2,3,4,3,2,3,4,4,4,5,4,4,2,3,2,3；先修关系口定义（画图）。【实现提示】可设学期总数不超过10,课程总数不超过60.如果输入的先修课程号不在该专业开设的课程序列中，则作为错误处理。应建立内部课程序号与课程序号Z间的对应关系。【选做内容】产主多种（例如5利
5、）不同的方案供用户选择，并使方案之间的差异尽可能的人。选题三：最小生成树问题【问题描
6、述】若要在n个城帀之间建设通信网络，只需要架设通信线路即可。如何以最低的经济代价建设这个通信网，是一个网的最小生成树问题。【基木要求】利用Kruskal（克鲁斯卡尔）算法求网的最小生成树。利用Prim（普里姆）算法求网的最小生成树。以文本形式输出生成树中各条边以及对应的权值。【测试数据】自行设计一个至少含8个顶点、12条边的无向带权图。【实现提示】通信线路一旦建立，必然是双向的。因此，构造最小生成树的网一定是无向网。设图的顶点数不超过30个；并为简单起见，网中边上的权值限定为不超过100的整数，它们可利用C语
7、言捉供的随机数函数产牛。图存储结构的选取应和所做的操作相适应。为了便于选取权值较小的边，此题的存储结构可以选择存储边（带权）的数组表示图。【选做内容】试利用堆排序的方法选择权值最小的边。选题四：交通咨询系统设计【问题描述】根据不同目的的旅客对交通工具有不同的要求。例如，因公出差的旅客希望在旅途中的时间尽可能短，出门旅游的游客则期望旅费尽町能省，而老年旅客则要求中转次数最少。编制一个全国城市之间的模拟交通咨询程序，为旅客捉供两种或三种最优决策的交通咨询。【基本要求】提供对城市信息的编辑功能（例如，添加或删除信息
8、等）。城市Z间限定只有两种交通工具：火车和飞机。提供对列千时刻表和飞机航班进行编辑的功能（例如，添加或删除信息等）。提供两种最优决策：最快到达和最省钱到达。全程只考虑一种交通工具。旅途屮耗费的总时间应该包括屮转站的等候时间。咨询以用户和计算机的对话方式进行。由用户输入起始站、终点站、最优决策原则和交通工具。输出信息包括：最快需要多长时间才能到达或者最少需要多少旅费才能到达，并详细说明依次于何时乘坐哪一•趟列车或哪一次航班到何地。【测试数据】模拟现实情况，自行设计一个全国交通图，至少含18个城市、2（）条铁路线
9、。并自行设计列车时刻表和飞机航班表。【实现提示】对全国城市交通图和列车时刻表及飞机航班表的编辑，应该提供文件形式和键盘输入两种方式。飞机航班表的信息包括：起始站的出发时间、终点站的到达时间和票价；列车时刻表则需根据交通图给出各个路段的详细信息，例如，对从北京到上海的火车，需给出北京至天津、天津至徐州及上海各段的出发时间、到达时间及票价等信息。以邻接表作为交通图的存储结构，表示边的结点内除含有邻接点的
