《算法设计与分析考试题目及答案》由会员分享，可在线阅读，更多相关《算法设计与分析考试题目及答案（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(n-1,A,C, B); move(n,a,b); hanoi(n-1, C, B, A); Hanoi塔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.B. C. O(f(n)+O(g(n) = O(minf(n),g(n) D. 6. 能采用贪心算法求最优解的问题，一般具有的重要性质为：（A）A. 最优子结构性质与贪心选择性质B重叠子问题性质与贪心选择性质C最优子结构性质与重叠子问题性质D. 预排序与递归
4、调用7. 回溯法在问题的解空间树中，按（D）策略，从根结点出发搜索解空间树。A 广度优先 B. 活结点优先 C.扩展结点优先 D. 深度优先8. 分支限界法在问题的解空间树中，按（A）策略，从根结点出发搜索解空间树。 A 广度优先 B. 活结点优先 C.扩展结点优先 D. 深度优先9. 程序块（A）是回溯法中遍历排列树的算法框架程序。void backtrack (int t) if (tn) output(x); else for (int i=t;in) output(x); else for (int i=0;in) output(x); else for (int i=0;in) ou
5、tput(x); else for (int i=t;i0，存在正数和n0 0使得对所有nn0有：0 f(n)0，存在正数和n0 0使得对所有nn0有：0 cg(n) 0，存在正数和n0 0使得对所有nn0有：0 f(n)0，存在正数和n0 0使得对所有nn0有：0 cg(n) f(n) ；二、 填空题1. 下面程序段的所需要的计算时间为（ ）。int MaxSum(int n, int *a, int &besti, int &bestj)int sum=0;for(int i=1;i=n;i+) int thissum=0;for(int j=i;jsum)sum=thissum;best
6、i=i;bestj=j;return sum;2. 有11个待安排的活动，它们具有下表所示的开始时间与结束时间，如果以贪心算法求解这些活动的最优安排（即为活动安排问题：在所给的活动集合中选出最大的相容活动子集合），得到的最大相容活动子集合为活动（ 1，4，8，11 ）。1413121110987654fi122886535031Si1110987654321i3. 所谓贪心选择性质是指（所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到）。4. 所谓最优子结构性质是指（问题的最优解包含了其子问题的最优解）。5. 回溯法是回溯法是指（具有限界函数的深度优先生成法）。6. 用回溯法
7、解题的一个显著特征是在搜索过程中动态产生问题的解空间。在任何时刻，算法只保存从根结点到当前扩展结点的路径。如果解空间树 中从根结点到叶结点的最长路径的长度为h(n)，则回溯法所需的计算空间通常为（O(h(n)）。7. 回溯法的算法框架按照问题的解空间一般分为（子集树）算法框架与（排列树）算法框架。8. 用回溯法解0/1背包问题时，该问题的解空间结构为（子集树）结构。9.用回溯法解批处理作业调度问题时，该问题的解空间结构为（排列树）结构。10.用回溯法解0/1背包问题时，计算结点的上界的函数如下所示，请在空格中填入合适的内容：Typep Knap:Bound(int i)/ 计算上界 Typew cleft = c - cw; / 剩余容量 Typep b = cp; / 结点的上界 / 以物品单位重量价值递减序装入物品 while (i = n & wi = cleft) cleft -= wi; b += pi; i+; / 装满背包 if (i = n) （b += pi/wi * cleft）; return b;11. 用回溯法解布线问题时，求最优解的主要程序段如下。如果布线区域划分为的方格阵列，扩展每个结点需O(1)的时间，L为最短布线路径的长度，则算法共耗时 ( O(mn) )，构造相应的最短距离需要（O(L)）时间。for (int i =
