《数据结构》课程教学大纲

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

1、《数据结构》课程教学大纲仅次于选择益友，就是选择好书。——考尔德《数据结构A》课程教学大纲DataStructureA课程代码：课程性质：专业基础理论课/必修适用专业：信息计算、信息安全开课学期：5总学时数：72总学分数：4.5编写年月：2003年7月修订年月：2007年7月执笔：高学军、刘科峰、李小英　　一、课程的性质和目的　　数据结构是信息与计算科学专业的一门重要专业基础课程。当用计算机来解决实际问题时，就要涉及到数据的表示及数据的处理，而数据表示及数据处理正是数据结构课程的主要研究对象，通过这两方面内容的学习，为后续课程，特别是软件方面的课程打下了厚实的知识基础，同时也提供

2、了必要的技能训练。因此，数据结构课程在信息与计算科学专业中具有举足轻重的作用。　　二、课程教学内容及学时分配　　第1章　绪论　（4学时）　　理解数据、数据元素和数据项的概念及其相互间的关系。理解数据结构的逻辑结构、存储结构的联系与区别，以及在数据结构上施加的运算及其实现。掌握简单的算法分析方法。　　本章知识点为：数据、数据元素、数据对象、数据结构、存储结构和数据类型等概念术语的确定含义；抽象数据类型的定义、表示和实现方法；描述算法的类C语言；算法设计的基本要求以及从时间和空间角度分析算法的方法。　　第2章　线性表　（10学时，2个学时实验上机）　　理解线性表的定义及其运算。理解顺序

3、表和链表的定义、组织形式、结构特征和类型说明，掌握在这两种表上实现的插入、删除和按值查找的算法。了解循环链表、双向(循环)链表的结构特点和在其上施加的插入、删除等操作。掌握稀疏多项式在线性表的两种存储结构上的实现方法。　　本章知识点为：线性表的逻辑结构定义、抽象数据类型定义和各种存储结构的描述方法；在线性表的两类存储结构(顺序的和链式的)上实现基本操作；稀疏多项式的抽象数据类型定义、表示和加法的实现。　　第3章　栈和队列　（6学时，2个学时实验上机）　　理解栈和队列的定义、特征及在其上所定义的基本运算。掌握在两种存储结构上对栈和队列所施加的基本运算的实现。熟练掌握循环队列和链队列的

4、基本操作实现算法，尤其是队满和队空的描述方法。　　本章知识点为：抽象数据类型栈的定义；栈的表示和实现；栈的应用；抽象数据类型队列的定义；链队列；循环队列。　　第4章　串　（4学时，2个学时实验上机）　　熟悉串的七种基本操作的定义，并能利用这些基本操作来实现串的其它各种操作的方法。熟练掌握在串的定长顺序存储结构上实现串的各种操作的方法。掌握串的堆存储结构以及在其上实现串操作的基本方法。　　本章知识点为：串的数据类型定义；串的三种存储表示：定长顺序存储结构、块链存储结构和堆分配存储结构；串的各种基本操作的实现及其应用；　　第5章　数组和广义表　（6学时，2个学时实验上机）　　了解数组的

5、两种存储表示方法，并掌握数组在以行为主的存储结构中的地址计算方法。掌握对特殊矩阵进行压缩存储时的下标变换公式。了解稀疏矩阵的两种压缩存储方法的特点和适用范围，领会以三元组表示稀疏矩阵时进行矩阵运算采用的处理方法。掌握广义表的结构特点及其存储表示方法。　　本章知识点为：数组的类型定义和表示方式；特殊矩阵和稀疏矩阵的压缩存储方法及运算的实现；广义表的逻辑结构和存储结构和广义表的操作。　　第6章　树和二叉树　（12学时，2个学时实验上机）　　深刻理解树的定义、性质及其存储方法，熟练掌握二叉树的二叉链表存储方式、结点结构和类型定义，并能画出给定二叉树的二叉链表的结构示意图；理解并掌握二叉树

6、的三种遍历方法，并能写出该三种遍历的算法；会完成树、森林与二叉树间的相互转换；理解哈夫曼树的构造方法，并能对给定的数据集合构造出哈夫曼树。　　本章知识点为：二叉树的定义、性质和存储结构；二叉树的遍历和线索化以及遍历算法的各种描述形式；树和森林的定义、存储结构、与二叉树的转换、遍历；树的多种应用。　　第7章　图　（12学时，2个学时实验上机）　　理解图的基本概念及术语，掌握图的两种存储结构(邻接矩阵和邻接表)的表示方法；熟练掌握图的两种遍历(深度优先搜索遍历和广度优先搜索遍历)的算法思想、步骤，并能列出在两种存储结构上按上述两种遍历算法得到的序列；理解最小生成树的概念，能按Prim算

7、法构造最小生成树；了解并掌握拓扑排序、关键路径、最短路径的算法思想。　　本章知识点为：图的定义和术语；图的四种存储结构：数组表示法、邻接表、十字链表和邻接多重表；图的两种遍历策略：深度优先搜索和广度优先搜索；图的连通性：连通分量和最小生成树；拓扑排序和关键路径；两类求最短路径问题的解法。第8章　查找　（10学时，2个学时实验上机）　　了解查找的基本思想及查找成功和不成功的概念，掌握在顺序表、有序表、索引表、散列表等上的查找方法和算法，并能求出相应的平均查找长度。　　本