算法设计与分析复习题目及答案修订稿.docx
《算法设计与分析复习题目及答案修订稿.docx》由会员分享，可在线阅读，更多相关《算法设计与分析复习题目及答案修订稿.docx（26页珍藏版）》请在冰点文库上搜索。
算法设计与分析复习题目及答案修订稿
WEIHUAsystemofficeroom【WEIHUA16H-WEIHUAWEIHUA8Q8-WEIHUA1688】
算法设计与分析复习题目及答案
分治法
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）ANP问题都是不可能解决的问题BP类问题包含在NP类问题中CNP完全问题是P类问题的子集DNP类问题包含在P类问题中
40、背包问题的贪心算法所需的计算时间为（
B）
A、O（n2n）B、O（nlogn）C、O（2n）D、O（n）
42．0-1背包问题的回溯算法所需的计算时间为（
A）
A、O（n2n）B、O（nlogn）C、O（2n）D、O（n）
.
47.背包问题的贪心算法所需的计算时间为（
B）。
A、O（n2n）B、O（nlogn）C、O（2n）D、O（n）
53．采用贪心算法的最优装载问题的主要计算量在于将集装箱依其重量从小到大排序，故算法的时间复杂度为（B）。
A、O（n2n）B、O（nlogn）C、O（2n）D、O（n）
56、算法是由若干条指令组成的有穷序列，而且满足以下性质（D）
（1）输入：
有0个或多个输入
（2）输出：
至少有一个输出
（3）确定性：
指令清晰，无歧义
（4）有限性：
指令执行次数有限，而且执行时间有限
A
（1）
（2）（3）B
（1）
（2）（4）C
（1）（3）（4）D
（1）
（2）（3）（4）
57、函数32n+10nlogn的渐进表达式是（B）.
A.2nB.32nC.nlognD.10nlogn
59、用动态规划算法解决最大字段和问题，其时间复杂性为（B）.
61、设f（N）,g（N）是定义在正数集上的正函数,如果存在正的常数C和自然数N0,使得当N≥N0时有f（N）≤Cg（N）,则称函数f（N）当N充分大时有下界g（N）,记作
f（N）∈○（g（N））,即f（N）的阶（A）g（N）的阶.A.不高于B.不低于C.等价于D.逼近
二、填空题
2、程序是算法用某种程序设计语言的具体实现。
3、算法的“确定性”指的是组成算法的每条指令是清晰的，无歧义的。
6、算法是指解决问题的一种方法或一个过程。
7、从分治法的一般设计模式可以看出，用它设计出的程序一般是递归算法。
11、计算一个算法时间复杂度通常可以计算循环次数、基本操作的频率或计算步。
14、解决0/1背包问题可以使用动态规划、回溯法和分支限界法，其中不需要排序的是动态规划，需要排序的是回溯法，分支限界法。
15、使用回溯法进行状态空间树裁剪分支时一般有两个标准：
约束条件和目标函数的界，N皇后问题和0/1背包问题正好是两种不同的类型，其中同时使用约束条件和目标函数的界进行裁剪的是0/1背包问题，只使用约束条件进行裁剪的是N皇后问题。
30.回溯法是一种既带有系统性又带有跳跃性的搜索算法。
33．回溯法搜索解空间树时，常用的两种剪枝函数为约束函数和限界函数。
34.任何可用计算机求解的问题所需的时间都与其规模有关。
35.快速排序算法的性能取决于划分的对称性。
36.Prim算法利用贪心策略求解最小生成树问题，其时间复杂度是O（n2）。
37.图的m着色问题可用回溯法求解，其解空间树中叶子结点个数是mn，解空间树中每个内结点的孩子数是m。
4.若序列X={B,C,A,D,B,C,D}，Y={A,C,B,A,B,D,C,D}，请给出序列X和Y的一个最长公共子序列{BABCD}或{CABCD}或{CADCD｝。
5.用回溯法解问题时，应明确定义问题的解空间，问题的解空间至少应包含一个（最优）解
背包问题的回溯算法所需的计算时间为__o（n*2n）__,用动态规划算法所需的计算时间为___o（min{nc,2n}_。
二、综合题（50分）
1.写出设计动态规划算法的主要步骤。
①问题具有最优子结构性质；②构造最优值的递归关系表达式；3最优值的算法描述；④构造最优解；
2.流水作业调度问题的johnson算法的思想。
①令N1={i|ai=bi}；②将N1中作业按ai的非减序排序得到N1’，将N2中作业按bi的非增序排序得到N2’；③N1’中作业接N2’中作业就构成了满足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个作业的最优调度方案，并计算最优值。
步骤为：
N1={1，3}，N2={2，4}；
N1’={1，3}，N2’={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=｛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）递归关系表达式为什么？
二叉树T的平均路长P=
+
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.描述0-1背包问题。
已知一个背包的容量为C，有n件物品，物品i的重量为Wi，价值为Vi，求应如何选择装入背包中的物品，使得装入背包中物品的总价值最大。
三、简答题（30分）
1.流水作业调度中，已知有n个作业，机器M1和M2上加工作业i所需的时间分别为ai和bi，请写出流水作业调度问题的johnson法则中对ai和bi的排序算法。
（函数名可写为sort（s,n））
2.最优二叉搜索树问题的动态规划算法（设函数名binarysearchtree））
1.
voidsort（flowjopes[],intn）
{
inti,k,j,l;
for（i=1;i<=n-1;i++）ag!
=0）k++;
if（k>n）break;ag==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;swap（s[i].index,s[k].index）;ag,s[k].tag）;}
}
2.
voidbinarysearchtree（inta[],intb[],intn,int**m,int**s,int**w）
{
inti,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++）
Init-single-source（G,s）
2.S=Φ
3.Q=V[G]
Q<>Φ
dou=min（Q）
S=S∪{u}
foreachvertex3
do4
四、算法理解题（本题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
二、简答题（本题25分，每小题5分）
1、分治法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同；对这k个子问题分别求解。
如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止；将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。
2、“最优化原理”用数学化的语言来描述：
假设为了解决某一优化问题，需要依次作出n个决策D1，D2，…，Dn，如若这个决策序列是最优的，对于任何一个整数k，13、某个问题的最优解包含着其子问题的最优解。
这种性质称为最优子结构性质。
4、回溯法的基本思想是在一棵含有问题全部可能解的状态空间树上进行深度优先搜索，解为叶子结点。
搜索过程中，每到达一个结点时，则判断该结点为根的子树是否含有问题的解，如果可以确定该子树中不含有问题的解，则放弃对该子树的搜索，退回到上层父结点，继续下一步深度优先搜索过程。
在回溯法中，并不是先构造出整棵状态空间树，再进行搜索，而是在搜索过程，逐步构造出状态空间树，即边搜索，边构造。
5、P（Polynomial问题）：
也即是多项式复杂程度的问题。
NP就是Non-deterministicPolynomial的问题，也即是多项式复杂程度的非确定性问题。
NPC（NPComplete）问题，这种问题只有把解域里面的所有可能都穷举了之后才能得出答案，这样的问题是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，则选择单位重量价值次高的物品并尽可能多地装入背包。
依此策略一直地进行下去，直到背包装满为止。
Ø具体算法可描述如下：
voidKnapsack（intn,floatM,floatv[],floatw[],floatx[]）
{Sort（n,v,w）;
inti;
for（i=1;i<=n;i++）x[i]=0;
floatc=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）的递归式如下。
voidKnapSack（intv[],intw[],intc,intn,intm[][11]）
{intjMax=min（w[n]-1,c）;
for（j=0;j<=jMax;j++）/*m（n,j）=00=m[n][j]=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--）
{intjMax=min（w[i]-1,c）;
for（j=0;j<=jMax;j++）/*m（i,j）=m（i+1,j）0=m[i][j]=m[i+1][j];
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（inti）
包问题的贪心算法
voidKnapsack（intn,floatM,floatv[],floatw[],floatx[]）
{
Sort（n,v,w）;
inti;
for（i=1;i<=n;i++）x[i]=0;
floatc=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.最大子段和:
动态规划算法
intMaxSum（intn,inta[]）
{
intsum=0,b=0；速排序
template
voidQuickSort（Typea[],intp,intr）
{
if（pintq=Partition（a,p,r）;
QuickSort（a,p,q-1）;列问题
Template
voidperm（Typelist[],intk,intm）
{定已按升序排好序的n个元素a[0:
n-1]，现要在这n个元素中找出一特定元素x。
据此容易设计出二分搜索算法：
template
intBinarySearch（Typea[],constType&x,intl,intr）
{
while（l<=r）{
intm=（（l+r）/2）;
if（x==a[m]）returnm;
if（x}
return-1;
}
6、合并排序描述如下：
template
voidMergesort（Typea[],intleft,intright）
{
if（leftinti=（left+right）/2;
Mergesort（a,left,i）;
Mergesort（a,i+1,right）;
Merge（a,b,left,i,right）;计算机求解问题的步骤：
1、问题分析2、数学模型建立3、算法设计与选择4、算法指标5、算法分析6、算法实现7、程序调试8、结果整理文档编制
2.算法定义：
算法是指在解决问题时，按照某种机械步骤一定可以得到问题结果的处理过程
3.算法的三要素
1、操作2、控制结构3、数据结构
13.分治法与动态规划法的相同点是：
将待求解的问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。
两者的不同点是：
适合于用动态规划法求解的问题，经分解得到的子问题往往不是互相独立的。
而用分治法求解的问题，经分解得到的子问题往往是互相独立的。
回溯法中常见的两类典型的解空间树是子集树和排列树。
22.请叙述动态规划算法与贪心算法的异同。
共同点：
都需要最优子结构性质，都用来求有优化问题。
不同点：
动态规划：
每一步作一个选择—依赖于子问题的解。
贪心方法：
每一步作一个选择—不依赖于子问题的解。
动态规划方法的条件：
子问题的重叠性质。
可用贪心方法的条件：
最优子结构性质；贪心选择性质。
动态规划：
自底向上求解；贪心方法：
自顶向下求解。
可用贪心法时，动态规划方法可能不适用；可用动态规划方法时，贪心法可能不适用。
23.请说明动态规划方法为什么需要最优子结构性质。
答：
最优子结构性质是指大问题的最优解包含子问题的最优解。
动态规划方法是自底向上计算各个子问题的最优解，即先计算子问题的最优解，然后再利用子问题的最优解构造大问题的最优解，因此需要最优子结构.
24.请说明：
（1）优先队列可用什么数据结构实现？
（2）优先队列插入算法基本思想？
（3）优先队列插入算法时间复杂度？
答：
（1）堆。
（2）在小根堆中，将元素x插入到堆的末尾，
然后将元素x的关键字与其双亲的关键字比较，
若元素x的关键字小于其双亲的关键字，
则将元素x与其双亲交换，然后再将元素x与其新双亲的关键字相比，直到元素x的关键字大于双亲的关键字，或元素x到根为止。
（3）O（logn）
26.在算法复杂性分析中，O、Ω、Θ这三个记号的意义是什么？
在忽略常数因子的情况
下，O、Ω、Θ分别提供了算法运行时间的什么界？
答：
如果存在两个正常数c和N0,对于所有的N≥N0，有|f（N）|≤C|g（N）|，则记作：
f（N）=O（g（N））。
这时我们说f（N）的阶不高于g（N）的阶。
若存在两个正常数C和自然数N0，使得当N≥N0时有|f（N）|≥C|g（N）|，记为f（N）=（
g（N））。
这时我们说f（N）的阶不低于g（N）的阶。
如果存在正常数c1，c2和n0，对于所有的n≥n0，有c1|g（N）|≤|f（N）|≤c2|g（N）|
则记作f（N）=（g,（N）
O、Ω、Θ分别提供了算法运行时间的上界、下界、平均
五、算法设计与分析题
1．用动态规划策略求解最长公共子序列问题：
（1）给出计算最优值的递归方程。
（2）给定两个序列X={B,C,D,A}，Y={A,B,C,B}，请采用动态规划策略求出其最长公共子序列，要求给出过程。
答：
1
（2）
Ｙ Ａ Ｂ Ｃ Ｂ
Ｘ 0 0 0 0
Ｂ 0 0 1 1 1
Ｃ 0 0 1 2 2
Ｄ 0 0122
Ａ 01122最长公共子序列：
｛ＢＣ｝
2．对下列各组函数f（n）和g（n），确定f（n）=O（g（n））或f（n）=Ω（g（n））或f（n）=θ（g（n）），并简要说明理由。
（1）f（n）=2n；g（n）=n!
（2）f（n）=
；g（n）=logn2
（3）f（n）=100；g（n）=log100
（4）f（n）=n3；g（n）=3n
（5）f（n）=3n；g（n）=2n
答：
（1）f（n）=O（g（n
升级会员 