《算法设计与分析》考试题目及答案(DOC)

《算法分析与设计》期末复习题

一、

选择题

1.应用Johnson法则的流水作业调度采用的算法是（D）

A. 贪心算法

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); } B. 分支限界法 C.分治法 D. 动态规划算法

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); } 3.? 动态规划算法的基本要素为（C） A. 最优子结构性质与贪心选择性质 B．重叠子问题性质与贪心选择性质 C．最优子结构性质与重叠子问题性质 D. 预排序与递归调用

4. 算法分析中，记号O表示（B）， 记号?表示（A）， 记号?表示（D）。 A.渐进下界 B.渐进上界 C.非紧上界 D.紧渐进界 E.非紧下界

5. 以下关于渐进记号的性质是正确的有：（A） A.f(n)B.

??(g(n)),g(n)??(h(n))?f(n)??(h(n))

f(n)?O(g(n)),g(n)?O(h(n))?h(n)?O(f(n))

C. O(f(n))+O(g(n)) = O(min{f(n),g(n)}) D.

6. 能采用贪心算法求最优解的问题，一般具有的重要性质为：（A）

A. 最优子结构性质与贪心选择性质 B．重叠子问题性质与贪心选择性质

f(n)?O(g(n))?g(n)?O(f(n))

C．最优子结构性质与重叠子问题性质 D. 预排序与递归调用

7. 回溯法在问题的解空间树中，按（D）策略，从根结点出发搜索解空间树。

A． 广度优先 B. 活结点优先 C.扩展结点优先 D. 深度优先

8. 分支限界法在问题的解空间树中，按（A）策略，从根结点出发搜索解空间树。 A． 广度优先 B. 活结点优先 C.扩展结点优先 D. 深度优先

9. 程序块（A）是回溯法中遍历排列树的算法框架程序。 A. B. C.

void backtrack (int t) { if (t>n) output(x); else for (int i=0;i<=1;i++) { x[t]=i; if (legal(t)) backtrack(t+1); } } void backtrack (int t) { if (t>n) output(x); else for (int i=0;i<=1;i++) { x[t]=i; if (legal(t)) backtrack(t-1); } } void backtrack (int t) { if (t>n) 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]); } } D.

10. 回溯法的效率不依赖于以下哪一个因素？（C ）

A. 产生x[k]的时间；

B. 满足显约束的x[k]值的个数； C. 问题的解空间的形式； D. 计算上界函数bound的时间；

E. 满足约束函数和上界函数约束的所有x[k]的个数。 F. 计算约束函数constraint的时间；

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的输入时，在某条带上所使用过的最小方格数。

void backtrack (int t) { if (t>n) output(x); else for (int i=t;i<=n;i++) { swap(x[t], x[i]); if (legal(t)) backtrack(t+1); } } 13. NP类语言在图灵机下的定义为（D）

A. NP={L|L是一个能在非多项式时间内被一台NDTM所接受的语言}； B. NP={L|L是一个能在多项式时间内被一台NDTM所接受的语言}； C. NP={L|L是一个能在多项式时间内被一台DTM所接受的语言}； D. NP={L|L是一个能在多项式时间内被一台NDTM所接受的语言}；

14. 记号O的定义正确的是（A）。

A. O(g(n)) = { f(n) | 存在正常数c和n0使得对所有n?n0有：0? f(n) ?

cg(n) }；

B. O(g(n)) = { f(n) | 存在正常数c和n0使得对所有n?n0有：0? cg(n) ?

f(n) }；

