发布时间 : 星期四 文章《算法设计与分析》考试题目及答案更新完毕开始阅读593ac7707a3e0912a21614791711cc7931b77876
《算法分析与设计》期末复习题
一、 选择题
1.应用Johnson法则的流水作业调度采用的算法是（D）
A. 贪心算法 B. 分支限界法 C.分治法
D. 动态规划算法
2.Hanoi塔问题如下图所示。现要求将塔座A上的的所有圆盘移到塔座B上，并仍按同样顺序叠置。移动圆盘时遵守Hanoi塔问题的移动规则。由此设计出解Hanoi塔问题的递归算法正确的为：（B）
A. void hanoi(int n, int A, int C, int B) { if (n > 0) { hanoi(n-1,A,C, B); B. void hanoi(int n, int A, int B, int C) { move(n,a,b); C. void hanoi(int n, int C, int B, int A) hanoi(n-1, C, B, A); if (n > 0) { D. void hanoi(int n, int C, int A, int B) } { 3. if (n > 0) ? 动态规划算法的基本要素为（ { C） hanoi(n-1, A, C, B); { if (n > 0) A. move(n,a,b); 最优子结构性质与贪心选择性质 hanoi(n-1, A, C, B); { hanoi(n-1, C, B, A); B．重叠子问题性质与贪心选择性质 move(n,a,b); hanoi(n-1, A, C, B); } hanoi(n-1, C, B, A); move(n,a,b); C．最优子结构性质与重叠子问题性质 } hanoi(n-1, C, B, A); D. 预排序与递归调用 } Hanoi塔
4. 算法分析中，记号O表示（B）， 记号?表示（A）， 记号?表示（D）。 A.渐进下界 B.渐进上界 C.非紧上界 D.紧渐进界 E.非紧下界
5. 以下关于渐进记号的性质是正确的有：（A） A.f(n)??(g(n)),g(n)??(h(n))?f(n)??(h(n)) B. f(n)?O(g(n)),g(n)?O(h(n))?h(n)?O(f(n)) C. O(f(n))+O(g(n)) = O(min{f(n),g(n)}) D. f(n)?O(g(n))?g(n)?O(f(n))
6. 能采用贪心算法求最优解的问题，一般具有的重要性质为：（A）
A. 最优子结构性质与贪心选择性质 B．重叠子问题性质与贪心选择性质 C．最优子结构性质与重叠子问题性质 D. 预排序与递归调用
7. 回溯法在问题的解空间树中，按（D）策略，从根结点出发搜索解空间树。广度优先 B.
活结点优先 C.扩展结点优先 D. 深度优先
8. 分支限界法在问题的解空间树中，按（A）策略，从根结点出发搜索解空间树。 A． 广度优先 B. 活结点优先 C.扩展结点优先 D. 深度优先 9. 程序块（A）是回溯法中遍历排列树的算法框架程序。 A.
void backtrack (int t) B. { void backtrack (int t) if (t>n) output(x); C. { void backtrack (int t) else if (t>n) output(x); { D. for (int i=t;i<=n;i++) { else if (t>n) output(x); swap(x[t], x[i]); void backtrack (int t) 10. 回溯法的效率不依赖于以下哪一个因素？（ for (int i=0;i<=1;i++) { C ） else if (legal(t)) backtrack(t+1); { x[t]=i; for (int i=0;i<=1;i++) { swap(x[t], x[i]); if (t>n) output(x); A. 产生x[k]的时间； if (legal(t)) backtrack(t+1); x[t]=i; } else } if (legal(t)) backtrack(t-1); } B. 满足显约束的x[k]值的个数； for (int i=t;i<=n;i++) { } } swap(x[t], x[i]); }C. 问题的解空间的形式； if (legal(t)) backtrack(t+1); D. 计算上界函数bound的时间； } } E. 满足约束函数和上界函数约束的所有x[k]的个数。
F. 计算约束函数constraint的时间； 11. 常见的两种分支限界法为（D）
A. 广度优先分支限界法与深度优先分支限界法； B. 队列式（FIFO）分支限界法与堆栈式分支限界法； C. 排列树法与子集树法；
D. 队列式（FIFO）分支限界法与优先队列式分支限界法； 12. k带图灵机的空间复杂性S(n)是指（B）
A. k带图灵机处理所有长度为n的输入时，在某条带上所使用过的最大方格数。 B. k带图灵机处理所有长度为n的输入时，在k条带上所使用过的方格数的总和。 C. k带图灵机处理所有长度为n的输入时，在k条带上所使用过的平均方格数。 D. k带图灵机处理所有长度为n的输入时，在某条带上所使用过的最小方格数。 13. NP类语言在图灵机下的定义为（D）
A. NP={L|L是一个能在非多项式时间内被一台NDTM所接受的语言}； B. NP={L|L是一个能在多项式时间内被一台NDTM所接受的语言}； C. NP={L|L是一个能在多项式时间内被一台DTM所接受的语言}；
D. NP={L|L是一个能在多项式时间内被一台NDTM所接受的语言}；14. 记号O的定义正确的是（A）。
A. O(g(n)) = { f(n) | 存在正常数c和n0使得对所有n?n0有：0? f(n) ? cg(n) }； B. O(g(n)) = { f(n) | 存在正常数c和n0使得对所有n?n0有：0? cg(n) ? f(n) }； C. O(g(n)) = { f(n) | 对于任何正常数c>0，存在正数和n0 >0使得对所有n?n0有：0
?f(n) D. O(g(n)) = { f(n) | 对于任何正常数c>0，存在正数和n0 >0使得对所有n?n0有：0 ?cg(n) < f(n) }； 15. 记号?的定义正确的是（B）。 A. O(g(n)) = { f(n) | 存在正常数c和n0使得对所有n?n0有：0? f(n) ? cg(n) }； B. O(g(n)) = { f(n) | 存在正常数c和n0使得对所有n?n0有：0? cg(n) ? f(n) }； C. (g(n)) = { f(n) | 对于任何正常数c>0，存在正数和n0 >0使得对所有n?n0有：0 ?f(n) D. (g(n)) = { f(n) | 对于任何正常数c>0，存在正数和n0 >0使得对所有n?n0有：0 ?cg(n) < f(n) }； 二、 填空题 1. 下面程序段的所需要的计算时间为（ O(n2) ）。 int MaxSum(int n, int *a, int &besti, int &bestj) { int sum=0; 2. 有11个待安排的活动，它们具有下表所示的开始时间与结束时间，如果以贪心算法 for(int i=1;i<=n;i++){ 求解这些活动的最优安排（即为活动安排问题：在所给的活动集合中选出最大的相 int thissum=0; for(int j=i;j<=n;j++){ 容活动子集合），得到的最大相容活动子集合为活动（ {1，4，8，11} ）。 thissum+=a[j]; if(thissum>sum) { i 1 2 3 4 5 6 7 8 9 10 11 sum=thissum; S[1 5 3 5 6 8 8 2 12 3 0 besti=i; 5 6 bestj=j; f[4 7 8 9 10 11 12 13 14 } } } 3. 所谓贪心选择性质是指（所求问题的整体最优解可以通过一系列局部最优的选择， 即贪心选择来达到）。 4. 所谓最优子结构性质是指（问题的最优解包含了其子问题的最优解）。 5. 回溯法是指（具有限界函数的深度优先生成法）。 6. 用回溯法解题的一个显着特征是在搜索过程中动态产生问题的解空间。在任何时 刻，算法只保存从根结点到当前扩展结点的路径。如果解空间树 中从根结点到叶结点的最长路径的长度为h(n)，则回溯法所需的计算空间通常为（O(h(n))）。 7. 回溯法的算法框架按照问题的解空间一般分为（子集树）算法框架与（排列树）算法 框架。 8. 用回溯法解0/1背包问题时，该问题的解空间结构为（子集树）结构。 9.用回溯法解批处理作业调度问题时，该问题的解空间结构为（排列树）结构。 10.用回溯法解0/1背包问题时，计算结点的上界的函数如下所示，请在空格中填入合 适的内容： Typep Knap Typep b = cp; // 结点的上界 ( O(mn) )，构造相应的最短距离需要（O(L)）时间。 // 以物品单位重量价值递减序装入物品 while (i <= n && w[i] <= cleft) { for (int i = 0; i < NumOfNbrs; i++) { cleft -= w[i]; nbr.row = here.row + offset[i].row; 12. 用回溯法解图的m着色问题时，使用下面的函数OK检查当前扩展结点的每一个儿子所 b += p[i]; nbr.col = here.col + offset[i].col; i++; if (grid[nbr.row][nbr.col] == 0) { 相应的颜色的可用性，则需耗时（渐进时间上限）（O（mn））。 } // 该方格未标记 // 装满背包 Bool Color::OK(int k) grid[nbr.row][nbr.col] if (i <= n) （b += p[i]/w[i] * cleft）; {// = grid[here.row][here.col] + 1; return b; for(int j=1;j<=n;j++) if ((nbr.row == finish.row) && 13. 旅行售货员问题的解空间树是（排列树）。证明题 } (nbr.col == finish.col)) break; // if((a[k][j]= =1)&&(x[j]= =x[k])) return false; 完成布线return true; 1. 一个分治法将规模为n的问题分成k个规模为n／m的子问题去解。设分解阀值} Q.Add(nbr);} n0=1，且adhoc解规模为1的问题耗费1个单位时间。再设将原问题分解为k个子问题 以及用merge将k个子问题的解合并为原问题的解需用f(n)个单位时间。用T(n)表示该 O(1)n?1?分治法解规模为|P|=n的问题所需的计算时间，则有：T(n)?? kT(n/m)?f(n)n?1?通过迭代法求得T（n）的显式表达式为：T(n)?nlogmk?logmn?1?j?0kjf(n/mj)