数据结构课程设计指导(题目)

上传人:宝路 文档编号:20368754 上传时间:2017-11-22 格式:DOC 页数:12 大小:120.75KB
返回 下载 相关 举报
数据结构课程设计指导(题目)_第1页
第1页 / 共12页
数据结构课程设计指导(题目)_第2页
第2页 / 共12页
数据结构课程设计指导(题目)_第3页
第3页 / 共12页
数据结构课程设计指导(题目)_第4页
第4页 / 共12页
数据结构课程设计指导(题目)_第5页
第5页 / 共12页
点击查看更多>>
资源描述

《数据结构课程设计指导(题目)》由会员分享,可在线阅读,更多相关《数据结构课程设计指导(题目)(12页珍藏版)》请在金锄头文库上搜索。

1、1、需求分析1 程序的功能;2 输入输出的要求;3 测试数据。2、概要设计包括程序设计组成框图,程序中使用的存储结构设计说明(如果指定存储结构请写出该存储结构的定义) 。3、详细设计包括模块功能说明(如函数功能、入口及出口参数说明,函数调用关系描述等) ,每个模块的算法设计说明(可以是描述算法的流程图) 。源程序要按照写程序的规则来编写。要结构清晰,重点函数的重点变量,重点功能部分要加上清晰的程序注释。4、调试分析测试数据,测试输出的结果,时间复杂度分析,和每个模块设计和调试时存在问题的思考(问题是哪些?问题如何解决?) ,算法的改进设想。5、核心源程序清单和执行结果源程序要按照写程序的规则来

2、编写。要结构清晰,重点函数的重点变量,重点功能部分要加上清晰的程序注释。 1、一元多项式乘法1) 问题描述已知 A(x)=a0+a1x+a2x2+anxn 和 B(x)=b0+b1x+b2x2+bmxm,并且在 A(x)和 B(x)中指数相差很多,求 A(x)=A(x)*B(x)。2) 基本要求(1)设计存储结构表示一元多项式;(2)设计算法实现一元多项式乘法;(3)分析算法的时间复杂度和空间复杂度。2、 迷宫问题1)问题描述迷宫求解是实验心理学中的一个经典问题,心理学家把一只老鼠从一个无顶盖的大盒子的入口处赶进迷宫,迷宫中设置很多隔壁,对前进方向形成了多处障碍,心理学家在迷宫的唯一出口处放置

3、了一块奶酪,吸引老鼠在迷宫中寻找通路以到达出口。例如,图 2 所示为一个迷宫示意图,其中双边矩形表示迷宫,1 代表有障碍,0 代表无障碍。2) 基本要求(1) 设计数据结构存储迷宫;(2) 设计存储结构保存从入口到出口的通路;(3) 设计算法完成迷宫问题的求解;(4) 分析算法的时间复杂度。3) 设计思想可以采用回溯法实现该问题的求解。回溯法是一种不断试探及时纠正错误的搜索方法。从入口出发,按某一方向向前探索,若能走通(未走过的) ,即某处可以到达,则到达新点,否则试探下一方向;若所有的方向均没有通路,则沿原路返回前一点,换下一个方向再继续试探,直到所有可能的通路都搜索到,或找到一条通路,或无

4、路可走又返回到入口点。0 1 2 3 4 5 6 7 8 90 1 1 1 1 1 1 1 1 1 11 1 0 1 1 1 0 1 1 1 12 1 1 0 1 0 1 1 1 1 13 1 0 1 0 0 0 0 0 1 14 1 0 1 1 1 0 1 1 1 15 1 1 0 0 1 1 0 0 0 16 1 0 1 1 0 0 1 1 0 17 1 1 1 1 1 1 1 1 1 1入口(1, 1)出口(6, 8)图 2 迷宫示意图,其中 1 代表有障碍,0 代表无障碍前进的方向有八个,分别是上、下、左、右、左上、左下、右上、右下在求解过程中,为了保证在任何位置上都能沿原路退回,需要

