数据结构软件课程教学大纲.PDF

《数据结构（软件）》课程教学大纲 一、课程总述 本课程大纲以2016 年软件工程本科专业人才培养方案为依据编制。 课程名称 数据结构 （软件） 课程代码 18115 课程性质 专业必修 先修课程 C 语言 （或者C++ ）程序设计，离散数学 总学时数 80 周学时数 5 开课院系 软件与通信工程学院 任课教师 邓庆山 严军勇 蒋娜 尹爱华 涂保东 编 写 人 邓庆山 编写时间 2016.12 大纲主审 课程负责人 邓庆山 王颖 人 使用教材 教材：《数据结构》（C 语言版） 第二版，严蔚敏编，人民邮电出版社，2016 《数据结构》（C 语言版）严蔚敏编，清华大学出版社 教学参考资 数据结构习题集（C 语言版），严蔚敏，清华大学出版社 料 数据结构，许卓群等，北京：高等教育出版社 数据结构（使用C 语言），蔡明志著，北京：科学出版社 《数据结构》是计算机、软件科学的核心基础课程之一。数据是计算机处 理的对象，本门课程研究的数据是非数值性、结构性的数据。学习本门课程要 课程教学目 求掌握各种主要数据结构的特点、计算机内的表示方法，以及处理数据的算法 的 实际，对于算法所花费的时间和空间代价的分析也要求有一定程度的了解和掌 握。通过本门课程的学习，使学生透彻地理解各种数据对象的特点，学会数据 的组织方法和实现方法，并进一步培养基本的良好的程序设计能力。 对“数据结构”这门课程，要求学生掌握以下几个方面的问题： (1)线性表、树、图的基本结构。 (2)线性表、树、图的基本算法。 (3)对算法时间复杂度、空间复杂度的计算。 课程教学要 (4)查找、排序的主要算法及比较。 求 (5)线性表、树、图的应用算法。 (6)了解若干算法在计算机领域中的应用实例。 其中(1)-(4)为基本要求，必须牢固掌握。(5)为较高层次要求，能加深 学生对数据结构基本概念、基本算法的理解。(6)为知识性要求，为开拓学 生思路，加强与其他课程间的联系而设。 重点： （1）顺序表和单链表的描述和插入、删除运算以及算法的效率分析，栈和 队列的运算及循环队列； 本课程的重 （2）二叉树的性质及遍历算法，线索二叉树的运算，树、森林与二叉树之 点和难点 间的转换，Huffman 树的构造算法及Huffman 编码、译码； （3）图的邻接矩阵和邻接表存储结构，图的深度优先和广度优先遍历，最 小生成树、拓扑排序、关键路径和最短路径的求解； （4）顺序查找、折半查找算法及平均查找长度； （5）插入、交换、选择等基本排序方法和改进的排序方法，归并排序算法 及堆排序算法； 难点： （1）单链表的插入、删除运算和链表的应用，栈与队列的应用； （2）二叉树的遍历算法，尤其是非递归遍历算法，线索二叉树的理解； （3）折半查找算法及平均查找长度、二叉查找树的构造、哈希表的冲突处 理； （4）快速排序算法、堆排序算法和归并排序算法； （5）求最小生成树、拓扑排序、关