算法设计与分析考试题目与答案.doc

- -?算法分析与设计?期末复习题一、 选择题1.应用Johnson法那么的流水作业调度采用的算法是DA. 贪心算法 B. 分支限界法 C.分治法 D. 动态规划算法2.Hanoi塔问题如下列图所示。现要求将塔座A上的的所有圆盘移到塔座B上，并仍按同样顺序叠置。移动圆盘时遵守Hanoi塔问题的移动规那么。由此设计出解Hanoi塔问题的递归算确的为：BA. void hanoi(int n, int A, int C, int B) if (n > 0) hanoi(n-1,A,C, B); move(n,a,b); hanoi(n-1, C, B, A); Hanoi塔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. 动态规划算法的根本要素为CA. 最优子构造性质与贪心选择性质B重叠子问题性质与贪心选择性质C最优子构造性质与重叠子问题性质D. 预排序与递归调用4. 算法分析中，记号O表示B， 记号表示A， 记号表示D。A.渐进下界B.渐进上界C.非紧上界D.紧渐进界E.非紧下界5. 以下关于渐进记号的性质是正确的有：AA.B.C. O(f(n)+O(g(n) = O(minf(n),g(n) D. 6. 能采用贪心算法求最优解的问题，一般具有的重要性质为：AA. 最优子构造性质与贪心选择性质B重叠子问题性质与贪心选择性质C最优子构造性质与重叠子问题性质D. 预排序与递归调用7. 回溯法在问题的解空间树中，按D策略，从根结点出发搜索解空间树。A 广度优先 B. 活结点优先 C.扩展结点优先 D. 深度优先8. 分支限界法在问题的解空间树中，按A策略，从根结点出发搜索解空间树。 A 广度优先 B. 活结点优先 C.扩展结点优先 D. 深度优先9. 程序块A是回溯法中遍历排列树的算法框架程序。void backtrack (int t) if (t>n) output(x); else for (int i=t;i<=n;i+) swap(xt, xi); if (legal(t) backtrack(t+1); swap(xt, xi); A.void backtrack (int t) if (t>n) output(x); else for (int i=0;i<=1;i+) xt=i; if (legal(t) backtrack(t+1); B. void backtrack (int t) if (t>n) output(x); else for (int i=0;i<=1;i+) xt=i; if (legal(t) backtrack(t-1); C.D.void backtrack (int t) if (t>n) output(x); else for (int i=t;i<=n;i+) swap(xt, xi); if (legal(t) backtrack(t+1); 10. 回溯法的效率不依赖于以下哪一个因素？C A. 产生xk的时间；B. 满足显约束的xk值的个数；C. 问题的解空间的形式；D. 计算上界函数bound的时间；E. 满足约束函数和上界函数约束的所有xk的个数。F. 计算约束函数constraint的时间；11. 常见的两种分支限界法为DA. 广度优先分支限界法与深度优先分支限界法；B. 队列式FIFO分支限界法与堆栈式分支限界法；C. 排列树法与子集树法；D. 队列式FIFO分支限界法与优先队列式分支限界法；12. k带图灵机的空间复杂性S(n)是指BA. k带图灵机处理所有长度为n的输入时，在某条带上所使用过的最大方格数。B. k带图灵机处理所有长度为n的输入时，在k条带上所使用过的方格数的总和C. 。C. k带图灵机处理所有长度为n的输入时，在k条带上所使用过的平均方格数。D. k带图灵机处理所有长度为n的输入时，在某条带上所使用过的最小方格数。13. NP类语言在图灵机下的定义为DA. 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使得对所有nn0有：0 f(n) cg(n) ；B. O(g(n) = f(n) | 存在正常数c和n0使得对所有nn0有：0 cg(n) f(n) ；C. O(g(n) = f(n) | 对于任何正常数c>0，存在正数和n0 >0使得对所有nn0有：0 f(n)<cg(n) ；D. O(g(n) = f(n) | 对于任何正常数c>0，存在正数和n0 >0使得对所有nn0有：0 cg(n) < f(n) ；15. 记号的定义正确的选项是B。A. O(g(n) = f(n) | 存在正常数c和n0使得对所有nn0有：0 f(n) cg(n) ；B. O(g(n) = f(n) | 存在正常数c和n0使得对所有nn0有：0 cg(n) f(n) ；C. (g(n) = f(n) | 对于任何正常数c>0，存在正数和n0 >0使得对所有nn0有：0 f(n)<cg(n) ；D. (g(n) = f(n) | 对于任何正常数c>0，存在正数和n0 >0使得对所有nn0有：0 cg(n) < f(n) ；二、 填空题1. 下面程序段的所需要的计算时间为 。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+=aj;if(thissum>sum)sum=thissum;besti=i;bestj=j;return sum;2. 有11个待安排的活动，它们具有下表所示的开场时间与完毕时间，如果以贪心算法求解这些活动的最优安排即为活动安排问题：在所给的活动集合中选出最大的相容活动子集合，得到的最大相容活动子集合为活动 1，4，8，11 。1413121110987654fi122886535031Si1110987654321i3. 所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来到达。4. 所谓最优子构造性质是指问题的最优解包含了其子问题的最优解。5. 回溯法是指具有限界函数的深度优先生成法。6. 用回溯法解题的一个显著特征是在搜索过程中动态产生问题的解空间。在任何时刻，算法只保存从根结点到当前扩展结点的路径。如果解空间树 中从根结点到叶结点的最长路径的长度为h(n)，那么回溯法所需的计算空间通常为O(h(n)。7. 回溯法的算法框架按照问题的解空间一般分为子集树算法框架与排列树算法框架。8. 用回溯法解0/1背包问题时，该问题的解空间构造为子集树构造。9.用回溯法解批处理作业调度问题时，该问题的解空间构造为排列树构造。10.用回溯法解0/1背包问题时，计算结点的上界的函数如下所示，请在空格中填入适宜的容：Typep Knap<Typew, Typep>:Bound(int i)/ 计算上界 Typew cleft = c - cw; / 剩余容量 Typep b = cp; / 结点的上界 / 以物品单位重量价值递减序装入物品 while (i <= n && wi <= cleft) cleft -= wi; b += pi; i+; / 装满背包 if (i <= n) b += pi/wi * cleft; return b;11. 用回溯法解布线问题时，求最优解的主要程序段如下。如果布线区域划分为的方格阵列，扩展每个结点需O(1)的时间，L为最短布线路径的长度，那么算法共耗时 ( O(mn) )，构造相应的最短距离需要O(L)时间。for (int i = 0; i < NumOfNbrs; i+) nbr.row = here.row + offseti.row; nbr.col = here.col + offseti.col; if (gridnbr.rownbr.col = 0) / 该方格未标记 gridnbr.rownbr.col = gridhere.rowhere.col + 1; if (nbr.row = finish.row) && (nbr.col = finish.col) break; / 完成布线 Q.Add(nbr); 12. 用回溯法解图的m着色问题时，使用下面的函数OK检查当前扩展结点的每一个儿子所相应的颜色的可用性，那么需耗时渐进时间上限Omn。Bool Color:OK(int k)/ for(int j=1;j<=n;j+)if(akj= =1)&&(xj= =xk) return false;return true;13. 旅行售货员问题的解空间树是排列树。6.7.三、 证明题1. 一个分治法将规模为n的问题分成k个规模为nm的子问题去解。设分解阀值n0=1，且adhoc解规模为1的问题消耗1个单位时间。再设将原问题分解为k个子问题以及用merge将k个子问题的解合并为原问题的解需用f(n)个单位时间。用T(n)表示该分治法解规模为|P|=n的问题所需的计算时间，那么有：通过迭代法求得Tn的显式表达式为：试证明Tn的显式表达式的正确性。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(maxf(n),g(n) 。证明：对于任意f1(n) O(f(n) ，存在正常数c1和自然数n1，使得对所有nn1，有f1(n) c1f(n) 。类似地，对于任意g1(n) O(g(n) ，存在正常数c2和自然数n2，使得对所有nn2，有g1(n) c2g(n) 。令c3=maxc1, c2， n3 =maxn1, n2，h(n)= maxf(n),g(n) 。那么对所有的 n n3，有f1(n) +g1(n) c1f(n) + c2g(n) c3f(n) + c3g(n)= c3(f(n) + g(n) c32 maxf(n),g(n)= 2c3h(n) = O(maxf(n),g(n) .4. 求证最优装载问题具有贪心选择性质。最优装载问题：有一批集装箱要装上一艘载重量为c的轮船。其中集装箱i的重量为Wi。最优装载问题要求确定在装载体积不受限制的情况下，将尽可能多的集装箱装上轮船。设集装箱已依其重量从小到大排序，(x1,x2,xn)是最优装载问题的一个最优解。又设。如果给定的最优装载问题有解，那么有。证明：四、 解答题1. 机器调度问题。问题描述：现在有n件任务和无限多台的机器，任务可以在机器上得到处理。每件任务的开场时间为si，完成时间为fi，si<fi 。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到其它顶点间最短路径。请将此过程填入下表中。432110030maxint10-1初始dist5dist4dist3dist2uS迭代4. 请写出用回溯法解装载问题的函数。装载问题：有一批共n个集装箱要装上2艘载重量分别为c1和c2的轮船，其中集装箱i的重量为wi，且。装载问题要求确定是否有一个合理的装载方案可将这n个集装箱装上这2艘轮船。如果有，找出一种装载方案。解：void backtrack (int i) / 搜索第i层结点if (i > n) / 到达叶结点更新最优解bestx,bestw;return; r -= wi;if (cw + wi <= c) / 搜索左子树 xi = 1; cw += wi;backtrack(i + 1); cw -= wi; if (cw + r > bestw) xi = 0; / 搜索右子树backtrack(i + 1); r += wi;5. 用分支限界法解装载问题时，对算法进展了一些改良，下面的程序段给出了改良局部；试说明斜线局部完成什么功能，以及这样做的原因，即采用这样的方式，算法在执行上有什么不同。/ 检查左儿子结点 Type wt = Ew + wi; / 左儿子结点的重量 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的最长公共子序列。由最长公共子序列问题的最优子构造性质建立子问题最优值的递归关系。用cij记录序列Xi和Yj的最长公共子序列的长度。其中， Xi=x1,x2,xi；Yj=y1,y2,yj。当i=0或j=0时，空序列是Xi和Yj的最长公共子序列。故此时Cij=0。其它情况下，由最优子构造性质可建立递归关系如下：在程序中，bij记录Cij的值是由哪一个子问题的解得到的。（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+) ci0 = 0; for (i = 1; i <= n; i+) c0i = 0; for (i = 1; i <= m; i+) for (j = 1; j <= n; j+) if (xi=yj) cij=ci-1j-1+1; bij=1;else if (ci-1j>=cij-1) cij=ci-1j; bij=2; else cij=cij-1; bij=3; （2） 函数LCS实现根据b的容打印出Xi和Yj的最长公共子序列。请填写程序中的空格，以使函数LCS完成构造最长公共子序列的功能请将bij的取值与1中您填写的取值对应，否那么视为错误。void LCS(int i，int j，char *x，int *b) if (i =0 | j=0) return; if (bij= 1) LCS(i-1，j-1，x，b); cout<<xi; else if (bij= 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("%dn ",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在二叉搜索树的叶结点中确定XXi，Xi+1，其概率为ai。在表示S的二叉搜索树T中，设存储元素Xi的结点深度为Ci；叶结点Xi，Xi+1的结点深度为di，那么二叉搜索树T的平均路长p为多少？假设二叉搜索树Tij=Xi，Xi+1，···，Xj最优值为mij，Wij= ai-1+bi+···+bj+aj，那么mij(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个或多个输入 一个或多个输出2.时间复杂性 空间复杂性 时间复杂度上下 3. 该问题具有最优子构造性质 4.BABCD或CABCD或CADCD 5.一个最优解 6.子问题 子问题 子问题 7.回溯法 8. o(n*2n) o(minnc,2n)9.最优子构造 重叠子问题10.动态规划法二、综合题1.问题具有最优子构造性质；构造最优值的递归关系表达式； 最优值的算法描述；构造最优解；2. 令N1=i|ai<bi，N2=i|ai>=bi；将N1中作业按ai的非减序排序得到N1，将N2中作业按bi的非增序排序得到N2；N1中作业接N2中作业就构成了满足Johnson法那么的最优调度。3.步骤为：N1=1，3，N2=2，4；N1=1，3， N2=4，2；最优值为：384.解空间为(0,0,0),(0,1,0),(0,0,1),(1,0,0),(0,1,1),(1,0,1),(1,1,0),(1,1,1)。解空间树为：ABCFEDGKJIHONML11100001011010该问题的最优值为：16 最优解为：1，1，05.二叉树T的平均路长P=+mij=Wij+minmik+mk+1j (1<=i<=j<=n,mii-1=0)mij=0 (i>j)6.一个背包的容量为C，有n件物品，物品i的重量为Wi，价值为Vi，求应如何选择装入背包中的物品，使得装入背包中物品的总价值最大。三、简答题1.void sort(flowjope s,int n) int i,k,j,l; for(i=1;i<=n-1;i+)/-选择排序 k=i; while(k<=n&&sk.tag!=0) k+; if(k>n) break;/-没有ai，跳出 else for(j=k+1;j<=n;j+) if(sj.tag=0) if(sk.a>sj.a) k=j; swap(si.index,sk.index); swap(si.tag,sk.tag); l=i;/-记下当前第一个bi的下标 for(i=l;i<=n-1;i+) k=i; for(j=k+1;j<=n;j+) if(sk.b<sj.b) k=j; swap(si.index,sk.index); /-只移动index和tag swap(si.tag,sk.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+) wii-1=ai-1; mii-1=0; for(l=0;l<=n-1;l+)/-l是下标j-i的差for(i=1;i<=n-l;i+) j=i+l;wij=wij-1+aj+bj;mij=mii-1+mi+1j+wij;sij=i;for(k=i+1;k<=j;k+) t=mik-1+mk+1j+wij;if(t<mij) mij=t;sij=k;一、 填空题此题15分，每题1分1、 算法就是一组有穷的，它们规定了解决某一特定类型问题的 。2、 在进展问题的计算复杂性分析之前，首先必须建立求解问题所用的计算模型。3个根本计算模型是、。3、 算法的复杂性是的度量，是评价算法优劣的重要依据。4、 计算机的资源最重要的是和资源。因而，算法的复杂性有和之分。5、 f(n)= 6×2n+n2，f(n)的渐进性态f(n)= O(   )6、 贪心算法总是做出在当前看来的选择。也就是说贪心算法并不从整体最优考虑，它所做出的选择只是在某种意义上的。7、 许多可以用贪心算法求解的问题一般具有2个重要的性质：性质和性质。二、简答题此题25分，每题5分1、 简单描述分治法的根本思想。2、 简述动态规划方法所运用的最优化原理。3、 何谓最优子构造性质？4、 简单描述回溯法根本思想。5、 何谓P、NP、NPC问题三、算法填空此题20分，每题5分1、n后问题回溯算法(1)用二维数组ANN存储皇后位置,假设第i行第j列放有皇后,那么Aij为非0值,否那么值为0。(2)分别用一维数组MN、L2*N-1、R2*N-1表示竖列、左斜线、右斜线是否放有棋子，有那么值为1,否那么值为0。for(j=0;j<N;j+) if( 1 ) /*平安检查*/ Aij=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( tr+1c>tr+1c+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算法求单源最短路径du:s到u的距离 pu:记录前一节点信息Init-single-source(G,s)for each vertex vVG do dv=; 1 ds=0Relax(u,v,w)if dv>du+w(u,v)then dv=du+wu,v; 2 dijkstra(G,w,s)1. Init-single-source(G,s) 2. S=3. Q=VG4.while Q<> do u=min(Q) S=Su for each vertex 3 do 4 四、算法理解题此题10分根据优先队列式分支限界法，求下列图中从v1点到v9点的单源最短路径，请画出求得最优解的解空间树。要求中间被舍弃的结点用×标记，获得中间解的结点用单圆圈框起，最优解用双圆圈框起。五、算法理解题此题5分设有n=2k个运发动要进展循环赛，现设计一个满足