《算法分析与设计》期末考试复习题纲(完整版)

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

一、选择题

1. 算法必须具备输入、输出和（ D ）等4个特性。

A．可行性和安全性 B．确定性和易读性

C．有穷性和安全性 D．有穷性和确定性

2. 算法分析中，记号O表示（ B ），记号Ω表示（ A ）

A.渐进下界 B.渐进上界

C.非紧上界 D.紧渐进界

3. 假设某算法在输入规模为n时的计算时间为T(n)=3*2^n。在某台计算机上实现并

完成概算法的时间为t秒。现有另一台计算机，其运行速度为第一台的64倍，那

么在这台新机器上用同一算法在t秒内能解输入规模为多大的问题？（ B ）解

题方法：3*2^n*64=3*2^x

A．n+8 B．n+6

C．n+7 D．n+5

4. 设问题规模为N时，某递归算法的时间复杂度记为T(N)，已知T(1)=1，

T(N)=2T(N/2)+N/2，用O表示的时间复杂度为（ C ）。

A．O(logN) B．O(N)

C．O(NlogN) D．O(N²logN)

5. 直接或间接调用自身的算法称为（ B ）。

A．贪心算法 B．递归算法

C．迭代算法 D．回溯法

6. Fibonacci数列中，第4个和第11个数分别是（ D ）。

A．5，89 B．3，89

C．5，144 D．3，144

7. 在有8个顶点的凸多边形的三角剖分中，恰有（ B ）。

A．6条弦和7个三角形 B．5条弦和6个三角形

C．6条弦和6个三角形 D．5条弦和5个三角形

8. 一个问题可用动态规划算法或贪心算法求解的关键特征是问题的（ B ）。

A．重叠子问题 B．最优子结构性质

C．贪心选择性质 D．定义最优解

9. 下列哪个问题不用贪心法求解（ C ）。

A．哈夫曼编码问题 B．单源最短路径问题

C．最大团问题 D．最小生成树问题

10. 下列算法中通常以自底向上的方式求解最优解的是（ B ）。

A．备忘录法 B．动态规划法

C．贪心法 D．回溯法

11. 下列算法中不能解决0/1背包问题的是（ A ）。

A．贪心法 B．动态规划

C．回溯法 D．分支限界法

12. 下列哪个问题可以用贪心算法求解（ D ）。

1

A．LCS问题 B．批处理作业问题

C．0-1背包问题 D．哈夫曼编码问题

13. 用回溯法求解最优装载问题时，若待选物品为m种，则该问题的解空间树的结点

个数为（ ）。

m+1

A．m! B．2

m+1m

C．2-1 D．2

14. 二分搜索算法是利用（ A ）实现的算法。

A．分治策略 B．动态规划法

C．贪心法 D．回溯法

15. 下列不是动态规划算法基本步骤的是（ B ）。P44

A．找出最优解的性质 B．构造最优解

C．算出最优解(应该是最优值) D．定义最优解

16. 下面问题（ B ）不能使用贪心法解决。

A．单源最短路径问题 B．N皇后问题

C．最小花费生成树问题 D．背包问题

17. 使用二分搜索算法在n个有序元素表中搜索一个特定元素，在最好情况和最坏情况

下搜索的时间复杂性分别为（ A ）。P17

A．O(1)，O(logn) B．O(n)，O(logn)

C．O(1)，O(nlogn) D．O(n)，O(nlogn)

18. 优先队列式分支限界法选取扩展结点的原则是（ C ）。P162

A．先进先出 B．后进先出

C．结点的优先级 D．随机

19. 下面不是分支界限法搜索方式的是（ D ）。P161

A．广度优先 B．最小耗费优先

C．最大效益优先 D．深度优先

20. 分支限界法解最大团问题时，活结点表的组织形式是（ B ）。

A．最小堆 B．最大堆

C．栈 D．数组

21. 下列关于计算机算法的描述不正确的是（ C ）。P1

A．算法是指解决问题的一种方法或一个过程

B．算法是若干指令的有穷序列

C. 算法必须要有输入和输出

D．算法是编程的思想

22. 下列关于凸多边形最优三角剖分问题描述不正确的是（ A ）。

A．n+1个矩阵连乘的完全加括号和n个点的凸多边形的三角剖分对应

B．在有n个顶点的凸多边形的三角剖分中，恰有n-3条弦

C．该问题可以用动态规划法来求解

D．在有n个顶点的凸多边形的三角剖分中，恰有n-2个三角形

