数据结构与算法教学大纲--2016

1、数据结构与算法课程教学大纲DataStructureAndAlgorithm课程编码：XJB08006课程类别：学科基础课程先修课程：程序设计基础、高等数学、线性代数后修课程：操作系统、算法分析与设计、面向对象程序设计总学分：4总学时：64周学时：4适用专业：软件工程、计算机科学与技术开课单位：信息科学技术学院授课教师：常静一、教学目标及教学要求数据结构与算法是计算机科学与技术、数字媒体技术、软件工程专业的一门重要学科基础课，是必修课。主要内容包括：线性表、栈和队列、用、数组和广义表、树、图、查找算法和排序算法。数据结构研究数据的组织方式，内容丰富、学习量大，隐含在各部分内容中的方法和技术多，

2、旨在让学生掌握计算机软件系统所必需的数据结构的算法。要求学生掌握贯穿全课程的动态链表存储结构，掌握算法设计的动态性和抽象性。要求学生学会分析研究计算机加工的数据对象的特征，以便在实际应用中选择适当的数据结构、存储结构和相应算法，初步掌握算法的时间与空间性能分析技巧，并培养复杂程序设计的技能。二、本课程的重点和难点（一）课程的重点：数据结构的逻辑结构、存储结构以及基本操作的概念及相互关系。线性表顺序存储实现中的创建、查找、插入和删除等基本操作及相关算法。栈、队列的定义、特点、性质。数组的存储表示方法，稀疏矩阵的压缩存储方法，广义表的定义。二叉树的定义、结构特点和性质，先序、中序、后序遍历的递归和

3、非递归算法，二叉树的线索化过程和算法，最优二叉树的特性及建立最优二叉树的算法，哈夫曼编码的算法。图的定义、术语、结构特点和性质，图的邻接矩阵、邻接表的存储结构及其构造方法，图的深度优先搜索和广度优先搜索算法，连通图的最小生成树算法，有向无环图的拓扑排序算法、关键路径的算法，最短路径求解中的Dijkstra算法和Floyed算法。简单插入排序、希尔排序、冒泡排序、快速排序、选择排序、堆排序、归并排序、基数排序算法。（二）课程的难点：抽象数据类型（ATD）的概念和实现方法，算法的时间复杂性和空间复杂性分析。线性表ADT链式存储实现中的某些操作。栈和队列在解决实际问题中的应用。二叉树的先序、中序、后

4、序遍历的非递归算法，二叉树的线索化算法。有向无环图的关键路径算法，最短路径求解中Floyed算法。二叉排序树结点的删除算法，二叉平衡树的构造算法。堆排序、归并排序算法以及它们的时间复杂性和空间复杂性分析。三、主要实践性教学环节及要求本课程主要依托教材所提供的课堂案例进行实践教学，通过每章节的学习，使用学生掌握所学章节知识在案例中的应用。四、采用的教学手段和方法教学手段采用传统教学手段和多媒体教学手段相结合的方式。课程教学在方法上，采用课堂讲授，课后自学，课堂讨论等多种教学形式。五、教材与主要参考文献教材：数据结构与算法（c+诚）.唐宁九等编著.清华大学出版社主要参考文献：数据结构（C语言版）.

5、严蔚敏，吴伟民.清华大学出版社数据结构（C语言版）.严蔚敏，李冬梅，吴伟民.人民邮电出版社六、考核形式与成绩计算期末考试采用笔试形式，闭卷考试。总评成绩由平时成绩和期末成绩组成，其中平时成绩占30%期末考试占70%七、教学内容和学时分配（一）第一章绪论2学时（课堂讲授2学时）主要内容：（1）数据结构的一些基本概念：数据、数据元素、数据的逻辑结构、物理结构等。（2）抽象数据类型的表示和实现。（3）算法的概念和特性。（4）算法时间复杂度和空间复杂度的分析。教学要求：掌握数据结构的基本概念，了解抽象数据类型，掌握算法时间复杂度和空间复杂度的分析方法。教学方法与手段：讲授法重点、难点：算法的时间复杂度

6、和空间复杂度（二）第二章线性表2学时（课堂讲授2学时）主要内容：（1）线性表的类型定义。（2）线性表的顺序表示和实现。（3）线性表的链式表示和实现。（4）线性表的应用，包括无序表和有序表的合并、多项式的加法运算等。教学要求：理解线性表的逻辑结构特性是数据元素之间存在着线性关系，在计算机中表示这种关系的两类不同的存储结构是顺序存储结构（顺序表）和链式存储结构（链表）。教学方法与手段：讲授法、实验法重点、难点：两类存储结构的描述方法，链表中的头结点、头指针和首元结点的区别及循环链表、双向链表的特点等。顺序表的查找、插入和删除算法，链表的查找、插入和删除算法。其它教学环节：实验内容：单链表的基本操作

