复习第一章 导引掌握：
1.算法的定义及其性质 (1.1节 )
2.算法分析的基础知识 (1.2节 )
重要的约定和假设
关于 O,?,的定义了解：
3.SPARKS语言 (1.3节 )
4.常用数据结构 (1.4节 )
5.递归与消去递归 (1.5节 )
第二章 分治法掌握：
1.基本知识分治法的基本思想,2.1节关系式的化简：
1）递推关系式的化简 作业题
2）常用求和公式在统计语句的频率时，求和公式的一般形式为：
h(n)i)(
)(
ng
if
)(2/)1(n 2
1
nni
ni
特殊形式
)( 1
1
k
ni
k ni
)(6/)12)(1(n 3
1
2 nnni
ni
第二章 分治法（续）
2.重要实例
二分检索算法及其算法分析,2.2节
基于 PARTITION的选择算法,2.6节
3.分类算法及其应用,2.4,2.5节一般了解：
4.找最大和最小元素,2.3节
5.最坏情况时间是 O(n)的选择算法,2.3节后半部分第三章 贪心方法掌握：
1.基本知识（ 3.1节）
基本概念：约束条件、目标函数、可行解、
最优解
贪心方法的适用对象：求输入的一个可行的子集
贪心方法的一般策略：度量标准
贪心解是问题最优解证明的基本思想第三章 贪心方法（续）
2.重要实例
背包问题：最优度量标准的选择、最优解的证明
（ 3.2节）
带有限期的作业排序问题：度量标准和处理策略、
作业集合可行性的判定（ 3.3节）
单源最短路径：给出一个图，能够写出算法的执行轨迹（ 3.6节）
例题和实验
4
5
2
6
3
1
10
10
15
3
10
4
15
20
30
迭代 选取的结点
S DIST
(1) (2) (3) (4) (5) (6)
置初值
1
2
3
4
－
3
2
5
6
1
1,3
1,3,2
1,3,2,5
1,3,2,5,6
0 20 15 +∞ +∞ +∞
0 19 15 +∞ 25 +∞
0 19 15 29 25 +∞
0 19 15 29 25 28
0 19 15 29 25 28
第三章 贪心方法（续）
一般了解：
3.最优归并模式 （ 3.4节）
4.最小生成树算法,（ 3.5节）
Prim 算法（保持连通）
Kruskal算法（不保持连通）
要求：给出图例，能够可以画出相应的最小成本生成树第四章 动态规划掌握：
1.基本知识（ 4.1节）
1）基本概念
多阶段决策过程
最优性原理
2）动态规划求解的一般策略：
证明最优性原理成立
列出递推关系式：向前处理法、向后处理法第四章 动态规划（续）
2.重要实例
多段图问题：段的定义、
（ 4.2节） 基于多段图的多阶段决策过程、
导出的递推关系式及算法
最优二分检索树：最优二分检索树的定义、
(4.4节 ) 最优二分检索树的多阶段决策过程、
递推关系式、
基于递推关系式的 W,C,R的计算习题
0/1背包问题,0/1背包问题的定义、向后递推策略、
(4.5节 ) 序偶 Si的表示方法及其计算过程习题第四章 动态规划（续）
一般了解：
3.每对结点之间的最短路径 (4.3节 )
4.最优二分检索树算法的实现 (4.4节 )
5.0/1背包问题算法的实现 (4.5节 )
第五章 基本检索和周游方法掌握：
1.基本概念：检索、周游
2.图的检索算法
宽度优先检索,BFS
深度优先检索,DFS
D_SEARCH
要求：掌握算法的处理规则，对给定的图，能够写出各算法检索的结点序列。
BFS检测序列,1 2 3 4 5 6 7 8
DFS检测序列,1 2 4 8 5 6 3 7
D_Search检测序列,1 3 7 8 5 4 6 2
1
2 3
4 5 6 7
8 无向图 G
第五章 基本检索和周游方法（续）
一般了解：
3.二元树的周游
4.树的周游
5.书中关于算法时间和空间复杂度的定理及其证明
1.算法的定义及其性质 (1.1节 )
2.算法分析的基础知识 (1.2节 )
重要的约定和假设
关于 O,?,的定义了解：
3.SPARKS语言 (1.3节 )
4.常用数据结构 (1.4节 )
5.递归与消去递归 (1.5节 )
第二章 分治法掌握：
1.基本知识分治法的基本思想,2.1节关系式的化简：
1）递推关系式的化简 作业题
2）常用求和公式在统计语句的频率时，求和公式的一般形式为：
h(n)i)(
)(
ng
if
)(2/)1(n 2
1
nni
ni
特殊形式
)( 1
1
k
ni
k ni
)(6/)12)(1(n 3
1
2 nnni
ni
第二章 分治法（续）
2.重要实例
二分检索算法及其算法分析,2.2节
基于 PARTITION的选择算法,2.6节
3.分类算法及其应用,2.4,2.5节一般了解：
4.找最大和最小元素,2.3节
5.最坏情况时间是 O(n)的选择算法,2.3节后半部分第三章 贪心方法掌握：
1.基本知识（ 3.1节）
基本概念：约束条件、目标函数、可行解、
最优解
贪心方法的适用对象：求输入的一个可行的子集
贪心方法的一般策略：度量标准
贪心解是问题最优解证明的基本思想第三章 贪心方法（续）
2.重要实例
背包问题：最优度量标准的选择、最优解的证明
（ 3.2节）
带有限期的作业排序问题：度量标准和处理策略、
作业集合可行性的判定（ 3.3节）
单源最短路径：给出一个图，能够写出算法的执行轨迹（ 3.6节）
例题和实验
4
5
2
6
3
1
10
10
15
3
10
4
15
20
30
迭代 选取的结点
S DIST
(1) (2) (3) (4) (5) (6)
置初值
1
2
3
4
－
3
2
5
6
1
1,3
1,3,2
1,3,2,5
1,3,2,5,6
0 20 15 +∞ +∞ +∞
0 19 15 +∞ 25 +∞
0 19 15 29 25 +∞
0 19 15 29 25 28
0 19 15 29 25 28
第三章 贪心方法（续）
一般了解：
3.最优归并模式 （ 3.4节）
4.最小生成树算法,（ 3.5节）
Prim 算法（保持连通）
Kruskal算法（不保持连通）
要求：给出图例，能够可以画出相应的最小成本生成树第四章 动态规划掌握：
1.基本知识（ 4.1节）
1）基本概念
多阶段决策过程
最优性原理
2）动态规划求解的一般策略：
证明最优性原理成立
列出递推关系式：向前处理法、向后处理法第四章 动态规划（续）
2.重要实例
多段图问题：段的定义、
（ 4.2节） 基于多段图的多阶段决策过程、
导出的递推关系式及算法
最优二分检索树：最优二分检索树的定义、
(4.4节 ) 最优二分检索树的多阶段决策过程、
递推关系式、
基于递推关系式的 W,C,R的计算习题
0/1背包问题,0/1背包问题的定义、向后递推策略、
(4.5节 ) 序偶 Si的表示方法及其计算过程习题第四章 动态规划（续）
一般了解：
3.每对结点之间的最短路径 (4.3节 )
4.最优二分检索树算法的实现 (4.4节 )
5.0/1背包问题算法的实现 (4.5节 )
第五章 基本检索和周游方法掌握：
1.基本概念：检索、周游
2.图的检索算法
宽度优先检索,BFS
深度优先检索,DFS
D_SEARCH
要求：掌握算法的处理规则，对给定的图，能够写出各算法检索的结点序列。
BFS检测序列,1 2 3 4 5 6 7 8
DFS检测序列,1 2 4 8 5 6 3 7
D_Search检测序列,1 3 7 8 5 4 6 2
1
2 3
4 5 6 7
8 无向图 G
第五章 基本检索和周游方法（续）
一般了解：
3.二元树的周游
4.树的周游
5.书中关于算法时间和空间复杂度的定理及其证明
