课程内容与考核目标
第1章 概论
（一）课程内容
　1.1 基本概念和术语
　1.2 学习数据结构的意义
　1.3 算法的描述和分析
（二）学习目的与要求
　　本章的目的是介绍数据结构中常用的基本概念和术语以及学习数据结构的意义，要求了解本章介绍的各种基本概念和术语，掌握算法描述和分析的方法。本章重点是了解数据结构的逻辑结构、存储结构及数据的运算三方面的概念及相互关系，难点是算法复杂度的分析方法。
（三）考核知识点与考核要求
　1.数据结构的基本概念和术语、要求达到“识记”层次。
　　1.1 数据、数据元素、数据项、数据结构等基本概念。
　　1.2 数据结构的逻辑结构、存储结构及数据运算的含义及其相互关系。
 　 1.3 数据结构的两大类逻辑结构和四种常用的存储表示方法。
　2.数据结构在软件系统中的作用，要求达到“识记”层次。
　　2.1 数据结构在各种软件系统中所起的作用。
　　2.2 选择合适的数据结构是解决应用问题的关键步骤。
　3.算法的描述和分析，要求达到“领会”层次。
　　3.1 算法、算法的时间复杂度和空间复杂度、最坏的和平均的时间复杂度等概念。
　　3.2 算法的时间复杂度不仅仅依赖于问题的规模，也取决于输入实例的初始状态。
        3.3 算法描述和算法分析的方法，对于一般算法能分析出时间复杂度。
第2章 线性表
（一）课程内容
  　2.1 线性表的逻辑结构
  　2.2 线性表的顺序存储结构
  　2.3 线性表的链式存储结构
  　2.4 顺序表和链表的比较
（二）学习目的与要求
　　本章目的是介绍线性表的逻辑结构和各种存储表示方法，以及定义在逻辑结构上的各种基本运算及其在存储结构上如何实现这些基本运算。要求在熟悉这些内容的基础上，能够针对具体应用问题的要求和性质，选择合适的存储结构设计出相应的有效算法，解决与线性表相关的实际问题。本章重点是熟练掌握顺序表和单链表上实现的各种基本算法及相关的时间性能分析，难点是能够使用本章所学到的基本知识设计有效算法解决与线性表相关的应用问题。
（三）考核知识与考核要求
  1.线性表的逻辑结构，要求达到“识记”层次。
  　1.1 线性表的逻辑结构特征。
　　1.2 线性表上定义的基本运算，并能利用基本运算构造出较复杂的运算。
　2.线性表的顺序存储结构，要求达到“综合利用”层次。
　　2.1 顺序表的含义及特点，即顺序表如何反映线性表中元素之间的逻辑关系。
　　2.2 顺序表上的插入、删除操作及其平均时间性能分析。
　　2.3 利用顺序表设计算法解决简单的应用问题。
　3.线性表的链式存储结构，要求达到“综合应用”层次。
　　3.1 链表如何表示线性表中元素之间的逻辑关系。
　　3.2 链表中头指针和头结点的使用。
　　3.3 单链表、双链表、循环链表链接方式上的区别。
　　3.4 单链表上实现的建表、查找、插入和删除等基本算法，并分析其时间复杂度。
    3.5  循环链表上尾指针取代头指针的作用，以及单循环链表上的算法与单链表上相应算法的异同点。
    3.6 双链表的定义及其相关的算法。
