计算机算法设计与分析复习题与答案1..docx

《算法分析与设计》期末复习题(一) 选择题 1.应用Johnson法则的流水作业调度采用的算法是（D） A. 贪心算法 B. 分支限界法 C.分治法 D. 动态规划算法 2.Hanoi塔问题如下图所示。现要求将塔座A上的的所有圆盘移到塔座B上，并仍按同样顺序叠置。移动圆盘时遵守Hanoi塔问题的移动规则。由此设计出解Hanoi塔问题的递归算法正确的为：（B） Hanoi塔B. void hanoi(int n, int A, int B, int C) 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); } } 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); } } 3.? 动态规划算法的基本要素为（C） A. 最优子结构性质与贪心选择性质 B．重叠子问题性质与贪心选择性质 C．最优子结构性质与重叠子问题性质 D. 预排序与递归调用 4. 算法分析中，记号O表示（B）， 记号表示（A）， 记号表示（D）。 A.渐进下界 B.渐进上界 C.非紧上界 D.紧渐进界 E.非紧下界 5. 以下关于渐进记号的性质是正确的有：（A） A. B. C. O(f(n))+O(g(n)) = O(min{f(n),g(n)}) D. 6. 能采用贪心算法求最优解的问题，一般具有的重要性质为：（A） A. 最优子结构性质与贪心选择性质 B．重叠子问题性质与贪心选择性质 C．最优子结构性质与重叠子问题性质 D. 预排序与递归调用 7. 回溯法在问题的解空间树中，按（D）策略，从根结点出发有哪些信誉好的足球投注网站解空间树。 广度优先 B. 活结点优先 C.扩展结点优先 D. 深度优先 8. 分支限界法在问题的解空间树中，按（A）策略，从根结点出发有哪些信誉好的足球投注网站解空间树。 A． 广度优先 B. 活结点优先 C.扩展结点优先 D. 深度优先 9. 程序块（A）是回溯法中遍历排列树的算法框架程序。 void backtrack void backtrack (int t) { if (tn) 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]); } } void backtrack (int t){ void backtrack (int t) { if (tn) output(x); else for (int i=0;i=1;i++) { x[t]=i; if (legal(t)) backtrack(t+1); } } void backtrack (int t){ void backtrack (int t) { if (tn) output(x); else for (int i=0;i=1;i++) { x[t]=i; if (legal(t)) backtrack(t-1); } } D.void v