第一章数据结构基本概念
1、基本概念：理解什么是数据、数据对象、数据元素、数据结构、数据的逻辑结构与物理结构、逻辑结构与物理结构间的关系。
2、面向对象概念：理解什么是数据类型、抽象数据类型、数据抽象和信息隐蔽原则。
了解什么是面向对象。
由于目前关于这个问题有许多说法，我们采用了一种最流行的说法，即Coad与Yourdon 给出的定义：面向对象= 对象+ 类+ 继承+ 通信。
要点：* 抽象数据类型的封装性
* 面向对象系统结构的稳定性
* 面向对象方法着眼点在于应用问题所涉及的对象
3、数据结构的抽象层次：理解用对象类表示的各种数据结构
4、算法与算法分析：理解算法的定义、算法的特性、算法的时间代价、算法的空间代价。
要点：* 算法与程序的不同之处需要从算法的特性来解释
* 算法的正确性是最主要的要求
* 算法的可读性是必须考虑的
* 程序的程序步数的计算与算法的事前估计
* 程序的时间代价是指算法的渐进时间复杂性度量
第二章数组
1、作为抽象数据类型的数组：数组的定义、数组的按行顺序存储与按列顺序存储
要点：* 数组元素的存放地址计算
2、顺序表：顺序表的定义、搜索、插入与删除
要点：* 顺序表搜索算法、平均比较次数的计算
* 插入与删除算法、平均移动次数的计算
3、多项式：多项式的定义
4、字符串：字符串的定义及其操作的实现
要点：* 串重载操作的定义与实现
第三章链接表
1、单链表：单链表定义、相应操作的实现、单链表的游标类。
要点：* 单链表的两种定义方式（复合方式与嵌套方式）
* 单链表的搜索算法与插入、删除算法
* 单链表的递归与迭代算法
2、循环链表：单链表与循环链表的异同
3、双向链表：双向链表的搜索、插入与删除算法、链表带表头结点的优点
4、多项式的链接表示
第四章栈与队列
1、栈：栈的特性、栈的基本运算
要点：* 栈的数组实现、栈的链表实现
* 栈满及栈空条件、抽象数据类型中的先决条件与后置条件
2、栈的应用：用后缀表示计算表达式，中缀表示改后缀表示
3、队列：队列的特性、队列的基本运算
要点：* 队列的数组实现：循环队列中队头与队尾指针的表示，队满及
队空条件
* 队列的链表实现：链式队列中的队头与队尾指针的表示、
4、双向队列：双向队列的插入与删除算法
5、优先级队列：优先级队列的插入与删除算法
第五章递归与广义表
1、递归：递归的定义、递归的数据结构、递归问题用递归过程求解
要点：* 链表是递归的数据结构，可用递归过程求解有关链表的问题
2、递归实现时栈的应用
要点：* 递归的分层（树形）表示：递归树
* 递归深度（递归树的深度）与递归工作栈的关系
* 单向递归与尾递归的迭代实现
3、广义表：广义表定义、广义表长度、广义表深度、广义表表头、广义表表尾要点：* 用图形表示广义表的存储结构
* 广义表的递归算法
第六章树与森林
1、树：树的定义、树的基本运算
要点：* 树的分层定义是递归的
* 树中结点个数与高度的关系
2、二叉树：二叉树定义、二叉树的基本运算
要点：* 二叉树性质、二叉树中结点个数与高度的关系、不同种类的二
叉树棵数
* 完全二叉树的顺序存储、完全二叉树的双亲、子女和兄弟的位
置
* 二叉树的前序·中序·后序·层次遍历
* 前序·中序·后序的线索化二叉树、前驱与后继的查找方法
3、霍夫曼树：霍夫曼树的构造方法、霍夫曼编码、带权路径长度的计算
4、树的存储：树的广义表表示、树的双亲表示、树与二叉树的对应关系、树的先根·中根·后根·层次遍历。
5、堆：堆的定义、堆的插入与删除算法
要点：* 形成堆时用到的向下调整算法及形成堆时比较次数的上界估计
* 堆插入时用到的向上调整算法
第七章集合与搜索
1、集合的概念：集合的基本运算、集合的存储表示
要点：* 用位数组表示集合时集合基本运算的实现
* 用有序链表表示集合时集合基本运算的实现
2、并查集：并查集定义、并查集的三种基本运算的实现
3、基本搜索方法
要点：* 对一般表的顺序搜索算法（包括有监视哨和没有监视哨）
* 对有序顺序表的顺序搜索算法、用判定树（即扩充二叉搜索树）
描述搜索，以及平均搜索长度（成功与不成功）的计算。
* 对有序顺序表的折半搜索算法、用判定树（即扩充二叉搜索树）
描述搜索，以及平均搜索长度（成功与不成功）的计算。
4、二叉搜索树：
要点：* 动态搜索树与静态搜索树的特性
* 二叉搜索树的定义、二叉搜索树上的搜索算法、二叉搜索树搜
索时的平均搜索长度（成功与不成功）的计算。
* AVL树结点上的平衡因子、AVL树的平衡旋转方法
* 高度为h的AVL树上的最少结点个数与最多结点个数
* AVL树的搜索方法、插入与删除方法
第八章图
1、图：图的定义与图的存储表示
要点：* 邻接矩阵表示（通常是稀疏矩阵）
* 邻接表与逆邻接表表示
* 邻接多重表(十字链表)表示
2、深度优先遍历与广度优先遍历
要点：* 生成树与生成树林的定义
* 深度优先搜索是个递归的过程，而广度优先搜索是个非递归的
过程
* 为防止重复访问已经访问过的顶点，需要设置一个访问标志数
组visited
3、图的连通性
要点：* 深度优先搜索可以遍历一个连通分量上的所有顶点
* 对非连通图进行遍历，可以建立一个生成森林
* 对强连通图进行遍历，可能建立一个生成森林
* 关节点的计算和以最少的边构成重连通图
4、最小生成树
要点：* 对于连通网络、可用不会构成环路的权值最小的n-1条边构成最小生成树
* 会画出用Kruskal算法及Prim算法构造最小生成树的过程
5、单源最短路径
要点：* 采用逐步求解的方式求某一顶点到其他顶点的最短路径
* 要求每条边的权值必须大于零
6、活动网络
要点：* 拓扑排序、关键路径、关键活动、AOE网
* 拓扑排序将一个偏序图转化为一个全序图。
* 为实现拓扑排序，要建立一个栈，将所有入度为零的顶点进栈
* 关键路径的计算
第九章排序
1、基本概念：关键码、初始关键码排列、关键码比较次数、数据移动次数、稳定性、附加存储、内部排序、外部排序
2、插入排序：
要点：* 当待排序的关键码序列已经基本有序时，用直接插入排序最快
3、选择排序：
要点：* 用直接选择排序在一个待排序区间中选出最小的数据时，与区
间第一个数据对调，而不是顺次后移。
这导致方法不稳定。
* 当在n个数据（n很大）中选出最小的5 ~ 8个数据时，锦标
赛排序最快
* 锦标赛排序的算法中将待排序的数据个数n补足到2的k次幂
2k-1 < n ￡2k
* 在堆排序中将待排序的数据组织成完全二叉树的顺序存储。
4、交换排序：
要点：* 快速排序是一个递归的排序方法
* 当待排序关键码序列已经基本有序时，快速排序显著变慢。
5、二路归并排序：
要点：* 归并排序可以递归执行
* 归并排序需要较多的附加存储。
可以采用一种"推拉法"（参
见教科书上习题）实现归并排序，算法的时间复杂度为O (n)、
空间复杂度为O(1)
* 归并排序对待排序关键码的初始排列不敏感，排序速度较稳定
6、外排序
要点：* 多路平衡归并排序的过程、I/O缓冲区个数的配置
* 外排序的时间分析、利用败者树进行多路平衡归并
* 利用置换选择方法生成不等长的初始归并段
* 最佳归并树的构造及WPL的计算
第十章索引与散列
1、线性索引：
要点：* 密集索引、稀疏索引、索引表计算
* 基于属性查找建立倒排索引、单元式倒排表
2、动态搜索树
要点：* 平衡的m路搜索树的定义、搜索算法
* B树的定义、B树与平衡的m路搜索树的关系
* B树的插入（包括结点分裂）、删除（包括结点调整与合并）
方法
* B树中结点个数与高度的关系
* B+树的定义、搜索、插入与删除的方法
3、散列表
要点：* 散列函数的比较
* 装填因子a 与平均搜索长度的关系，平均搜索长度与表长m 及表中已有数据对象个数n的关系
* 解决地址冲突的（闭散列）线性探查法的运用，平均探查次数的计算
* 线性探查法的删除问题、散列表类的设计中必须为各地址设置三个状态
* 线性探查法中的聚集问题
* 解决地址冲突的（闭散列）双散列法的运用，平均探查次数的计算
* 双散列法中再散列函数的设计要求与表长m互质，为此m设计为质数较宜
* 解决地址冲突的（闭散列）二次散列法的运用，平均探查次数的计算
* 注意：二次散列法中装填因子a 与表长m的设置
*解决地址冲突的（开散列）链地址法的运用，平均探查次数的计算。