算法设计与分析复习题
1、分治法的基本思想：是将一个规模为N的问题分解为K个规模较小的子问题，这些子问题互相独立且与原问
题相同。递归地解这些子问题，然后将各子问题的解合并得到原问题的解。
2、贪心选择性质：指所求问题的整体最优解可以通过一系列局部最优的选择，
3、什么是剪枝函数：回溯法搜索解空间树时，通常采用两种策略避免无效搜索，提高回溯法的搜索效率。其一 是用约束函数在扩展结点处剪 去不满足约束的子树；其二是用限界函数剪去得不到最优解的子树。这两类函 数统称为剪枝函数。
4、 分支限界法的基本思想：
(1)分支限界法常以广度优先或以最小耗费(最大效益)优先的方式 搜索问题的解空间树。
(2)在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有 儿子结点。在这些儿子结点中，导致不可行解或导致 非最优解的儿子结点被舍弃，其余儿子结点 被加入活 结点表中。
(3)此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程，这个过程一直持续到找到所需 的解或活结点表这空时为止。
5、 什么是算法的复杂性：是该算法所需要的计算机资源的多少，它包括时间和空间资源。
6、 最优子结构性质：该问题的最优解包含着其子问题的最优解。
7、 回溯法：是一个既带有系统性又带有跳跃性的搜索算法。这在问题的解空间树中，按深度优先策略，从根结 点出发搜索解空间树。算法搜索至解空间树的任一结点时，先判断该结点是否包含问题的解。如果肯定不包 含，则跳过对以该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策 略搜索。
8、什么是分支定界法：对有约束条件的最优化问题所有可行解定向、适当地进行搜索。将可行解空间不断地划 分为越来越小的子集（分支），并为每一个子集的解计算一个上界和下界（定界）。
9、 算法满足的性质：输入、输出、确定性、有限性。
10、递归算法的优点：结构清晰，可读性强，容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试 程序带来很大方便。
11、回溯法效率的因素： （1）产生x[k]的时间。 （2）满足显约束的x[k]值的个数。 （3）计算约束函数constraint的时间。 （4）计算上界函数bound的时间。 （5）满足约束函数和上界函数约束的所有x[k]的个数
12、最常见的分支限界法有两种：队列式（FIFO）分支限界法和优先队列式分支限界法。
13、 什么是算法, 算法具有的特性是什么？ 是解决问题的方法和过程, (1) 输入0个或多个信息
(2) 输出至少一个信息 (3) 确定性：组成算法的每个指令是清晰的，无二义的，整个过程是确定的 (4) 有限性：
14、 什么是动态规划法：
将问题分解成多级或许多子问题，然后顺序求解子问题，前一个子问题的解为后一个子问题的求解提供有用的信息。
15、 什么是贪心法：从问题某一初始或推测值出发，一步步的攀登给定目标，尽可能快的去逼近更好的解，当达到某一步不能继续时终止。
16、递归算法的缺点：运行效率较低，耗费的计算时间和占用的存储空间都多。为了达到此目的，根据具体程序的特点对递归调用工作栈进行简化，尽量减少栈操作，压缩栈存储空间以达到节省计算时间和存储空间的目的。
17、合并排序的时间复杂度是：T(n)=O(nlogn)。
18、快速排序的时间复杂度是：T(n)=O(nlogn)。
19、动态规划算法的基本要素：最优子结构性质和子问题重叠性质。
20、贪心算法的基本要素：贪心选择性质和最优子结构性质。
选择题
1、二分搜索算法是利用（ ）实现的算法。A、分治策略 B、动态规划法 C、贪心法 D、回溯法
2、下列不是动态规划算法基本步骤的是（ ）。A、找出最优解的性质 B、构造最优解 C、算出最优解 D、定义最优解
3、下列算法中通常以深度优先方式系统搜索问题解的是（ ）。A、备忘录法 B、动态规划法 C、贪心法 D、回溯法
4、最大效益优先是（ ）的搜索方式。A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 5、0-1背包问题的回溯算法所需的计算时间为（ ） O（n2n） B、O（nlogn） C、O（2n） D、O（n）
简答题
1、写出设计流水作业调度算法的主要步骤。
2、举例说明贪心算法与动态规划算法的的主要差别。 3、写出用回溯法搜索子集树的一般算法。
4、简述利用贪心算法解决“单源最短路径”问题的基本思想。 5、简述分治法的基本思想。
6、写出设计动态规划算法的主要步骤。 7、简述分支限界法与回溯法的异同。 8、写出用回溯法搜索排列树的算法。
算法题：
0—1背包问题：给定n种物品和一背包，物品i的重量是wi，其价值为vi，背包的容量为C。问应该如何装入背包中物品的总价值最大？写出用分支限界算法解决该问题的算法。
例题
1.选择范例
（1）分支限界法与回溯法都是在问题的解空间树T上搜索问题的解，二者（）。 A．求解目标不同，搜索方式相同B．求解目标不同，搜索方式也不同 C．求解目标相同，搜索方式不同D．求解目标相同，搜索方式也相同
（2）下列是动态规划算法基本要素的是（ ）。
A、最优子结构 B、构造最优解 C、算出最优解 D、定义最优解
（3）Strassen矩阵乘法是利用（ ）实现的算法。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法
（4）下面不是分支界限法搜索方式的是（ ）。
A、广度优先 B、最小耗费优先 C、最大效益优先 D、深度优先
2.判断范例
（1）所有的递归函数都能找到对应的非递归定义。-----（ ） （2）满足最优子结构性质必满足贪心选择性质。-----（ ） （3）满足贪心选择性质必满足最优子结构性质。-----（ ）
（4）状态空间树中，只有展开了所有子结点的结点才称为死结点。-----（ ） （5）变治法是基于变换的思想。分两个阶段工作，即“变”阶段和“治”阶段.变治法的三种类型：1)实例化简(instance simplification)2)改变表现(representation change)3)问题化简(problem reduction)。例如AVL树，多路查找树都是 实例化简的具体应用。-----（ ）
（6）时空权衡是指在算法的设计中，对算法的时间和空间作出权衡。常见的以空间换取时间的方法有：输入增 强（计数排序，串匹配算法的改进）预构造（散列法，B树） -----（ ）
（7）动态规划算法基本思想是将待求解问题分解成若干个子问题，并且经分解得到的子问题是互相独立的。求 解时有些子问题被重复计算了许多次。-----（ ）
2．解释下面术语
哈密尔顿环 贪心算法 分枝限界方法 0/1背包问题 算法
3.简答范例
简述回溯法求解问题的一般步骤。 简述状态空间树的广度优先展开方法。 状态空间树中的活结点、E-结点、死结点 简述用回溯法设计算法的步骤。
举例说明最小生成树在实际中的应用。
4.分析设计题
上课反复讲、反复强调的几个问题，要求懂原理，会设计（关键是思路，表达方法可以是语言、伪代码、代码），会进行复杂度分析。
建议：答题时不要把所有的东西写一大段，适当分步骤、分要点，如XXX算法原理 ①做什么，怎么做 ②做什么，怎么做 ③做什么，怎么做 ……等
8. 以下是分数背包问题的贪心算法 算法 GREEDY_KANPSACK
输入：表示背包容量的实数C, 物品数n, 表示n个物品的体积和价值的实数数组s[1..n]和v[1..n]。 输出：装入背包物品的最大总价值maxv和相应的最优解x[1..n]。 for i=1 to n
y[i]=v[i]/s[i] //求n个物品的单位体积价值y[1..n]。 end for
//对y[1..n]按降序地址排序，排序结果返回到数组d[1..n] //中, 使得y[d[1]]>=y[d[2]]>=…>=y[d[n]]。 d=sort(y, n)
for i=1 to n x[i]=0 //对x[1..n]初始化。
i=1; maxv=0; rc=C //以下rc表示当前背包的剩余容量。 while ____________ and i<=n
j=d[i] // uj为当前考虑选择的物品 if s[j]<=rc then
x[j]= ____________; rc= ____________ //物品uj全部装入背包。 else
x[j]= ____________ //选择物品uj的一部分将背包填满。 rc=0 end if
maxv= ____________ i= ____________
end while return maxv, x[1..n] end GREEDY_KNAPSACK