选择题
1.算法性质有哪几条。算法是指....
性质：有限性，确定性，可行性，输入性，输出性。
算法是求解问题的一系列计算步骤，用来将输入数据转换成输出结果，在计算机中表现为指令的有限序列，并且每条指令表示一个或多个操作。算法就是描述解决问题的方法。
2.分治法设计出来的程序是递推的、迭代的还是递推的?
采用递归：因为原问题和子问题在结构上比较相似，可以采用相似的方法
3.回溯法：问题解空间树是按什么策略 广度优先还是深度优先
深度优先搜索
4.常见的两种分支限界法 队列（广度）和优先队列
（1）队列式分支限界法
（2）优先队列式分支限界法
5.采用优先队列分支限界解背包时，活结点表的组织形式是什么样子的？
（最小堆or最大堆or栈or数组），要求价值最大，那么按优先队列是（是最大堆）
6.贪心和动态规划的共同点是什么？
A.构建最优解
B.最优子结构
7.动态规划算法的基本要素是什么？两方面
最优子结构性质和重叠子问题性质
8.分治法的设计思想是难以解决的大问题分解成小问题，最后分问题解合成原问题解，那么要求原问题和子问题，问题规模不同，问题性质相同
9.以下不属于贪心算法的是：
- 单源最短路径中的Dijkstra算法
- 最小生成树的Prim算法
- 最小生成树的Kruskal算法
- 深度优先遍历
10.下列算法中不能解决01背包的是
- 贪心法
- 动态规划
- 回溯法
- 分支限界法
填空题
1.给程序分析计算时间，时间成本，注意要用O来表达，O里要写成f（n）的函数形式//
2.回溯法搜索解空间树，常用的两种剪枝函数是什么：约束函数和限界函数
3.回溯法的求解目标是找出解空间树满足约束条件的所有解，分支限界则是找出一个解，或是找出某种意义下的最优解，当然回溯也能找最优解，看看书中他俩各自的对比
4.算法在运行时，资源量，主要有什么（时间、空间等）复杂性，什么复杂性？//
5.常用的图的存储结构有什么：邻接矩阵，邻接表
6.解0-1背包问题时，不需要对物品进行排序的算法是哪一个？///
解答题1..采用特征方程求解一个递归方程P79
2.叙述分治和动态规划的概念和异同，把关键要点答出来就行
| 概念 | ①分治法：将问题分解成多个独立且与原问题性质相同的子问题，并且递归的解这些子问题，然后将各子问题的解合并得到原问题的解。 ②动态规划法：将较大问题分解为较小的同类子问题，它可以解决子问题重叠现象，利用最优子结构，自底向上从子问题的最优解逐步构造出整个问题的最优解。 |
| 相同点 | 二者都要求原问题具有最优子结构性质,都是将原问题分而治之,分解成若干个规模较小(小到很容易解决的程序)的子问题.然后将子问题的解合并,形成原问题的解. |
| 不同点 | 1.分治法与动态规划实现方法不同: ① 分治法通常利用递归求解.（例：归并排序，快速排序，快速傅里叶变换，一般用树结构） ② 动态规划通常通过状态转移方程利用迭代法自底向上求解,但也能用具有记忆功能的递归法自顶向下求解. 2.子问题有区别: ① 分治法分解后的子问题是相互独立的，但是被分解得到的子问题数目太多，有些子问题会被重复计算多次。 ② 动态规划分解后的子问题不是相互独立的，它们相互间有联系,有重叠部分.它可以将已解决子问题的答案保存下来，在需要子问题答案的时候便可直接获得，而不需要重复计算，这样就可以避免大量的重复计算，提高效率。 |
3.用优先队列分支限界解任务分配问题，代码填空，四个空。（看我的博客）
1.计算题，使用分支限界法求解01背包问题，3个物品，重量和价值，背包容量设计题
（1）画出解空间树
（2）Say如何剪枝，
（3）求出最优解，三问
2.曾经的作业，动态规划求他们的最长公共子串，要知道什么是公共子串。
(1)定义动态规划数组dp，需要讲述dp元素的含义（结合问题），绘制表格，进行计算。
(2)用文字解述每个单元格的计算规则。
(3)写出计算dp的伪代码，用if else（一定要包含状态转移方程，dp[i][j]等于什么）
