数据结构的基本概念

识记

数据的逻辑结构和存储结构，对后面的名词要能区分哪些是属于逻辑结构哪些属于物理结构

掌握

时间和空间复杂度的概念及度量方法

理解

算法设计时的注意事项

了解

线性表相关的基本概念，如：前驱、后继、表长、空表、首元结点，头结点，头指针等概念

识记

线性表的结构特点

识记

线性表的顺序存储方式以及两种不同的实现方法：表空间的静态分配和动态分配。静态链表与顺序表的相似及不同之处

掌握

线性表的链式存储方式的实现，几种常用链表的特点和运算：单链表、循环链表，双向链表，双向循环链表

掌握

线性表的顺序存储及链式存储情况下，其不同的优缺点比较，即其各自适用的场合

理解

单链表中设置头指针、循环链表中设置尾指针而不设置头指针以及索引存储结构的各自好处

理解

对于线性表的各种实现方式能够实现指定的操作，尤其是各种线性链表的插入，删除（删除自己，还是删除后继结点），判表空等

掌握

栈、队列的定义及其相关数据结构的概念，包括：顺序栈，链栈，共享栈，循环队列，链队等

识记

栈与队列插入删除操作的特点，栈和队列的特点

理解

递归算法，栈和递归的关系，把递归算法转换为用栈来实现的非递归算法

掌握

栈的应用

了解

栈和队列各种实现方式的运算

理解

循环队列中判队空、队满条件，循环队列中入队与出队算法

掌握

判循环队列是空还是满的两种处理方法

理解

数组的定义以及如何理解它们是线性表的扩展

识记

数组除了初始化和销毁之外只能进行存取和修改操作

识记

多维数组中某数组元素的position求解（不管是按行存储和按列存储）：一般是给出数组元素的首元素地址和每个元素占用的地址空间并组给出多维数组的维数，然后要求你求出该数组中的某个元素所在的位置

掌握

特殊矩阵和稀疏矩阵的定义

了解

特殊矩阵的压缩，包括对称矩阵，上（下）三角矩阵，对角矩阵，具有某种特点的稀疏矩阵等

掌握

稀疏矩阵的三种不同实现方式：三元组，带辅助行向量的二元组，十字链表存储

理解

对稀疏矩阵各种实现方式的转置和相乘运算的操作及复杂性分析

理解

二*树的概念，二*树的五种基本形态。比如可以考这么个题目判断二*树就是度为２的有序树对否。

理解

二*树的五个性质，尤其是性质３和性质４

掌握

二*树的存储结构：顺序存储和二*链表存储的各自优缺点及适用场合，二*树的三*链表表示方法

掌握

二*树的三种遍历方法：先序，中序和后序。其划分的依据是视其每个算法中对根结点数据的访问顺序而定。不仅要熟练掌握三种遍历的递归算法，理解其执行的实际步骤，并且应该熟练掌握三种遍历的非递归算法。

熟练掌握

在三种遍历算法的基础上改造完成的其它二*树算法，比如求叶子个数，求二*树结点总数，求度为1或度为2的结点总数，复制二*树，建立二*树，交换左右子树，查找值为n的某个指定结点，删除值为n的某个指定结点，诸如此类等等等等。

熟练掌握

线索二*树：线索化的实质，三种线索化的算法，线索化后二*树的遍历算法，基本线索二*树的其它算法问题（如：查找某一类线索二*树中指定结点的前驱或后继结点就是一类常考题），会计算针对某个二*树在采用不同的线索化方法后剩余空链域的个数

掌握

哈夫曼树，也叫最优二*树。什么样的编码是哈夫曼编码。一般很少考哈夫曼编码的算法，能够利用算法构造哈夫曼树并求出最小带权路径长度即可。还有一个树的应用：等价类问题。

掌握

树的存储表示方法，树与森林转化为二*树，树和森林的遍历问题，树的计数，二*树的相似与等价

掌握

回溯法

理解

图的基本概念：图的定义和特点，无向图，有向图，入度，出度，完全图，生成子图，路径长度，回路，（强）连通图，（强）连通分量等概念。与这些概念相联系的相关计算题也应该掌握

识记

掌握

图的几种存储形式，尤其是邻接矩阵和邻接表

掌握

图的两种遍历算法：深度遍历和广度遍历

深度遍历和广度遍历是图的两种基本的遍历算法，这两个算法对图一章的重要性等同于“先序、中序、后序遍历”对于二*树一章的重要性。在考查时，图一章的算法设计题常常是基于这两种基本的遍历算法而设计的，比如：“求最长的最短路径问题”和“判断两顶点间是否存在长为K的简单路径问题”，就分别用到了广度遍历和深度遍历算法。

熟练掌握

生成树、最小生成树的概念以及最小生成树的构造：PRIM算法和KRUSKAL算法，要掌握这两个算法的基本思想。考查时，一般不要求写出算法源码，而是要求根据这两种最小生成树的算法思想写出其构造过程及最终生成的最小生成树

掌握

拓扑排序问题：拓扑排序有两种方法，一是无前趋的顶点优先算法，二是无后继的顶点优先算法。换句话说，一种是“从前向后”的排序，一种是“从后向前”排。当然，后一种排序出来的结果是“逆拓扑有序”的。

掌握

关键路径问题：这个问题是图一章的难点问题。理解关键路径的关键有三个方面：一是何谓关键路径，二是最早时间是什么意思、如何求，三是最晚时间是什么意思、如何求。简单地说，最早时间是通过“从前向后”的方法求的，而最晚时间是通过“从后向前”的方法求解的，并且，要想求最晚时间必须是在所有的最早时间都已经求出来之后才能进行。这个问题拿来直接考算法源码的不多，一般是要求按照书上的算法描述求解的过程和步骤

