2010级软件专业数据结构课程设计计划(2)

(2) 使用汉字显示。

题目16：构造可以使n个城市连接的最小生成树 【问题描述】

给定一个地区的n个城市间的距离网，用Prim算法或Kruskal算法建立最小生成树，并计算得到的最小生成树的代价。 【基本要求】

(1) 城市间的距离网采用邻接矩阵表示，邻接矩阵的存储结构定义采用课本中给出的定义，若两个城市之间不存在道路，则将相应边的权值设为自己定义的无穷大值。要求在屏幕上显示得到的最小生成树中包括了哪些城市间的道路，并显示得到的最小生成树的代价；

(2) 表示城市间距离网的邻接矩阵（要求至少6个城市，10条边）；

(3) 最小生成树中包括的边及其权值，并显示得到的最小生成树的代价； (4) 使用汉字显示。

题目17：图的遍历的实现 【问题描述】

图的DFS,BFS的递归和非递归算法的实现。 【基本要求】

(1) 先任意创建一个图；

(2) 图的DFS,BFS的递归和非递归算法的实现； (3) 要求用有向图和无向图分别实现；

(4) 要求用邻接矩阵、邻接表多种结构存储实现。

题目18：教学计划编制问题 【问题描述】

大学的每个装业都要制定教学计划，假设任何专业都有固定的学习年限，每学年含两学期，每学期的实际长度和学分上限值均相等，每个专业开设的课程都是确定的，而且课程在开设实际的安排必须满足先修关系，每门课程有哪些先修课程是确定的，可以有任意多门，也可以没有，每门课恰好占一个学期，试在这样的前提下设计一个教学计划编制程序。 【基本要求】

(1) 属于参数包括学期总数，一学期的学分上限，每门课的课程号（固定占三位的字母数字串），学分和直接先修课的课程号；

(2) 允许用户指定下列两种编排策略之一，一是使学生在各学期中的学习负担尽量均匀，二是使课程尽可能的集中在前几个学期中；

(3) 若根据给定的条件问题无解，则报告适当的信息，否则将教学计划输出到用户指定的文件中，计划的表格格式自行设计；

(4) 使用汉字显示。

题目19：关键路径问题 【问题描述】

设计一个程序求出完成整项工程至少需要多少时间以及整项工程中的关键活动。

【基本要求】

6

（1）对一个描述工程的AOE网，应判断其是否能够顺利进行；

（2）若该工程能顺利进行，输出完成整项工程至少需要多少时间，以及每一个关键活动所依附的两个顶点、最早发生时间、最迟发生时间；

（3）使用汉字显示。

题目20：二叉排序树的实现 【问题描述】

实现二叉排序树的操作算法，包括建立、插入、删除、查找以及中序遍历。 【基本要求】

（1）作为一个完整的系统，应具有友好的界面和较强的容错能力； （2）使用汉字显示。

题目21：散列法的实验研究 【问题描述】

散列法中，散列函数构造方法多种多样，同时对于同一散列函数解决冲突的方法也可以不同。两者是影响查询算法性能的关键因素。对于几种典型的散列函数构造方法，做实验观察，不同的解决冲突方法对查询性能的影响。 【基本要求】

（1） 设计不同的散列函数，比较冲突率；

（2） 在散列函数确定的前提下，尝试各种不同类型处理冲突的方法，考察

平均查找长度的变化； （3） 使用汉字显示。

题目22：排序综合 【问题描述】

利用随机函数产生N个随机整数（20000以上），对这些数进行多种方法排序。

【基本要求】

(1) 至少采用三种方法实现上述问题求解（提示，可采用的方法有插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序）。并把排序后的结果保存在不同的文件中；

(2) 统计每一种排序方法的性能（以上机运行程序所花费的时间为准进行对比），找出其中两种较快的方法；

(3) 使用汉字显示。 学生应在教师的指导下，根据自己的实际情况，选择设计题目（以小组为单位实现）。一组一题。如需自行申请选题，需经指导教师批准。 2．设计步骤

(1) 问题分析和任务定义

根据设计题目的要求，充分地分析和理解问题，明确问题要求做什么？（而不是怎么做？）限制条件是什么？ (2) 概要设计

7

对问题描述中涉及的操作对象定义相应的数据类型，并按照以数据结构为中心的原则划分模块，定义主程序模块和各抽象数据类型。概要设计的结果应写出每个抽象数据类型的定义(包括数据结构的描述和每个基本操作的功能说明)，各个主要模块的算法，并画出模块之间的调用关系图。 (3) 详细设计

定义相应的存储结构并写出各函数的伪码算法。在这个过程中，要综合考虑系统功能，使得系统结构清晰、合理、简单和易于调试，抽象数据类型的实现尽可能做到数据封装，基本操作的规格说明尽可能明确具体。详细设计的结果是对数据结构和基本操作作出进一步的求精，写出数据存储结构的类型定义，写出函数形式的算法框架；界面要求有合理的提示，每个功能可以设立菜单，根据提示，可以完成相关的功能要求；有些数据要存储在数据文件中（数据文件的数据读写方法等相关内容在c语言程序设计的书上，请自学解决）。 (4) 程序编码

把详细设计的结果进一步求精为程序设计语言程序。同时加入一些注解，使程序中逻辑概念清楚。 (5) 程序调试与测试

采用自底向上，分模块进行，即先调试低层函数。能够熟练掌握调试工具的各种功能，设计测试数据确定疑点，通过修改程序来证实它或绕过它。测试数据要求使用合法数据和非法数据进行程序测试，以保证程序的稳定；调试正确后，认真整理源程序及其注释，形成格式和风格良好的源程序清单和结果。 (6) 结果分析

程序运行结果包括正确的输入及其输出结果和含有错误的输入及其输出结果。算法的时间、空间复杂性分析。

(7) 编写课程设计报告 3．课程设计的基本要求

（1）严格遵守软件系统开发步骤，适当应用理论知识，充分发挥主观能动性。结合课题，独立思考，努力钻研，勤于实践，勇于创新。

（2）严格考勤，独立按时完成规定的工作任务，不得弄虚作假，不准抄袭他人内容，如报告内容雷同，成绩以不及格计。

（3）每组实现的结果必须进行检查和演示。课程设计结束后，应提交以下文档： 1）纸质文档：课程设计报告，格式请参考课程设计报告模版。

2）电子文档：放在一个以题目命名的文件夹中，包括课程设计报告电子版和系统源程序。

四．课程设计说明书（报告）的撰写规范

学生按要求完成课程设计报告的写作，具体格式请参考课程设计报告模版。课程设计报告应按照规定的格式撰写，其中总结部分可以包括：课程设计过程中遇到的困难及其采用的解决办法；进行了哪些功能扩展，特别是重点说明独创或

8

创新的部分；在课程设计过程中的收获、以及对《数据结构》课程的认识等内容。

各种设计文档用A4纸打印，报告中使用的图形或图表应使用适当工具绘制，清晰、准确。 五．课程设计的考核

采用出勤情况、完成的程序、课程设计报告相结合的形式，按优、良、中、及格、不及格五级记分制给出每位学生的成绩。

1、出勤情况（20%） 2、程序运行（30%） 3、课程设计报告（45%） 4、创新部分（5%-10%）

9

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库2010级软件专业数据结构课程设计计划(2)在线全文阅读。