《数据结构》教学大纲_第1页
《数据结构》教学大纲_第2页
《数据结构》教学大纲_第3页
《数据结构》教学大纲_第4页
《数据结构》教学大纲_第5页
已阅读5页,还剩2页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

《数据结构》教学大纲教学性质、目的与任务《数据结构》是计算机学科的主干基础课,主要介绍基本的数据结构、典型算法及其应用。对计算机学科而言,《数据结构》是进一步学习和开展高层次研究的必修课。国际著名计算机科学家、图灵奖获得者D.E.Knuth教授指出:“程序就是用计算机所能接受的语言编写的算法,对于计算机程序设计而言,算法是最基本的”。数据结构与算法有着不可分割的关系,是计算机算法和计算机程序设计的理论基础。因此,《数据结构》课程在计算机科学中占有十分重要的地位。《数据结构》课程的教学目标是使学生理解数据结构的基本概念、计算机内部数据对象的表示和特性,掌握数据的逻辑结构、存储结构及其差异,以及各种操作的实现,能够针对实际问题选择合适的数据结构和方法设计出结构清晰、正确易读、复杂性较优的算法,同时掌握对算法进行时间、空间复杂性分析的基本技能。《数据结构》课程的主要任务是教授学生数据结构和算法的基本理论和方法,算法分析的基本方法,数据结构在计算机科学中的基本应用,为《程序设计》、《编译原理》、《操作系统》和《数据库》等课程的学习以及计算机软件的研发奠定理论基础和培养实践能力。同时,《数据结构》课程的学习过程也是复杂问题求解和规范化程序设计的训练过程,注重培养学生的问题分析、数据抽象和算法设计能力,同时训练学生按照软件工程规范编写程序的素养。二、教学基本要求1、了解数据结构及其分类、数据结构与算法的密切关系。2、系统掌握线性表、树和图等基本数据结构的定义、性质和特点。3、熟练掌握各种基本数据结构的存储结构、逻辑结构及相关算法,能够根据实际问题选择合适的数据结构。4、掌握各种数据结构在排序和查找等常用算法中的应用。5、掌握算法时空复杂性分析的基本技巧。6、了解数据结构课程中各知识点的来龙去脉及相互关系。7、注重培养学生利用算法语言和面向对象程序设计语言设计算法和编写程序的技巧与能力。8、注重培养学生的创新能力,采用理论与实践相结合的方法,利用启发式教学方式,提高学生分析问题和解决问题的能力,使学生完成本门课程的学习任务之后,能够综合运用多种数据结构解决实际问题。三、各章节内容及学时分配整个课程内容可分为十一章,具体章节如下。绪论(理论教学4学时)知识点:数据结构的的逻辑结构、存储结构及数据运算的含义及相互关系;算法时间和空间复杂度分析;算法描述语言;复杂性函数渐进表示。重点:数据结构的的逻辑结构、存储结构及数据运算;算法时间和空间复杂度分析。1.1为什么要学习数据结构(1.1与1.2共2学时)1.2数据结构概念1.2.1数据的逻辑结构1.2.2数据的存储结构1.2.3对数据结构的操作1.2.4数据结构示例1.3算法(1.3至1.5共2学时)1.3.1算法及其特性1.3.2算法的描述1.3.3算法的评价准则1.4算法的正确性证明1.5算法分析基础1.5.1算法时间复杂性的分析方法1.5.2复杂性函数的渐进表示1.5.3算法时间与空间分析1.5.4计算复杂性和算法的效率第二章线性表、堆栈、队列(理论教学10学时,实验教学8学时)知识点:线性表的定义;线性表的顺序和链接存储结构;单链表;循环链表;双向链表;堆栈的定义及应用、顺序栈、链式栈;队列的定义及应用、顺序队列、链式队列。重点:单链表;堆栈和队列的定义及其应用。2.1线性表的定义和基本操作(2.1与2.2共2学时)2.2线性表的顺序存储结构2.3线性表的链接存储结构(2.3与2.4共3学时)2.3.1单链表2.3.2循环链表2.3.3双向链表2.4复杂性分析2.5堆栈(3学时)2.5.1堆栈的定义和主要操作2.5.2顺序栈2.5.3链式栈2.5.4顺序栈与链式栈的比较2.5.5堆栈应用——括号匹配2.6队列(2学时)2.6.1队列的定义和主要操作2.6.2顺序队列2.6.3链式队列2.6.4顺序队列与链式队列的比较2.6.5队列与堆栈的扩展第三章数组和字符串(理论教学5学时)知识点:高维数组的存储和寻址方式;特殊矩阵的压缩存储方式;稀疏矩阵的压缩存储表示及操作算法。重点:稀疏矩阵的压缩存储表示及算法。3.1数组(2学时)3.1.1数组的存储和寻址3.1.2一维数组类3.2矩阵(2学时)3.2.1矩阵类3.2.2特殊矩阵3.2.3三元组表3.2.4十字链表3.3字符串(1学时)3.3.1字符串的定义与字符串类3.3.2模式匹配算法第四章树(理论教学14学时,实验教学8学时)知识点:树的定义;二叉树定义和主要性质;二叉树链接存储及操作;线索二叉树定义、存储和基本算法;树与二叉树的转换、树的存储;树与森林的遍历;哈夫曼树。重点:二叉树定义和主要性质;二叉树链接存储及操作;树与森林的遍历;哈夫曼树。4.1树的基本概念(1学时)4.1.1树的定义4.1.2树的相关术语4.2二叉树(3学时)4.2.1二叉树定义和主要性质4.2.2二叉树顺序存储4.2.3二叉树链接存储4.2.4二叉树遍历4.2.5创建二叉树4.2.6复制建二叉树4.3线索二叉树(2学时)4.3.1线索二叉树定义4.3.2线索二叉树存储4.3.3线索二叉树基本算法4.4树和森林(4学时)4.4.1树与二叉树的转换4.4.2树的顺序存储4.4.3树的链接存储4.4.4树和森林的遍历4.5压缩与哈夫曼树(2学时)4.5.1文件编码4.5.2扩充二叉树4.5.3哈夫曼树和哈夫曼编码4.6树的应用(2学时)4.6.1表达式求值4.6.2分类与决策树第五章图(理论教学13学时,实验教学8学时)知识点:图的基本概念;图的邻接矩阵和邻接表存储;图的深度优先和广度优先遍历;拓扑排序;关键路径;最短路径;普里姆算法和克鲁斯卡尔算法。重点:图的邻接矩阵和邻接表存储;图的深度优先和广度优先遍历;最短路径问题。5.1图的基本概念(5.1与5.2共1学时)5.2图的存储结构与类定义5.2.1存储结构5.2.2Graph类5.3图的遍历算法(2学时)5.3.1深度优先遍历5.3.2广度优先遍历5.4拓扑排序(2学时)5.5关键路径(2学时)5.6最短路径问题(2学时)5.6.1无权最短路径问题5.6.2正权最短路径问题5.6.3每对顶点之间的最短路径5.7最小支撑树(2学时)5.7.1普里姆算法5.7.25.8图的应用(2学时)5.8.1可及性与Warshall算法5.8.2连通分量5.8.3图在网络分析和信息检索中的应用第六章递归(理论教学4学时)知识点:递归的定义和基本过程;递归与堆栈关系;递归效率分析。重点:递归基本过程;递归与堆栈关系。6.1递归的定义(6.1与6.2共2学时)6.2基本递归过程6.3递归过程实现与堆栈(6.3至6.5共2学时)6.4递归法求解问题6.4.1委员会问题6.4.2回溯6.5递归的效率第七章排序(理论教学10学时,实验教学8学时)知识点:直接插入排序;Shell排序;冒泡排序;快速排序;直接选择排序;堆排序;合并排序;基于关键词比较的排序算法分析;基数分布;值分布。重点:Shell排序;快速排序;堆排序;合并排序。7.1排序的基本概念(7.1和7.2共2学时)7.2插入排序7.2.1直接插入排序7.2.2Shell排序7.3交换排序(2学时)7.3.1冒泡排序7.3.2快速排序7.4选择排序(2学时)7.4.1直接选择排序7.4.2堆排序7.5合并排序(1学时)7.6基于关键词比较的排序算法分析(1学时)7.6.1平方阶排序算法及改进算法7.6.2线性对数阶排序算法7.6.3分治排序的一般方法7.6.4基于关键词比较的排序算法下界7.7分布排序(1学时)7.7.1基数分布7.7.2值分布7.8外排序(1学时)7.8.1外存储器7.8.2磁带排序7.8.3磁盘排序第八章查找(理论教学12学时,实验教学4学时)知识点:有序表顺序查找;对半查找;斐波那契查找;二叉查找树概念和性质;二叉查找树的查找、插入和删除算法;最优二叉查找树;高度平衡树;B树及B+树;散列函数及冲突调解。重点:有序表顺序查找;对半查找;二叉查找树概念和性质;二叉查找树的查找、插入和删除算法;散列函数及冲突调解。8.1顺序查找(1学时)8.1.1无序表的顺序查找8.1.2有序表的顺序查找8.2基于关键词比较的查找(2学时)8.2.1对半查找8.2.2一致对半查找8.2.3斐波那契查找8.2.4插值查找8.3二叉查找树(2学时)8.3.1基本概念和性质8.3.2查找、插入和删除8.3.3平均情况时间分析8.4最优二叉查找树(1学时)8.4.1访问频率8.4.2最优二叉查找树8.4.3近似最优树的构造8.5平衡树(1学时)8.5.1高度平衡树8.5.2重量平衡树8.6红黑树(1学时)8.6.1红黑树的性质8.6.2旋转8.6.3插入8.6.4删除8.7B树及其变形树(1学时)8.7.1多叉树8.7.2B树8.7.3B树变形树8.8数字查找(1学时)8.9散列(2学时)8.9.1散列函数8.9.2冲突调解8.9.3删除8.9.4重量平衡树的应用——按位置查找由于课时所限,“内存管理”、“文件”和“随机数”作为选讲内容。第九章内存管理(理论教学4学时)9.1概述 (9.1和9.2共2学时)9.2均匀大小记录的分配和回收算法 9.2.1记录分配算法 9.2.2访问计数器法 9.2.3废料收集方法 9.3不同大小记录的分配和回收算法 (1学时)9.3.1查找分配策略 9.3.2边界标识法 9.3.3压缩分配 9.4伙伴系统 (1学时)9.4.1伙伴系统概述 9.4.2分配记录和释放记录算法 第十章文件(理论教学5学时)10.1文件的基本概念 (10.1和10.2共2学时)10.1.1文件及其分类 10.1.2文件的逻辑结构与存储结构 10.2顺序文件 10.2.1顺序无序文件 10.2.2顺序有序文件 10.2.3增补文件 10.3杂凑文件 (1学时)10.3.1杂凑(散列、哈希)文件 10.3.2可扩充的杂凑文件 10.4索引文件 (1学时)10.4.1动态索引结构和静态索引结构 10.4.2ISAM文件 10.4.

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论