《数据结构》教学大纲

1、数据结构教学大纲一、课程基本信息1课程中文名称：数据结构2课程英文名称：Data Structures3课程类别：必修4适用专业：计算机科学与技术5总学时：72学时（其中理论54学时，上机18学时）6总学分：4二、本课程在教学计划中的地位、作用和任务本课程是计算机专业的专业基础课，是该专业的主干课之一，是研究数据之间的关系以及对数据如何进行有效处理的学科。课程的任务是介绍一些最常用的数据结构，阐明数据结构内在的逻辑关系，讨论它们在计算机中的存储表示，并结合各种典型应用说明它们在进行各种运算（操作）时的动态性质及实际的执行算法。三、理论教学内容与教学基本要求1第一章 绪论（3学时）教学内容：什么

2、是数据结构；数据结构的基本概念和常用的术语；数据结构发展的历史以及数据结构在计算机科学中地位；算法描述和算法分析教学基本要求：了解数据结构的发展和地位；了解各种算法描述方法和算法设计的基本要求；理解数据结构、逻辑结构、存储结构和抽象数据类型的基本概念；掌握对算法的评价标准和算法效率的度量方法。教学重点：理解数据结构、逻辑结构、存储结构和抽象数据类型的基本概念；掌握对算法的评价标准和算法效率的度量方法教学难点：算法的评价标准和算法效率的度量方法2第二章 线性表（9学时）教学内容：线性表的逻辑结构；线性表的顺序存储结构；线性表的链式存储结构；线性表应用举例教学基本要求：理解线性表的概念、逻辑结构特

3、性以及两种存储结构特性，针对实际应用能从时间和空间复杂度的角度选用适当的存储结构；熟练掌握线性表的顺序存储结构及其各种基本运算；熟练掌握线性表的链式存储结构（单链表、循环链表、双向链表）及其各种基本运算，能在实际应用中选用适当的链表结构。教学重点：线性表的概念、逻辑结构特性以及两种存储结构特性，线性表的顺序存储结构及其各种基本运算；线性表的链式存储结构（单链表、循环链表、双向链表）及其各种基本运算教学难点：线性表的各种基本运算3第三章 字符串（3学时）教学内容：串类型的定义；串的表示和实现；串操作的应用举例教学基本要求：了解串的应用；掌握串的基本概念、顺序和链式存储结构；掌握串的各种基本运算；

4、 熟练掌握顺序存储结构上串的各种操作。教学重点：串的基本概念、顺序和链式存储结构及各种基本运算教学难点：串的各种基本运算4第四章 栈和队列（6学时）教学内容：栈；栈的应用；栈与递归过程；队列教学基本要求：掌握栈和队列的定义、表示、实现和应用；掌握栈的顺序存储结构和链式存储结构以及相应操作的实现；了解递归的概念和递归过程的实现；掌握队列的顺序存储结构（循环队列）和链式存储结构的实现。教学重点：栈和队列的定义、表示、实现和应用；栈的顺序存储结构和链式存储结构以及相应操作的实现；队列的顺序存储结构（循环队列）和链式存储结构的实现教学难点：栈和队列的顺序存储结构和链式存储结构以及相应操作的实现5第五章

5、 树和二叉树（9学时）教学内容：树的定义；二叉树；遍历二叉树和线索二叉树；树和森林；哈夫曼树及其应用教学基本要求：熟练掌握二叉树的定义、性质、各种存储结构的特点及适用范围；熟练掌握二叉树的各种遍历算法；理解线索二叉树的概念、存储结构及线索化算法；掌握树和森林与二叉树间的转换，掌握树和森林的遍历算法；掌握哈夫曼树的概念、存储结构；掌握建立哈夫曼树和哈夫曼编码的方法及带权路径长度的计算；理解树的基本概念及其存储结构。教学重点：二叉树的定义、性质、各种存储结构的特点及适用范围；二叉树的各种遍历算法；树和森林与二叉树间的转换教学难点：二叉树的各种遍历算法，线索二叉树线索化算法6第六章 集合与字典（9学

6、时）教学内容：静态查找表；动态查找表；哈希表教学基本要求：理解查找及其算法的时间复杂度；理解静态查找表的概念；理解二叉平衡树，B树的概念；理解哈希表的含义；掌握二叉排序树查找算法；掌握哈希函数的构造方法，哈希表的建立和查找以及处理冲突的基本方法；熟练掌握顺序查找、折半查找和分块查找算法，能对其性能进行分析。教学重点：顺序查找、折半查找和分块查找算法，哈希函数的构造方法，哈希表的建立和查找以及处理冲突的基本方法教学难点：哈希函数的构造方法，哈希表的建立和查找以及处理冲突的基本方法，各种查找算法的性能进行分析7第八章 内部排序（6学时）教学内容：基本概念；插入排序；快速排序；选择排序；归并排序；基

7、数排序；各种内部排序方法的比较讨论教学基本要求：了解内部排序的概念；了解归并排序、基数排序的算法；掌握插入类排序的算法，直接插入排序、希尔排序； 掌握交换类排序的算法，冒泡排序、快速排序； 掌握选择类排序的算法，简单选择排序、堆排序；掌握各种排序方法的特点，能够对各种排序算法进行评价，并能加以灵活应用。教学重点：插入类排序的算法，直接插入排序、希尔排序；掌握交换类排序的算法，冒泡排序、快速排序，掌握选择类排序的算法，简单选择排序、堆排序教学难点：各种排序方法的特点，能够对各种排序算法进行评价，并能加以灵活应用8第九章 图（9学时）教学内容：图的定义和术语；图的存储结构；图的遍历；图的连通性问题

8、；有向无环图及其应用；最短路径教学基本要求：理解图的基本概念，掌握图的邻接矩阵和邻接表的存储结构；理解带权最短路径的概念，掌握用Dijkstra方法求最短路径的算法；掌握构造最小生成树的方法及其算法；掌握求拓扑排序和关键路径的方法，理解其算法；熟练掌握图的深度优先和广度优先遍历算法。教学重点：图的基本概念，掌握图的邻接矩阵和邻接表的存储结构，图的深度优先和广度优先遍历算法，用Dijkstra方法求最短路径的算法；构造最小生成树的方法及其算法；求拓扑排序和关键路径的方法教学难点：用Dijkstra方法求最短路径的算法；构造最小生成树的方法及其算法；求拓扑排序和关键路径的方法四、实验教学内容与要求

9、（简要说明，详见实验课大纲）根据实验大纲和要求进行。详见实验大纲。五、考核方式考试六、成绩评定期末考试成绩占70%，平时成绩和实验成绩占30%七、本课程对学生创新能力培养的措施选择一些算法作为作业让学生独立去实现，采用激励与督促手段，随后加以检查和评讲。八、教材与参考书教 材：张乃孝算法与数据结构北京：高等教育出版社，2006年（面向21世纪课程教材）参考书：1 严蔚敏，吴伟民数据结构（第二版）北京：清华大学出版社，1992年2 张乃孝数据结构与算法学习辅导及习题详解北京：电子工业出版社，2004年九、其它必要的说明1本课程教学大纲是按照计算机科学与技术（四年制）本科培养方案及课程基本要求并结合我校计算机科学与技术专业的学科建设情况与教学计划制定的。