23. 动态规划法求解问题的基本步骤不包括（ C ）。P44

A．递归地定义最优值

B．分析最优解的性质，并刻画其结构特征

C．根据计算最优值时得到的信息，构造最优解 (可以省去的)

D．以自底向上的方式计算出最优值

24. 分治法所能解决的问题应具有的关键特征是（ C ）。P16

2

A．该问题的规模缩小到一定的程度就可以容易地解决

B．该问题可以分解为若干个规模较小的相同问题

C．利用该问题分解出的子问题的解可以合并为该问题的解

D．该问题所分解出的各个子问题是相互独立的

25. 下列关于回溯法的描述不正确的是（ D ）。P114

A．回溯法也称为试探法

B．回溯法有“通用解题法”之称

C．回溯法是一种能避免不必要搜索的穷举式搜索法

D．用回溯法对解空间作深度优先搜索时只能用递归方法实现

26. 常见的两种分支限界法为（ D ）。P161

A. 广度优先分支限界法与深度优先分支限界法；

B. 队列式（FIFO）分支限界法与堆栈式分支限界法；

C. 排列树法与子集树法；

D. 队列式（FIFO）分支限界法与优先队列式分支限界法；

二、填空题

1. f(n)=3n+10的渐近性态f(n)= O( n )，

g(n)=10log3的渐近性态g(n)= O( n )。

2. 一个“好”的算法应具有正确性、 可读性 、 健壮性 和高效率和

低存储量需求等特性。

3. 算法的时间复杂性函数表示为 C=F(N,I,A) ，分析算法复杂性的目的在于比较

求解同意问题的两个不同算法的效率 的效率。

4. 构成递归式的两个基本要素是 递归的边界条件 和 递归的定义 。

5. 单源最短路径问题可用 分支限界法 和 贪心算法 求解。

6. 用分治法实现快速排序算法时，最好情况下的时间复杂性为 O(nlogn) ，最坏情况下

的时间复杂性为 O(n^2) ，该算法所需的时间与 运行时间 和

划分 两方面因素有关。P26

7. 0-1背包问题的解空间树为 完全二叉 树；n后问题的解空间树为 排列 树；

8. 常见的分支限界法有队列式（FIFO）分支限界法和优先队列式分支限界法。

9. 回溯法搜索解空间树时常用的两种剪枝函数为 约束函数 和 剪枝函数 。

10. 分支限界法解最大团问题时，活结点表的组织形式是 最大堆 ；分支限界法

解单源最短路径问题时，活结点表的组织形式是 最小堆 。

三、算法填空题

1. 递归求解Hanoi塔问题/阶乘问题。

例1 :阶乘函数n! P12

阶乘的非递归方式定义：

n!n(n1)(n2)21

试写出阶乖的递归式及算法。

递归式为：



1

n



0

边界条件

n!





n(n1)!n0

3

n

22

递归方程

递归算法：

int factorial (int n)

{ if (n==0) return 1; 递归出口

return n * factorial (n-1); 递归调用

}

例2:用递归技术求解Hanoi塔问题,Hanoi塔的递归算法。P15

其中Hanoi (int n, int a, int c, int b)表示将塔座A上的n个盘子移至塔座C，以塔座B为辅助。

Move(a,c)表示将塔座a上编号为n的圆盘移至塔座c上。

void hanoi (int n, int a, int c, int b)

{

if (n > 0)

{

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

move(a,c);

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

}

}

2. 用分治法求解快速排序问题。

快速排序算法 P25 、作业、课件第2章（2）42页-50页

template

void QuickSort (Type a[], int p, int r)

{

if (p

int q=Partition(a,p,r);

QuickSort (a,p,q-1);

QuickSort (a,q+1,r)；

}

}

4

Partition函数的具体实现

template

int Partition (Type a[], int p, int r)