　　3.7 利用链表设计算法解决简单的应用问题。
　4.顺序表和链表的比较，要求达到“领会”层次。
　　4.1 顺序表和链表的主要优缺点。
　　4.2 针对线性表上所需要执行的主要操作，知道选择顺序表还是链表作为其存储结构才能取得较优的时空性能。
第3章 栈和队列
（一）课程内容
　3.1 栈
　3.2 队列
　3.3 栈和队列的应用
（二）学习目的与要求
　　本章目的是介绍栈和队列的逻辑结构定义及在两种存储结构上如何实现栈和队列的基本运算。要求在掌握栈和队列的特点的基础上，懂得在什么样的情况下能够使用栈或队列。本章重点是掌握栈和队列在两种存储结构上实现的基本运算，难点是循环队列中对边界条件的处理。
（三）考核知识与考核要求
　1.栈的逻辑结构、存储结构及其相关算法，要求达到“综合应用”层次。
　　1.1 栈的逻辑结构特点，栈与线性表的异同。
　　1.2 顺序栈和链栈上实现的进栈、退栈等基本算法。
　　1.3 栈的“上溢”和“下溢”的概念及其判别条件。
　　1.4 利用栈设计算法解决简单的应用问题。
　2.队列的逻辑结构、存储结构及其相关算法，要求达到“综合应用”层次。
　　2.1 队列的逻辑结构特点，队列与线性表的异同。
　　2.2 顺序队列（主要是循环队列）和链队列上实现的入队、出队等基本算法。
　　2.3 队列的“上溢”和“下溢”的概念及其判别条件。
　　2.4 使用数组实现的循环队列取代普通的顺序队列的原因。
　　2.5 循环队列中对边界条件的处理方法。
　　2.6 利用队列设计算法解决简单的应用问题。
　3.栈和队列的应用，要求达到“领会”层次。
　　栈和队列的特点，什么样的情况下能够使用栈或队列。
第4章 串
（一）课程内容
　4.1 串及其运算
　4.2 串的存储结构
（二）学习目的与要求
　　本章目的是介绍串的逻辑结构、存储结构及其串上的基本运算，由于C语言及其它高级语言均已具备了较强的串处理功能，故本章重点是掌握串上实现的模式匹配算法，这也是本长的难点。
（三）考核知识与考核要求
　1.串及其运算，要求达到“领会”层次。
　　1.1 串的有关概念及基本运算。
　　1.2 串与线性表的关系。
　2.串的存储结构，要求达到“简单应用”层次。
　　2.1 串的两种存储表示。
　　2.2 串上实现的模式匹配算法及其时间性能分析。
　　2.3 使用C语言提供的串操作函数构造与串相关的算法解决简单的应用问题。
第5章 多维数组和广义表
（一）课程内容
　5.1 多维数组
　5.2 矩阵的压缩存储
　5.3 广义表的概念
（二）学习目的与要求
　　本章目的是介绍多维数组的逻辑结构特征及其存储方式，特殊矩阵和稀疏矩阵的压缩存储方法及广义表的概念，要求考生熟悉这些内容。本章重点是熟悉多维数组的存储方式、矩阵的压缩存储方式、广义表的定义及其求表头和表尾的运算，难点是稀疏矩阵的压缩存储表示下实现的算法。
（三）考核知识点与考核要求
　1.多维数组，要求达到“领会”层次。
　　1.1 多维数组的逻辑结构特征。
　　1.2 多维数组的顺序存储结构及地址计算方式。
　　1.3 数组是一种随机存取结构的原因。
　2.矩阵的压缩存储，要求达到“领会”层次。
　　2.1 特殊矩阵和稀疏矩阵的概念。
　　2.2 特殊矩阵和压缩存储时的下标变换方法。
　　2.3 稀疏矩阵的三元组表表示方法及有关算法。
　3.广义表的概念，要求达到“领会”层次。
　　3.1 广义表的有关概念及其与线性表的关系。
　　3.2 广义表的括号表示和图形表示之间的转换。
　　3.3 求给定的非空广义表的表头和表尾运算。
第6章 树
（一）课程内容
　6.1 树的概念
　6.2 二叉树
　6.3 二叉树的遍历
　6.4 线索二叉树
　6.5 树和森林
　6.6 哈夫曼树及其应用
（二）学习目的与需求
　　本章目的是介绍二叉树的定义、性质、存储结构、遍历、线索化、树的定义、存储结构、遍历、树和森林与二叉树的转换，哈夫曼树及哈夫曼编码等内容。要求在熟悉这些内容的基础上，重点掌握二叉树的遍历算法及其相关应用，难点是使用本章所学到的有关知识设计出有效算法，解决与树或二叉树相关的应用问题。
（三）考核知识点与考核要求
　1.树的概念，要求达到“领会”层次。
　　1.1 树的逻辑结构特征。
　　1.2 树的不同表示方法。
　　1.3 树的常用术语及含义。
　2.二叉树，要求达到“简单应用”层次。
　　2.1 二叉树的递归定义及树与二叉树的差别。
　　2.2 二叉树的性质，了解相应的证明方法。
　　2.3 二叉树的两种存储方法、特点及适用范围。
　3.二叉树的遍历，要求达到“综合应用”层次。
　　3.1 二叉树的三种遍历算法，理解其执行过程。
　　3.2 确定三种遍历所得到的相应的结点访问序列。
　　3.3 以遍历算法为基础，设计有关算法解决简单的应用问题。
　4.线索二叉树，要求达到“领会”层次。
　　4.1 二叉树线索化的目的及实质。
　　4.2 在中序线索树中查找给定结点的中序前趋和中序后继的方法。
　　4.3 查找给定结点的前序前趋和后序后继并非有效的原因。
　5.树和森林，要求达到“领会”层次。
　　5.1 树和森林与二叉树之间的转换方法。
　　5.2 树的各种存储结构及其特点。
　　5.3 树的两种遍历方法。
　6.哈夫曼树及其应用，要求达到“简单应用”层次。
　　6.1 最优二叉树和最优前缀码的概念及特点。
　　6.2 哈夫曼算法的思想。
　　6.3 根据给定的叶结点及其权值构造出相应的最优二叉树。
　　6.4 根据最优二叉树构造对应的哈夫曼编码。
第7章 图
（一）课程内容
  7.1 图的概念
