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

《数据结构与算法--教学大纲》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、~《数据结构与算法》教学大纲适用专业：_信息与技术科学_理论学时：_36_实践学时：___36__一、课程说明1、开课的意义，课程的性质、目的与任务《数据结构》是计算机科学与技术专业的一门重要专业基础课,用计算机解决任何实际问题都离不开数据的表示和数据处理,而数据的表示和处理的核心问题之一是数据结构及其实现----这正是数据结构的基本内容。从这个意义上来讲,数据结构课程在知识学习和技能的培养两个方面都处于关键性地位。该课程不仅为数据库及其应用、编译、操作系统、网络等后继课程提供了必要基础知识,也为计算机及应用专业人员提供了必要的技能训

2、练。2、课程的教学目标及要求(1)知识方面：从数据结构及其实现这两个层次及其相互关系的角度,系统地学习和掌握常用基本数据构,及其不同的实现,了解并掌握分析、比较和选择不同数据结构及不同存储结构、不同运算实现的原则和方法,为后继课程的学习打好基础(2)技能方面:系统学习和掌握在不同存储结构上实现不同算法及其设计思想,从中休会并撑握结构选择和算法设计的思维方式及技巧,提高分析问题和解决问题的能力3、课程与其他课程的联系与分工本课程要求的预备知识有：统计学、数据库、数据仓库、人工智能。4、课程简表课程类型课时数考核方式专业必修72考试二、大

3、纲本文（一）课程内容与重点难点第一章.绪论教学内容：介绍数据结构中常用的基本概念和术语及学习数据结构的意义。教学要求：熟练掌握数据结构的一些基本术语和概念，了解抽象数据类型定义和使用，了解算法的基本概念和术语，了解算法的描述方法，掌握算法的时间复杂性分析。重点：了解数据结构的逻辑结构、存储结构及数据的运算三方面的概念及相互关系，算法的概念和特性。难点：算法时间复杂性分析方法。~~~~第二章.线性表教学内容：介绍线性表的逻辑结构和存储表示方法，以及定义在逻辑结构上的各种基本运算及其在存储结构上如何实现这些基本运算。教学要求：熟练掌握线性

4、表的基本概念和类型定义；熟练掌握对顺序表和单链表的常用操作方法及其程序实现；了解循环链表和双向链表的定义和它的插入、删除等操作方法。重点：熟练掌握顺序表和单链表上实现的各种基本算法及相关的时间性能分析。难点：使用本章所学到的基本知识设计有效算法解决与线性表相关的应用问题。第三章.特殊线性表——栈、队列和串教学内容：介绍栈和队列的逻辑结构定义以及在存储结构上如何实现栈和队列的基本运算，介绍串的逻辑结构、存储结构及其串上的基本运算。教学要求：熟练掌握栈和队列的定义，掌握顺序和链式存储的栈和队列的各种运算的方法及程序实现，掌握表达式求值等经

5、典问题求解方法并了解其算法，掌握串的有关概念及基本运算，掌握串的存储结构，理解串的BF算法，了解KMP算法。重点：熟练掌握栈和队列的特点；掌握栈和队列在两种存储结构上实现的基本运算。难点：两栈共享空间；循环队列边界条件的处理；队满队空的判定条件，串的模式匹配算法。第四章．广义线性表——数组和广义表教学内容：介绍数据的逻辑结构特征及其存储方式，特殊矩阵和稀疏矩阵的压缩存储方法及广义表的概念。教学要求：掌握数组的逻辑结构特征及其存储方式，了解特殊矩阵和稀疏矩阵的压缩存储方法及广义表的概念，了解广义表的逻辑结构和存储结构。重点：掌握数组的存

6、储方式。难点：稀疏矩阵压缩存储表示下实现的算法。第五章．树和二叉树教学内容：介绍树、二叉树等的有关概念、存储结构等方面。教学要求：掌握树的定义、性质、存储结构，熟练掌握二叉树的定义、性质、存储结构及各种遍历算法与实现，掌握树与二叉树的转换，了解线索二叉树，了解树的遍历，了解哈夫曼树的定义，一般了解其应用，了解森林与二叉树转换等。~~~~重点：掌握二叉树的性质及遍历算法及其有关应用。难点：二叉树的非递归算法，使用本章所学到的有关知识设计出应用问题的有效算法。第六章．图教学内容：介绍图的概念、两种常用的存储结构、两种遍历算法以及图的应用算

7、法。教学要求：掌握图的定义和术语；掌握邻接矩阵和邻接表表示法；熟练掌握图两种遍历的基本思想和算法；了解求图的最小生成树的prim和kruskal算法；了解最短路径问题和拓扑排序。重点：掌握在图的两种存储结构上实现的遍历算法。难点：求最小生成树，求最短路径以及拓扑排序。第七章．检索技术教学内容：介绍关于线性表、树和哈希表的查找方法、算法实现以及各种查找方法的时间性能（平均查找长度）分析。教学要求：理解查找的基本概念，掌握线性表的顺序查找的思想和算法；理解二叉查找树的概念以及二叉查找树上查找的基本思想和算法；理解平衡二叉树的调整方法；理解

8、哈希表、哈希表构造的基本方法以及处理冲突的方法；以及各种查找方法的时间性能分析。重点：掌握顺序查找、折半查找，二叉查找树上查找的基本思想和算法实现。难点：二叉查找树的删除算法。第八章．排序技术教学内容：介绍内部排序方法的