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

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

一、选择题

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

A. 贪心算法

B. 分支限界法

C.分治法

D. 动态规划算法

2.Hanoi塔问题如下图所示。现要求将塔座A上的的所有圆盘移到塔座B上，并仍按同样顺序叠置。移动圆盘时遵守Hanoi塔问题的移动规则。由此设计出解

Hanoi塔问题的递归算法正确的为：（B）

Hanoi塔

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(min{f(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. 深度优先

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

A.

B.

C.

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

13. N P类语言在图灵机下的定义为（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) }；

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

有：0 ≤f(n)

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

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，存在正数和n

>0使得对所有n≥n0

有：0 ≤f(n)

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

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

二、填空题

1.下面程序段的所需要的计算时间为（2

O(n)）。Array

2.有11个待安排的活动，它们具有下表所示的开始时间与结束时间，如果

以贪心算法求解这些活动的最优安排（即为活动安排问题：在所给的活

动集合中选出最大的相容活动子集合），得到的最大相容活动子集合为活动（ {1，4，8，11} ）。

3. 所谓贪心选择性质是指（所求问题的整体最优解可以通过一系列局部最

优的选择，即贪心选择来达到）。

4. 所谓最优子结构性质是指（问题的最优解包含了其子问题的最优解）。

5. 回溯法是指（具有限界函数的深度优先生成法）。

6. 用回溯法解题的一个显著特征是在搜索过程中动态产生问题的解空间。在任何时刻，算法只保存从根结点到当前扩展结点的路径。如果解空间树 中从根结点到叶结点的最长路径的长度为h(n)，则回溯法所需的计算空间通常为（O(h(n))）。

7. 回溯法的算法框架按照问题的解空间一般分为（子集树）算法框架与（排列树）算法框架。

8. 用回溯法解0/1背包问题时，该问题的解空间结构为（子集树）结构。 9.用回溯法解批处理作业调度问题时，该问题的解空间结构为（排列树）结构。

10.用回溯法解0/1背包问题时，计算结点的上界的函数如下所示，请在空格中填入合适的内容：

14

13

12

11

10

9

8

7

6

5

4

f[i]

12 2 8 8 6 5 3 5 0 3 1 S[i] 11 10 9 8 7 6 5 4 3 2 1 i

11. 用回溯法解布线问题时，求最优解的主要程序段如下。如果布线区域划分为

n m 的方格阵列，扩展每个结点需O(1)的时间，L 为最短布线路径的长度，则

算法共耗时 ( O(mn) )，构造相应的最短距离需要（O(L)）时间。 12. 用回溯法解图的m 着色问题时，使用下面的函数OK 检查当前扩展结点的每一个儿子所相应的颜色的可用性，则需耗时（渐进时间上限）（O （mn ））。

13. 旅行售货员问题的解空间树是（排列树）。

三、证明题

1. 一个分治法将规模为n的问题分成k个规模为n／m的子问题去解。设分

解阀值n0=1，且adhoc解规模为1的问题耗费1个单位时间。再设将原问题分解为k个子问题以及用merge将k个子问题的解合并为原问题的解需用f(n)个单位时间。用T(n)表示该分治法解规模为|P|=n的问题所需的计算时间，

则有：

(1)1 ()

(/)()1

O n

T n

kT n m f n n

=

?

=?

+>

?

通过迭代法求得T（n）的显式表达式为：

log1

log

()(/)

n

m

k j j

m

j

T n n k f n m

-

=

=+∑

试证明T（n）的显式表达式的正确性。

2. 举反例证明0/1背包问题若使用的算法是按照p i/w i的非递减次序考虑选择的物品，即只要正在被考虑的物品装得进就装入背包，则此方法不一定能得到最优解（此题说明0/1背包问题与背包问题的不同）。

证明：举例如：p={7,4,4},w={3,2,2},c=4时，由于7/3最大，若按题目要求的方法，只能取第一个，收益是7。而此实例的最大的收益应该是8，取第2，3 个。

3. 求证：O(f(n))+O(g(n)) = O(max{f(n),g(n)}) 。

证明：对于任意f1(n)∈O(f(n)) ，存在正常数c1和自然数n1，使得对所有n≥n1，有f1(n)≤c1f(n) 。

类似地，对于任意g1(n) ∈O(g(n)) ，存在正常数c2和自然数n2，使得对所有n≥n2，有g1(n) ≤c2g(n) 。

令c3=max{c1, c2}，n3 =max{n1, n2}，h(n)= max{f(n),g(n)} 。

则对所有的n ≥n3，有

f1(n) +g1(n) ≤c1f(n) + c2g(n)

≤c3f(n) + c3g(n)

= c3(f(n) + g(n))

≤c32 max{f(n),g(n)}

= 2c3h(n) = O(max{f(n),g(n)}) .

4. 求证最优装载问题具有贪心选择性质。

（最优装载问题：有一批集装箱要装上一艘载重量为c 的轮船。其中集装箱i 的重量为Wi 。最优装载问题要求确定在装载体积不受限制的情况下，将尽可能多的集装箱装上轮船。 设集装箱已依其重量从小到大排序，(x 1,x 2,…,x n )是最优装载问题的一个最优解。又设1min{|1}i i n

k i x ≤≤== 。如果给定的最优装载问题有解，

则有1k n ≤≤。）

证明： 四、

解答题

1. 机器调度问题。

问题描述：现在有n 件任务和无限多台的机器，任务可以在机器上得到处理。每件任务的开始时间为s i ，完成时间为f i ，s i

问题实例：若任务占用的时间范围是{[1，4]，[2，5]，[4，5]，[2，6]，[4，7]}，则按时完成所有任务最少需要几台机器？（提示：使用贪心算法）

画出工作在对应的机器上的分配情况。

2. 已知非齐次递归方程：f (n)bf (n 1)g(n)f (0)c =-+??=? ，其中，b 、c 是常数，

g(n)是n 的某一个函数。则f(n)的非递归表达式为：n

n

n i i 1f (n)cb b g(i)-==+∑。

现有Hanoi 塔问题的递归方程为：h(n)2h(n 1)1

h(1)1=-+??=? ，求h(n)的非递归表

达式。

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

n 1

n 1

n 1i i 1

n 1n 22n h(n)cb

b g(i)

22 (22121)

----=--=+=+++++=-∑

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

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

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

4

3 2 1 100 30 maxint

10 - {1} 初始 dist[5] dist[4] dist[3] dist[2] u S 迭代

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

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

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

12

1

n

i

i

w c c

=

≤+

∑

。装载问题要求确定是否有一个合理

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

解答：斜线标识的部分完成的功能为：提前更新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。其它情况下，由最优子结构性质可建立

递归关系如下：

00,0 [][][1][1]1,0;

max{[][1],[1][]},0;

i j

i j

i j

c i j c i j i j x y

c i j c i j i j x y

?==

?

=--+>=

?

?-->≠

?

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

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

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

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

一、填空题

1.的一系列运算，此外，算法还应具有以下五个重要特性:_________,________,________,__________,__________。

2.算法的复杂性有_____________和___________之分，衡量一个算法好坏的标准是______________________。

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所需的时间分别为a

i 和b

i

，且

(a

1,a

2

,a

3

,a

4

)=(4,5,12,10)，(b

1

,b

2

,b

3

,b

4

)=(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=｛X

1，X

2

，···，X

n

｝是严格递增的有序集，利用二叉树的结点来存储S中

的元素，在表示S的二叉搜索树中搜索一个元素X，返回的结果有两种情形，（1）

在二叉搜索树的内结点中找到X=X

i ，其概率为b

i

。（2）在二叉搜索树的叶结点中

确定X∈（X

i ，X

i+1

），其概率为a

i

。在表示S的二叉搜索树T中，设存储元素X

i

的结点深度为C

i ；叶结点（X

i

，X

i+1

）的结点深度为d

i

，则二叉搜索树T的平均路

长p为多少？假设二叉搜索树T[i][j]=｛X

i ，X

i+1

，···，X

j

｝最优值为m[i][j]，

W[i][j]= a

i-1+b

i

+···+b

j

+a

j

，则m[i][j](1<=i<=j<=n)递归关系表达式为什么？

6.描述0-1背包问题。

三、简答题（30分）

1.流水作业调度中，已知有n个作业，机器M1和M2上加工作业i所需的时间分

别为a

i 和b

i

，请写出流水作业调度问题的johnson法则中对a

i

和b

i

的排序算法。

（函数名可写为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.最优子结构重叠子问题

10.动态规划法 二、综合题

1.①问题具有最优子结构性质；②构造最优值的递归关系表达式； ③最优值的算法描述；④构造最优解；

2. ①令N 1={i|a i =b i }；②将N 1中作业按a i 的非减序排序得到N 1’，将N 2中作业按b i 的非增序排序得到N 2’；③N 1’中作业接N 2’中作业就构成了满足Johnson 法则的最优调度。

3.步骤为：N1={1，3}，N2={2，4}；

N 1’={1，3}， N 2’={4，2}； 最优值为：38

4.解空间为{(0,0,0),(0,1,0),(0,0,1),(1,0,0),(0,1,1),(1,0,1), (1,1,0),(1,1,1)}。 解空间树为：

该问题的最优值为：16 最优解为：（1，1，0） 5.二叉树T 的平均路长P=∑=+n i 1

Ci)(1*bi +∑=n

j 0

dj *aj

{

m[i][j]=0 (i>j)

6.已知一个背包的容量为C ，有n 件物品，物品i 的重量为W i ，价值为V i ，求应如何选择装入背包中的物品，使得装入背包中物品的总价值最大。 三、简答题 1.

void sort(flowjope s[],int n) {

int i,k,j,l;

for(i=1;i<=n-1;i++)//-----选择排序

m[i][j]=W[i][j]+min{m[i][k]+m[k+1][j]} (1<=i<=j<=n,m[i][i-1]=0)

{

k=i;

while(k<=n&&s[k].tag!=0) k++;

，跳出

if(k>n) break;//-----没有a

i

else

{

for(j=k+1;j<=n;j++)

if(s[j].tag==0)

if(s[k].a>s[j].a) k=j;

swap(s[i].index,s[k].index);

swap(s[i].tag,s[k].tag);

}

}

的下标

l=i;//-----记下当前第一个b

i

for(i=l;i<=n-1;i++)

{

k=i;

for(j=k+1;j<=n;j++)

if(s[k].b

swap(s[i].index,s[k].index); //-----只移动index和tag

swap(s[i].tag,s[k].tag);

}

}

2.

void binarysearchtree(int a[],int b[],int n,int **m,int **s,int **w) {

int i,j,k,t,l;

for(i=1;i<=n+1;i++)

{

w[i][i-1]=a[i-1];

m[i][i-1]=0;

}

for(l=0;l<=n-1;l++)//----l是下标j-i的差

for(i=1;i<=n-l;i++)

{

j=i+l;

w[i][j]=w[i][j-1]+a[j]+b[j];

m[i][j]=m[i][i-1]+m[i+1][j]+w[i][j];

s[i][j]=i;

for(k=i+1;k<=j;k++)

{

t=m[i][k-1]+m[k+1][j]+w[i][j];

if(t

{

m[i][j]=t;

s[i][j]=k;

}

}

}

}

一、填空题（本题15分，每小题1分）

1、算法就是一组有穷的，它们规定了解决某一特定类型问题

的。

2、在进行问题的计算复杂性分析之前，首先必须建立求解问题所用的计算模

型。3个基本计算模型是、、。

3、算法的复杂性是的度量，是评价算法优劣的重要依据。

4、计算机的资源最重要的是和资源。因而，算法的复杂性有

和之分。

5、f(n)= 6×2n+n2，f(n)的渐进性态f(n)= O( )

6、贪心算法总是做出在当前看来的选择。也就是说贪心算法并不从整

体最优考虑，它所做出的选择只是在某种意义上的。

7、许多可以用贪心算法求解的问题一般具有2个重要的性质：性质

和性质。

二、简答题（本题25分，每小题5分）

1、简单描述分治法的基本思想。

2、简述动态规划方法所运用的最优化原理。

3、何谓最优子结构性质？

4、简单描述回溯法基本思想。

5、何谓P、NP、NPC问题

三、算法填空（本题20分，每小题5分）

1、n后问题回溯算法

(1)用二维数组A[N][N]存储皇后位置,若第i行第j列放有皇后,则A[i][j]为非0值,否则值为0。

(2)分别用一维数组M[N]、L[2*N-1]、R[2*N-1]表示竖列、左斜线、右斜线是否放有棋子，有则值为1,否则值为0。

for(j=0;j

if( 1 ) /*安全检查*/

{ A[i][j]=i+1; /*放皇后*/

2 ；

if(i==N-1) 输出结果；

else 3 ；; /*试探下一行*/

4 ； /*去皇后*/

5 ；;

}

2、数塔问题。有形如下图所示的数塔，从顶部出发，在每一结点可以选择向左走或是向右走，一起走到底层，要求找出一条路径，使路径上的值最大。for(r=n-2;r>=0;r--) //自底向上递归计算

for(c=0; 1 ;c++)

if( t[r+1][c]>t[r+1][c+1]) 2 ；

else 3 ；

3、Hanoi算法

Hanoi(n,a,b,c)

if （n==1） 1 ；

else

{ 2 ；

3 ；

Hanoi(n-1,b, a, c);

}

4、Dijkstra算法求单源最短路径

d[u]:s到u的距离 p[u]:记录前一节点信息

Init-single-source(G,s)

for each vertex v∈V[G]

do { d[v]=∞; 1 }

d[s]=0

Relax(u,v,w)

if d[v]>d[u]+w(u,v)

then { d[v]=d[u]+w[u,v];

2

}

dijkstra(G,w,s)

1. Init-single-source(G,s)

2. S=Φ

3. Q=V[G]

4.while Q<> Φ

do u=min(Q)

S=S∪{u}

for each vertex 3

do 4

四、算法理解题（本题10分）

根据优先队列式分支限界法，求

下图中从v1点到v9点的单源最

短路径，请画出求得最优解的解

空间树。要求中间被舍弃的结点

用×标记，获得中间解的结点用

单圆圈○框起，最优解用双圆圈

◎框起。

五、算法理解题（本题5分）

设有n=2k个运动员要进行循环赛，现设计一个满足以下要求的比赛日程表：

①每个选手必须与其他n-1名选手比赛各一次；

②每个选手一天至多只能赛一次；

③循环赛要在最短时间内完成。

（1）如果n=2k，循环赛最少需要进行几天；

（2）当n=23=8时，请画出循环赛日程表。

六、算法设计题（本题15分）

分别用贪心算法、动态规划法、回溯法设计0-1背包问题。要求：说明所使用的算法策略；写出算法实现的主要步骤；分析算法的时间。

七、算法设计题（本题10分）

通过键盘输入一个高精度的正整数n(n的有效位数≤240)，去掉其中任意s 个数字后，剩下的数字按原左右次序将组成一个新的正整数。编程对给定的n 和s，寻找一种方案，使得剩下的数字组成的新数最小。

【样例输入】

178543

S=4

【样例输出】

13

一、填空题（本题15分，每小题1分）

1．规则一系列运算

2. 随机存取机RAM(Random Access Machine)；随机存取存储程序机RASP(Random Access Stored Program Machine)；图灵机(Turing Machine)

3. 算法效率

4. 时间、空间、时间复杂度、空间复杂度

5．2n

6．最好局部最优选择