还剩7页未读,继续阅读
文本内容:
《数据结构与算法》教学大纲
一、教学目的和要求1
二、教学中应注意的问题1
三、教学课时分配2课程名称数据结构与算法学时64学时课程类型必修课程性质软件服务外包专业的基础课程开课学期第3学期先修课程离散数学、软件工程计算基础1/软件工程计算基础n适用专业软件服务外包专业
一、教学目的和要求
1、教学目的《数据结构》是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作的科学学会分析研究计算机加工数据对象的特性,以便为应用所设计的数据选择合适的逻辑结构和物理结构以及恰当的算法,并初步掌握算法的复杂度分析技术,这是一个从事计算机科学与技术研究和应用的科学工作者的基本要求,也是进一步学习计算机的重要基础,不论是对程序设计,还是对实现编译程序、操作系统、数据库等均具有十分重要的意义学习掌握数据结构,并应用它来处理其它问题,也是进行复杂程序设计的一种基本训练,对培养学生的数据抽象能力意义重大
2、课程讲授基本要求1讲述抽象数据类型和算法分析方法2详细介绍线性表、栈、队列、数组、广义表、串、树和二叉树、图等数据结构的逻辑结构、存储结构和运算的实现3介绍各种查找方法,重点介绍顺序查找、折半查找方法、二叉排序树的构造和查找方法、哈希表查找法,简单介绍B树4介绍各种排序方法,重点介绍直接插入排序、shell排序、冒泡排序、快速排序、简单选择排序、堆排序、归并排序和基数排序算法,并对比分析各种排序算法的性能5介绍外排序和文件的组织方法,重点介绍顺序文件、索引文件、直接存取文件、多重表文件和倒排文件的特点、构造方法
二、教学中应注意的问题
1、突出重点紧紧围绕数据结构的中心内容数据之间的逻辑结构表示、重点是物理结构的表示以及相应的算法进行讲解
2、重视难点结合典型问题或者实际事例进行数据结构的设计以及有关算法的实现进行讲解
3、本课程的前导课,至少学过一门通用的高级语言的程序设计离散数学(图论部分)等课程
三、教学课时分配第一章抽象数据类型和算法分析基础基本内容
1、抽象数据类型的定义与实现(2学时)抽象数据类型的逻辑定义;抽象数据类型的物理实现
2、算法复杂度分析(2学时)实际执行时间;基本操作的频度;渐进时间复杂度重点抽象数据类型的定义与实现,算法复杂度分析方法难点理解程序的基本元素(语法及语义),掌握基本的数据结构讲授提示结合简单的抽象数据类型实例,介绍抽象数据类型定义、实现的具体过程结合典型的时间复杂度类型,分别给出分析实例,包括基本操作的频度、算法的渐进时间复杂度习题要求布置少量简单习题作为课后练习第二章线性表基本学时6学时4学时讲授+2学时课内练习;教学内容.顺序表类型(2学时);.线性表的实现方法(2学时).线性表的操作(2学时)重点线性表的抽象数据类型定义、用顺序结构实现线性表、用链表结构实现线性表(单链表、循环链表、双向链表)、线性表的应用难点顺序表和链表的处理异同、两种存储方式查找某一结点的不同方式讲授提示结合简单的抽象数据类型实例,介绍抽象数据类型定义、实现的具体过程结合典型的时间复杂度类型,分别给出分析实例,包括基本操作的频度、算法的渐进时间复杂度习题要求布置适量应用型习题作为课后练习,使学生熟练掌握所学内容第三章栈和队列基本学时6学时4学时讲授+2学时课内练习;教学内容.栈和队列的实现(3学时);.栈和队列的典型应用(3学时)重占
八、、栈和队列的特性和典型应用;递归算法的设计与分析;栈和递归的实现机制;递归程序转化为非递归程序的方法难点利用栈和队列解决实际问题的方法,递归程序转化为非递归程序的方法讲授提示详细解释递归的定义和应用,明确递归到非递归转换的原因习题要求布置适量应用型习题作为课后练习,使学生熟练掌握所学内容第四章字符串基本学时4学时2学时讲授+2学时课内练习;教学内容.串操作的实现(2学时);.子串移动方法(1学时).KMP匹配算法(1学时)重占堆串存储结构的特点;定长顺序串、堆串操作实现的异同;串的模式匹配;串的应用难点串的模式匹配讲授提示提示学生熟练掌握子串移动这一常用操作的不同实现方法,包括以源地址为基准,以目标地址为基准,同时使用源地址和目标地址等方法习题要求布置适量应用型习题作为课后练习,使学生熟练掌握所学内容第五章数组和广义表基本学时6学时4学时讲授+2学时课内练习;教学内容.多维数组(1学时);.特殊矩阵的压缩存储(2学时).快速转置算法(1学时).十字链表(1学时).广义表(1学时)重占
八、、数组的存储结构与地址计算,特殊矩阵的压缩存储,稀疏矩阵;广义表的存储结构和基本操作难点多维数组的存储结构与地址计算,特殊矩阵的压缩存储公式推导,用三元组表实现矩阵的快速转置,广义表的存储结构讲授提示为了便于学生理解,讲授时宜多用例子进行习题要求布置适量应用型习题作为课后练习,使学生熟练掌握所学内容第六章树形结构及其应用基本学时14学时10学时讲授+4学时课内练习;教学内容.二叉树的操作(4学时);.二叉树的存储结构(1学时).二叉树遍历的应用(4学时).递归转换为非递归(2学时).树的存储结构与操作(2学时).哈夫曼树(1学时)重占二叉树的遍历算法及其应用(递归遍历算法、非递归遍历算法、递归转换为非递归等);树的存储结构与操作实现;树、森林及其二叉树的对应关系难点二叉树的遍历算法及其应用讲授提示注意体会栈和队列在二叉树遍历中的应用讲授时宜多用实际例子,以便学生理解和掌握习题要求布置适量应用型习题作为课后练习,使学生熟练掌握所学内容第七章图结构及其应用基本学时12学时8学时讲授+4学时课内练习;教学内容.图的深度优先搜索(3学时).图的广度优先搜索(3学时).图的遍历算法的应用(4学时).图的典型算法(2学时)重点图的存储结构(邻接矩阵、邻接表);图的遍历方法;图的典型算法(最小生成树、拓扑排序、关键路径、最短路径)难点图的遍历方法;图的典型算法讲授提示通过实例关键要讲清遍历算法的思想,提示学生注意掌握算法的本质习题要求布置适量应用型习题作为课后练习,使学生熟练掌握所学内容第八章查找技术基本学时16学时10学时讲授+6学时课内练习;教学内容.折半查找(3学时);.二叉排序树(3学时).平衡二叉排序树(4学时).B树(4学时).散列查找(2学时)重点折半查找;二叉排序树;计算散列式查找;查找方法的性能分析难点二叉排序树的删除操作;查找方法的性能分析;平衡二叉排序树;B树讲授提示通过实例讲清查找算法的思想习题要求布置适量应用型习题作为课后练习,使学生熟练掌握所学内容第九章内部排序基本学时10学时6学时讲授+4学时课内练习;教学内容.排序方法(9学时);插入排序(直接插入排序、Shell排序);交换排序(冒泡排序、快速排序);选择排序(简单选择排序、堆排序);归并排序;分配排序(桶排序、基数排序);.排序算法分析(1学时);-时间代价;-空间代价重点直接插入排序,Shell排序;冒泡排序,快速排序;简单选择排序,堆排序;排序算法的综合比较难点Shell排序,堆排序;排序算法的时间复杂度分析;排序算法的综合比较讲授提示通过实例讲清查找算法的思想习题要求布置适量应用型习题作为课后练习,使学生熟练掌握所学内容第十章外部排序与文件组织基本学时2学时教学内容.排序算法(1学时);置换选择排序;多路归并;最佳归并树.文件组织技术(1学时)索引文件;散列文件;倒排表重占-=±=^
八、、外排序的基本方法;索引文件;多重表;倒排表难点索引文件;多重表;倒排表讲授提示利用操作系统的文件存储结构讲解本单元习题要求无
四、实践性教学环节要求数据结构是一门理论与实践性相结合的课程,通过实验巩固所学理论,培养学生的分析问题解决问题的能力,提高学生的程序设计技巧和技能学生应认真对待实验,按要求做好实验中的内容,正确作出实验总结和写出实验报告本课程安排实验16学时,6个实验,内容见实验讲义
五、学时分配表
六、参考书目
1.《数据结构与算法(第2版)》,张晓莉等,著机械工业出版社,2008-07-
01.《数据结构与算法(第4版)》廖明宏,高等教育出版社,2007-11-
01.《数据结构(C语言版)》,(美)霍罗威茨等著,李建中等译,机械工业出版社2006-7-1o章节名称学时分配(学时)授课实验上机讨论备注第一章绪论4第二章线性表42第三章栈与队列42第四章串22第五章数组与广义表42第六章树和二叉树122第七章图102第八章查找142第九章排序82第十章文件2合计6416总授课时80。