(2014-2015-1)-《数据结构》教学大纲.doc

数据结构课程教学大纲一、课程基本信息1、课程编号：2、课程名称：数据结构3、英文名称：Data Structure4、适用专业：网络工程5、课程简介：用数字计算机解决实际问题都离不开数据表示和数据处理，而数据表示和处理的核心问题致意是数据结构及实现这正是数据结构课程的基本内容。数据结构课程在知识学习和技能培养两个方面都处于关键性地位。二、课程说明1、教学目的要求：通过本课程的学习，应达到知识和技能两方面的目标：知识方面：从数据结构及其实现的角度系统地学习和掌握常用基本数据结构及其不同的实现方法，了解并掌握分析、比较和选择不同数据结构及不同存储结构、不同算法实现的原则和方法，为后继课程的学习打下良好的基础。技能方面：通过对本课程的知识传递、算法设计和上机实践的训练，培养学生的数据抽象能力、逻辑思维能力和程序设计的能力，提高分析问题和解决问题的能力。2、与相关课程衔接：先修课程：面向对象编程、操作系统原理。后继课程：数据库等。3、周学时/总学时：4学时/68学时。其中理论课时38，实验课时30。4、开课学期：第3学期5、教学方式：课堂讲授与实验并重。6、考试方式：期末笔试占50%、期中测验20%、实验20%、平时表现10%。7、作业：课后安排适当的作业。8、教材：数据结构C+版王红梅 胡明 王涛. 清华大学出版社,2009 9、教学参考书：1 数据结构（C+版）学习辅导和实验指导王红梅 胡明 王涛. 清华大学出版社,20052 数据结构（C+版）教师用户王红梅 胡明 王涛. 清华大学出版社,20053 数据结构与算法许卓群等编著. 数据结构与算法. 高等教育出版社,20084 数据结构严蔚敏等编著. 清华大学出版社, 1997三、课程理论内容与教学要求第1章 绪论熟练掌握数据结构的一些基本术语和概念，了解抽象数据类型定义和使用，了解算法的基本概念和术语，了解算法的描述方法，掌握算法的时间复杂性分析。主要内容：1.1数据结构在程序设计中的作用1.2数据结构的研究对象1.3数据结构的基本概念1.4算法及算法分析重点：了解数据结构的逻辑结构、存储结构及数据的运算三方面的概念及相互关系，算法的概念和特性。难点：算法时间复杂性分析方法。学时分配：理论课4学时。第2章 线性表熟练掌握线性表的基本概念和类型定义；熟练掌握对顺序表和单链表的常用操作方法及其程序实现；了解循环链表和双向链表的定义和它的插入、删除等操作方法。主要内容：2.1线性表的逻辑结构2.2线性表的顺序存储结构及实现2.3线性表的链接存储结构及实现2.4顺序表和单链表的比较2.5线性表的其他存储方法重点：熟练掌握顺序表和单链表上实现的各种基本算法及相关的时间性能分析。难点：使用本章所学到的基本知识设计有效算法解决与线性表相关的应用问题。学时分配：理论课4学时，实验课6学时。第3章 栈和队列熟练掌握栈和队列的定义，掌握顺序和链式存储的栈和队列的各种运算的方法及程序实现，掌握表达式求值等经典问题求解方法并了解其算法。主要内容： 3.1栈3.2队列重点：熟练掌握栈和队列的特点；掌握栈和队列在两种存储结构上实现的基本运算。难点：两栈共享空间；循环队列边界条件的处理；队满队空的判定条件，串的模式匹配算法。学时分配：理论课2学时，实验课4学时。第4章 字符串和多维数组掌握串的有关概念及基本运算，掌握串的存储结构，理解串的BF算法，了解KMP算法。掌握数组的逻辑结构特征及其存储方式，了解特殊矩阵和稀疏矩阵的压缩存储方法。主要内容：4.1 字符串4.2多维数组4.3矩阵的压缩存储重点：掌握数组的存储方式。难点：稀疏矩阵压缩存储表示下实现的算法。学时分配：理论课4学时，实验课2学时第5章 树和二叉树掌握树的定义、性质、存储结构，熟练掌握二叉树的定义、性质、存储结构及各种遍历算法与实现，掌握树与二叉树的转换，了解线索二叉树，了解树的遍历，了解哈夫曼树的定义，一般了解其应用，了解森林与二叉树转换等。主要内容：5.1树的逻辑结构5.2树的存储结构5.3二叉树的逻辑结构5.4二叉树的存储结构及实现5.5树、森林与二叉树的转换重点：掌握二叉树的性质及遍历算法及其有关应用。难点：二叉树的非递归算法，使用本章所学到的有关知识设计出应用问题的有效算法。学时分配：理论课6学时，实验课6学时。第6章 图掌握图的定义和术语；掌握邻接矩阵和邻接表表示法；熟练掌握图两种遍历的基本思想和算法；了解求图的最小生成树的prim和kruskal算法；了解最短路径问题和拓扑排序。主要内容：6.1图的逻辑结构6.2图的存储结构及实现6.3最小生成树6.4最短路径重点：掌握在图的两种存储结构上实现的遍历算法。难点：求最小生成树，求最短路径以及拓扑排序。学时分配：理论课6学时，实验课4学时。第7章 查找技术理解查找的基本概念，掌握线性表的顺序查找的思想和算法；理解二叉查找树的概念以及二叉查找树上查找的基本思想和算法；理解平衡二叉树的调整方法；理解哈希表、哈希表构造的基本方法以及处理冲突的方法；以及各种查找方法的时间性能分析。主要内容：7.1概述7.2线性表的查找技术7.3树表的查找技术7.4散列表的查找技术重点：掌握顺序查找、折半查找，二叉查找树上查找的基本思想和算法实现。难点：二叉查找树的删除算法。学时分配：理论课4学时，实验课4学时。第8章 排序技术排序是计算机程序设计的重要运算，是数据处理的一项基本活动。掌握内部排序方法的指导思想和特点，熟悉各种内部排序算法并理解其基本思想；了解各种内排序算法的优缺点、时间和空间的性能比较以及使用场合。主要内容：8.1概述8.2插入排序8.3交换排序8.4选择排序8.5归并排序8.6 分配排序8.7各种排序方法的比较重点：各种内排序的基本思想及内排序方法的执行过程。难点：各种内排序方法的实现。学时分配：理论课6学时，实验课4学时。第9章 索引技术索引是为了加快查找速度而设计的一种数据结构，索引技术是组织大型数据库以及磁盘文件的一项重要技术。本章介绍基本的线性索引技术和树形索引技术。主要内容：9.1索引的基本概念9.2线性索引技术9.3树形索引重点：树形索引难点：B