《算法分析与设计》期末复习题(一) 一、 选择题 1
应用 Johnson 法则的流水作业调度采用的算法是（D） A
贪心算法 B
分支限界法 C
动态规划算法 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 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); } 3
动态规划算法的基本要素为（C） A
最优子结构性质与贪心选择性质 B．重叠子问题性质与贪心选择性质 C．最优子结构性质与重叠子问题性质 D
预排序与递归调用 4
算法分析中，记号O 表示（B）， 记号 表示（A）， 记号 表示（D）
渐进下界 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)
