《《算法分析与设计》期末考试复习题-学生版.doc.pdf》由会员分享，可在线阅读，更多相关《《算法分析与设计》期末考试复习题-学生版.doc.pdf（13页珍藏版）》请在三一文库上搜索。
1、算法分析与设计期末复习题 一、 选择题 1 . 应用Johnson法则的流水作业调度采用的算法是（D） A.贪心算法B.分支 限界法C.分治法 2. Hanoi塔问题如下图所示。现要求将塔座A上的的所有圆盘移到塔座B上，并 仍按同样顺序叠置。移动圆盘时遵守Hanoi塔问题的移动规则。由此设计出解 Hanoi塔问题的递归算法正确的为：(B) A. void hem()i(int n, int A, int C, int B) j i if (n 0) hanoi (nl, A, C, B); move (n, a, b); hanoi (nl, C, B, A); B. void hanoi (
2、int n, int A, int B, int C) i t if (n 0) hanoi (nl, A, C, B); move (n, a, b); hanoi (nT, C, B, A); C. void hanoi (int n, int j c, int B, int A) t if (n 0) t hanoi (nl, A, C, B); move (n, a, b); hanoi (nl, C,B, A); D. void hanoi(int n, int C, int A, int B) j i if (n 0) hanoi (n-1, A, C, B); move (n,
3、a, b); hanoi (n-1, C, B, A); D.动态规划算法 Hanoi 塔 3.动态规划算法的基本耍素为(C) A.最优子结构性质与贪心选择性质 B.重叠子问题性质与贪心选择性质 C.最优了结构性质与重叠了问题性质 D.预排序与递归调用 4.算法分析中，记号O表示(B),记号。表示 A.渐进下界 B.渐进上界 C.非紧上界 D.紧渐进界 E.非紧下界 5.以下关于渐进记号的性质是止确的有：(A) A. f (n) = 0(g(n),g(n) = 0(h(n) n f (n) = 0(h(n) B. f (n) = O(g(n),g(n) = O(h(n) = h(n) = O(
4、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.能采用贪心算法求最优解的问题，一般具有的重要性质为：(A) A.最优子结构性质与贪心选择性质 B.重叠了问题性质与贪心选择性质 C.最优子结构性质与重叠子问题性质 D.预排序与递归调用 7.回溯法在问题的解空间树中，按（D）策略，从根结点出发搜索解空间树。 A.广度优先B.活结点优先C.扩展结点优先D.深度优先 8.分支限界法在问题的解空间树中，按（A）策略，从根结点出发搜索解空间树。 A.广度优先B.活结点优先C.扩展结点优先D.深度优先 记号0表不
5、(D)o 9.程序块（A）是回溯法屮遍历排列树的算法框架程序。 void backtrack (int t) if (tn) output (x); else for (int i二t;i二n;i+) swap(xt, xi); if (legal (t) backtrack (t+1); swap(xt, xi); void backtrack (int t) if (tn) output (x); el se for (int i二0;i二l;i+) xt=i; if (legal (t) backtrack (t+1); void backtrack (int t) if (tn) ou
6、tput(x); el se for (int i二0;iUl;i+) xt=i; if (legal (t) backtrack (tl); D. void backtrack (int t) if (tn) output(x); else for (int i二t;i二n;i+) swap(xt, xi); if (legal (t) backtrack (t+1); 10.回溯法的效率不依赖于以下哪一个因素？（C ） A产生xk的时间 ; B.满足显约束的xk值的个数； C.问题的解空间的形式； D.计算上界函数bound的时间； E.满足约束函数和上界函数约束的所冇xk的个数。 F.计
7、算约束函数constraint的时间； C. 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的输入吋，在某条带上所使用过的
8、最小方格数。 13.NP类语言在图灵机下的定义为(D) A.NP=L|L是一个能在非多项式时间内被一台NDTM所接受的语言； B.NP=L|L是一个能在多项式时间内被一台NDTM所接受的语言； C.NP-L| L是一个能在多项式时间内被一台DTM所接受的语言； D.NP=L|L是一个能在多项式时间内被一台NDTM所接受的语言； 14.记号0的定义止确的是(A)。 A.0(g(n) = f (n) |存在正常数c和nO使得对所有nlrio有：00,存在正数和n()0使得对所nn0 有：0 0,存在止数和n0使得对所有nnoli : 0 0,存在正数和n0使得对所nn0 有：0 0,存在正数和0使
9、得对所有nlrio 有：0 sum) sum二thissum; besti=i; bestj二j; return sum; 2.有11个待安排的活动，它们具有下表所示的开始时间与结束时间，如果以贪心算 法求解这些活动的最优安排（即为活动安排问题：在所给的活动集合小选出最大的 相容活动子集合），得到的最大相容活动子集合为活动（1, 4, 8, 11）。 1 12 345 6 7 8 9 1011 Si 1 3 0 535 688212 Hi4567891011121314 3.所谓贪心选择性质是指（所求问题的整体最优解可以通过一系列局部最优的 选择，即贪心选择来达到）。 4.所谓最优了结构性质是
10、指（问题的最优解包含了其了问题的最优解）。 5.回溯法是指（具有限界函数的深度优先生成法）。 6.用回溯法解题的一个显著特征是在搜索过程屮动态产生问题的解空间。在任 何时刻，算法只保存从根结点到当前扩展结点的路径。如果解空间树中从根 结点到叶结点的最长路径的长度为h（n）,则回溯法所需的计算空间通常为 （O（h（n）0 7.回溯法的算法框架按照问题的解空间一般分为（子集树）算法框架与（排列 树）算法框架。 / 剩余容量 Typep b = cp; / 结点的上界 / 以物品单位重量价值递减序装入物品while (i nl, n2, 有gl(n) n3,有 fl(n) +gl(n) n) / 到
11、达叶结点 更新最优解bestx, bestw;return; r 二wi; if (cw + wi bestw) xi二0; / 搜索右了树 backtrack(i + 1) ; r += wi; 5.用分支限界法解装载问题时，对算法进行了一些改进，下面的程序段给出了改进 部分；试说明斜线部分完成什么功能，以及这样做的原因，即采用这样的方式，算 法在执行上有什么不同。 / 检查左儿子结点 Type wt 二 Ew + wi; / 左儿子结点的重量 if (wt bestw) bestw = wt; / 加入活结点队列 if (i bestw / 可能含最优解 Q. Delete (Ew) ;
12、/ 取下一扩展结点解答：斜线标识的部分完成的 功能为：提前更新bestw值； 这样做可以尽早的进行对右了树的剪枝。具体为：算法Maxloading初始 时 将bestw设置为0,直到搜索到第一个叶结点时才更新bestwo因此在算法搜索到第一 个叶子结点之前，总有bestw二0, r0故Ew+rbcstw总是成立。也就是说，此时 右子树测试不起作用。 为了使上述右子树测试尽早生效，应提早更新best%又知算法最终找到的最优 值是所求问题的了集树中所有可行结点和应重量的最大值。而结点所相应得重量仅 在搜索进入左子树是增加，因此，可以在算法每一次进入左子树时更新bestw的值。 7.最长公共子序列问
13、题 : 给定2个序列X=xl, x2,，xm和Y=yl, y2, , yn, 找出X 和Y的最长公共子序列。 由最长公共子序列问题的最优子结构性质建立子问题最优值的递归关系。用 ci j记录序列Xi和Yj的最长公共子序列的长度。其中， Xi二xl, x2,，xi ；Yj=yl, y2, ?, yj 0;xi = yJ maxc ij-l,ci-lj i,j0xi工儿 在程序中，bij记录Cij的值是由哪一个了问题的解得到的。 （1）请填写程序中的空格，以使函数LCSLength完成计算最优值的功能。 void LCSLength(int m, int n, char *x, char *y,
14、int *c, int *b) int 1, j; for(i 1; i =ci j-1) cij=ci-lj; bij二2; else ci j=ci j-1; bi j=3; （2）函数LCS实现根据b的内容打印出Xi和Yj的最长公共子序列。请填 写程序中的空格，以使函数LCS完成构造最长公共子序列的功能（请将 bij的取值与（1）中您填写的取值对应，否则视为错误）。 void LCS(int i, int j, char *x, int *b) if (i =0 | j=0) return; if (bi j二二1) LCS (iT , j-1, x, b); coutxi; else if (bij= 2) LCS(i-1, j, x, b); else LCS(i, j-1, x, b); f(k-l); f(k-l);