考试范围
1.问答题
2.根据代码写时间复杂度
3.0-1背包问题的分支限界法/回溯法计算实例
4.正确性证明（lcs，不相交区间）
5.动态规划填表（lcs，背包，矩阵）
6.算法设计实践题
一、问答题
1．什么是最坏情况时间复杂性？什么是平均情况时间复杂性？
最坏情况的时间复杂性是规模为n的所有输入中，基本运算执行次数为最多的时间复杂性。平均时间复杂性是规模为n的所有输入的算法时间复杂性的平均值（假设每种输入情况等概率出现）。
2．什么是递归算法？什么是递归函数？
递归：若一个对象部分地包含它自己，或用它自己给自己定义，则称这个对象是递归的。
递归算法:直接或间接地调用自身的算法。
递归函数:用函数自身给出定义的函数。
3．递归函数的二要素是什么？
边界条件、递归方程。
4．分治法的设计思想是什么？
将要求解的较大规模的问题分割成若干个更小规模的子问题。
对这若干子问题分别求解。如果子问题的规模仍然不够小，则再划分为若干个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。
5．什么叫问题的最优子结构性质？
最优子结构性质：问题的最优解包含着其子问题的最优解。
6．动态规划基本步骤是什么？
分解。将原问题可以分解为若干个规模较小的相同问题。
递归地定义最优值。（相当于分治法中的合并操作）
以自底向上的方式计算出最优值。
根据计算最优值时得到的信息，构造最优解。
7．动态规划算法的基本要素是什么？举例说明一些可以用动态规划算法解决的问题。
动态规划算法的基本要素是：最优子结构：问题的最优解包含子问题 的最优解、重叠子问题：每次产生的子问题不是新问题，被反复计算多次。
矩阵连乘、最长公共子序列、0-1背包问题
8．说明分治法与动态规划法的相同点和不同之处？
与分治法类似，动态规划法也是把问题一层一层地分解为规模逐渐减小的同类型的子问题。动态规划法与分治法的一个重要的不同点在于，用分治法分解后得到的子问题通常都是相互独立的，而用动态规划法分解后得到的子问题很多都是重复的。因此，对重复出现的子问题，只是在第一次遇到时才进行计算，然后把计算所得的结果保存起来；当再次遇到该子问题时，就直接引用已保存的结果，而不再重新求解。
9．贪心算法的两个重要要素是什么？举例说明一些可以用贪心算法解决的问题。
两个重要要素：贪心选择性质：所求的问题的整体最优解可以通过一系列局部最优的选择达到、最优子结构性质：问题最优解包含子问题最优解。
活动安排问题、最优装载问题、单源最短路径问题
10．什么叫贪心选择性质？
所求问题的整体最优解可以通过一系列的局部最优选择来得到，即贪心选择来达到。
11．贪心算法与动态规划算法的的相同点和不同之处？
相同点：都具有最优子结构性质，都用来求解最优化问题。
不同点：贪心算法具有贪心选择性质，局部最优解能得到整体最优解。动态规划具有重叠子问题性质。
12．背包问题与0－1背包问题有何区别？
0-1背包问题物品有两种选择，要么放进去要么不放进去，而背包问题可以放部分，重量的选择可以是非整数
13．回溯法与分支限界法之间的相同点是什么？不同之处在哪些方面？
回溯法和分支限界法都需要隐式地构造解空间树并对其进行搜索。回溯法以深度优先的顺序进行搜索，避免不必要的搜索。分支限界法则以广度优先或最小耗费（最大效益优先）的方式搜索解空间树。
14．分支限界法基本思想是什么？
分支限界法以广度优先或以最小耗费（最大效益）优先的方式搜索解空间树。扩展子结点时，一次性生成它的所有孩子结点，舍弃不可能导致可行解或最优解的子结点，其余节点进入队列。
15．常用的剪枝函数有哪两类？
约束函数剪枝和限界函数剪枝。
16．约束函数的功能是什么？
在扩展节点处剪去不满足约束的子树，保留可行解点。
17．限界函数的功能是什么？
剪去可行但得不到最优解的子树。
18．常见的两种分支限界法是什么？
（1）队列式(FIFO)分支限界法
按照队列先进先出（FIFO）原则选取下一个节点为扩展节点。
（2）优先队列式分支限界法
按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。
19．什么是P问题和NP问题？
如果一个问题可以找到一个能在多项式时间里解决它的算法，那么这个问题就属于P问题。
NP问题不是非P类问题，是多项式复杂程度的非确定性问题。 是指可以在多项式的时间里验证一个解的问题。
20．回溯法中剪枝函数有哪几类？各有何用途？
约束函数：用约束函数在扩展结点处剪去不满足约束的子树,保留可行节点；
限界函数：用限界函数剪去得不到最优解的子树。
21．什么是NP完全问题？
NP完全问题又叫NPC问题。同时满足下面两个条件的问题就是NPC问题。
第一条，它是一个NP问题；
第二条，所有的NP问题都可以约化到它。
22.子集树和排列树。
都是回溯法的状态空间树。
子集树：从n个元素组成的集合S中找出S满足某种性质的子集时，相应的解空间树。
排列树：当所给问题是确定n个元素满足某种性质的排列时，相应解空间树为排列数。
二、时间复杂度计算：
1.动态规划、贪心：
最内层循环次数。
5.递归
三、证明：
活动安排问题
最长公共子序列问题
四、动态规划填表：
最长公共子序列：
从左至右、从上往下更新。
0-1背包：
从左至右、从下往上更新。w为重量/体积，v为价值。
矩阵连乘：
五、实践题
1.棋盘覆盖
2.循环赛安排
3.矩阵连乘
4.添加括号数目问题
5.找新数
6.0-1背包问题（回溯法）
算法设计与分析/数据结构与算法实验6：0-1背包问题（回溯法）
7.0-1背包问题（分支限界法）
算法设计与分析/数据结构与算法实验7：0-1背包问题（分支限界法）
