数据结构理论课教学大纲.doc

《数据结构理论课教学大纲.doc》由会员分享，可在线阅读，更多相关《数据结构理论课教学大纲.doc（7页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构理论课程教学大纲课程代码 ： 课程名称 ：数据结构/Data Structure 课程类型 ：学科专业基础课 学时学分 ：80学时/5学分 适用专业 ：专科计算机专业 开课部门 ：灾害信息工程系 一、 课程的地位、目的和任务 数据结构是计算机相关专业的一门重要专业基础课，是计算机学科的公认主干课。课程内容由数据结构和算法分析初步两部分组成。 数据结构是针对处理大量非数值性程序问题而形成的一门学科，内涵丰富、应用范围广。它既有完整的学科体系和学科深度，又有较强的实践性。通过课程的学习，应使学生理解和掌握各种数据结构(物理结构和逻辑结构)的概念及其有关的算法；熟悉并了解目前常用数据结构在计

2、算机诸多领域中的基本应用。 经过上机实习和课程设计的训练，使学生能够编制、调试具有一定难度的中型程序；以培养良好的软件工程习惯和面向对象的软件思维方法。二、课程与相关课程的联系与分工 该课程是计算机专业的入门、提高课程，前序课是离散数学、C语言程序设计。对于后续开设面向对象程序设计语言、网站开发、操作系统和数据库等课程打下坚实的理论和程序设计基础，该课程是一门必修的计算机骨干课程。三、教学内容与基本要求 第一章 绪论教学内容：数据、数据元素、数据结构、数据类型、抽象数据类型、算法及其设计原则、时间复杂度、空间复杂度。教学重点与难点：数据结构的概念，算法分析。教学要求：(1)掌握数据、数据对象、

3、数据元素、数据结构、数据的逻辑结构与物理结构、逻辑结构与物理结构间的关系等数据结构的基本概念；(2)了解数据类型、抽象数据类型、数据抽象和信息隐蔽原则以及面向对象这种数据抽象实现方法；(3)了解算法的定义、算法的特性、算法的时间代价、算法的空间代价。 第二章 线性表教学内容：线性表、顺序表、链表、有序表。教学重点与难点：链表是本章的重点和难点。扎实的指针操作和内存动态分配的编程技术是学好本章的基本要求，分清链表中指针 p 和结点 *p 之间的对应关系，区分链表中的头结点、头指针和首元结点的不同所指以及循环链表、双向链表的特点等。教学要求：(1)了解线性表的逻辑结构特性是数据元素之间存在着线性关

4、系，在计算机中表示这种关系的两类不同的存储结构是顺序存储结构和链式存储结构。用前者表示的线性表简称为顺序表，用后者表示的线性表简称为链表；(2)熟练掌握这两类存储结构的描述方法以及线性表的基本操作在这两种存储结构上的实现；(3)能够从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特点及其适用场合；(4)结合线性表类型的定义增强对抽象数据类型的理解。第三章 栈和队列教学内容：顺序栈、链栈、循环队列、链队列。教学重点与难点：栈和队列是在程序设计中被广泛使用的两种线性数据结构，因此本章的学习重点在于掌握这两种结构的特点，以便能在应用问题中正确使用。教学要求：(1)掌握栈和队列这两种抽象数据类

5、型的特点，并能在相应的应用问题中正确选用它们；(2)熟练掌握栈类型的两种实现方法；(3)熟练掌握循环队列和链队列的基本操作实现算法；(4)理解递归算法执行过程中栈的状态变化过程。第四章 串和数组教学内容：串的类型定义、串的存储表示、串匹配、KMP算法、数组的类型定义、数组的存储表示、特殊矩阵的压缩存储表示方法、随机稀疏矩阵的压缩存储表示方法。教学重点和难点：重点在于了解串类型定义中各基本操作的定义以及串的实现方法，并学会利用这些基本操作来实现串的其它操作，学习数组类型的定义及其存储表示。本章的难点是理解实现串匹配的KMP算法的思想。教学要求：(1)理解串类型定义中各基本操作的特点，并能正确利用

6、它们进行串的其它操作；(2)理解串类型的各种存储表示方法；(3)理解串匹配的各种算法。(4)理解数组类型的特点及其在高级编程语言中的存储表示和实现方法，并掌握数组在“以行为主”的存储表示中的地址计算方法；(5)掌握特殊矩阵的存储压缩表示方法；(6)理解稀疏矩阵的两类存储压缩方法的特点及其适用范围，领会以三元组表示稀疏矩阵时进行矩阵运算所采用的处理方法。第五章 树和二叉树教学内容：树的类型定义、二叉树的类型定义、二叉树的存储表示、二叉树的遍历以及其它操作的实现、线索二叉树、树和森林的存储表示、树和森林的遍历以及其它操作的实现、最优树和赫夫曼编码。教学重点和难点：二叉树和树的遍历及其应用是本章的学