7、。实验要求：实现带头结点的单链表的查找、插入和删除等算法。（三）第三章栈和队列8学时（课堂讲授6学时+课程实验2学时）主要内容：（1）栈的类型定义，栈的顺序存储和链接存储的表示和实现。（2）栈与递归的实现，递归程序转换为非递归程序的方法。（3）队列的类型，队列的顺序存储（循环队）和链接存储的表示和实现。教学要求：掌握栈和队列的特点，并能在相应的应用问题中正确选用。教学方法与手段：讲授法、实验法重点、难点：栈的顺序栈和链栈的进栈出栈算法，特别应注意栈满和栈空的条件。循环队列和链队列的进队出队算法，特别是循环队列中队头与队尾指针的变化情况。其它教学环节：实验内容：栈的应用。实验要求：借助栈来解决某

8、些实际应用问题,如表达式求值、迷宫问题等。（四）第四章用4学时（课堂讲授4学时）主要内容：（1）用类型的定义。（2）用的表示和实现，包括顺序存储和链式存储表示。（3）数组的存储方法。教学要求：了解用的顺序存储结构和堆存储结构。教学方法与手段：讲授法、讨论法重点、难点：用的设计、实现方法和基本操作。（五）第五章数组和广义表6学时（课堂讲授6学时）主要内容：（1）数组的定义（2）矩阵及特殊矩阵（3）广义表的概念教学要求：掌握数组和广义表的概念，掌握特殊矩阵的存储方法，掌握广义表的概念及存储结构。教学方法与手段：讲授法、讨论法重点、难点：数组的顺序存储方式，特殊矩阵，广义表的存储结构(六)第六章树和

9、二叉树10学时(课堂讲授8学时+课程实验2学时)主要内容：(1)二叉树的定义和术语，二叉树的性质，特殊的二叉树。(2)二叉树的存储结构，顺序存储和二叉链表。(3)二叉树的的前序、中序、后序、层次遍历方法。线索化二叉树。(4)树和森林的定义，树的存储，树、森林与二叉树的转换。(5)树的应用，哈夫曼树及哈夫曼编码。教学要求：了解树和森林的概念，包括树的定义、树的术语。掌握二叉树的概念、性质及二叉树的表示。掌握线索化二叉树的特性及寻找某结点的前驱和后继的方法。了解树的存储、树和森林与二叉树的转换方法。教学方法与手段：讲授法、实验法重点、难点：二叉树的遍历算法，哈夫曼树的实现方法、构造哈夫曼编码的方法

10、及带权路径长度的计算。其它教学环节：实验内容：二叉树的基本算法。实验要求：利用二叉链表方法建立二叉树，实现二叉树的前、中、后序三种遍历算法，并运用遍历算法实现二叉树的其他操作，如计算二叉树结点个数、叶子结点个数、二叉树的高度等。(七)第七章图10学时(课堂讲授8学时+课程实验2学时)主要内容：(1)图的定义和术语。(2)图的存储结构两种存储结构：邻接矩阵和邻接表表示法。(3)图的两种遍历策略：深度优先搜索和广度优先搜索。(4)构造最小生成树的两种算法：普里姆算法和克鲁斯卡尔算法。(5)拓扑排序和关键路径。(6)两类求最短路径问题的算法，迪杰斯特拉算法和弗洛伊德算法。教学要求：掌握图的基本概念及

11、相关术语和性质，掌握图的邻接矩阵和邻接表表示法，了解实际问题的求解效率与采用何种存储结构和算法有密切联系。了解关键路径的概念和求解方法，了解弗洛伊德算法。教学方法与手段：讲授法、实验法重点、难点：图的两种搜索路径的遍历：深度优先搜索和广度优先搜索的算法构造最小生成树的两种算法及拓扑排序算法的思想，迪杰斯特拉算法。其它教学环节：实验内容：图的建立和搜索。实验要求：使用邻接矩阵或邻接表表示法存储一个图，实现图的深度优先搜索和广度优先搜索的算法。(八)第八章查找6学时(课堂讲授6学时)主要内容：(1)查找的基本概念，平均查找长度。(2)基于线性表的查找：顺序查找、折半查找。(3)基于树表的查找：二叉

12、排序树、平衡二叉树、B-树和B+W。(4)散列表：散列表的基本概念，散列函数的构造方法、处理冲突的方法、散列表的查找与分析。教学要求：熟练掌握顺序表和有序表的查找方法及其实现，掌握二叉排序树的插入和查找算法及其实现，了解平衡二叉树、B-树和B+W的各种操作。教学方法与手段：讲授法、讨论法重点、难点：散列表的构造方法、处理冲突的方法。折半查找过程的判定树的构造方法，以及按定义计算各种查找方法在等概率情况下查找成功时的平均查找长度。(九)第九章排序6学时(课堂讲授6学时)主要内容：(1)排序的基本概念，包括正序，逆序，稳定性，排序方法的分类。(2)插入排序：直接插入排序、折半插入排序和希尔排序。(3)交换排序：冒泡排序和快速排序。(4)选择排序：简单选择排序和堆排序。(5)归并排序：2-路归并排序。(6)基数排序：多关键字的排序和链数基数排序。(7)排序算法分析：各种排序算法的比较和移动次数，时间复杂度和空间复杂度的分析。教学要求：