　7.2 图的存储结构
　7.3 图的遍历
　7.4 生成树和最小生成树
　7.5 最短路径
　7.6 拓扑排序
（二）学习目的与要求
　　本章目的是介绍图的基本概念、两种常用的存储结构、两种遍历算法以及图的应用算法，要求考生在熟悉这些内容的基础上，重点掌握在图的两种存储结构上实现的遍历算法。本章难点是图的应用算法：求最小生成树，求最短路径以及拓扑排序，只要求考生掌握这些算法的基本思想及时间性能。
（三）考核知识与考核要求
　1.图的概念，要求达到“领会”层次。
　　1.1 图的逻辑结构特征。
　　1.2 图的常用术语及含义。
　2.图的存储结构，要求达到“简单应用”层次。
　　2.1 邻接矩阵和邻接表这两种存储结构的特点及适用范围。
　　2.2 根据应用问题的特点和要求选择合适的存储结构。
　3.图的遍历，要求达到“简单应用”层次。
　　3.1 连通图及非连通图的深度优先搜索和广度优先搜索两种遍历算法,其执行过程以及时间分析。
　　3.2 确定两种遍历所得到的顶点访问序列。
　　3.3 图的两种遍历与树的遍历之间的关系。
　　3.4 两种遍历所使用的辅助数据结构（栈或队列）在遍历过程中所起的作用。
　　3.5 利用图的两种遍历设计算法解决简单的应用问题。
　4.生成树和最小生成树，要求达到“领会”层次。
　　4.1 生成树和最小生成树的概念。
　　4.2 对遍历给定的图，画出深度优先和广度优先生成树或生成森林。
　　4.3 Prim和Kruskal算法的基本思想、时间性能及这两种算法各自的特点。
　　4.4 要求对给定的连通图，根据Prim和Kruskal算法构造出最小生成树。
　5.最短路径，要求达到“领会”层次。
　　5.1 最短路径的含义。
　　5.2 求单源最短路径的Dijkstra算法的基本思想和时间性能。
　　5.3 对于给定的有向图，根据Dijkstra算法画出求单源最短路径的过程示意图。
　6.拓扑排序，要求达到“领会”层次。
　　6.1 拓扑排序的基本思想和步骤。
　　6.2 拓扑排序不成功的原因。
　　6.3  对给定的有向图，若拓扑序列存在，则要求写出一个或多个拓扑序列。
第8章 排序
（一）课程内容
  8.1 基本概念
　8.2 插入排序
　8.3 交换排序
　8.4 选择排序
　8.5 归并排序
　8.6 分配排序
　8.7 各种排序方法的比较和选择
（二）学习目的与要求
　　本章目的是介绍五类内部排序方法的基本思想、排序过程、算法实现、时间和空间性能的分析以及各种排序方法的比较和选择。要求在熟悉这些内容的基础上，重点掌握快速排序、堆排序、归并排序和基数排序的基本思想及排序过程，本章难点是这四个排序算法的实现。
（三）考核知识点与考核要求
　1.基本概念，要求达到“识记”层次。
　　1.1 排序在数据处理中的重要性。
　　1.2 排序方法的“稳定”性含义。
　　1.3 排序方法的分类及算法好坏的评判标准。
　2.插入排序，要求达到“综合应用”层次。
　　2.1 直接插入排序的基本思想和算法实现，以及在最好、最坏和平均情况下的时间性能分析。
    2.2 直接插入排序中哨兵的作用。
　　2.3 针对给定的输入实例，要能写出直接插入排序的排序过程。
　3.交换排序，要求达到“综合应用”层次。
　　3.1 冒泡排序的基本思想。
　　3.2  快速排序的基本思想和算法实现，以及在最坏和平均情况下的时间性能分析，了解算法的稳定性。
    3.3 基准元素（划分元）对划分是否平衡的影响。
