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

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

一、选择题

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(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)(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.

void backtrack(int t)

{

B.

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]);

}

}

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);

}

}

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);

}

}

D.

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);

}

}

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.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 n 有： 0f(n)

cg(n) }；

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

f(n) }；

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

有： 0f(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有： 0f(n)

cg(n) }；

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

f(n) }；

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

有： 0f(n)

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

c>0

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

二、填空题

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

2

）。O ( n )

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;j<=n;j++){

thissum+=a[j];

if(thissum>sum){

sum=thissum;

besti=i;

bestj=j;

}

}

}

return sum;

}

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

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

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

i1234567891011

S[i]130535688212

f[i]4567891011121314

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

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

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

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

6.用回溯法解题的一个显著特征是在搜索过程中动态产生问题的解空间。在任

何时刻，算法只保存从根结点到当前扩展结点的路径。如果解空间树

中从根结点到叶结点的最长路径的长度为 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 && w[i] <= cleft) {

cleft -= w[i];

b += p[i];

i++;

}

//装满背包

if (i <= n)

return b;

（b += p[i]/w[i] * cleft） ; }

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

n m 的方格阵列，扩展每个结点需O(1)的时间，L为最短布线路径的长度，则算法共耗时 ( O(mn) ) ，构造相应的最短距离需要（ O(L) ）时间。

for (int i = 0; i < NumOfNbrs; i++) {

nbr.row = here.row + offset[i].row;

nbr.col = here.col + offset[i].col;

if (grid[nbr.row][nbr.col] == 0) {

//该方格未标记

grid[nbr.row][nbr.col]

= grid[here.row][here.col] + 1;

if ((nbr.row == finish.row) &&

(nbr.col == finish.col)) break; // 完成布线 Q.Add(nbr);}

}

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

Bool Color::OK(int k)

{//

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

if((a[k][j]= =1)&&(x[j]= =x[k])) return false;

return true;

}

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

三、

证明题

1.

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

解阀值 n0=1，且 adhoc 解规模为 1 的问题耗费 1 个单位时间。再设将原问题

分解为 k 个子问题以及用 merge 将 k 个子问题的解合并为原问题的解需用 f(n)

个单位时间。用 T(n) 表示该分治法解规模为 |P|=n 的问题所需的计算时间，

O(1) n 1 则有： T (n)

f (n) n

1

kT( n / m)

log

log m n 1

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

k

k j f ( n / m j )

T (n) n

j 0

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

2. 举反例证明 0/1 背包问题若使用的算法是按照

i

i 的非递减次序考虑选择的

p /w

物品，即只要正在被考虑的物品装得进就装入背包， 则此方法不一定能得到最优解（此题说明 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) 。

所有 类似地，对于任意

n n2，有 g1(n)

g1(n)

c2g(n)

。

O(g(n))

，存在正常数

c2 和自然数

n2，使得对

令 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) 是最优装载问题的一个最优解。又设 k min{ i | x i1}。如果给定的最优装载问题有解，

1 i n

则有 1 k n 。）

证明：

四、解答题

1.机器调度问题。

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

时间范围。两个任务 i ，j 重叠指两个任务的时间范围区间有重叠，而并非指 i ，

j 的起点或终点重合。例如：区间 [1，4]与区间 [2， 4]重叠，而与 [4， 7] 不重叠。

一个可行的任务分配是指在分配中没有两件重叠的任务分配给同一台机器。因此，

在可行的分配中每台机器在任何时刻最多只处理一个任务。

最优分配是指使用的机器最少的可行分配方案。

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

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

f (n)bf (n1)g(n)

2. 已知非齐次递归方程：，其中，b、c是常数，

f (0)c

n

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

i 1

现有 Hanoi 塔问题的递归方程为：

h(n) 2h(n1) 1

h(1)，求 h(n)的非递归表

1

达式。

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

n1

h(n)cb n 1b n 1i g(i)

i1

2n 12n 2... 22 2 1

2n1

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

问题的描述：给定带权有向图（如下图所示）G =(V,E) ，其中每条边的权是非负实数。另外，还给定V 中的一个顶点，称为源。现在要计算从源到所有其它

各顶点的最短路长度。这里路的长度是指路上各边权之和。这个问题通常称为单源最短路径问题。

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

迭代S u dist[2]dist[3]dist[4]dist[5]

初始{1}-10maxint30100

1

2

3

4

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

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

n

w i c1c2

其中集装箱 i 的重量为 wi ，且i 1。装载问题要求确定是否有一个合理

的装载方案可将这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。其它情况下，由最优子结构性质可建立

0i0, j0

递归关系如下：c[ i ][ j ]c[ i1][ j1]1i , j0; x i y j

max{ c[ i ][ j1], c[i1][ j ]}i , j0; x i y j

在程序中， 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）中您填写的取值对应，否则视为错误）。

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<

}

else if (b[i][j]== 2) LCS( i-1

，j，x，b);

else LCS(i ，j-1 ，x，b);

}

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

void f(int k)

{ if( k>0 )

{ printf("%d\n ",k);

f(k-1);

f(k-1);

}

}

一、填空题（20 分）

1.一个算法就是一个有穷规则的集合，其中之规则规定了解决某一特殊类型问题的

一系列运算，此外，算法还应具有以下五个重要特

性:_________,________,________,__________,__________ 。

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

是______________________。

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

。

Y 的一4. 若序列 X={B,C,A,D,B,C,D} ，Y={A,C,B,A,B,D,C,D}，请给出序列X 和

个最长公共子序列。

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=｛X1，X2，···，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] ， a i-1 +b i +··· +b j +a j，则 m[i][j](1<=i<=j<=n) 递归关系表达式为什么？ W[i][j]=

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*2 n) o(min{nc,2 n })

9.最优子结构重叠子问题

10.动态规划法

二、综合题

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

法描述；④构造最优解；

2.①令 N1={i|a i =b i } ；②将 N1中作业按 a i的非减序排序得到 N1’，

将 N2中作业按 b i的非增序排序得到 N2’；③ N1’中作业接 N2’中作业就构成了满足 Johnson 法则的最优调度。

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

N1’={1 ，3} ， N2’={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)}。

解空间树为：

1A

B C

1

010 D E F G

1

10110

00

H I J K L M N O

该问题的最优值为： 16最优解为：（1，1，0）

n n

5. 二叉树 T 的平均路长 P=bi * (1 Ci) +aj * dj

i 1j0

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

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++)//-----选择排序

{

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);

}

}

记下当前第一个 b

l=i;//-----的下标

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、计算机的资源最重要的是和资源。因而，算法的复杂性有

和之分。

n2

5、f(n)= 6 ×2 +n

，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]

非 0 值, 否则值为 0。

存储皇后位置, 若第i行第j列放有皇后, 则A[i][j]为(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；

else3；

3、Hanoi 算法

Hanoi(n,a,b,c)

if （ n==1）else

{2

31

；

；

；

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 vertex3

do4

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

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

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

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

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

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

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

◎框起。

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

k

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

①每个选手必须与其他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(RandomAccess Machine) ；随机存取存储程

序机 RASP(Random Access Stored Program Machine) ；图灵机 (Turing Machine)

3.算法效率

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

5．2n

6．最好局部最优选择