1、算法分析与设计期末复习题一、 选择题1.应用 Johnson 法则的流水作业调度采用的算法是（D）A. 贪心算法 B. 分支限界法 C.分治法 D. 动态规划算法2.Hanoi 塔问题如下图所示。现要求将塔座 A 上的的所有圆盘移到塔座 B 上，并仍按同样顺序叠置。移动圆盘时遵守 Hanoi 塔问题的移动规则。由此设计出解 Hanoi 塔问题的递归算法正确的为：（B）Hanoi 塔A. void hanoi(int n, int A, int C, int B)if (n 0)hanoi(n-1,A,C, B);move(n,a,b);hanoi(n-1, C, B, A);B. void h
2、anoi(int n, int A, int B, int C)if (n 0)hanoi(n-1, A, C, B);move(n,a,b);hanoi(n-1, C, B, A);C. void hanoi(int n, int C, int B, int A)if (n 0)hanoi(n-1, A, C, B);move(n,a,b);hanoi(n-1, C, B, A);3. 动态规划算法的基本要素为（C）A. 最优子结构性质与贪心选择性质B重叠子问题性质与贪心选择性质C最优子结构性质与重叠子问题性质D. 预排序与递归调用4. 算法分析中，记号 O 表示（B） ， 记号 表示（ A
3、） ， 记号 表示（D） 。A.渐进下界B.渐进上界C.非紧上界D.紧渐进界E.非紧下界5. 以下关于渐进记号的性质是正确的有：（A）A. f(n)g(),n(h)f(nh()B. O)OfC. O(f(n)+O(g(n) = O(minf(n),g(n) D. f(n)g()(n)f()6. 能采用贪心算法求最优解的问题，一般具有的重要性质为：（A）A. 最优子结构性质与贪心选择性质B重叠子问题性质与贪心选择性质D. void hanoi(int n, int C, int A, int B)if (n 0)hanoi(n-1, A, C, B);move(n,a,b);hanoi(n-1,
4、 C, B, A);C最优子结构性质与重叠子问题性质D. 预排序与递归调用7. 回溯法在问题的解空间树中，按（D）策略，从根结点出发搜索解空间树。A 广度优先 B. 活结点优先 C.扩展结点优先 D. 深度优先8. 分支限界法在问题的解空间树中，按（A）策略，从根结点出发搜索解空间树。A 广度优先 B. 活结点优先 C.扩展结点优先 D. 深度优先9. 程序块（A）是回溯法中遍历排列树的算法框架程序。A.B. C.void backtrack (int t)if (tn) output(x);elsefor (int i=t;in) output(x);elsefor (int i=0;in)
5、 output(x);elsefor (int i=0;in) output(x);elsefor (int i=t;i0，存在正数和 n0 0 使得对所有n n0有：0 f(n)0，存在正数和 n0 0 使得对所有n n0有：0 cg(n) 0，存在正数和 n0 0 使得对所有 nn0有：0 f(n)0，存在正数和 n0 0 使得对所有 nn0有：0 cg(n) sum) sum=thissum;besti=i;bestj=j;return sum;2. 有 11 个待安排的活动，它们具有下表所示的开始时间与结束时间，如果以贪心算法求解这些活动的最优安排（即为活动安排问题：在所给的活动集合中
6、选出最大的相容活动子集合） ，得到的最大相容活动子集合为活动（ 1，4，8，11 ） 。3. 所谓贪心选择性质是指（所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到） 。4. 所谓最优子结构性质是指（问题的最优解包含了其子问题的最优解） 。5. 回溯法是指（具有限界函数的深度优先生成法） 。6. 用回溯法解题的一个显著特征是在搜索过程中动态产生问题的解空间。在任何时刻，算法只保存从根结点到当前扩展结点的路径。如果解空间树 中从根结点到叶结点的最长路径的长度为 h(n)，则回溯法所需的计算空间通常为（O(h(n)） 。7. 回溯法的算法框架按照问题的解空间一般分为（子集树）算法
7、框架与（排列树）算法框架。8. 用回溯法解 0/1 背包问题时，该问题的解空间结构为（子集树）结构。9.用回溯法解批处理作业调度问题时，该问题的解空间结构为（排列树）结构。10.用回溯法解 0/1 背包问题时，计算结点的上界的函数如下所示，请在空格中填入合适的内容：1413121110987654fi122886535031Si1110987654321iTypep Knap:Bound(int i)/ 计算上界Typew cleft = c - cw; / 剩余容量Typep b = cp; / 结点的上界/ 以物品单位重量价值递减序装入物品while (i = n b += pi;i+;/
8、 装满背包if (i = n) （b += pi/wi * cleft）;return b;11. 用回溯法解布线问题时，求最优解的主要程序段如下。如果布线区域划分为 的方格阵列，扩展每个结点需 O(1)的时间，L 为最短布线路径的长度，nm则算法共耗时 ( O(mn) )，构造相应的最短距离需要（O(L)）时间。12. 用回溯法解图的 m 着色问题时，使用下面的函数 OK 检查当前扩展结点的每一个儿子所相应的颜色的可用性，则需耗时（渐进时间上限） （O （mn ） ） 。for (int i = 0; i NumOfNbrs; i+) nbr.row = here.row + offseti
9、.row;nbr.col = here.col + offseti.col;if (gridnbr.rownbr.col = 0) / 该方格未标记gridnbr.rownbr.col= gridhere.rowhere.col + 1;if (nbr.row = finish.row) / 完成布线Q.Add(nbr); Bool Color:OK(int k)/for(int j=1;j=n;j+)if(akj= =1)return true;13. 旅行售货员问题的解空间树是（排列树） 。三、 证明题1. 一个分治法将规模为 n 的问题分成 k 个规模为 nm 的子问题去解。设分解阀值
10、n0=1，且 adhoc 解规模为 1 的问题耗费 1 个单位时间。再设将原问题分解为 k 个子问题以及用 merge 将 k 个子问题的解合并为原问题的解需用f(n)个单位时间。用 T(n)表示该分治法解规模为|P|=n 的问题所需的计算时间，则有： (1)()/OnTnkmf通过迭代法求得 T（n）的显式表达式为：log1l0()(/)nmkjjjTf试证明 T（n）的显式表达式的正确性。2. 举反例证明 0/1 背包问题若使用的算法是按照 pi/wi 的非递减次序考虑选择的物品，即只要正在被考虑的物品装得进就装入背包，则此方法不一定能得到最优解（此题说明 0/1 背包问题与背包问题的不同
11、） 。证明：举例如：p=7,4,4,w=3,2,2,c=4 时，由于 7/3 最大，若按题目要求的方法，只能取第一个，收益是 7。而此实例的最大的收益应该是 8，取第 2，3 个。3. 求证：O(f(n)+O(g(n) = O(maxf(n),g(n) 。证明：对于任意 f1(n) O(f(n) ，存在正常数 c1 和自然数 n1，使得对所有n n1，有 f1(n) c1f(n) 。类似地，对于任意 g1(n) O(g(n) ，存在正常数 c2 和自然数 n2，使得对所有 n n2，有 g1(n) c2g(n) 。令 c3=maxc1, c2， n3 =maxn1, n2，h(n)= maxf
12、(n),g(n) 。则对所有的 n n3，有f1(n) +g1(n) c1f(n) + c2g(n) c3f(n) + c3g(n)= c3(f(n) + g(n)c32 maxf(n),g(n)= 2c3h(n) = O(maxf(n),g(n) .4. 求证最优装载问题具有贪心选择性质。（最优装载问题：有一批集装箱要装上一艘载重量为 c 的轮船。其中集装箱 i 的重量为 Wi。最优装载问题要求确定在装载体积不受限制的情况下，将尽可能多的集装箱装上轮船。 设集装箱已依其重量从小到大排序，(x 1,x2,xn)是最优装载问题的一个最优解。又设 。如果给定的最优装载问1min|ikx题有解，则有 。 ）1kn证明：四、 解答题1. 机器调度问题。问题描述：现在有 n 件任务和无限多台的机器，任务可以在机器上得到处理。每件任务的开始时间为 si，完成时间为 fi，s ifi 。s i，f i为处理任务 i 的时间范围。两个任务 i，j 重叠指两个任务的时间范围区间有重叠，而并非指 i，j 的起点或终点重合。例如：区间1，4与区间2，4重叠，而与4，7不重叠。一个可行的任务分配是指在分配中没有两件重叠的任务分配给同一台机器。因此，在可行的分配中每台机器在任何时刻最多只处理一