　　3.4 针对给定的输入实例，能写出快速排序的排序过程。
　4.选择排序，要求达到“简单应用”层次。
　　4.1 堆、小根堆、大根堆、堆项等有关概念和定义。
　　4.2 堆性质及堆与完全二叉树的关系。
　　4.3 直接选择排序和堆排序的基本思想和算法实现，以及时间性能分析。
　　4.4 针对给定的输入实例，写出堆排序的排序过程。
　5.归并排序，要求达到“领会”层次。
　　5.1 归并排序的基本思想和算法实现，以及时间性能分析。
　　5.2 针对给定的输入实例，能写出归并排序的排序过程。
　6.分配排序，要求达到“领会”层次。
　　6.1 箱排序和基数排序的基本思想和算法实现，以及时间性能分析。
　　6.2 针对给定的输入实例，能写出箱排序和基数排序的排序过程。
　　6.3 分配排序与其它几类排序的区别。
　7.各种排序方法的比较和选择，要求达到“简单应用”层次。
　　7.1 通过对被排序的记录数目、记录信息量的大小、关键字的结构及初始状态、稳定性要求、辅助空间的大小、各种时间性能等方面的比较掌握各种排序的优缺点。
　　7.2 根据实际问题的特点和要求选择合适的排序方法。
第9章 查找
（一）课程内容
　9.1 基本概念
　9.2 线性表的查找
　9.3 树的查找
　9.4 散列技术
（二）学习目的与要求
　　本章目的是介绍线性表、树和散列表的查找方法，算法实现以及各种查找方法的时间性能（平均查找长度）分析。要求考生在熟悉这些内容的基础上，重点掌握顺序查找、二分查找，二叉查找树上查找以及散列表上查找的基本思想和算法实现。本章难点是二叉查找树的删除算法及B—树上的插入和删除算法。
（三）考核知识点与考核要求
　1.基本概念，要求达到“识记”层次。
　　1.1 查找在数据处理中的重要性。
　　1.2 查找算法效率的评判标准。
　2.线性表的查找，要求达到“简单应用”层次。
　　2.1 顺序查找、二分查找、分块查找的基本思想、算法实现和查找效率分析。
　　2.2 顺序查找中哨兵的作用。
　　2.3 二分查找对存储结构及关键字的要求。
　　2.4 通过比较线性表上三种查找方法的优缺点，能根据实际问题的要求和特点，选择出合适的查找方法。
　3.树的查找，要求达到“简单应用”层次。
　　3.1 二叉查找树和B—树的定义和特点以及用途。
　　3.2 二叉查找树的插入、删除、建树和查找算法及时间性能。
　　3.3 建立一棵二叉查找树的过程实质上是对输入实例的排序过程，输入实例对所建立的二叉查找树形态的影响。
　　3.4 B－树的插入、删除及查找方法的基本思想。
　　3.5 B－树的查找效率。
　4.散列技术，要求达到“简单应用”层次。
　　4.1 散列表、散列函数、散列地址和装填因子等有关概念。
　　4.2 散列函数的选取原则及产生冲突的原因。
　　4.3 几种常用的散列函数构造方法。
　　4.4 两类解决冲突的方法及其优缺点。
　　4.5 产生“堆积”现象的原因。
　　4.6 采用线性探测法和拉链法解决冲突时，散列表的建表方法、查找过程以及算法实现和时间分析。
　　4.7 散列表和其它表的本质区别。
第10章 文件
（一）课程内容
　10.1 文件的基本概念
　10.2 顺序文件
　10.3 索引文件
　10.4 索引顺序文件
　10.5 散列文件
　10.6 多关键字文件
（二）学习目的与要求
　　本章目的是介绍存储在外存上的数据结构(即文件)的有关概念、各种文件的特点、组织方法及查询和更新操作，要求对这些内容做一般性的了解。
（三）考核知识点与考核要求
　1.文件的基本概念,要求达到"识记"层次。
　　1.1 文件的有关概念。
　　1.2 文件的逻辑结构及其操作。
　　1.3 文件的存储结构（组织方式）分类。
　　1.4 评价文件组织效率的标准。
　2.顺序文件，要求达到“识记”层次。
　　2.1 顺序文件的特点及外存种类的适应性。
　　2.2 顺序文件上各种查找方法的基本思想及对外存种类的要求。
　3.索引文件，要求达到“识记”层次。
　　3.1 索引文件的组织方式和特点。
　　3.2 索引文件的查询和更新操作的基本思想。
　4.索引顺序文件，要求达到“识记”层次。
　　4.1 索引顺序文件是最常用的一种文件组织方式的原因。
　　4.2 两种最常用的索引顺序文件（ISAM文件和VSAM文件）的组织方式和特点。
　　4.3 在ISAM文件和VSAM文件上查询和更新操作的基本思想。
　5.散列文件，要求达到“识记”层次。
　　5.1 散列文件的组织方式和特点。
　　5.2 散列文件的查询和更新操作的基本思想。
　6.多关键字文件，要求达到“识记”层次。
　　6.1 多关键字文件与其它文件的区别。
　　6.2 多重表文件和倒排文件的组织方式和特点。
　　6.3 多重表文件和倒排文件上查询及更新操作的基本思想。
参考教材：

《数据结构--C语言版》 清华大学出版社，严蔚敏等。