《算法设计与分析》考试题目及答案教学内容.docx
《《算法设计与分析》考试题目及答案教学内容.docx》由会员分享，可在线阅读，更多相关《《算法设计与分析》考试题目及答案教学内容.docx（37页珍藏版）》请在冰点文库上搜索。
《算法设计与分析》考试题目及答案教学内容
《算法设计与分析》考试题目及答案
《算法分析与设计》期末复习题
一、选择题
1.应用Johnson法则的流水作业调度采用的算法是（D）
A.贪心算法B.分支限界法C.分治法D.动态规划算法
2.Hanoi塔问题如下图所示。
现要求将塔座A上的的所有圆盘移到塔座B上，并仍按同样顺序叠置。
移动圆盘时遵守Hanoi塔问题的移动规则。
由此设计出解Hanoi塔问题的递归算法正确的为：
（B）
B.voidhanoi（intn,intA,intB,intC）
{
if（n>0）
{
hanoi（n-1,A,C,B）;
move（n,a,b）;
hanoi（n-1,C,B,A）;
}
}
C.voidhanoi（intn,intC,intB,intA）
{
if（n>0）
{
hanoi（n-1,A,C,B）;
move（n,a,b）;
hanoi（n-1,C,B,A）;
}
}
D.voidhanoi（intn,intC,intA,intB）
{
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.
B.
C.O（f（n））+O（g（n））=O（min{f（n）,g（n）}）
D.
6.能采用贪心算法求最优解的问题，一般具有的重要性质为：
（A）
A.最优子结构性质与贪心选择性质
B．重叠子问题性质与贪心选择性质
C．最优子结构性质与重叠子问题性质
D.预排序与递归调用
7.回溯法在问题的解空间树中，按（D）策略，从根结点出发搜索解空间树。
A．广度优先B.活结点优先C.扩展结点优先D.深度优先
8.分支限界法在问题的解空间树中，按（A）策略，从根结点出发搜索解空间树。
A．广度优先B.活结点优先C.扩展结点优先D.深度优先
9.程序块（A）是回溯法中遍历排列树的算法框架程序。
voidbacktrack（intt）
{
if（t>n）output（x）;
else
for（inti=t;i<=n;i++）{
swap（x[t],x[i]）;
if（legal（t））backtrack（t+1）;
swap（x[t],x[i]）;
}
}
A.
voidbacktrack（intt）
{
if（t>n）output（x）;
else
for（inti=0;i<=1;i++）{
x[t]=i;
if（legal（t））backtrack（t+1）;
}
}
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.。
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
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）
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）
二、填空题
1.下面程序段的所需要的计算时间为（
）。
intMaxSum（intn,int*a,int&besti,int&bestj）
{
intsum=0;
for（inti=1;i<=n;i++）{
intthissum=0;
for（intj=i;j<=n;j++）{
thissum+=a[j];
if（thissum>sum）{
sum=thissum;
besti=i;
bestj=j;
}
}
}
returnsum;
}
2.有11个待安排的活动，它们具有下表所示的开始时间与结束时间，如果以贪心算法求解这些活动的最优安排（即为活动安排问题：
在所给的活动集合中选出最大的相容活动子集合），得到的最大相容活动子集合为活动（{1，4，8，11}）。
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
3.所谓贪心选择性质是指（所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到）。
4.所谓最优子结构性质是指（问题的最优解包含了其子问题的最优解）。
5.回溯法是指（具有限界函数的深度优先生成法）。
6.用回溯法解题的一个显著特征是在搜索过程中动态产生问题的解空间。
在任何时刻，算法只保存从根结点到当前扩展结点的路径。
如果解空间树中从根结点到叶结点的最长路径的长度为h（n），则回溯法所需的计算空间通常为（O（h（n））
）。
7.回溯法的算法框架按照问题的解空间一般分为（子集树）算法框架与（排列树）算法框架。
8.用回溯法解0/1背包问题时，该问题的解空间结构为（子集树）结构。
9.用回溯法解批处理作业调度问题时，该问题的解空间结构为（排列树）结构。
10.用回溯法解0/1背包问题时，计算结点的上界的函数如下所示，请在空格中填入合适的内容：
TypepKnap:
:
Bound（inti）
{//计算上界
Typewcleft=c-cw;//剩余容量
Typepb=cp;//结点的上界
//以物品单位重量价值递减序装入物品
while（i<=n&&w[i]<=cleft）{
cleft-=w[i];
b+=p[i];
i++;
}
//装满背包
if（i<=n）（b+=p[i]/w[i]*cleft）;
returnb;
}
11.用回溯法解布线问题时，求最优解的主要程序段如下。
如果布线区域划分为
的方格阵列，扩展每个结点需O
（1）的时间，L为最短布线路径的长度，则算法共耗时（O（mn）），构造相应的最短距离需要（O（L））时间。
for（inti=0;inbr.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））。
BoolColor:
:
OK（intk）
{//
for（intj=1;j<=n;j++）
if（（a[k][j]==1）&&（x[j]==x[k]））returnfalse;
returntrue;
}
13.旅行售货员问题的解空间树是（排列树）。
6.
7.
三、证明题
1.一个分治法将规模为n的问题分成k个规模为n／m的子问题去解。
设分解阀值n0=1，且adhoc解规模为1的问题耗费1个单位时间。
再设将原问题分解为k个子问题以及用merge将k个子问题的解合并为原问题的解需用f（n）个单位时间。
用T（n）表示该分治法解规模为|P|=n的问题所需的计算时间，则有：
通过迭代法求得T（n）的显式表达式为：
试证明T（n）的显式表达式的正确性。
2.举反例证明0/1背包问题若使用的算法是按照pi/wi的非递减次序考虑选择的物品，即只要正在被考虑的物品装得进就装入背包，则此方法不一定能得到最优解（此题说明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））
c32max{f（n）,g（n）}
=2c3h（n）=O（max{f（n）,g（n）}）.
4.求证最优装载问题具有贪心选择性质。
（最优装载问题：
有一批集装箱要装上一艘载重量为c的轮船。
其中集装箱i的重量为Wi。
最优装载问题要求确定在装载体积不受限制的情况下，将尽可能多的集装箱装上轮船。
设集装箱已依其重量从小到大排序，（x1,x2,…,xn）是最优装载问题的一个最优解。
又设
。
如果给定的最优装载问题有解，则有
。
）
证明：
四、解答题
1.机器调度问题。
问题描述：
现在有n件任务和无限多台的机器，任务可以在机器上得到处理。
每件任务的开始时间为si，完成时间为fi，si[si，fi]为处理任务i的时间范围。
两个任务i，j重叠指两个任务的时间范围区间有重叠，而并非指i，j的起点或终点重合。
例如：
区间[1，4]与区间[2，4]重叠，而与[4，7]不重叠。
一个可行的任务分配是指在分配中没有两件重叠的任务分配给同一台机器。
因此，在可行的分配中每台机器在任何时刻最多只处理一个任务。
最优分配是指使用的机器最少的可行分配方案。
问题实例：
若任务占用的时间范围是{[1，4]，[2，5]，[4，5]，[2，6]，[4，7]}，则按时完成所有任务最少需要几台机器？
（提示：
使用贪心算法）
画出工作在对应的机器上的分配情况。
2.已知非齐次递归方程：
，其中，b、c是常数，g（n）是n的某一个函数。
则f（n）的非递归表达式为：
。
现有Hanoi塔问题的递归方程为：
，求h（n）的非递归表达式。
解：
利用给出的关系式，此时有：
b=2,c=1,g（n）=1,从n递推到1，有：
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，且
。
装载问题要求确定是否有一个合理的装载方案可将这n个集装箱装上这2艘轮船。
如果有，找出一种装载方案。
解：
voidbacktrack（inti）
{//搜索第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.用分支限界法解装载问题时，对算法进行了一些改进，下面的程序段给出了改进部分；试说明斜线部分完成什么功能，以及这样做的原因，即采用这样的方式，算法在执行上有什么不同。
//检查左儿子结点
Typewt=Ew+w[i];//左儿子结点的重量
if（wt<=c）{//可行结点
if（wt>bestw）bestw=wt;
//加入活结点队列
if（i}
//检查右儿子结点
if（Ew+r>bestw&&iQ.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。
其它情况下，由最优子结构性质可建立递归关系如下：
在程序中，b[i][j]记录C[i][j]的值是由哪一个子问题的解得到的。
（1）请填写程序中的空格，以使函数LCSLength完成计算最优值的功能。
voidLCSLength（intm，intn，char*x，char*y，int**c，int**b）
{
inti，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;}
elseif（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）中您填写的取值对应，否则视为错误）。
voidLCS（inti，intj，char*x，int**b）
{
if（i==0||j==0）return;
if（b[i][j]==1）{
LCS（i-1，j-1，x，b）;
cout<}
elseif（b[i][j]==2）LCS（i-1，j，x，b）;
elseLCS（i，j-1，x，b）;
}
8.对下面的递归算法，写出调用f（4）的执行结果。
voidf（intk）
{if（k>0）
{printf（"%d\n",k）;
f（k-1）;
f（k-1）;
}
}
一、填空题（20分）
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所需的时间分别为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个或多个输
升级会员 