C. O(g(n)) = { f(n) | 对于任何正常数c>0，存在正数和n0 >0使得对所有n?n0

有：0 ?f(n)

D. O(g(n)) = { f(n) | 对于任何正常数c>0，存在正数和n0 >0使得对所有

n?n0有：0 ?cg(n) < f(n) }；

15. 记号?的定义正确的是（B）。

A. O(g(n)) = { f(n) | 存在正常数c和n0使得对所有n?n0有：0? f(n) ?

cg(n) }；

B. O(g(n)) = { f(n) | 存在正常数c和n0使得对所有n?n0有：0? cg(n) ?

f(n) }；

C. (g(n)) = { f(n) | 对于任何正常数c>0，存在正数和n0 >0使得对所有n?n0

有：0 ?f(n)

D. (g(n)) = { f(n) | 对于任何正常数c>0，存在正数和n0 >0使得对所有n?n0

有：0 ?cg(n) < f(n) }；

现有Hanoi塔问题的递归方程为：???h(n)?2h(n?1)?1h(1)?1 ，求h(n)的非递归表

达式。

解：利用给出的关系式，此时有：b=2, c=1, g(n)=1, 从n递推到1，有：

n?1h(n)?cb?2n?1n?1??i?1bn?1?ig(i)?2n?2?...?2?2?1

2?2?1n

3. 单源最短路径的求解。

问题的描述：给定带权有向图（如下图所示）G =(V,E)，其中每条边的权是非负实数。另外，还给定V中的一个顶点，称为源。现在要计算从源到所有其它各顶点的最短路长度。这里路的长度是指路上各边权之和。这个问题通常称为单源最短路径问题。

解法：现采用Dijkstra算法计算从源顶点1到其它顶点间最短路径。请将此过程填入下表中。

迭代

S {1}

u -

dist[2] dist[3] dist[4] dist[5] 10

maxint

30

100

初始 1 2 3 4

4. 请写出用回溯法解装载问题的函数。

装载问题：有一批共n个集装箱要装上2艘载重量分别为c1和c2的轮船，

n其中集装箱i的重量为wi，且

?i?1wi?c1?c2。装载问题要求确定是否有一个合理

的装载方案可将这n个集装箱装上这2艘轮船。如果有，找出一种装载方案。

解：void backtrack (int i)

{// 搜索第i层结点

if (i > n) // 到达叶结点

更新最优解bestx,bestw;return; r -= w[i];

if (cw + w[i] <= c) {// 搜索左子树 x[i] = 1; cw += w[i];

backtrack(i + 1); cw -= w[i]; } if (cw + r > bestw) {

x[i] = 0; // 搜索右子树 backtrack(i + 1); } r += w[i]; }

5. 用分支限界法解装载问题时，对算法进行了一些改进，下面的程序段给出了改进部分；试说明斜线部分完成什么功能，以及这样做的原因，即采用这样的方式，算法在执行上有什么不同。

// 检查左儿子结点 Type wt = Ew + w[i]; // 左儿子结点的重量 if (wt <= c) { // 可行结点 if (wt > bestw) bestw = wt; // 加入活结点队列 if (i < n) Q.Add(wt); } // 检查右儿子结点 if (Ew + r > bestw && i < n) Q.Add(Ew); // 可能含最优解 Q.Delete(Ew); // 取下一扩展结点

解答：斜线标识的部分完成的功能为：提前更新bestw值；

这样做可以尽早的进行对右子树的剪枝。具体为：算法Maxloading初始时将bestw设置为0，直到搜索到第一个叶结点时才更新bestw。因此在算法搜索到第一个叶子结点之前，总有bestw=0，r>0 故Ew+r>bestw总是成立。也就是说，此时右子树测试不起作用。

为了使上述右子树测试尽早生效，应提早更新bestw。又知算法最终找到的最优值是所求问题的子集树中所有可行结点相应重量的最大值。而结点所相应得重量仅在搜索进入左子树是增加，因此，可以在算法每一次进入左子树时更新bestw的值。

7. 最长公共子序列问题：给定2个序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}，找出X和Y的最长公共子序列。

由最长公共子序列问题的最优子结构性质建立子问题最优值的递归关系。用c[i][j]记录序列Xi和Yj的最长公共子序列的长度。其中，

Xi={x1,x2,…,xi}；Yj={y1,y2,…,yj}。当i=0或j=0时，空序列是Xi和Yj的最长公共子序列。故此时C[i][j]=0。其它情况下，由最优子结构性质可建立

?0?c[i?1][j?1]?1递归关系如下：c[i][j]???max{c[i][j?1],c[i?1][j]}?i?0,j?0i,j?0;xi?yi,j?0;xi?yjj

在程序中，b[i][j]记录C[i][j]的值是由哪一个子问题的解得到的。

（1） 请填写程序中的空格，以使函数LCSLength完成计算最优值的功能。

void LCSLength(int m，int n，char *x，char *y，int **c，int **b) { int i，j; for (i = 1; i <= m; i++) c[i][0] = 0; for (i = 1; i <= n; i++) c[0][i] = 0; for (i = 1; i <= m; i++) for (j = 1; j <= n; j++) { if (x[i]==y[j]) { c[i][j]=c[i-1][j-1]+1; b[i][j]=1;} else if (c[i-1][j]>=c[i][j-1]) { c[i][j]=c[i-1][j]; b[i][j]=2;} else { c[i][j]=c[i][j-1]; b[i][j]=3; }

（2） 函数LCS实现根据b的内容打印出Xi和Yj的最长公共子序列。请填

写程序中的空格，以使函数LCS完成构造最长公共子序列的功能（请将b[i][j]的取值与（1）中您填写的取值对应，否则视为错误）。

8.对下面的递归算法，写出调用f(4)的执行结果。

void f(int k) { if( k>0 ) { printf(\ f(k-1); f(k-1); void LCS(int i，int j，char *x，int **b) { if (i ==0 || j==0) return; if (b[i][j]== 1) { LCS(i-1，j-1，x，b); cout<

3.某一问题可用动态规划算法求解的显著特征是____________________________________。

4.若序列X={B,C,A,D,B,C,D}，Y={A,C,B,A,B,D,C,D}，请给出序列X和Y的一个最长公共子序列_____________________________。

5.用回溯法解问题时，应明确定义问题的解空间，问题的解空间至少应包含___________。

6.动态规划算法的基本思想是将待求解问题分解成若干____________，先求解___________，然后从这些____________的解得到原问题的解。 7.以深度优先方式系统搜索问题解的算法称为_____________。

8.0-1背包问题的回溯算法所需的计算时间为_____________,用动态规划算法所需的计算时间为____________。

9.动态规划算法的两个基本要素是___________和___________。 10.二分搜索算法是利用_______________实现的算法。 二、综合题（50分）

1.写出设计动态规划算法的主要步骤。

2.流水作业调度问题的johnson算法的思想。

3.若n=4，在机器M1和M2上加工作业i所需的时间分别为ai和bi，且(a1,a2,a3,a4)=(4,5,12,10)，(b1,b2,b3,b4)=(8,2,15,9)求4个作业的最优调度方案，并计算最优值。

4.使用回溯法解0/1背包问题：n=3，C=9，V={6,10,3}，W={3,4,4},其解空间有长度为3的0-1向量组成，要求用一棵完全二叉树表示其解空间（从根出发，左1右0），并画出其解空间树，计算其最优值及最优解。 5.设S=｛X1，X2，···，Xn｝是严格递增的有序集，利用二叉树的结点来存储S中的元素，在表示S的二叉搜索树中搜索一个元素X，返回的结果有两种情形，（1）在二叉搜索树的内结点中找到X=Xi，其概率为bi。（2）在二叉搜索树的叶结点中确定X∈（Xi，Xi+1），其概率为ai。在表示S的二叉搜索树T中，设存储元素Xi的结点深度为Ci；叶结点（Xi，Xi+1）的结点深度为di，则二叉搜索树T的平均路长p为多少？假设二叉搜索树T[i][j]=｛Xi，Xi+1，···，Xj｝最优值为m[i][j]，W[i][j]= ai-1+bi+···+bj+aj，则m[i][j](1<=i<=j<=n)递归关系表达式为什么？ 6.描述0-1背包问题。 三、简答题（30分） 1.流水作业调度中，已知有n个作业，机器M1和M2上加工作业i所需的时间分别为ai和bi，请写出流水作业调度问题的johnson法则中对ai和bi的排序算法。（函数名可写为sort(s,n)）

2.最优二叉搜索树问题的动态规划算法（设函数名binarysearchtree)） 答案： 一、填空

1．确定性 有穷性 可行性 0个或多个输入 一个或多个输出 2.时间复杂性 空间复杂性 时间复杂度高低 3. 该问题具有最优子结构性质 4.{BABCD}或{CABCD}或{CADCD｝ 5.一个（最优）解

6.子问题 子问题 子问题 7.回溯法

8. o(n*2n) o(min{nc,2n}) 9.最优子结构 重叠子问题

本文来源：https://www.bwwdw.com/article/i6k.html