算法设计与分析报告考试题(自测)

1.一个算法就是一个有穷规则的集合，其中之规则规定了解决某一特殊类型问题的一系列运算，此外，算法还应具有以下五个重要特性:_有穷性__,_确定性_,_可行性_,_ （0个或多个）输入__,_ （1个或多个）_输出_。

2.算法的复杂性有__时间复杂性__和__空间复杂性__之分，衡量一个

算法好坏的标准是__时间复杂度高低___。

3.某一问题可用动态规划算法求解的显著特征是___该问题具有最优

子结构性质___。

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

5.用回溯法解问题时，应明确定义问题的解空间，问题的解空间至少应包含_问题的一个（最优）解_。

6.动态规划算法的基本思想是将待求解问题分解成若干_子问题_，先求解_子问题__，然后从这些_子问题_的解得到原问题的解。

7.以深度优先方式系统搜索问题解的算法称为__回溯法__。

8.0-1背包问题的回溯算法所需的计算时间为__O（n2n）__,用动态规划算法所需的计算时间为_O（n）__。o(min{nc,2n})

9.动态规划算法的两个基本要素是_最优子结构_和_重叠子问题

___。

10.二分搜索算法是利用__动态规划法__实现的算法。

二、综合题（50分）

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

1、解：（1）找出最优解的性质，并刻画其结构特征；

（2）递归地定义最优值；

（3）以自底向上的方式计算出最优值；

（4）根据计算最优值时得到的信息，构造最优解。

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

③最优值的算法描述；④构造最优解

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

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

③N1’中作业接N2’中作业就构成了满足Johnson法则的最优调度。

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

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

N1’={1，3}， N2’={4，2}；

最优值为：38

4.使用回溯法解0/1背包问题：n=3（3种物品），C=9（背包的容量为9），V={6,10,3}（3种物品的价值分别为6,10,3），W={3,4,4}（3种物品的重量分别为3,4,4）,其解空间有长度为3的0-1向量组成，要求用一棵完全二叉树表示其解空间（从根出发，左1右0），并画出其解空间树，计算其最优值及最优解。

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=6+10 最优解为：（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]，W[i][j]= a i-1+

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

5、解：二叉树T的平均路长P=∑

=+

n

i1

Ci)

