《算法分析与设计》期末复习题
一、
选择题
1.应用Johnson法则的流水作业调度采用的算法是（D）
A. 贪心算法 B. 分支限界法 C.分治法
塔问题如下图所示。现要求将塔座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); move(n,a,b); hanoi(n-1, C, B, A); } D. 动态规划算法
Hanoi塔
B. void hanoi(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); }
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, C, B, A); } 3.? 动态规划算法的基本要素为（C） A. 最优子结构性质与贪心选择性质 B．重叠子问题性质与贪心选择性质 C．最优子结构性质与重叠子问题性质 D. 预排序与递归调用
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）策略，从根结点出发搜索解空间树。
A． 广度优先 B. 活结点优先 C.扩展结点优先 D. 深度优先
8. 分支限界法在问题的解空间树中，按（A）策略，从根结点出发搜索解空间树。 A． 广度优先 B. 活结点优先 C.扩展结点优先 D. 深度优先
9. 程序块（A）是回溯法中遍历排列树的算法框架程序。 A. B. C.
void backtrack (int t) { if (t>n) output(x); else for (int i=0;i<=1;i++) { x[t]=i; if (legal(t)) backtrack(t+1); } } void backtrack (int t) { if (t>n) output(x); else for (int i=0;i<=1;i++) { x[t]=i; if (legal(t)) backtrack(t-1); } } void backtrack (int t) { if (t>n) output(x); else for (int i=t;i<=n;i++) { swap(x[t], x[i]); if (legal(t)) backtrack(t+1); swap(x[t], x[i]); } } D.
10. 回溯法的效率不依赖于以下哪一个因素（C ）
A. 产生x[k]的时间；
B. 满足显约束的x[k]值的个数； C. 问题的解空间的形式； 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的输入时，在某条带上所使用过的最小方格数。
void backtrack (int t) { if (t>n) output(x); else for (int i=t;i<=n;i++) { swap(x[t], x[i]); if (legal(t)) backtrack(t+1); } } 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) }；
《算法设计与分析》考试题目及答案
