数据结构与算法课程设计任务书 （2013级软件工程本科专业）
学生姓名： 学号： 班级：2013软件工程
题目类型：软件工程（R） 指导教师： 李明 一．
题目简介
1. 集合运算问题。设计一个程序，实现两个集合的并集、交集、差集、显示输出等，要求
结果集合中的元素不重复；实现一个集合的幂集的求解。（1）
2. 排序算法比较问题。设计各类排序算法的程序，通过随机的数据测试，比较各算法的关
键字比较次数和关键字移动次数。（2）
3. 方程求解问题。方程A+B+C+D+E=F刚好有一个满足0≤A≤B≤C≤D≤E≤F≤75的整
数解。请编写一个求出该解的程序。（3） 4. 图的基本操作与实现。
(1)自选存储结构,输入含n个顶点（用字符表示顶点）和e条边的图G； (2)求每个顶点的度,输出结果；
(3)指定任意顶点x为初始顶点,对图G作DFS遍历,输出DFS顶点序列(提示:使用一个栈实现DFS)；
(4)指定任意顶点x为初始顶点,对图G作BFS遍历,输出BFS顶点序列(提示:使用一个队列实现BFS)；
(5)输入顶点x,查找图G:若存在含x的顶点,则删除该结点及与之相关连的边,并作DFS遍历(执行操作3)；否则输出信息“无x”；
(6)判断图G是否是连通图，输出信息“YES”/“NO”；
(7)如果选用的存储结构是邻接矩阵,则用邻接矩阵的信息生成图G的邻接表,即复制图G,然再执行操作(2)；反之亦然。（4）
5
5
5
5
5
5
二、各题目的设计与实现要求
1. 针对具体问题，查阅文献资料（一般在3篇以上）；
2. 建立每个题目用到的数据的逻辑结构和物理结构（存储结构）；
3. 完成相应算法的设计； 4. 完成程序的实现；
5. 完成测试工作，分析算法复杂度； 6. 撰写设计说明书； 7. 做好答辩工作。
三、提交的成果
1. 课程设计说明书一份，内容包括： （1) 中文摘要100字；关键词3-5个； （2) 序言；
（3）对各个问题采用类C或C++语言定义相关的数据类型（数据结构）； （4）各问题处理的流程图或伪码描述的算法； （5）描述实现函数的调用关系图； （6）调试分析：
a、调试中遇到的问题及对问题的解决方法； b、算法的时间复杂度和空间复杂度； （7）输出典型数据，获得测试结果； （8）源程序（带注释）；
（9) 设计总结、参考文献、致谢等。 2. 刻制光盘一张。
四、主要参考文献
1 严蔚敏，吴伟民.数据结构（C语言版）[M].北京：清华大学出版社.2003 2 严蔚敏，吴伟民.数据结构题集（C语言版）[m]. 北京：清华大学出版社.2003 3 William Ford,William Topp.DATA STRUCTURE WITH C++ .北京：清华大学出版社（影印版）. 2005
4 谭浩强.c语言程序设计[M].北京：清华大学出版社. 2005.
5 Clifford A. Shaffer. 张铭,刘晓丹译.数据结构与算法分析（Java版） , A Practical Introduction to Data Structures and Algorithm Analysis Java Edition , 北京：电子工业出版社 2001
五、各阶段时间安排（共2周） 周次 日期 星期一 第1周 星期二~三 星期四~五 星期一~三 第2周 星期四~五 检查程序，答辩 B馆501 内容 教师讲解设计要求，准备参考资料 分析设计要求，进行数据结构及算法设计 算法设计，编程实现 编程上机实现、测试程序 地点 B馆401 B馆401 B馆401 B馆501 2014年12月27日