1/7《数据结构与算法》课程教学大纲DataStructureAndAlgorithm课程编码：XJB08006课程类别：学科基础课程先修课程：程序设计基础、高等数学、线性代数后修课程：操作系统、算法分析与设计、面向对象程序设计总学分：4总学时：64周学时：4适用专业：软件工程、计算机科学与技术开课单位：信息科学技术学院授课教师：常静一、教学目标及教学要求数据结构与算法是计算机科学与技术、数字媒体技术、软件工程专业的一门重要学科基础课，是必修课。主要内容包括：线性表、栈和队列、串、数组和广义表、树、图、查找算法和排序算法。数据结构研究数据的组织方式，内容丰富、学习量大，隐含在各部分内容中的方法和技术多，旨在让学生掌握计算机软件系统所必需的数据结构的算法。要求学生掌握贯穿全课程的动态链表存储结构，掌握算法设计的动态性和抽象性。要求学生学会分析研究计算机加工的数据对象的特征，以便在实际应用中选择适当的数据结构、存储结构和相应算法，初步掌握算法的时间与空间性能分析技巧，并培养复杂程序设计的技能。二、本课程的重点和难点（一）课程的重点：数据结构的逻辑结构、存储结构以及基本操作的概念及相互关系。线性表顺序存储实现中的创建、查找、插入和删除等基本操作及相关算法。栈、队列的定义、特点、性质。数组的存储表示方法，稀疏矩阵的压缩存储方法，广义表的定义。二叉树的定义、结构特点和性质，先序、中序、后序遍历的递归和非递归算法，二叉树的线索化过程和算法，最优二叉树的特性及建立2/7最优二叉树的算法，哈夫曼编码的算法。图的定义、术语、结构特点和性质，图的邻接矩阵、邻接表的存储结构及其构造方法，图的深度优先搜索和广度优先搜索算法，连通图的最小生成树算法，有向无环图的拓扑排序算法、关键路径的算法，最短路径求解中的Dijkstra算法和Floyed算法。简单插入排序、希尔排序、冒泡排序、快速排序、选择排序、堆排序、归并排序、基数排序算法。（二）课程的难点：抽象数据类型(ATD)的概念和实现方法，算法的时间复杂性和空间复杂性分析。线性表ADT链式存储实现中的某些操作。栈和队列在解决实际问题中的应用。二叉树的先序、中序、后序遍历的非递归算法，二叉树的线索化算法。有向无环图的关键路径算法，最短路径求解中Floyed算法。二叉排序树结点的删除算法，二叉平衡树的构造算法。堆排序、归并排序算法以及它们的时间复杂性和空间复杂性分析。三、主要实践性教学环节及要求本课程主要依托教材所提供的课堂案例进行实践教学，通过每章节的学习，使用学生掌握所学章节知识在案例中的应用。四、采用的教学手段和方法教学手段采用传统教学手段和多媒体教学手段相结合的方式。课程教学在方法上，采用课堂讲授，课后自学，课堂讨论等多种教学形式。五、教材与主要参考文献教材：《数据结构与算法（C++版）》.唐宁九等编著.清华大学出版社主要参考文献：数据结构（C语言版）．严蔚敏，吴伟民．清华大学出版社数据结构（C语言版）．严蔚敏，李冬梅，吴伟民．人民邮电出版社六、考核形式与成绩计算期末考试采用笔试形式，闭卷考试。总评成绩由平时成绩和期末成绩组成，其中平时成绩占30%，期末考试占70%。3/7七、教学内容和学时分配（一）第一章绪论2学时（课堂讲授2学时）主要内容：(1)数据结构的一些基本概念：数据、数据元素、数据的逻辑结构、物理结构等。(2)抽象数据类型的表示和实现。(3)算法的概念和特性。(4)算法时间复杂度和空间复杂度的分析。教学要求：掌握数据结构的基本概念，了解抽象数据类型，掌握算法时间复杂度和空间复杂度的分析方法。教学方法与手段：讲授法重点、难点：算法的时间复杂度和空间复杂度（二）第二章线性表2学时（课堂讲授2学时）主要内容：(1)线性表的类型定义。(2)线性表的顺序表示和实现。(3)线性表的链式表示和实现。(4)线性表的应用，包括无序表和有序表的合并、多项式的加法运算等。教学要求：理解线性表的逻辑结构特性是数据元素之间存在着线性关系，在计算机中表示这种关系的两类不同的存储结构是顺序存储结构（顺序表）和链式存储结构（链表）。教学方法与手段：讲授法、实验法重点、难点：两...