7、习重点，而编写实现二叉树和树的各种操作的递归算法也恰是本章的难点所在。教学要求：(1)领会树和二叉树的类型定义，理解树和二叉树的结构差别；(2)熟记二叉树的主要特性，并掌握它们的证明方法；(3)熟练掌握二叉树的各种遍历算法，并能灵活运用遍历算法实现二叉树的其它操作；(4)理解二叉树的线索化过程以及在中序线索化树上找给定结点的前驱和后继的方法；(5)熟练掌握二叉树和树的各种存储结构及其建立的算法；(6)学会编写实现树的各种操作的算法；(7)了解最优树的特性，掌握建立最优树和赫夫曼编码的方法。第六章 图教学内容：图的类型定义、图的存储表示、图的深度优先搜索遍历和图的广度优先搜索遍历、无向网的最小生

8、成树、最短路径、拓扑排序、关键路径。教学重点和难点：图的应用极为广泛，而且图的各种应用问题的算法都比较经典，因此本章重点在于理解各种图的算法及其应用场合。教学要求：(1)领会图的类型定义；(2)熟悉图的各种存储结构及其构造算法，了解各种存储结构的特点及其选用原则；(3)熟练掌握图的两种遍历算法；(4)理解各种图的应用问题的算法。 第七章 查找教学内容：顺序表、有序表、索引顺序表、静态查找树、二叉查找树、二叉平衡树、哈希表。教学重点和难点：本章重点在于理解查找表的结构特点及其各种表示方法的特点和适用场合。教学要求：(1)理解“查找表”的结构特点以及各种表示方法的适用性；(2)熟练掌握以顺序表或有

9、序表表示静态查找表时的查找方法；(3)熟悉静态查找树的构造方法和查找算法，理解静态查找树和折半查找的关系；(4)熟练掌握二叉查找树的构造和查找方法；(5)理解二叉平衡树的构造过程；(6)熟练掌握哈希表的构造方法，深刻理解哈希表与其它结构的表的实质性的差别；(7)掌握描述查找过程的判定树的构造方法，以及按定义计算各种查找方法在等概率情况下查找成功时的平均查找长度。 第八章 排序教学内容：排序、直接插入排序、折半插入排序、表插入排序、希尔排序、起泡排序、快速排序、简单选择排序、堆排序、2-路归并排序、基数排序、排序方法的综合比较。教学重点和难点：希尔排序、快速排序、堆排序和归并排序等高效方法是本章

10、的学习重点和难点。教学要求：(1)理解排序的定义和各种排序方法的特点，并能加以灵活应用。排序方法有不同的分类方法，基于“关键字间的比较”进行排序的方法可以按排序过程所依据的不同原则分为插入排序、交换排序、选择排序、归并排序和计数排序等五类；(2)掌握各种排序方法的时间复杂度的分析方法。能从“关键字间的比较次数”分析排序算法的平均情况和最坏情况的时间性能。按平均时间复杂度划分，内部排序可分为三类：O (n2) 的简单排序方法，O (n*logn) 的高效排序方法和O (d*n)的基数排序方法；(3)理解排序方法“稳定”或“不稳定”的含义，弄清楚在什么情况下要求应用的排序方法必须是稳定的。 四、

11、课程学时分配（以章节为单位） 教学内容学时分配合计讲课上机实验讨论/习题绪论2学时2学时4学时线性表6学时2学时8学时栈和队列4学时2学时6学时串和数组6学时2学时8学时树和二叉树12学时2学时14学时图14学时2学时16学时查找10学时2学时12学时排序10学时2学时12学时合计64学时16学时80学时五、教材与教参教材 ：数据结构教程(C语言版)作者 ：李春葆 曾平 喻丹丹 编著 出版社 ：中国人民大学出版社 参考书：数据结构与算法教程作者：邹永林 周蓓 唐晓阳 杨剑勇 编著出版社：机械工业出版社参考书：数据结构(C语言版)(含CD)作者：严蔚敏 吴伟民 编著出版社：清华大学出版社参考书：

12、数据结构习题集(C语言版)作者：严蔚敏 编著出版社：清华大学出版社参考书：数据结构习题解析与实训作者：张世和 编著出版社：清华大学出版社六、教学方法与考核方式理论课程在多媒体教室中全程采用电子课件教学，上课时使用专门的演示软件边讲边演示。实践课程部分以作业的形式布置给同学们，另一部分采用实例式教学，由教师带领学生们对实际问题进行分析，进而根据所学知识找到最佳的解决方法。本课强调软件编程能力的培养。本课成绩考核方式如下：期末考核成绩占总成绩的50，平时成绩占50。设置平时成绩及格线、期末考核成绩及格线，两个及格线均达到的学生通过课程考核。平时成绩不及格者不得参加该课程的期末考核，该课程成绩记为不及格，不得补考，只能重修。平时成绩及格、期末考试成绩不及格者，总成绩按期末成绩记载为不及格。期末成绩未达到40分的学生不得参加补考，只能重修。平时成绩由考勤（10）、作业（20）、期中考试成绩（20）和读书笔记四部分组成。学生每门课程的听课笔记或读书笔记不少于1万字，内容是课堂听课笔记和（或）与课程内容相关的课外读书笔记，一律手写，不得使用电子版本。记平时成绩时，学生未到课次数达到应到课次数三分之一的、未完成作业量达到三分之一的，平时成绩为零分。读书笔记不计分数，但作为课程考核的必要内容，没有读书笔记或读书笔记达不到主讲教师要求的，平时成绩为零分。