{

int i = p, j = r + 1;

Type x=a[p];

// 将< x的元素交换到左边区域

// 将> x的元素交换到右边区域

while (true) {

while (a[++i]

while (a[- -j] >x);

if (i >= j) break;

Swap(a[i], a[j]);

}

a[p] = a[j];

a[j] = x;

return j;

}

3. 用贪心算法求解最优装载问题。

最优装载问题 P95 课件第4章(2)第3-8页

template

void Loading(int x[], Type w[], Type c, int n)

{

int *t = new int [n+1];

Sort(w, t, n);

for (int i = 1; i <= n; i++) x[i] = 0;

for (int j = 1; j <= n && w[t[j]] <= c; j++)

{x[t[i]] = 1; c -= w[t[j]];}

}

5

4. 用回溯法求解0-1背包/批处理作业调度 /最大团问题，要会画解空间树。

例1：用回溯法求解0-1背包 P133课件第5章(2)第24-38页

template

class Knap

{

private:

Typep Bound(int i); //计算上界

void Backtrack(int i);

Typew c; //背包容量

int n; //物品数

Typew *w; //物品重量数组

Typep *p; //物品价值数组

Typew cw; //当前重量

Typep cp; //当前价值

Typep bestp; //当前最优价值

};

void Knap::Backtrack(int i)

{ if(i>n) { bestp=cp; return; }

if(cw+w[i]<=c) //进入左子树

{ cw+=w[i];

cp+=p[i];

Backtrack(i+1);

cw-=w[i];

cp-=p[i]; }

if(Bound(i+1)>bestp) //进入右子树

Backtrack(i+1);

}

Typep Knap::Bound(int i)

{

Typew cleft=c-cw; //剩余的背包容量

Typep b=cp; //b为当前价值

//依次装入单位重量价值高的整个物品

6

while(i<=n&&w[i]<=cleft)

{ cleft-=w[i]; b+=p[i]; i++; }

if(i<=n) //装入物品的一部分

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

return b; //返回上界

}

class Object //物品类

{

friend int Knapsack(int *,int *,int,int);

public:

int operator <(Object a) const

{

return (d>=a.d);

}

int ID; //物品编号

float d; //单位重量价值

};

Typep Knapsack( Typep p[],Typew w[],Typew c,int n)

{ //为Typep Knapsack初始化

Typew W=0; //总重量

Typep P=0; //总价值

Object* Q=new Object[n]; //创建物品数组，下标从0开始

for(int i=1;i<=n;i++) //初始物品数组数据

{ Q[i-1].ID=i;

Q[i-1].d=1.0*p[i]/w[i];

P+=p[i]; W+=w[i];

}

if(W<=c) //能装入所有物品

return P;

if(W<=c) //能装入所有物品

return P;

QuickSort(Q,0,n-1); //依物品单位重量价值非增排序

7

Knap K;

K.p=new Typep[n+1];

K.w=new Typew[n+1];

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

{ K.p[i]=p[Q[i-1].ID]; K.w[i]=w[Q[i-1].ID]; }

=0; =0; K.c=c;

K.n=n; =0; ack(1);

delete[] Q; delete[] K.w;

delete[] K.p; return ;

}

例2：批处理作业调度 课件第5章(2)P2-5问题描述,课本P125-127

解空间：排列树

算法描述：

class Flowshop

{

static int [][] m, // 各作业所需的处理时间

[] x, // 当前作业调度

[] bestx, // 当前最优作业调度

[] f2, // 机器2完成处理时间

f1, // 机器1完成处理时间

f, // 完成时间和

bestf, // 当前最优的完成时间和

n; // 作业数

static void Backtrack(int i)

{

if (i > n)

{ for (int j = 1; j <= n; j++) bestx[j] = x[j]; bestf = f; }

else

for (int j = i; j <= n; j++) {

f1+=m[x[j]][1];//第j个作业在第一台机器上所需时间

f2[i]=((f2[i-1]>f1)?f2[i-1]:f1)+m[x[j]][2];

f+=f2[i];

if (f < bestf) //约束函数

{ Swap(x[i], x[j]); Backtrack(i+1); Swap(x[i], x[j]);

f1 - =m[x[j]][1];

f - =f2[i];

}

}

8

}

例3：最大团问题，要会画解空间树。

class Clique

{

friend int MaxClique(int **,int [],int);

public:

void Print(); //输出最优解

private:

void Backtrack(int i);

int **a; //图G的邻接矩阵，下标从1开始

int n; //图G的顶点数

int *x; //当前解

int *bestx; //当前最优解

int cn; //当前团的顶点数

int bestn; //当前最大团的顶点数

};

void Clique::Backtrack(int i)

{ if(i>n)

{ for(int j=1;j<=n;j++) bestx[j]=x[j]; bestn=cn; return;}

//判断第i个顶点是否与已选顶点都有边相连

int OK=1;

for(int j=1;j

if(x[j]&&a[i][j]==0) //i与当前团中的顶点无边相连

{ OK=0; break; } //只要与当前团中一个顶点无边相连，则中止

if(OK) //进入左子树

9