期末考试要点
考核时长120分钟。考核结束后可以与老师讨论。
1、填空题（10分，5道题，每道题2分，都是单选）
2、选择题（10分，5道题，每道题2分）
前两部分均是考察基础概念。
3、应用题（3～6题，都是20分1题，一共80分）
题1，第二章的分治
关键词
1、分治过程（初始状态，第1趟状态，第n躺状态）
2、分治的算法分析，分析时间复杂度（数学推理/图示）
题2，第三章的动态规划
关键词
1、找到状态（小明爬楼梯例子），状态表达的变量/属性
2、状态转移方程（核心，初始状态、结束状态、过程中一般的状态）
3、边界情况
4、函数的编写（根据状态转移方程翻译为代码，用c++或者伪代码，将状态转移方程表达出来）
题3，第四章贪心
关键词
1、思路，构造局部最优的策略
2、时间复杂度（关键步骤在哪里）
题4，第五章回溯
关键词
1、解空间，构造是关键
2、两个基本的类型（a.子集树 b.排列树）
注：
1、画出树，解结构的形态
2、求解最优，并解释表达的内涵
4、复习策略：
5道选择和5道填空大部分集中在
- 第1章：基础知识
- 第6章：线性规划
- 第7章：网络流算法
- 第8章：算法分析和问题的计算复杂度
- 第9章：NP完全性
大题的章节，填空选择也可能会涉及。
4道大题集中于
- 第2章分治策略
- 第3章动态规划
- 第4章贪心算法
- 第5章回溯和分支限界