(1

*

bi+∑

=

n

j0

dj

*

aj

{

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

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

6、解：已知一个背包的容量为C，有n件物品，物品i的重量

为W i，价值为V i，求应如何选择装入背包中的物品，使得装入背包中

物品的总价值最大。

三、简答题（30分）

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

需的时间分别为a i和b i，请写出流水作业调度问题的johnson法则中

对a i和b i的排序算法。（函数名可写为sort(s,n)）

2.最优二叉搜索树问题的动态规划算法（设函数名binarysearchtree)）

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

答案：

一、填空

1．确定性有穷性可行性 0个或多个输入一个或多个输出

2.时间复杂性空间复杂性时间复杂度高低

3. 该问题具有最优子结构性质

4.{BABCD}或{CABCD}或{CADCD｝

5.一个（最优）解

6.子问题子问题子问题

7.回溯法

8. o(n*2n) o(min{nc,2n})

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}；

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 1Ci)(1*bi +∑=n

j 0

dj *aj

{

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

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

1.

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

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

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个基本计算模型是顺序结构随机存取机RAM、循环结构随机存取存储程序机RASP、条件结构图灵机TM。

3、算法的复杂性是时间资源和空间资源算法效率的度量，是

评价算法优劣的重要依据。

4、计算机的资源最重要的是时间和空间资源。因而，算法的

复杂性有时间复杂性和空间复杂性之分。

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

6、贪心算法总是做出在当前看来最优的选择。也就是说贪心算

法并不从整体最优考虑，它所做出的选择只是在某种意义上的局部最优选择。

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

最优子结构性质和贪心选择性质。

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

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

1、答：分治法的基本思想是将一个规模为n 的问题分解为k个规模较小的子问题，这些子问题相互独立且与原问题相同。递归地解这些子问题，然后将个子问题的解合并得到原问题的解。

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

2、答：在动态规划中，不管子问题以后是否被用到，只要它被计算过，就将其结果填入表中。

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

3、答：当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用动态规

划算法或贪心算法求解的关键特征。

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

4、答：回溯法是一个既带有系统性又带有跳跃性的搜索算法，用其解决问题时，应明确定义问题的解空间。确定解空间的组织结构后，回溯法从开始结点（根结点）出发，以深度优先方式搜索整个解空间。这个开始结点成为活结点，同时也成为当前的扩展结点。在当前扩展结点处，搜索向纵深方向移至一个新结点。这个新结点成为新的活结点，并成为当前的扩展结点。如果在当前扩展结点处不能在向纵深方向移动，则当前扩展结点就成为死结点。此时，应往回移动（回溯）至最近的活结点处，并使这个活结点成为当前扩展结点。回溯法以这种工作方式递归地在解空间中搜索，直至找到所要求的解或解空间中已无活结点为止。

5、何谓P、NP、NPC问题

5、答：P(Polynomial问题)：也即是多项式复杂程度的问题。NP就是Non-deterministic Polynomial的问题，也即是多项式复杂程度的非确定性问题。

NPC(NP Complete)问题，这种问题只有把解域里面的所有可能都穷举了之后才能得出答案，这样的问题是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．最好局部最优选择

7. 贪心选择最优子结构

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

6、分治法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题，

这些子问题互相独立且与原问题相同；对这k个子问题分别求解。如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止；将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。

7、“最优化原理”用数学化的语言来描述：假设为了解决某一优化问题，需

要依次作出n个决策D1，D2，…，Dn，如若这个决策序列是最优的，对于任何一个整数k，1 < k < n，不论前面k个决策是怎样的，以后的最优决策只取决于由前面决策所确定的当前状态，即以后的决策Dk+1，Dk+2，…，Dn也是最优的。

8、某个问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性

质。

9、回溯法的基本思想是在一棵含有问题全部可能解的状态空间树上进行深度

优先搜索，解为叶子结点。搜索过程中，每到达一个结点时，则判断该结点为根的子树是否含有问题的解，如果可以确定该子树中不含有问题的解，则放弃对该子树的搜索，退回到上层父结点，继续下一步深度优先搜索过程。在回溯法中，并不是先构造出整棵状态空间树，再进行搜索，而是在搜索过程，逐步构造出状态空间树，即边搜索，边构造。

10、P(Polynomial问题)：也即是多项式复杂程度的问题。

NP就是Non-deterministic Polynomial的问题，也即是多项式复杂程度的非确定性问题。

NPC(NP Complete)问题，这种问题只有把解域里面的所有可能都穷举了之后才能得出答案，这样的问题是NP里面最难的问题，这种问题就是NPC问题。

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

1、n后问题回溯算法

(1) !M[j]&&!L[i+j]&&!R[i-j+N]

(2) M[j]=L[i+j]=R[i-j+N]=1;

(3) try(i+1,M,L,R,A)

(4) A[i][j]=0

(5) M[j]=L[i+j]=R[i-j+N]=0

2、数塔问题。

（1）c<=r

(2)t[r][c]+=t[r+1][c]

（3）t[r][c]+=t[r+1][c+1]

3、Hanoi算法

（1）move(a,c)

（2）Hanoi(n-1, a, c , b)

（3）Move(a,c)

4、（1）p[v]=NIL

（2）p[v]=u

(3) v∈adj[u]

（4）Relax(u,v,w)

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

五、（1）8天（2分）；

（2）当n=23=8时，循环赛日程表（3分）。六、算法设计题（本题15分）

（1）贪心算法 O（nlog（n））

首先计算每种物品单位重量的价值Vi/Wi

可能多的单位重量价值最高的物品装入背包。若将这种物品全部装入背包后，背包内的物品总重量未超过C，则选择单位重量价值次高的物品并尽

可能多地装入背包。依此策略一直地进行下去，直到背包装满为止。 具体算法可描述如下：

void Knapsack(int n,float M,float v[],float w[],float x[]) {Sort(n,v,w); int i;

for (i=1;i<=n;i++) x[i]=0; float c=M;

for (i=1;i<=n;i++) {if (w[i]>c) break; x[i]=1; c-=w[i]; }

if (i<=n) x[i]=c/w[i]; }

（2）动态规划法 O(nc)

m(i ，j)是背包容量为j ，可选择物品为i ，i+1，…，n 时0-1背包问题的最优值。由0-1背包问题的最优子结构性质，可以建立计算m(i ，j)的递归式如下。

void KnapSack(int v[],int w[],int c,int n,int m[][11]) {int jMax=min(w[n]-1,c);

for (j=0;j<=jMax;j++) /*m(n,j)=0 0=

for (j=w[n];j<=c;j++) /*m(n,j)=v[n] j>=w[n]*/ m[n][j]=v[n];

for (i=n-1;i>1;i--)

{ int jMax=min(w[i]-1,c);

for (j=0;j<=jMax;j++) /*m(i,j)=m(i+1,j) 0=

for (j=w[i];j<=c;j++)/*m(n,j)=v[n] j>=w[n]*/ m[i][j]=max(m[i+1][j],m[i+1][j-w[i]]+v[i]); }

m[1][c]=m[2][c]; if(c>=w[1])

m[1][c]=max(m[1][c],m[2][c-w[1]]+v[1]); }

（3）回溯法 O(2n )

cw:当前重量 cp:当前价值 bestp ：当前最优值 void backtrack(int i)

i i i i w j w j j i m v w j i m j i m j i m <≤≥?

?

?++-++=0),1(}

),1(),,1(max{),(n

n n

w j w j v j n m <≤≥??

?=00),(

//回溯法i初值1

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

}

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

为了尽可能地逼近目标，我们选取的贪心策略为：每一步总是选择一个使剩下的数最小的数字删去，即按高位到低位的顺序搜索，若各位数字递增，则删除最后一个数字，否则删除第一个递减区间的首字符。然后回到串首，按上述规则再删除下一个数字。重复以上过程s次，剩下的数字串便是问题的解了。

具体算法如下：

输入s, n;

while（ s > 0 ）

{ i=1; //从串首开始找

while (i < length(n)) && (n[i]

{i++;}

delete(n,i,1); //删除字符串n的第i个字符

s--;

}

while (length(n)>1)&& (n[1]=‘0’)

delete(n,1,1); //删去串首可能产生的无用零

输出n;

算法设计与分析复习资料1

一 1.循环赛日程表问题的相关叙述。 2.算法运行时所需要占用的存储空间有？ 3.动态规划法的求解步骤 4.解空间树是排列树的问题有。 5.分治法的步骤 6.就会场安排问题，贪心法的最佳贪心策略 7.快速排序法基准元素的选取方法 8.满足满m叉树的问题有？ 9.分支限界法的解题步骤 10.事前分析法相关的影响因素有 11.用分治法求解的问题一般需要具备一些特征，主要有？ 二 1．给定一个有向带权图G=(V，E)，其中每条边的权是一个非负实数，另外，给定V中的一个顶点，称为源点。现在要计算从源点到所有其它各个顶点的最短路径长度，这里的路径长度是指路径上经过的所有边上的权值之和，这个问题通常称为单源最短路径问题。 2．采用回溯法可以求解0-1背包问题，其解空间的形式为：（x1,x2,…,xn）或n 元组。 3．当所给的问题是从n个元素的排列中找出满足某种性质的一个排列时，相应的解空间树称为排列树。 4．一个正在生成孩子的结点称为扩展结点。 5．子集树是用回溯法解题时经常遇到的一种典型的解空间树。当所给的问题是从n个元素组成的集合S中找出满足某种性质的一个子集时，相应的解空间树称为子集树。 6．当所给问题的n个元素中每一个元素均有m种选择，要求确定其中的一种选择，使得对这n个元素的选择结果组成的向量满足某种性质，即寻找满足某种特性的n个元素取值的一种组合，这类问题的解空间树称为满m叉树。 7．一个自身已生成但其孩子还没有全部生成的结点称为活结点 8．回溯法中，对于问题的一个实例，解向量满足显约束的所有n元组构成了该实例的一个解空间 9．分支限界法有两种：队列式分支限界法和优先队列式分支限界法。 10．分支限界法采用的是宽度优先搜索。 11．时间复杂性的度量方法通常有两种：事后统计法和事前分析估算法 12．一个所有孩子已经生成的结点称做死结点 13．在最小生成树的生成方法中，Kruskal算法从边的角度出发，每一次将图中的权值最小的边取出来，在不构成环的情况下，将该边加入最小生成树。 三 1．分治法字面上的解释是分而治之，就是把一个复杂的问题分成两个或更多的相同子问题，子问题相互独立，如果子问题还是不容易解决，再把子问题分成更小的子问题…，直到最后各个子问题可以简单地直接求解，对各个子问题递归求解，将子问题的解进行合并即得原问题的解。 2．动态规划法要求将大问题分解成规模较小的子问题，经分解得到的各个子问题往往不是相互独立的。在求解过程中，将已解决的子问题的解进行保存，在需要时可以轻松找出。采

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

算法设计与分析考试题 及答案 Company number：【WTUT-WT88Y-W8BBGB-BWYTT-19998】

一、填空题（20分） 1.一个算法就是一个有穷规则的集合，其中之规则规定了解决某一特殊类型问题的一系列运算，此外，算法还应具有以下五个重要特性:确定性 有穷性 可行性 0个或多个输入 一个或多个输出 2.算法的复杂性有时间复杂性 空间复杂性之分，衡量一个算法好坏的标准是 时间复杂度高低 3.某一问题可用动态规划算法求解的显着特征是 该问题具有最优子结构性质 4.若序列X={B,C,A,D,B,C,D}，Y={A,C,B,A,B,D,C,D}，请给出序列X 和Y 的一个最长公共子序列{BABCD}或{CABCD}或{CADCD ｝ 5.用回溯法解问题时，应明确定义问题的解空间，问题的解空间至少应包含一个（最优）解 6.动态规划算法的基本思想是将待求解问题分解成若干_子问题 ，先求解_子问题 ，然后从这些子问题 的解得到原问题的解。 7.以深度优先方式系统搜索问题解的算法称为回溯法 背包问题的回溯算法所需的计算时间为o(n*2n ) ,用动态规划算法所需的计算时间为o(min{nc,2n }) 9.动态规划算法的两个基本要素是最优子结构 _和重叠子问题 10.二分搜索算法是利用动态规划法实现的算法。 二、综合题（50分） 1.写出设计动态规划算法的主要步骤。 ①问题具有最优子结构性质；②构造最优值的递归关系表达式； ③最优值的算法描述；④构造最优解； 2. 流水作业调度问题的johnson 算法的思想。 ①令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. 若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个作业的最优调度方案，并计算最优值。 步骤为：N1={1，3}，N2={2，4}； N 1’={1，3}， N 2’={4，2}； 最优值为：38 4. 使用回溯法解0/1背包问题：n=3，C=9，V={6,10,3}，W={3,4,4},其解空间有长度为3的0-1向量组成，要求用一棵完全二叉树表示其解空间（从根出发，左1右0），并画出其解空间树，计算其最优值及最优解。 解空间为{(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. 设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)递归关系表达式为什么 .二叉树T 的平均路长P=∑=+n i 1 Ci)(1*bi +∑=n j 0 dj *aj

中科院陈玉福计算机算法设计与分析期末简答题答案

1. 贪心算法和动态规划算法有什么共同点和区别？它们都有那些优势和劣势？ 共通点：动态规划和贪心算法都是一种递推算法，均有局部最优解来推导全局最优解 区别：贪心算法中，作出的每步贪心决策都无法改变，每一步的最优解一定包含上一步的 最优解，而上一部之前的最优解则不作保留。 动态优化算法，全局最优解中一定包含某个局部最优解，但不一定包含前一个局部最优解，因此需要记录之前的所有最优解 动态规划算法利用子问题重叠性质，对每一个子问题只计算一次，将其解保存在一个表格中。不同的子问题个数随着输入问题的规模呈多项式增长，因此，动态规划算法通常只需要多项式时间，从而获得较高的解题效率。但它需要计算之前所有情况花费，更加耗费空间。 贪心算法所作的选择依赖于以往所作过的选择,但决不依赖于将来的选择,这使得算法在编 码和执行过程中都有一定的速度优势。贪心算法是只是找局部最优解，不一定是全局最优解。 2. 试比较回溯法与分枝限界算法，分别谈谈这两个算法比较适合的问题？ 二者都是在解空间树里搜索问题的可靠解或最优解，但是搜索的方式不同，回溯法采用深 度优先的方式，直到达到问题的一个可行解，或经判断沿此路径不会达到问题的可行解或最优解时，停止向前搜索，并沿原路返回到该路径上最后一个还可扩展的节点，然后，从该节点出发朝新的方向纵深搜索。分枝限界法采用的是宽度优先的方式，它将活节点存放在一个特殊的表中，其策略是，在扩展节点处，首先生成其所有的儿子节点，将那些导致不可行解或导致非最优解的儿子节点舍弃，其余儿子节点加入活节点表中，然后，从活节点中取出一个节点作为当前扩展节点，重复上述节点中扩展过程。可以看出，回溯法一般用于求问题的一个可行解，而分枝限界可以用于求出问题的所有可行解。 3. 何谓最优化原理？采用动态规划算法必须满足的条件是什么？动态规划算法是通过什 么问题的什么特性提高效率的？ 一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其具有最优子结构性质。最优子结构性质，子问题重叠性质是计算模型采用动态规划算法求解的两个基本要素。 动态规划算法利用子问题重叠性质，对每一个子问题只计算一次，将其解保存在一个表格中。不同的子问题个数随着输入问题的规模呈多项式增长，因此，动态规划算法通常只需要多项式时间，从而获得较高的解题效率 4. 什么是多项式时间算法？ 若存在一个常数C，使得对于所有n>=0，都有|f(n)| <= C*|g(n)|，则称函数f(n)是O(g(n))。时间复杂度是O(p(n))的算法称为多项式时间算法，这里p(n)是关于n的多项式。 时间复杂度为O(nlog(n))、O(n^3)的算法都是多项式时间算法，时间复杂度为O(n^log(n))、O(n!)、O(2^n)的算法是指数时间算法。 一个优化问题如果已经找到了多项式时间算法，则称该问题为多项式时间可解问题，并 将这类问题的集合记为P，因此多项式时间可解问题就称为P类问题。。

算法设计与分析复习题目及答案19874

一。选择题 1、二分搜索算法就是利用( A )实现的算法。 Ａ、分治策略B、动态规划法C、贪心法 D、回溯法 2、下列不就是动态规划算法基本步骤的就是( A )。 A、找出最优解的性质 B、构造最优解 C、算出最优解 D、定义最优解 ３、最大效益优先就是( A )的一搜索方式。 Ａ、分支界限法Ｂ、动态规划法Ｃ、贪心法Ｄ、回溯法 4、在下列算法中有时找不到问题解的就是( B )。 Ａ、蒙特卡罗算法 B、拉斯维加斯算法 C、舍伍德算法 D、数值概率算法 5、回溯法解旅行售货员问题时的解空间树就是( B )。 A、子集树???Ｂ、排列树C、深度优先生成树?D、广度优先生成树 6.下列算法中通常以自底向上的方式求解最优解的就是( Ｂ)。 Ａ、备忘录法?B、动态规划法?C、贪心法????D、回溯法 7、衡量一个算法好坏的标准就是(C )。?A 运行速度快Ｂ占用空间少 C 时间复杂度低 D 代码短?８、以下不可以使用分治法求解的就是(D )。?Ａ棋盘覆盖问题Ｂ选择问题 C 归并排序 D 0/1背包问题?9、实现循环赛日程表利用的算法就是( A )。 A、分治策略?? B、动态规划法 C、贪心法??Ｄ、回溯法 10、下列随机算法中运行时有时候成功有时候失败的就是(C ) A 数值概率算法 B 舍伍德算法 C 拉斯维加斯算法 D 蒙特卡罗算法 11.下面不就是分支界限法搜索方式的就是( D )。 Ａ、广度优先?B、最小耗费优先C、最大效益优先D、深度优先 12、下列算法中通常以深度优先方式系统搜索问题解的就是( D )。 Ａ、备忘录法B、动态规划法??C、贪心法???D、回溯法

13、备忘录方法就是那种算法的变形。( B ) A、分治法? B、动态规划法? C、贪心法?? D、回溯法 1４、哈弗曼编码的贪心算法所需的计算时间为( B )。 A、Ｏ(n2n)?? B、O(nｌogｎ)? C、O(2ｎ) ??? D、Ｏ(n) 15.分支限界法解最大团问题时,活结点表的组织形式就是( B )。 A、最小堆???? B、最大堆?? C、栈???Ｄ、数组 １6.最长公共子序列算法利用的算法就是( B )。 A、分支界限法? B、动态规划法? C、贪心法 D、回溯法 17.实现棋盘覆盖算法利用的算法就是( A )。 Ａ、分治法??Ｂ、动态规划法C、贪心法??D、回溯法 18、下面就是贪心算法的基本要素的就是( C )。 A、重叠子问题?Ｂ、构造最优解??C、贪心选择性质??D、定义最优解 1９.回溯法的效率不依赖于下列哪些因素( D ) A、满足显约束的值的个数????Ｂ、计算约束函数的时间 C、计算限界函数的时间?? D、确定解空间的时间 ２０、下面哪种函数就是回溯法中为避免无效搜索采取的策略( B ) A.递归函数?B、剪枝函数? C。随机数函数???Ｄ、搜索函数 21、下面关于NＰ问题说法正确的就是(B )?A NＰ问题都就是不可能解决的问题?B P类问题包含在ＮＰ类问题中?C NP完全问题就是P类问题的子集 D ＮP类问题包含在P类问题中 22、蒙特卡罗算法就是( B )的一种。 Ａ、分支界限算法 B、概率算法C、贪心算法D、回溯算法 2３、下列哪一种算法不就是随机化算法( C ) A、蒙特卡罗算法 B、拉斯维加斯算法 C、动态规划算法 D、舍伍德算法 24、 ( D )就是贪心算法与动态规划算法的共同点。Ａ、重叠子问题B、构造最优解?C、贪心选择性质D、最优子结构性质２5、矩阵连乘问题的算法可由( B)设计实现。

算法设计与分析报告考试题(自测)

1.一个算法就是一个有穷规则的集合，其中之规则规定了解决某一特殊类型问题的一系列运算，此外，算法还应具有以下五个重要特性:_有穷性__,_确定性_,_可行性_,_ （0个或多个）输入__,_ （1个或多个）_输出_。 2.算法的复杂性有__时间复杂性__和__空间复杂性__之分，衡量一个 算法好坏的标准是__时间复杂度高低___。 3.某一问题可用动态规划算法求解的显著特征是___该问题具有最优 子结构性质___。 4.若序列X={B,C,A,D,B,C,D}，Y={A,C,B,A,B,D,C,D}，请给出序列X 和Y的一个最长公共子序列_{A,B,C,D}_。{BABCD}或{CABCD}或{CADCD｝ 5.用回溯法解问题时，应明确定义问题的解空间，问题的解空间至少应包含_问题的一个（最优）解_。 6.动态规划算法的基本思想是将待求解问题分解成若干_子问题_，先求解_子问题__，然后从这些_子问题_的解得到原问题的解。 7.以深度优先方式系统搜索问题解的算法称为__回溯法__。 8.0-1背包问题的回溯算法所需的计算时间为__O（n2n）__,用动态规划算法所需的计算时间为_O（n）__。o(min{nc,2n}) 9.动态规划算法的两个基本要素是_最优子结构_和_重叠子问题 ___。 10.二分搜索算法是利用__动态规划法__实现的算法。

二、综合题（50分） 1.写出设计动态规划算法的主要步骤。 1、解：（1）找出最优解的性质，并刻画其结构特征； （2）递归地定义最优值； （3）以自底向上的方式计算出最优值； （4）根据计算最优值时得到的信息，构造最优解。 ①问题具有最优子结构性质；②构造最优值的递归关系表达式； ③最优值的算法描述；④构造最优解 2.流水作业调度问题的johnson算法的思想。 2、解：①令N1={i|a i=b i}；②将N1中作业按a i 的非减序排序得到N1’，将N2中作业按b i的非增序排序得到N2’； ③N1’中作业接N2’中作业就构成了满足Johnson法则的最优调度。 3.若n=4，在机器M1和M2上加工作业i所需的时间分别为a i和b i，且(a1,a2,a3,a4)=(4,5,12,10)，(b1,b2,b3,b4)=(8,2,15,9)求4个作业的最优调度方案，并计算最优值。 3、解：步骤为：N1={1，3}，N2={2，4}； N1’={1，3}， N2’={4，2}； 最优值为：38

算法设计与分析试卷(2010)

算法设计与分析试卷(A 卷) 一、 选择题 （ 选择1-4个正确的答案, 每题2分，共20分） （1）计算机算法的正确描述是： B 、D A ．一个算法是求特定问题的运算序列。 B ．算法是一个有穷规则的集合，其中之规则规定了一个解决某一特定类型的问题的运算序列。 C ．算法是一个对任一有效输入能够停机的图灵机。 D ．一个算法，它是满足5 个特性的程序，这5个特性是：有限性、确定性、能 行性、有0个或多个输入且有1个或多个输出。 （2）影响程序执行时间的因素有哪些？ C 、D A ．算法设计的策略 B ．问题的规模 C ．编译程序产生的机器代码质量 D ．计算机执行指令的速度 （3）用数量级形式表示的算法执行时间称为算法的 A A ．时间复杂度 B ．空间复杂度 C ．处理器复杂度 D ．通信复杂度 （4）时间复杂性为多项式界的算法有： A ．快速排序算法 B ．n-后问题 C ．计算π值 D ．prim 算法 （5）对于并行算法与串行算法的关系，正确的理解是： A ．高效的串行算法不一定是能导出高效的并行算法 B ．高效的串行算法不一定隐含并行性 C ．串行算法经适当的改造有些可以变化成并行算法 D. 用串行方法设计和实现的并行算法未必有效 （6）衡量近似算法性能的重要标准有： A A ．算法复杂度 B ．问题复杂度 C ．解的最优近似度 D ．算法的策略 （7）分治法的适用条件是，所解决的问题一般具有这些特征： ABCD A ．该问题的规模缩小到一定的程度就可以容易地解决； B ．该问题可以分解为若干个规模较小的相同问题； C ．利用该问题分解出的子问题的解可以合并为该问题的解 D ．该问题所分解出的各个子问题是相互独立的。 （8）具有最优子结构的算法有： A ．概率算法 B ．回溯法 C ．分支限界法 D ．动态规划法 （9）下列哪些问题是典型的NP 完全问题： A ．排序问题 B ．n-后问题 C ．m-着色问题 D ．旅行商问题 （10）适于递归实现的算法有： C A ．并行算法 B ．近似算法 C ．分治法 D ．回溯法 二、算法分析题（每小题5分，共10分） （11）用展开法求解递推关系： （12）分析当输入数据已经有序时快速排序算法的不足，提出算法的改进方案。 ???>+-==1 1)1(211)(n n T n n T

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

算法设计与分析考试题及 答案 It was last revised on January 2, 2021

一、填空题（20分） 1.一个算法就是一个有穷规则的集合，其中之规则规定了解决某一特殊类型问题的一系列运算， 此外，算法还应具有以下五个重要特性:确定性有穷性可行性 0个或多个输入一个或多 个输出 2.算法的复杂性有时间复杂性空间复杂性之分，衡量一个算法好坏的标准是时间复杂度高低 3.某一问题可用动态规划算法求解的显着特征是该问题具有最优子结构性质 4.若序列X={B,C,A,D,B,C,D}，Y={A,C,B,A,B,D,C,D}，请给出序列X和Y的一个最长公共子序列{BABCD}或{CABCD}或{CADCD｝ 5.用回溯法解问题时，应明确定义问题的解空间，问题的解空间至少应包含一个（最优）解 6.动态规划算法的基本思想是将待求解问题分解成若干_子问题，先求解_子问题，然后从这些 子问题的解得到原问题的解。 7.以深度优先方式系统搜索问题解的算法称为回溯法 背包问题的回溯算法所需的计算时间为o(n*2n) ,用动态规划算法所需的计算时间为o(min{nc,2n}) 9.动态规划算法的两个基本要素是最优子结构_和重叠子问题 10.二分搜索算法是利用动态规划法实现的算法。 二、综合题（50分） 1.写出设计动态规划算法的主要步骤。 ①问题具有最优子结构性质；②构造最优值的递归关系表达式；③最优值的算法描述；④构造 最优解； 2.流水作业调度问题的johnson算法的思想。 ①令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.若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个作业的最优调度方案，并计算最优 值。 步骤为：N1={1，3}，N2={2，4}； N 1’={1，3}， N 2 ’={4，2}； 最优值为：38 4.使用回溯法解0/1背包问题：n=3，C=9，V={6,10,3}，W={3,4,4},其解空间有长度为3的0-1向量组成，要求用一棵完全二叉树表示其解空间（从根出发，左1右0），并画出其解空间树，计算其最优值及最优解。 解空间为{(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）

算法设计与分析复习题目及答案

一。选择题 1、二分搜索算法是利用（ A ）实现的算法。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 2、下列不是动态规划算法基本步骤的是（ B ）。 A、找出最优解的性质 B、构造最优解 C、算出最优解 D、定义最优解 3、最大效益优先是（ A ）的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 4、在下列算法中有时找不到问题解的是（ B ）。 A、蒙特卡罗算法 B、拉斯维加斯算法 C、舍伍德算法 D、数值概率算法 5. 回溯法解旅行售货员问题时的解空间树是（ B ）。 A、子集树 B、排列树 C、深度优先生成树 D、广度优先生成树6．下列算法中通常以自底向上的方式求解最优解的是（ B ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 7、衡量一个算法好坏的标准是（C ）。 A 运行速度快 B 占用空间少 C 时间复杂度低 D 代码短 8、以下不可以使用分治法求解的是（D ）。 A 棋盘覆盖问题 B 选择问题 C 归并排序 D 0/1背包问题 9. 实现循环赛日程表利用的算法是（ A ）。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 10、下列随机算法中运行时有时候成功有时候失败的是（C ） A 数值概率算法 B 舍伍德算法 C 拉斯维加斯算法 D 蒙特卡罗算法 11．下面不是分支界限法搜索方式的是（ D ）。 A、广度优先 B、最小耗费优先 C、最大效益优先 D、深度优先12．下列算法中通常以深度优先方式系统搜索问题解的是（ D ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 13.备忘录方法是那种算法的变形。（ B ）

算法设计与分析试卷(2010)

内部资料，转载请注明出处，谢谢合作。 算法设计与分析试卷(A 卷) 一、 选择题 （ 选择1-4个正确的答案, 每题2分，共20分） （1）计算机算法的正确描述是： A ．一个算法是求特定问题的运算序列。 B ．算法是一个有穷规则的集合，其中之规则规定了一个解决某一特定类型的问题的运算序列。 C ．算法是一个对任一有效输入能够停机的图灵机。 D ．一个算法，它是满足5 个特性的程序，这5个特性是：有限性、确定性、能 行性、有0个或多个输入且有1个或多个输出。 （2）影响程序执行时间的因素有哪些？ A ．算法设计的策略 B ．问题的规模 C ．编译程序产生的机器代码质量 D ．计算机执行指令的速度 （3）用数量级形式表示的算法执行时间称为算法的 A ．时间复杂度 B ．空间复杂度 C ．处理器复杂度 D ．通信复杂度 （4）时间复杂性为多项式界的算法有： A ．快速排序算法 B ．n-后问题 C ．计算π值 D ．prim 算法 （5）对于并行算法与串行算法的关系，正确的理解是： A ．高效的串行算法不一定是能导出高效的并行算法 B ．高效的串行算法不一定隐含并行性 C ．串行算法经适当的改造有些可以变化成并行算法 D. 用串行方法设计和实现的并行算法未必有效 （6）衡量近似算法性能的重要标准有： A ．算法复杂度 B ．问题复杂度 C ．解的最优近似度 D ．算法的策略 （7）分治法的适用条件是，所解决的问题一般具有这些特征： A ．该问题的规模缩小到一定的程度就可以容易地解决； B ．该问题可以分解为若干个规模较小的相同问题； C ．利用该问题分解出的子问题的解可以合并为该问题的解 D ．该问题所分解出的各个子问题是相互独立的。 （8）具有最优子结构的算法有： A ．概率算法 B ．回溯法 C ．分支限界法 D ．动态规划法 （9）下列哪些问题是典型的NP 完全问题： A ．排序问题 B ．n-后问题 C ．m-着色问题 D ．旅行商问题 （10）适于递归实现的算法有： A ．并行算法 B ．近似算法 C ．分治法 D ．回溯法 二、算法分析题（每小题5分，共10分） （11）用展开法求解递推关系： （12）分析当输入数据已经有序时快速排序算法的不足，提出算法的改进方案。 ???>+-==1 1)1(211)(n n T n n T

计算机算法设计与分析期末考试复习题

1、二分搜索算法是利用（ A ）实现的算法。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 2、下列不是动态规划算法基本步骤的是（ A ）。 A、找出最优解的性质 B、构造最优解 C、算出最优解 D、定义最优解 3、最大效益优先是（ A ）的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 4、最长公共子序列算法利用的算法是（ B ）。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 5. 回溯法解TSP问题时的解空间树是（ A ）。 A、子集树 B、排列树 C、深度优先生成树 D、广度优先生成树6．下列算法中通常以自底向上的方式求解最优解的是（ B ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 7、衡量一个算法好坏的标准是（C ）。 A 运行速度快 B 占用空间少 C 时间复杂度低 D 代码短 8、以下不可以使用分治法求解的是（D ）。 A 棋盘覆盖问题 B 选择问题 C 归并排序 D 0/1背包问题 9. 实现循环赛日程表利用的算法是（ A ）。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 10、实现最长公共子序列利用的算法是（ B ）。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法11．下面不是分支界限法搜索方式的是（ D ）。 A、广度优先 B、最小耗费优先 C、最大效益优先 D、深度优先 12．下列算法中通常以深度优先方式系统搜索问题解的是（ D ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 13. 一个问题可用动态规划算法或贪心算法求解的关键特征是问题的（ B ）。 A、重叠子问题 B、最优子结构性质 C、贪心选择性质 D、定义最优解14．广度优先是（ A ）的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 15．背包问题的贪心算法所需的计算时间为（ B ）。

《算法设计与分析》复习题(汇编)

填空 1．直接或间接地调用自身的算法称为 递归 。 2．算法的复杂性是 算法效率 的度量，是评价算法优劣的重要依据。 3．以广度优先或以最小耗费方式搜索问题解的算法称为 分支限界法 。 4．回溯法解题的显著特点是在搜索过程中动态产生问题的解空间。在任何时刻，算法只保存从根结点到当前扩展结点的路径。如果解空间树中从根结点到叶结点的最长路径的长度为h(n)，则回溯法所需的计算空间通常为 o(h(n)) 。 5．人们通常将问题的解决方案分为两大类：一类是可以通过执行若干个步骤就能得出问题 6．算法就是一组有穷的 规则 ，它们规定了解决某一特定类型问题的 一系列运算 。 7．在进行问题的计算复杂性分析之前，首先必须建立求解问题所用的计算模型。3个基本计算模型是 随机存取机、 随机存取存储程序机 、 图灵机 。 8．快速排序算法的性能取决于 划分的对称性 。 9．计算机的资源最重要的是 内存 和 运算 资源。因而，算法的复杂性有时间 和 空间 之分。 10．贪心算法总是做出在当前看来 最优 的选择。也就是说贪心算法并不从整体最优考虑，它所做出的选择只是在某种意义上的 局部最优解 。 11．许多可以用贪心算法求解的问题一般具有2个重要的性质： 最优子结构的 性质和 贪心选择的 性质。 12．常见的两种分支限界法为 队列式 和 优先队列式 。 13．解决0/1背包问题可以使用动态规划、回溯法和分支限界法，其中需要排序的是 回溯法 ，不需要排序的是 动态规划和分支限界法 。 14．f ( n ) = 6 × 2n + n 2，f(n)的渐进性态f ( n ) = O ( 2^n )。 15．对于含有n 个元素的排列树问题，最好情况下计算时间复杂性为 ，最坏情况下计算时间复杂性为 n! 。 16．在忽略常数因子的情况下，O 、Ω和Θ三个符号中， Θ 提供了算法运行时间的一个上界。 17．回溯法的求解过程，即在问题的解空间树中，按 深度优先 策略从根结点出发搜索解空间树。 18．分支限界法的求解过程，即在问题的解空间树中，按 广度优先 策略从根结点出发搜索解空间树。 19．多项式10()m m A n a n a n a =+ ++的上界为 2^n 。 20．用分支限界法解布线问题时，对空间树搜索结束的标志是 活结点表为空 。 21．使用回溯法进行状态空间树裁剪分支时一般有两个标准：约束条件和目标函数的界，N 皇后问题和0/1背包问题正好是两种不同的类型，其中同时使用约束条件和目标函数的界进

算法设计与分析试卷及答案

湖南科技学院二○年学期期末考试 信息与计算科学专业年级《算法设计与分析》试题 考试类型:开卷试卷类型:C卷考试时量:1２０分钟 题号一二三四五总分统分人 得分 阅卷人 复查人 一、填空题(每小题3 分，共计30 分) １、用O、Ω与θ表示函数f与g之间得关系＿__________＿__＿_＿_＿＿_＿__＿___＿＿。 2、算法得时间复杂性为,则算法得时间复杂性得阶为_＿__＿＿____＿_＿_＿____＿＿_＿__＿。 3、快速排序算法得性能取决于_＿_____＿_______＿__＿__＿_＿___＿__。 4、算法就是__＿_＿______＿＿_＿＿__＿________＿___＿___＿___＿___＿_＿_＿_＿＿_＿__。 5、在对问题得解空间树进行搜索得方法中,一个活结点最多有一次机会成为活结点得就是＿_______＿__＿____________＿。 6、在算法得三种情况下得复杂性中,可操作性最好且最有实际价值得就是__＿_＿情况下得时间复杂性。 7、大Ω符号用来描述增长率得下限,这个下限得阶越__＿________,结果就越有价值。。 8、_＿_＿__＿_＿____＿________＿_____就是问题能用动态规划算法求解得前提。 9、贪心选择性质就是指_＿____________＿______＿_＿__＿__＿______＿________________＿__＿_____＿____＿____＿_＿______＿__＿__＿___＿_＿__＿___＿_＿＿＿________＿__。 1０、回溯法在问题得解空间树中,按______＿＿＿_＿__＿策略,从根结点出发搜索解空间树。 二、简答题(每小题10分,共计3０分) １、试述回溯法得基本思想及用回溯法解题得步骤。 2、有８个作业{１,２,…,8}要在由2台机器M1与Ｍ２组成得流水线上完成加工。每个作业加工得顺序都就是先在M1上加工,然后在M2上加工。M１与M2加工作业ｉ所需得时间分别为: M１10 2 8 12 6 ９４14

算法设计与分析课后习题

第一章 1. 算法分析题 算法分析题1－1 求下列函数的渐进表达式 (1). 3n^2 + 10n < 3n^2 + 10n^2 = 13n^2 = O(n^2) (2). n^2 / 10 + 2^n 当n>5是，n^2 < 2 ^n 所以，当n >= 1时，n^2/10 < 2 ^n 故: n^2/10 + 2^n < 2 ^n + 2^n = 2*2^n = O(2^n) (3). 21 + 1/n < 21 + 1 = 22 = O(1) (4). log(n^3)=3log(n)=O(log(n)) (5). 10log(3^n) = (10log3)n = O(n) 算法分析题1-6 (1)因为：f(n)=log(n^2) = 2log(n); g(n) = log(n) + 5 所以：f(n)=Θ(log(n)+5) =Θ(g(n)) (2)因为：log(n) < √n ; f(n) = 2log(n); g(n)= √n 所以：f(n) = O(g(n)) (3)因为：log(n) < n; f(n) = n; g(n) = log(n^2) = 2log(n) 所以；f(n) = Ω(g(n)) (4)因为：f(n) = nlogn +n; g(n) = logn 所以：f(n) =Ω(g(n)) (5)因为: f(n) = 10; g(n) = log(10) 所以:f(n) =Θ(g(n)) (6)因为: f(n)=log^2(n); g(n) = log(n) 所以: f(n) ==Ω(g(n)) (7)因为: f(n) = 2^n < 100*2^n; g(n)=100n^2; 2^n > n ^2 所以: f(n) = Ω(g(n)) (8)因为：f(n) = 2^n; g(n) = 3 ^n; 2 ^n < 3 ^n 所以: f(n) = O(g(n)) 习题1－9 证明：如果一个算法在平均情况下的计算时间复杂性为Θ(f(n)),该算法在最坏情况下所需的计算时间为Ω(f(n)). 分析与解答：

2015算法设计与分析考试复习刚要习题

计算机算法设计与分析复习题一、填空题1、一个算法复杂性的高低体现在计算机运行该算法所需的时间和存储器资源上，因此算法的复杂性有时间复杂性和空间复杂性之分。2、出自于“平衡子问题”的思想，通常分治法在分割原问题，形成若干子问题时，这些子问题的规模都大致相同。3、使用二分搜索算法在n个有序元素表中搜索一个特定元素，在最佳情况下，搜索的时间复杂性为O （1），在最坏情况下，搜索的时间复杂性为O（logn）。4、已知一个分治算法耗费的计算时间T(n)，T(n)满足如下递归方程： n2O(1) T(n)2T(n/2)O(n)n2解得此递归方可得T(n)= O（）。 nlogn5、动态规划算法有一个变形方法备忘录方法。这种方法不同于动态规划算法“自底向上”的填充方向，而是“自顶向下”的递归方向，为每个解过的子问题建立了备忘录以备需要时查看，同样也可避免相同子问题的重复求解。递归的二分查找算法在divide阶段所花的时间是 O(1) ，conquer阶段6．所花的时间是 T(n/2) ，算法的时间复杂度是 O( log n) 。7．Prim算法利用贪心策略求解最小生成树问题，其时间复杂度是 2O(n) 。8．背包问题可用贪心法，回溯法等策略求解。39．用动态规划算法计算矩阵连乘问题的最优值所花的时间是 O(n) ，子2问题空间大小是 O(n) 。10．图的m着色问题可用回溯法求解，其解空间树中叶子结点个数是nm ，解空间树中每个内结点的孩子数是 m 。11．单源最短路径问题可用贪心法、分支限界等策略求解。12、一个算法的优劣可以用（时间复杂度）与（空间复杂度）与来衡量。 13、回溯法在问题的解空间中，按（深度优先方式）从根结点出发搜索解空间树。 14、直接或间接地调用自身的算法称为（递归算法）。 15、记号在算法复杂性的表示法中表示（渐进确界或紧致界）。 16、在分治法中，使子问题规模大致相等的做法是出自一种（平衡(banlancing)子问题）的思想。 17、动态规划算法适用于解（具有

算法设计与分析期末试题答案解析

1、用计算机求解问题的步骤： 1、问题分析 2、数学模型建立 3、算法设计与选择 4、算法指标 5、算法分析 6、算法实现 7、程序调试 8、结果整理文档编制 2、算法定义：算法是指在解决问题时，按照某种机械步骤一定可以得到问题结果的处理过程 3、算法的三要素 1、操作 2、控制结构 3、数据结构 算法具有以下5个属性： 有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。 确定性：算法中每一条指令必须有确切的含义。不存在二义性。只有一个入口和一个出口 可行性：一个算法是可行的就是算法描述的操作是可以通过已经实现的基本运算执行有限次来实现的。 输入：一个算法有零个或多个输入，这些输入取自于某个特定对象的集合。 输出：一个算法有一个或多个输出，这些输出同输入有着某些特定关系的量。 算法设计的质量指标： 正确性：算法应满足具体问题的需求； 可读性：算法应该好读，以有利于读者对程序的理解；

健壮性：算法应具有容错处理，当输入为非法数据时，算法应对其作出反应，而不是产生莫名其妙的输出结果。 效率与存储量需求：效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间。一般这两者与问题的规模有关。 经常采用的算法主要有迭代法、分而治之法、贪婪法、动态规划法、回溯法、分支限界法 迭代法 基本思想：迭代法也称“辗转法”，是一种不断用变量的旧值递推出新值的解决问题的方法。 解题步骤：1、确定迭代模型。根据问题描述，分析得出前一个（或几个）值与其下一个值的迭代关系数学模型。 2、建立迭代关系式。迭代关系式就是一个直接或间接地不断由旧值递推出新值的表达式，存储新值的变量称为迭代变量 3、对迭代过程进行控制。确定在什么时候结束迭代过程，这是编写迭代程序必须考虑的问题。不能让迭代过程无休止地重复执行下去。迭代过程的控制通常可分为两种情况：一种是所需的迭代次数是个确定的值，可以计算出来；另一种是所需的迭代次数无法确定。对于前一种情况，可以构建一

算法设计与分析期末总复习

复习 一、简答题（每小题5分，选答2题，共10分） 1. 什么是算法？试说明算法设计分析过程的一般框架和主要步骤。 2. 简述非递归算法时间效率分析的通用方案。 3. 简述递归算法时间效率的通用方案。 4. 简述蛮力法、分治法、减治法，变治法、时空权衡、动态规划、贪婪技术、迭代改进八种算法设计技术中至少三种技术基本思想或原理。 二、分析题（每小题10分，共20分） 1. 考虑下面的算法。P52 算法Mystery(n) //输入：非负整数n S=0 for i ← 1 to n do S ← S + i*i Return S a.该算法求的是什么？ b.它的基本操作是什么？ c.该基本操作执行了多少次？ d.该算法的效率类型是什么？ 2. 考虑下面的递归算法。P52 算法Secret(A[0..n-1]) //输入：包含n个实数的数组A[0..n-1] minval ← A[0]; maxval ← A[0] for i ←1 to n-1 do if A[i] < minval minval ← A[i] if A[i] > maxval maxval ← A[i] return maxval – minval a.该算法求的是什么？ b.它的基本操作是什么？ c.该基本操作执行了多少次？ d.该算法的效率类型是什么？ 3. 考虑下面的递归算法P59 算法Q(n) //输入：正整数 if n=1 return 1 else return Q(n-1) + 2*n -1 a. 建立该函数值的递推关系并求解，以确定该算法计算的是什么； b. 建立该算法所做的乘法运算次数的递推关系并求解； c. 建立该算法所做的加减运算次数的递推关系并求解。 三、算法设计题（每小题10分，共20分） 1. 应用快速排序对序列E，X，A，M，P，L，E按照字母顺序排序。并画出相应的递归调

算法设计与分析试卷及答案.doc

湖南科技学院二○ 年 学期期末考试 信息与计算科学专业 年级《算法设计与分析》 试题 考试类型：开卷 试卷类型： C 卷 考试时量： 120 分钟 题号 一 二 三 四 五 总分 统分人 得 分 阅卷人 一、填空题（每小题 3 分，共计 30 分） 1. 用 O 、Ω和θ表示函数 f 与 g 之间的关系 ______________________________ 。 f n n lo g n g n log n 1, n 1 2. 算法的时间复杂性为 f (n) n ，则算法的时间复杂性的阶 8 f (3n / 7) n, 2 为__________________________ 。 3. 快速排序算法的性能取决于 ______________________________ 。 4. 算法是 _______________________________________________________ 。 5. 在对问题的解空间树进行搜索的方法中，一个活结点最多有一次机会成为活结点的 是_________________________ 。 6. 在算法的三种情况下的复杂性中， 可操作性最好且最有实际价值的是 _____情况下的时间复杂性。 7. 大Ω符号用来描述增长率的下限，这个下限的阶越 ___________，结果就越有价值。 。 8. ____________________________ 是问题能用动态规划算法求解的前提。 9. 贪心选择性质是指 ________________________________________________________ ____________________________________________________________ 。

算法设计与分析复习题目及答案doc

分治法 1、二分搜索算法是利用（分治策略）实现的算法。 9. 实现循环赛日程表利用的算法是（分治策略） 27、Strassen矩阵乘法是利用（分治策略）实现的算法。 34．实现合并排序利用的算法是（分治策略）。 实现大整数的乘法是利用的算法（分治策略）。 17．实现棋盘覆盖算法利用的算法是（分治法）。 29、使用分治法求解不需要满足的条件是（子问题必须是一样的）。 不可以使用分治法求解的是（0/1背包问题）。 动态规划 下列不是动态规划算法基本步骤的是（构造最优解） 下列是动态规划算法基本要素的是（子问题重叠性质）。 下列算法中通常以自底向上的方式求解最优解的是（动态规划法） 备忘录方法是那种算法的变形。（动态规划法） 最长公共子序列算法利用的算法是（动态规划法）。 矩阵连乘问题的算法可由（动态规划算法B）设计实现。 实现最大子段和利用的算法是（动态规划法）。 贪心算法 能解决的问题：单源最短路径问题，最小花费生成树问题，背包问题，活动安排问题， 不能解决的问题：N皇后问题，0/1背包问题 是贪心算法的基本要素的是（贪心选择性质和最优子结构性质）。 回溯法 回溯法解旅行售货员问题时的解空间树是（排列树）。 剪枝函数是回溯法中为避免无效搜索采取的策略 回溯法的效率不依赖于下列哪些因素（确定解空间的时间）

分支限界法 最大效益优先是（分支界限法）的一搜索方式。 分支限界法解最大团问题时，活结点表的组织形式是（最大堆）。 分支限界法解旅行售货员问题时，活结点表的组织形式是（最小堆） 优先队列式分支限界法选取扩展结点的原则是（结点的优先级） 在对问题的解空间树进行搜索的方法中,一个活结点最多有一次机会成为活结点的是( 分支限界法 ). 从活结点表中选择下一个扩展结点的不同方式将导致不同的分支限界法,以下除( 栈式分支限界法 )之外都是最常见的方式. （1）队列式(FIFO)分支限界法：按照队列先进先出（FIFO）原则选取下一个节点为扩展节点。 （2）优先队列式分支限界法：按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。 （最优子结构性质）是贪心算法与动态规划算法的共同点。 贪心算法与动态规划算法的主要区别是（贪心选择性质）。 回溯算法和分支限界法的问题的解空间树不会是( 无序树 ). 14．哈弗曼编码的贪心算法所需的计算时间为（ B ）。 A、O（n2n） B、O（nlogn） C、O（2n） D、O（n） 21、下面关于NP问题说法正确的是（B ） A NP问题都是不可能解决的问题 B P类问题包含在NP类问题中 C NP完全问题是P类问题的子集 D NP类问题包含在P类问题中 40、背包问题的贪心算法所需的计算时间为（ B ）