一、判断 选择 20-30分 送分

二、综合题 50-60分

简答 画图 红黑树 求最大流

算法分析：递归算法的时间分析 平摊分析

阅读算法 回答问题

比如哈夫曼编码 怎么得到一颗最优的前缀码树

三、算法设计20-30分

1-2个题。

红黑树 的插入 删除一个结点 不考。

插入删除算法的时间复杂度要清楚。

不会有这样的题：用胚的方法来求最优解。

但要明白胚的定义和基本概念

怎么证明问题的贪心选择性质 和 最优子结构性质 这个要考

三个符号的定义 要清楚

2.基本思想 所有指令

不需要分析平均情况下的复杂度分析，但是常用的结论你要知道。

要求掌握势函数方法， ②③只有很少的情况才能用。

正确性分析不是重点：

循环不变式不考。

cut就是 反正。

归纳法用的很多的。

归纳法要掌握。

贪心选择性质的证明？

证明你这样一个贪心选择包含在某1个最优解中。

剔除一定不在最优解中的。

会用2. ford-fulkerson

剩余网络怎么构造

增广路径是个什么概念。

二分图不做要求。

pouxu理论不再要求，