2015计科《数据结构与算法》课程设计

1、数据结构与算法课程设计序号：403040002课程名称：数据结构与算法课程设计学分：1适用专业：计算机科学与技术课程设计的目的、任务与基本要求：课程设计的目的是培养学生综合程序设计的能力， 训练学生灵活应用所学数据结构知识，独立完成问题分析、总体设计、详细设计和编程实现 等软件开发全过程的综合实践能力。巩固、深化学生的理论知识，提高编程水平，并在此过 程中培养他们严谨的科学态度和良好的学习作风。为今后学习其他计算机课程打下基础。课 程设计为学生提供了一个既动手又动脑，独立实践的机会，将书本上的理论知识和工作、生 产实际有机地结合起来，从而锻炼学生分析问题、解决实际问题的能力，提高学生的编程序

2、能力和创新意识。在处理每个题目时，要求从分析题目的需求入手，按设计抽象数据类型、 构思算法、通过算法的设计实现抽象数据类型、编制上机程序和上机调试等若干步骤完成题 目，最终写出完整的课程设计与程序分析报告。前期准备工作完备与否直接影响到后序上机 调试工作的效率。课题要求：一人一机，二至三人一组。课程设计结束，要求学生提供可运行的软件及源程序，打印课程设计报告与其电子版。课程设计内容：【课程设计题目一】一元稀疏多项式加法、乘法器【问题描述】利用单链表实现设计一个一元多项式的的计算器，用于完成两个多项式P(x)、Q(x)的 加法、减法、乘法及求导运算。例如(x2+4x5+2x9)+(x+3xQ 或

3、(7x4+4x6+2x9)*(x4+3x【基本要求】输入并建立两个多项式P(x)和。(x)；输出每个多项式，要求输出时按指数从小到大输出。两个多项式完成加法、减法、乘法、求导运算。输出两个多项式的加法、减法、乘法、求导的结果。写出课程设计报告【实现提示】用带表头结点的单链表存储多项式。【测试数据】分别选定三组测试数据进行测试，验证程序的正确性。【课程设计题目二】局域网的架设问题【问题描述】若要在8个城市(A、B、C、D、E、F、G、H)之间架设局域网，如何以最低的经济代价 架设这个局域网，并求出A城市到其他各城市之间的最短距离。【基本要求】（1）利用二种方法（Prim算法和克鲁斯卡尔（Krus

4、kual）算法生成局域网的架设方 案（2）利用迪杰斯特拉算法求最短距离。（3）写出课程设计报告。【测试数据】分别对每种方法选定两组测试数据进行测试，验证程序的正确性。【课程设计题目三】校园网架设的方案与设计问题【问题描述】若要在扬州大学的七个校区（江阳路南校区、江阳路北校区、瘦西湖校区、农学院校区、 工学院校区、水利学院校区、医学院校区）之间架设校园网，如何以最低的经济代价架设这 个校园网，（任意两校区之间距离估计一下）。并求出江阳路南校区到其他各校区之间的最短 距离。【基本要求】（1）利用二种方法（Prim算法和克鲁斯卡尔（Kruskual）算法生成校园网的架设方案（2）利用迪杰斯特拉算法求

5、出江阳路校区到其他各校区之间的最短距离。（3）写出课程设计报告。【测试数据】对每种方法设定一组模拟测试数据进行测试，验证程序的正确性。【课程设计题目四】城市景点导游咨询系统【问题描述】设计一个你所在城市景点导游程序，为来访的客人提供各种信息查询服务。【基本要求】（1）设计你所在城市平面图，所含景点不少于10个。以图中顶点表示城市各景点， 存放景点名称，地址，景点简介等信息；以边表示路径，存放路径长度等相关信息。（2）为来访客人提供图中任意景点相关信息的查询。（3）为来访客人提供图中任意景点的问路查询，即查出任意两个景点之间的一条最 短的简单路径。（4）写出课程设计报告【测试数据】选定一组模拟测

6、试数据进行测试，验证程序的正确性。【课程设计题目五】通信网络的架设问题【问题描述】若要在n（N10）个城市之间建设通信网络，只需要架设n-1条线路即可，如何以最低 的经济代价建设这个通信网，是一个网的最小生成树问题。【基本要求】（1）利用二种方法（Prim算法和克鲁斯卡尔（Kruskual）生成网中的最小生成树。（2）求出任意两个城市之间通信的最短距离。（3）将n个城市设计为一个有向图，求出一组拓扑排序。（4）写出课程设计报告。【测试数据】分别对每种方法选定三组测试数据进行测试，验证程序的正确性。【课程设计题目六】内部排序的比较【问题描述】比较内部排序一一冒泡排序、直接插入排序、二分插入排序、

7、选择排序、快速排序的运 行时间。给出算法执行的时间阶或每个程序的运行时间，精确到秒。【基本要求】（1）比较下列几种内部排序：冒泡排序、插入排序、二分插入排序、选择排序、快速 排序的运行时间。要求随机生成20000个测试数据进行测试，并输出每个程序的运行时间， 精确到秒。（2）验证每个排序程序的稳定性（3）写出课程设计报告【测试数据】选定测试数据进行测试，验证程序的正确性并对计算时间进行比较。【课程设计题目七】二叉树及其遍历方法【问题描述】用递归和非递归两种方法创建一棵二叉树，并对它们进行先序遍历、中序遍历、后序遍 历及层次遍历，并求出该二叉树的深度和叶子结点数、输入一个结点查找该结点的双亲、祖

8、 先及左右孩子结点。【基本要求】（1）用递归和非递归两种方法创建一棵二叉树。（2）用递归和非递归两种方法，对二叉树进行先序遍历、中序遍历、后序遍历及层 次遍历。（3）求出该二叉树的深度和叶子结点数。（4）输入一个结点查找该结点的双亲、祖先及左右孩子结点。（5）写出课程设计报告【测试数据】选定两组测试数据进行测试，验证程序的正确性。【课程设计题目八】表达式的求值演算【问题描述】以字符序列的形式从终端输入语法正确的、不含变量的整数表达式。利用教材中给出的 算符优先关系，加上乘方厂）和求除（）运算符，实现对算术混合运算表达式的求值。【基本要求】（1）表达式中含有乘方厂）、加（+）、减（-）、乘（*）

9、、除（/）、求除（%）运算；并含有 括号。（2）分别以五组不同的表达式作为测试实例，每个实例中含有上述所有运算符，测试 其结果的正确性。写出课程设计报告【测试数据】选定五组测试数据进行测试，验证程序的正确性。【课程设计题目九】设计一个矩阵运算器【问题描述】设计一个矩阵运算器，对矩阵进行乘方厂)、加(+)、减(-)、乘(*)、转置等运算；【基本要求】参见数据结构题集P136页4.1求含有乘方厂)、加(+)、减(-)、乘(*)运算；。写出课程设计报告【测试数据】分别选定一组测试数据进行测试，验证程序的正确性。【课程设计题目十】自来水管理架设问题【问题描述】若要在扬州大学的八个居民区(A区、B区、C

10、区、D区、E区、F区、G区、H区)之间 架设自来水管道，如何以最低的经济代价架设这个自来水管道。【基本要求】利用二种方法(Prim算法和克鲁斯卡尔(Kruskual)算法生成自来水管道的架设写出课程设计报告。【测试数据】分别对每种方法选定三组测试数据进行测试，验证程序的正确性。【课程设计题目十一】哈夫曼树与哈夫曼码【问题描述】创建一棵哈夫曼树并实现哈夫曼编码的输出。【基本要求】输入一个文本，统计各字符出现的频度，输出结果使用字符出现的频度构造哈夫曼树输出各字符按上述频度所构造的哈夫曼编码输入一个由0和1组成的代码序列，翻译并输出与之对应的文本，若最后的代码 子序列不能译为文本，则输出相关出错信

11、息写出课程设计报告【测试数据】分别对选定两组测试数据进行测试，验证程序的正确性。【课程设计题目十二】二叉排序树【问题描述】输入一个数列创建一棵二叉排序树T,对二叉排序树T按递增、递减两种序列输出，计 算该二叉排序树T的平均查找长度并输出，在二叉排序树T上删除指定结点，并输出二叉排 序树T中指定结点的平衡因子。【基本要求】输入一个数列L，生成一棵二叉排序树T对二叉排序树T作递增、递减输出计算二叉排序树T的平均查找长度，输出结果在二叉排序树T上删除指定结点输出二叉排序树T中指定结点的平衡因子写出课程设计报告【测试数据】分别对选定两组测试数据进行测试，验证程序的正确性。【课程设计题目十三】双向链表的操作【问题描述】创建一个双向链表，并实现双向链表的基本操作。【基本要