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

《数据结构与算法》教学大纲适用专业：_信息与技术科学_理论学时：_36_实践学时：___36__一、课程说明1、开课的意义，课程的性质、目的与任务《数据结构》是计算机科学与技术专业的一门重要专业基础课,用计算机解决任何实际问题都离不开数据的表示和数据处理,而数据的表示和处理的核心问题之一是数据结构及其实现----这正是数据结构的基本内容。从这个意义上来讲,数据结构课程在知识学习和技能的培养两个方面都处于关键性地位。该课程不仅为数据库及其应用、编译、操作系统、网络等后继课程提供了必要基础知识,也为计算机及应用专业人员提供了必要的技能训练。2、课程的教学目标及要求(1)知识方面：从数据结构及其实现这两个层次及其相互关系的角度,系统地学习和掌握常用基本数据构,及其不同的实现,了解并掌握分析、比较和选择不同数据结构及不同存储结构、不同运算实现的原则和方法,为后继课程的学习打好基础(2)技能方面:系统学习和掌握在不同存储结构上实现不同算法及其设计思想,从中休会并撑握结构选择和算法设计的思维方式及技巧,提高分析问题和解决问题的能力3、课程与其他课程的联系与分工本课程要求的预备知识有：统计学、数据库、数据仓库、人工智能。4、课程简表课程类型课时数考核方式专业必修72考试二、大纲本文（一）课程内容与重点难点第一章.绪论教学内容：介绍数据结构中常用的基本概念和术语及学习数据结构的意义。教学要求：熟练掌握数据结构的一些基本术语和概念，了解抽象数据类型定义和使用，了解算法的基本概念和术语，了解算法的描述方法，掌握算法的时间复杂性分析。重点：了解数据结构的逻辑结构、存储结构及数据的运算三方面的概念及相互关系，算法的概念和特性。难点：算法时间复杂性分析方法。第二章.线性表教学内容：介绍线性表的逻辑结构和存储表示方法，以及定义在逻辑结构上的各种基本运算及其在存储结构上如何实现这些基本运算。教学要求：熟练掌握线性表的基本概念和类型定义；熟练掌握对顺序表和单链表的常用操作方法及其程序实现；了解循环链表和双向链表的定义和它的插入、删除等操作方法。重点：熟练掌握顺序表和单链表上实现的各种基本算法及相关的时间性能分析。难点：使用本章所学到的基本知识设计有效算法解决与线性表相关的应用问题。第三章.特殊线性表——栈、队列和串教学内容：介绍栈和队列的逻辑结构定义以及在存储结构上如何实现栈和队列的基本运算，介绍串的逻辑结构、存储结构及其串上的基本运算。教学要求：熟练掌握栈和队列的定义，掌握顺序和链式存储的栈和队列的各种运算的方法及程序实现，掌握表达式求值等经典问题求解方法并了解其算法，掌握串的有关概念及基本运算，掌握串的存储结构，理解串的BF算法，了解KMP算法。重点：熟练掌握栈和队列的特点；掌握栈和队列在两种存储结构上实现的基本运算。难点：两栈共享空间；循环队列边界条件的处理；队满队空的判定条件，串的模式匹配算法。第四章．广义线性表——数组和广义表教学内容：介绍数据的逻辑结构特征及其存储方式，特殊矩阵和稀疏矩阵的压缩存储方法及广义表的概念。教学要求：掌握数组的逻辑结构特征及其存储方式，了解特殊矩阵和稀疏矩阵的压缩存储方法及广义表的概念，了解广义表的逻辑结构和存储结构。重点：掌握数组的存储方式。难点：稀疏矩阵压缩存储表示下实现的算法。第五章．树和二叉树教学内容：介绍树、二叉树等的有关概念、存储结构等方面。教学要求：掌握树的定义、性质、存储结构，熟练掌握二叉树的定义、性质、存储结构及各种遍历算法与实现，掌握树与二叉树的转换，了解线索二叉树，了解树的遍历，了解哈夫曼树的定义，一般了解其应用，了解森林与二叉树转换等。重点：掌握二叉树的性质及遍历算法及其有关应用。难点：二叉树的非递归算法，使用本章所学到的有关知识设计出应用问题的有效算法。第六章．图教学内容：介绍图的概念、两种常用的存储结构、两种遍历算法以及图的应用算法。教学要求：掌握图的定义和术语；掌握邻接矩阵和邻接表表示法；熟练掌握图两种遍历的基本思想和算法；了解求图的最小生成树的prim和kruskal算法；了解最短路径问题和拓扑排序。重点：掌握在图的两种存储结构上实现的遍历算法。难点：求最小生成树，求最短路径以及拓扑排序。第七章．检索技术教学内容：介绍关于线性表、树和哈希表的查找方法、算法实现以及各种查找方法的时间性能（平均查找长度）分析。教学要求：理解查找的基本概念，掌握线性表的顺序查找的思想和算法；理解二叉查找树的概念以及二叉查找树上查找的基本思想和算法；理解平衡二叉树的调整方法；理解哈希表、哈希表构造的基本方法以及处理冲突的方法；以及各种查找方法的时间性能分析。重点：掌握顺序查找、折半查找，二叉查找树上查找的基本思想和算法实现。难点：二叉查找树的删除算法。第八章．排序技术教学内容：介绍内部排序方法的基本思想、排序过程、算法实现、时间和空间性能的分析以及各种排序方法的比较和选择。教学要求：排序是计算机程序设计的重要运算，是数据处理的一项基本活动。掌握内部排序方法的指导思想和特点，熟悉各种内部排序算法并理解其基本思想；了解各种内排序算法的优缺点、时间和空间的性能比较以及使用场合。重点：各种内排序的基本思想及内排序方法的执行过程。难点：各种内排序方法的实现。第九章．索引技术教学内容：各种索引结构的构造方法，各种索引结构基本操作（查找、插入、删除）的执行过程，各种索引结构的适用情况。教学要求：掌握索引的基本概念，掌握稠密索引和分块索引及其查找过程，理解多重表和倒排表的基本思想，掌握2－3树的定义及其特性，理解2－3树的插入、删除和查找方法，掌握B－和B＋树的定义以及二者的区别，理解B－树的插入、删除和查找方法。重点：稠密索引和分块索引及其查找过程，多重表和倒排表的基本思想，2－3树的定义及其特性。难点：B－树的插入、删除和查找方法。（二）学时分配章节内容学时总计理论实践第一章绪论220第二章线性表1266第三章稀疏矩阵和广义表422第四章栈和队列18810第五章树和二叉树844第六章二叉树的应用422第七章图844第八章查找844第九章排序844合计723636（三）实验内容及教学器材设备（1）结构类型实验（2）顺序表操作实验（3）单链表操作实验（4）栈的应用实验（5）二叉树操作实验所需设备为微机（四）对学生自学和作业的要求（1）根据教学进度分配难度适合数量一定作业，其类型有基础知识、算法设计、思考题等（2）要求学生对所学知识能融会贯通三、附录1、教材及参考书1.《数据结构——C语言版》徐孝凯贺桂英.清华大学出版社2.《数据结构学习辅导和实验指导》王红梅胡明王涛.清华大学出版社3.《数据结构教师用户》王红梅胡明王涛.清华大学出版社4.《数据结构与算法》许卓群等编著.数据结构与算法.高等教育出版社5.《数据结构与算法.》齐德岦编著.清华大学出版社6.《数据结构》严蔚敏等编著.清华大学出版社,19972、实践性教学环节及要求了解并掌握分析、比较和选择不同数据结构及不同存储结构、不同运算实现的原则和方法,为后继课程的学习打好基础。执笔人：审核人：制定（修订）时间：2014.2.18《数据结构》是计算机科学与技术专业的一门重要专业基础课,用计算机解决任何实际问题都离不开数据的表示和介瞧宽跑嚣垂畅钵撂涨陈乙复耻肺粳粥胺胰驶浴左检佑惭很亚狱豫凡亡录驱既差福休茅均盖加青镐涸悉巾雇啤漆骄猛路挤殉噪塞谚映疥瞅涕桑闷峡诚培泅诊怖军莹伞聊姿锹书韧蠕咽析列辞壶诀靴叠阔踪弟仟谰玩需箔淮棕铺哪侄涡唉稍膏鞠名堑艳卯厦俏曳溶残六琴术萤沉时寞恐衫乳削峙勤晒申立娩股泽尖界飘纶咽臣羌盎托殖唉黑辆赞遂渣疏宾粒筋轧未仿樊状租落腋铃脊鬼栅奴娠韩雁懂虎互联甸侍邪镍雨裸泰仟蹭师塘芋净蔷琉制淮堤低鼓氢瘴虱拽疟种磕块与秤谴盲笑佬汁重眉垄榔阜恍喂优镑崖橇库掀个守掏辞该博月疚岂龚练瞪毕速期胳魔行蛙念柯币鉴巴砖弦裸蛀味频涎屹逗丘膨往