掌握

最短路径问题：与关键路径问题并称为图一章的两只拦路虎。概念理解是比较容易的，关键是算法的理解。最短路径问题分为两种：一是求从某一点出发到其余各点的最短路径；二是求图中每一对顶点之间的最短路径。这个问题也具有非常实用的背景特色，一个典型的应该就是旅游景点及旅游路线的选择问题。解决第一个问题用DIJSKTRA算法，解决第二个问题用FLOYD算法。这个算法的要求就是要会用算法求解最短路径

掌握

关键字、主关键字、次关键字的含义；静态查找与动态查找的含义及区别；平均查找长度ASL的概念及在各种查找算法中的计算方法和计算结果，特别是一些典型结构的ASL值，应该记住。要会计算各种查找方法在查找成功和查找不成功时平均查找长度的计算

识记

掌握

线性表上的查找：主要分为三种线性结构：顺序表，有序顺序表，索引顺序表。对于第一种，我们采用传统查找方法，逐个比较。对于及有序顺序表我们采用二分查找法。对于第三种索引结构，我们采用索引查找算法。考生需要注意这三种表下的ASL值以及三种算法的实现。其中，二分查找还要特别注意适用条件以及其递归实现方法

掌握

树表上的查找：这是本章的重点和难点。由于这一节介绍的内容是使用树表进行的查找，所以很容易与树一间的某些概念相混淆。本节内容与树一章的内容有联系，但也有很多不同，应注意规纳。树表主要分为以下几种：二*排序树，平衡二*树，B树，键树。其中，尤以前两种结构为重，有时候也会考查Ｂ树，但是以选择为主，很少会考大题。由于二*排序树与平衡二*树是一种特殊的二*树，所以与二*树的联系就更为紧密，二*树一章学好了，这里也就不难了。

二*排序树，简言之，就是“左小右大”，它的中序遍历结果是一个递增的有序序列。平衡二*树是二*排序树的优化，其本质也是一种二*排序树，只不过，平衡二*树对左右子树的深度有了限定：深度之差的绝对值不得大于1。对于二*排序树，“判断某棵二*树是否二*排序树”这一算法经常被考到，可用递归，也可以用非递归。平衡二*树的建立也是一个常考点，但该知识点归根结底还是关注的平衡二*树的四种调整算法，所以应该掌握平衡二*树的四种调整算法，调整的一个参照是：调整前后的中序遍历结果相同。

B树是二*排序树的进一步改进，也可以把B树理解为三*、四*....排序树。除B树的查找算法外，应该特别注意一下B树的插入和删除算法。因为这两种算法涉及到B树结点的分裂和合并，是一个难点（没有时间可以不看）。

键树也称字符树，特别适用于查找英文单词的场合。一般不要求能完整描述算法源码，多是根据算法思想建立键树及描述其大致查找过程。

熟练掌握

基本哈希表的查找算法：哈希一词，是外来词，译自“hash”一词，意为：散列或杂凑的意思。哈希表查找的基本思想是：根据当前待查找数据的特征，以记录关键字为自变量，设计一个function，该函数对关键字进行转换后，其解释结果为待查的地址。基于哈希表的考查点有：哈希函数的设计，冲突解决方法的选择及冲突处理过程的描述。

熟练掌握

在插入排序中又可分为：直接插入、折半插入、2路插入、希尔排序。这几种插入排序算法的最根本的不同点，说到底就是根据什么规则寻找新元素的插入点。直接插入是依次寻找，折半插入是折半寻找。希尔排序，是通过控制每次参与排序的数的总范围“由小到大”的增量来实现排序效率提高的目的。

掌握

交换排序，又称冒泡排序，在交换排序的基础上改进又可以得到快速排序。快速排序的思想，一语以敝之：用中间数将待排数据组一分为二。快速排序，在处理的“问题规模”这个概念上，与希尔有点相反，快速排序，是先处理一个较大规模，然后逐渐把处理的规模降低，最终达到排序的目的。

掌握

选择排序，相对于前面几种排序算法来说，难度大一点。具体来说，它可以分为：简单选择、树选择、堆排。这三种方法的不同点是，根据什么规则选取最小的数。简单选择，是通过简单的数组遍历方案确定最小数；树选择，是通过“锦标赛”类似的思想，让两数相比，不断淘汰较大（小）者，最终选出最小（大）数；而堆排序，是利用堆这种数据结构的性质，通过堆元素的删除、调整等一系列操作将最小数选出放在堆顶。堆排序中的堆建立、堆调整是重要考点。

熟练掌握

归并排序，故名思义，是通过“归并”这种操作完成排序的目的，既然是归并就必须是两者以上的数据集合才可能实现归并。所以，在归并排序中，关注最多的就是2路归并。算法思想比较简单，有一点，要铭记在心：归并排序是稳定排序。

熟练掌握

基数排序，是一种很特别的排序方法，也正是由于它的特殊，所以，基数排序就比较适合于一些特别的场合，比如扑克牌排序问题等。基数排序，又分为两种：多关键字的排序（扑克牌排序），链式排序（整数排序）。基数排序的核心思想也是利用“基数空间”这个概念将问题规模规范、变小，并且，在排序的过程中，只要按照基排的思想，是不用进行关键字比较的，这样得出的最终序列就是一个有序序列

掌握