原创力文档- 1、本文档共14页，可阅读全部内容。
- 2、原创力文档（book118）网站文档一经付费（服务费），不意味着购买了该文档的版权，仅供个人/单位学习、研究之用，不得用于商业用途，未经授权，严禁复制、发行、汇编、翻译或者网络传播等，侵权必究。
- 3、本站所有内容均由合作方或网友上传，本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺！文档内容仅供研究参考，付费前请自行鉴别。如您付费，意味着您自己接受本站规则且自行承担风险，本站不退款、不进行额外附加服务；查看《如何避免下载的几个坑》。如果您已付费下载过本站文档，您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等，请点击“版权申诉”（推荐），也可以打举报电话：400-050-0827(电话支持时间：9:00-18:30)。
复习
第一章导引
掌握：
1.算法的定义及其性质(1.1节)
2.算法分析的基础知识(1.2节)
重要的约定和假设
关于O，Ω，的定义
了解：
3.SPARKS语言(1.3节)
4.常用数据结构(1.4节)
5.递归与消去递归(1.5节)
第二章分治法
掌握：
1.基本知识
分治法的基本思想：2.1节
关系式的化简：
1）递推关系式的化简作业题
2）常用求和公式
在统计语句的频率时，求和公式的一般形式为：
特殊形式
第二章分治法（续）
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
02015+∞+∞+∞
01915+∞25+∞
019152925+∞
01915292528
01915292528
第三章贪心方法（续）
一般了解：
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检测序列：12345678
DFS检
文档评论（0）