《《算法设计与分析》考试题目及答案》由会员分享，可在线阅读，更多相关《《算法设计与分析》考试题目及答案（24页珍藏版）》请在金锄头文库上搜索。
1、算法分析与设计期末复习题一、选择题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 塔hanoi(n-1,A,C, B);move(n,a,b);hanoi(n-1, C, B, A);B. void hanoi(in
2、t 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. 动态规划算法的基本要
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(minf(n),g(n)D. f (n)O(g(n)g(n) O(f (n)6. 能采用贪心
4、算法求最优解的问题，一般具有的重要性质为： （A） A. 最优子结构性质与贪心选择性质B重叠子问题性质与贪心选择性质C最优子结构性质与重叠子问题性质D. 预排序与递归调用7. 回溯法在问题的解空间树中，按（ D）策略，从根结点出发搜索解空间树。A 广度优先B. 活结点优先C.扩展结点优先D. 深度优先8. 分支限界法在问题的解空间树中， 按（ A）策略，从根结点出发搜索解空间树。A 广度优先B. 活结点优先C.扩展结点优先D. 深度优先9. 程序块（ A ）是回溯法中遍历排列树的算法框架程序。A.voidbacktrack(int t)B.if (tn) output(x);elsefor (
5、int i=t;in) output(x);elsefor (int i=0;in) output(x); elsefor (int i=0;in) output(x);elsefor (int i=t;i0，存在正数和 n0 0 使得对所有 n n0有： 0f(n)0，存在正数和 n0 0 使得对所有nn0 有： 0cg(n) 0，存在正数和 n0 0 使得对所有 nn0有： 0f(n)0 使得对所有 nnc000有： 0cg(n) f(n) ；二、填空题1.下面程序段的所需要的计算时间为（2）。O ( n )int MaxSum(int n, int *a,int &besti,int &
6、bestj)int sum=0;for(int i=1;i=n;i+)int thissum=0;for(int j=i;jsum)sum=thissum;besti=i;bestj=j;return sum;2. 有 11 个待安排的活动，它们具有下表所示的开始时间与结束时间，如果以贪心算法求解这些活动的最优安排（即为活动安排问题：在所给的活动集合中选出最大的相容活动子集合） ，得到的最大相容活动子集合为活动（ 1 ，4，8，11）。i1234567891011Si130535688212fi45678910111213143. 所谓贪心选择性质是指（ 所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到 ）。4. 所谓最优子结构性质是指（ 问题的最优解包含了其子问题的最优解 ）。5. 回溯法是指（ 具有限界函数的深度优先生成法 ）。6. 用回溯法解题的一个显著特征是在搜索过程中动态产生问题的解空间。 在任何时刻，算法只保存从根结点到当前扩展结点的路径。如果解空间树中从根结点到叶结点的最长路径的长度为 h(n) ，则回溯法所需的计算空间