5、一个后进先出的栈来保存从入口到当前位置的路径。可以将迷宫定义成一个二维数组,则每个点有 8 个试探方向,如当前点的坐标是(x, y),与其相邻的 8 个点的坐标都可根据与该点的相邻方位而得到,规定试探顺序为顺时针方向,将这 8 个方向的坐标增量放在一个结构数组 move8中,在 move 数组中,每个元素由两个域组成:x 表示横坐标增量,y 表示纵坐标增量。这样会很方便地求出从某点(x,y)按某一方向 v (0v7) 到达新点( i,j)的坐标:i =x+movev.x ; j=y+movev.y 。算法用伪代码描述如下:1. 栈初始化;2. 将入口点坐标(x , y)及该点的方向 d(设为-

6、1)入栈;3. 当栈不空时循环执行下述操作:3.1 (x , y , d)容忍值,则在 j 处放置放大器 ;2.2 否则 D(i) = maxD(i),D (j) +d(j) ;【思考题】本题假设分布网络是一棵二叉树结构,如果是树结构应如何设计算法?5、哈夫曼编码1) 问题描述设某编码系统共有 n 个字符,使用频率分别为w 1, w2, , wn,设计一个不等长的编码方案,使得该编码系统的空间效率最好。2) 基本要求(1) 设计数据结构;(2) 设计编码算法;(3) 分析时间复杂度和空间复杂度。3) 设计思想利用 Huffman 编码树求得最佳的编码方案。根据哈夫曼算法,建立哈夫曼树时,可以将

7、哈夫曼树定义为一个结构型的一维数组HuffTree,保存哈夫曼树中各结点的信息,每个结点包括:权值、左孩子、右孩子、双亲,如图 6 所示。由于哈夫曼树中共有 2n-1 个结点,并且进行 n-1 次合并操作,所以该数组的长度为 2n-1。构造哈夫曼树的伪代码如下:1. 数组 huffTree 初始化,所有元素结点的双亲、左右孩子都置为-1;2. 数组 huffTree 的前 n 个元素的权值置给定权值 wn;3. 进行 n-1 次合并3.1 在二叉树集合中选取两个权值最小的根结点,其下标分别为 i1, i2;3.2 将二叉树 i1、i2 合并为一棵新的二叉树 k;在哈夫曼树中,设左分支为 0,右

8、分支为 1,从根结点出发,遍历整棵哈夫曼树,求得各个叶子结点所表示字符的哈夫曼编码。【思考题】对于采用哈夫曼编码树进行的编码,如何设计解码算法?6、TSP 问题1) 问题描述所谓 TSP 问题是指旅行家要旅行 n 个城市,要求各个城市经历且仅经历一次,并要求所走的路程最短。该问题又称为货郎担问题、邮递员问题、售货员问题,是图问题中最广为人知的问题。2) 基本要求(1) 上网查找 TSP 问题的应用实例;(2) 分析求 TSP 问题的全局最优解的时间复杂度;(3) 设计一个求近似解的算法;(4) 分析算法的时间复杂度。3) 设计思想对于 TSP 问题,一种最容易想到的也肯定能得到最佳解的算法是穷

9、举法,即考虑所有可能的旅行路线,从中选择最佳的一条。但是用穷举法求解 TSP 问题的时间复杂度为 (n!),当 n 大到一定程度后是不可解的。本实验只要求近似解,可以采用贪心法求解:任意选择某个城市作为出发点,然后前往最近的未访问的城市,直到所有的城市都被访问并且仅被访问一次,最后返回到出发点。为便于查找离某顶点最近的邻接点,可以采用邻接矩阵存储该图。算法用伪代码描述如下:weight lchild rchild parent图 6 哈夫曼树的结点结构1. 任意选择某个顶点 v 作为出发点;2. 执行下述过程,直到所有顶点都被访问:2.1 v=最后一个被访问的顶点;2.2 在顶点 v 的邻接点

10、中查找距离顶点 v 最近的未被访问的邻接点 j;2.2 访问顶点 j;3. 从最后一个访问的顶点直接回到出发点 v;【思考题】上网查找 TSP 问题的应用实例,写一篇综述报告。7、医院选址问题1)问题描述n 个村庄之间的交通图可以用有向网图来表示,图中边上的权值表示从村庄 i 到村庄 j 的道路长度。现在要从这 n 个村庄中选择一个村庄新建一所医院,问这所医院应建在哪个村庄,才能使所有的村庄离医院都比较近?2) 基本要求(1) 建立模型,设计存储结构;(2) 设计算法完成问题求解;(3) 分析算法的时间复杂度。3) 设计思想医院选址问题实际是求有向图中心点的问题。首先定义顶点的偏心度。设图 G

11、=(V ,E) ,对任一顶点 k,称 E(k)=maxd(i, k)(i V)为顶点 k 的偏心度。显然,偏心度最小的顶点即为图 G 的中心点。如图 7(a)所示是一个带权有向图,其各顶点的偏心度如图(b)所示。医院选址问题的算法用伪代码描述如下:1对加权有向图,调用 Floyd 算法,求每对顶点间最短路径长度的矩阵;2对最短路径长度矩阵的每列求大值,即得到各顶点的偏心度;3具有最小偏心度的顶点即为所求。【思考题】图的存储结构和算法的设计需要一定的灵活性和技巧。从医院选址问题的a bcde1253214 顶点 偏心度a b 6b 8d 5e 7(a) (b)图 7 带权有向图及各顶点的偏心度求

12、解过程,你有什么感想?8、 排序二叉树的遍历( 用递归或非递归的方法都可以) 1)问题描述输入树的各个结点,建立排序二叉树,对建立的排序二叉树进行层次、先序、中序和后序遍历并统计该二叉树中叶子结点的数目。 2)基本要求(1)用菜单实现(2)能够输入树的各个结点,并能够输出用不同方法遍历的遍历序列和叶子结点的数目。9、集合运算1)问题描述使用链表来表示集合,完成集合的合并,求交集等操作。2) 基本要求(1)用链表表示两个集合(2)对两个集合分别从小到大排序(3)两个集合合并成另一个新集合,如数值相同,合并为一个数据项(4)求出两个集合的交集建立一个新的集合。附录 2:课程设计说明书规范一、课程设

13、计说明书规范课程设计说明书是课程设计主要成果之一,对于设计类,应包括图纸、程序、实物成果等。1、说明书基本格式说明书可以手写或打印,书写要用黑或蓝黑墨水,书写工整;打印时正文采用 5 号宋体,A4 纸,页边距均为 20mm,行间距采用 18 磅。文中标题采用宋体加粗。2、说明书结构及要求(1)封面(见附录 3)包括:题目、系别、班级、完成日期、成绩及指导教师(签字) 、学生姓名等项。(2)课程设计任务书 (格式见附录 4)(3)目录要求层次清晰,给出标题及页次。最后一项为参考资料 。打印时各章题序及标题用小 4 号黑体, 其余用小 4 号宋体。(4)正文正文应按照目录所确定的顺序依次撰写,要求

14、计算准确,论述清楚、简练、通顺,插图清晰整洁。文中图、标及公式应规范地绘制和书写。(5)参考资料参考资料按下述顺序和格式书写:1毛昶熙,周名德等闸坝工程水力学与设计管理.北京:水利电力出版社,1995:89如参考网上资料,请写明网址。注:正文内容可参考以下内容:正文a) 总体设计(程序设计组成框图、流程图)b) 详细设计(模块功能说明(如函数功能、入口及出口参数说明,函数调用关系描述等)c) 调试与测试:调试方法,测试结果的分析与讨论,测试过程中遇到的主要问题及采取的解决措施d) 关键源程序清单和执行结果:清单中应有足够的注释问题描述和功能设计(附录 3:封面要求:)学 号数据结构课程设计设

15、计 说 明 书题目起止日期: 2009 年 10 月 20 日 至 2009 年 12 月 14 日学 生 姓 名班 级成 绩指 导 教 师 (签 字 )电子与信息工程系年 月 日附表 4天津城市建设学院课程设计任务书20092010 学年第 1 学期电子与信息工程 系 专业 班级课程设计名称: 数据结构课程设计 设计题目: 完成期限:自 2009 年 10 月 20 日至 2009 年 12 月 14 日共 周设计依据、要求及主要内容(可另加附页):一、设计目的熟悉各种数据结构和运算,会使用数据结构的基本操作解决一些实际问题。二、设计要求 在本课程设计过程中要求学生:(1)重视课程设计环节,用严谨、科学和踏实的工作态度对待课程设计的每一项任务;(2)按照课程设计的题目要求,独立地完成各项任务,严禁抄袭;凡发现抄袭,抄袭者与被抄袭者皆以零分计入本课程设计成绩。凡发现实验报告或源程序雷同,涉及的全部人员皆以零分计入本课程设计成绩。(3)学生在接受设计任务后,首先要按设计任务书的要求编写设计进程表。(4)认真编写课程设计报告。三、设计内容(自填,只填自己的设计内容)四、参考文献1、王红梅,数据结构,清华大学出版社2、王红梅,数据结构学习辅导与实验指导,清华大学出版社3、严蔚敏、吴伟民, 数据结构 C 语言版 ,清华

展开阅读全文
相关资源
正为您匹配相似的精品文档
相关搜索

最新文档


当前位置:首页 > 中学教育 > 试题/考题

电脑版 |金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号