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

1、一、填空题（20分）1 .一个算法确实是一个有穷规那么的集合，其中之规那么规定了解决某一特殊类型问题的一系列运算，另外，算法还应具有以下五个重耍特性:,。2 .算法的复杂性有和之分，衡量一个算法好坏的标准是o3 .某一问题可用动态计划算法求解的显著特点是4 .假设序列X=B,C,A,D,B,C,D,Y=A,C,B,A,B,D,C,D,请给出序列X和Y的一个最长公共子序列o5 .用回溯法解问题时，应明肯概念问题的解空间，问题的解空间至少应包括O6 .动态计划算法的大体思想是将待求解问题分解成假设干，先求解,然后从这些的解取得原问题的解。7 .以深度优先方式系统搜索问题解的算法称为o背包问题的回溯

2、算法所需的计算时刻为，用动态计划算法所需的计算时刻为O9 .动态计划算法的两个大体要素是和。10 .二分搜索算法是利用实现的算法。二、综合题（50分）1 .写出设计动态计划算法的要紧步骤。2 .流水作业调度问题的johnson算法的思想。3 .假设n=4,在机械Ml和M2上加工作业i所需的时刻别离为a：和*且(ai,a2,a3,a,)=(4,5,12,10),(bbb2,b3,b,)=(8,2,15,9)求4个作业的最优调度方案，并计算最优值。4 .利用回溯法解0/1背包问题：n=3,C=9,V=6,10,3,W=3,4,4),其解空间有长度为3的0-1向量组成，要求用一棵完全二叉树表示其解空

3、间(从根动身，左1右0),并画出其解空间树，计算其最优值及最优解。5 .设S=X1，X2,XJ是严格递增的有序集，利用二叉树的结点来存储S中的元素，在表示S的二叉搜索树中搜索一个元素X,返回的结果有两种情形，(1)在二叉搜索树的内结点中找到X二X：,其概率为b1O(2)在二叉搜索树的叶结点中确信Xe(X,X-),其概率为a10在表示S的二叉搜索树T中，设存储元素&的结点深度为C；叶结点(无，X.)的结点深度为&,那么二叉搜索树T的平均路长p为多少?假设二叉搜索树,XJ最优值为Wij=ai-i+bi+bj+aj,那么mij(l=i=j=n)递归关系表达式什么缘故？6 .描述0-1背包问题。三、简

4、答题(30分)1 .流水作业调度中，已知有n个作业，机械Ml和M2上加工作业i所需的时刻别离为a和h,请写出流水作业调度问题的johnson法那么中对电和瓦的排序算法。(函数名可写为sort(s,n)2 .最优二叉搜索树问题的动态计划算法(设函数名binarysearchtree)答案：一、填空L确信性有穷性可行性0个或多个输入一个或多个输出3 .时刻复杂性空间复杂性时刻复杂度高低4 .该问题具有最优子结构性质5 .BABCD或CABCD或CADCD6 .一个(最优)解7 .子问题子问题子问题8 .回溯法9 .o(n*2n)o(minnc,2n)10 最优子结构重叠子问题11 .动态计划法二、

5、综合题1 .问题具有最优子结构性质；构造最优值的递归关系表达式；最优值的算法描述；构造最优解；2 .令N尸i|abj,N2=ia=bj；将NI中作业按区的非减序排序取得工，将N?中作业按b,的非增序排序取得帅；NJ中作业接NJ中作业就组成了知足Johnson法那么的最优调度。3 .步骤为：N1=1,3,N2=2,4；NJ=1,3,NJ=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,l)o解空间树为:最优解为:0)(1, 1,16该问题的最优值为:5 .二叉树T的平均路长P=fbi*(

6、l+Ci)+aj*djr-1y=Omij=Wij+minmik+mk+lj(l=i=jj)6 .已知一个背包的容量为C,有n件物品，物品i的重量为肌，价值为匕，求应如何选择装入背包中的物品，使得装入背包中物品的总价值最大。三、简答j1.voidsort(flowjopes,intn)inti,k,jj;for(i=1;in)break;ag=O)if(sk.asj.a)k=j;swap(si.index,sk.index);swap(si.tag,sk.tag);)l=i;sj.b)k=j;swap(si.index,sk.index);ag,sk.tag);)voidbinarysearch

7、tree(inta,intb,intnjnt*m,int*w)(intfor(i=l;i=n+l;i+)fOr(l=0J=n-1*l+)HanoiHanoiInit-single-2. S二中3. Q二VQO中dou=min(Q)S=SUuforeachvertexdo4四、算法明白得题（此题10分）根据优先队列式分支限界法，求以下图中从V1点到V9点的单源最短途径，请画出求得最优解的解空间树。要求中间被舍弃的结点用X标记，取得中间解的结点用单圆圈O框起，最优解用双圆圈框起。五、算法明白得题（此题5分）设有1】=2卜个运动员要进行循环赛，现设计一个知足以下要求的竞赛日程表：每一个选手必需与其他

8、n-1名选手竞赛各一次:每一个选手一天最多只能赛一次；循环赛要在最短时刻内完成。（1）若是n=2,循环赛最少需要进行几天:（2）当n=23=8时，请画出循环赛日程表。六、算法设计题（此题15分）别离用贪婪算法、动态计划法、回溯法设计0-1背包问题.要求：说明所利用的算法策略：写出算法实现的要紧步骤：分析算法的时刻。七、算法设计题（此题10分）通过键盘输入一个高精度的正整数n（n的有效位数W240）,去掉其中任意s个数字后，剩下的数字按原左右顺序将组成一个新的正整数。编程对给定的n和s,寻觅一种方案，使得剩下的数字组成的新数最小，【样例输入】178543S=4【样例输出】13一、填空题（此题15

9、分，每题1分）1 .规那么一系列运算2 .随机存取机RAM（RandomAccessMachine）；随机存取存储程序机RASP（RandomAccessStoredProgramMachine）：图灵机（TuringMachine）3 .算法效率4 .时刻、空间、时刻复杂度、空间复杂度5 .2n6 .最好局部最优选择7 .贪婪选择最优子结构二、简答题(此题25分，每题5分)1、分治法的大体思想是将一个规模为n的问题分解为k个规模较小的子问题，这些子问题相互独立且与原问题相同：对这k个子问题别离求解。若是子问题的规模仍然不够小，那么再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很

10、容易求出其解为止：将求出的小规模的问题的解归并为一个更大规模的问题的解，自底向上慢慢求出原先问题的解。2、“最优化原理”用数学化的语言来描述：假设为了解决某一优化问题，需要依次作出n个决策DI,D2,.Dn,如假设那个决策序列是最优的，关于任何一个整数k,lkn,不论前面k个决策是如何的，以后的最优决策只取决于由前面决策所确信的当前状态,即以后的决策Dk+1,Dk+2,，Dn也是最优的。3、某个问题的最优解包括着其子问题的最优解。这种性质称为最优子结构性质、4、回溯法的大体思想是在一棵含有问题全数可能解的状态空间树上进行深度优先搜索，解为叶子结点。搜索进程中，每抵达一个结点时，那么判定该结点为

11、根的子树是不是含有问题的解，若是能够确信该子树中不含有问题的解，那么舍弃对该子树的搜索，退回到上层父结点，继续下一步深度优先搜索进程。在回溯法中，并非是先构造出整棵状态空间树，再进行搜索，而是在搜索进程，慢慢构造出状态空间树，即边搜索，边构造。5、P(Polynomial问题)：也即是多项式复杂程度的问题。NP确实是Non-deterministicPolynomial的问题，也即是多项式复杂程度的非确信性问题。NPC(NPComplete)问题，这种问题只有把解域里面的所有可能都穷举了以后才能得出答案，如此的问题是NP里面最难的问题，这种问题确实是NPC问题。三、算法填空(此题20分，每题5

12、分)一、n后问题回溯算法(1) !Mj&!Li+j&!Ri-j+N(2) Mj=Li+j=Ri-j+N=l;(3) try(i+l,M,L,R,A)(4) Aij=O(5) Mj=Li+j=Ri-j+N=O二、数塔问题。(1) c=r(2)trc+=tr+lc(3) trc+=tr+1c+13、Hanoi算法(1) move(a,c)(2) Hanoi(n-1,a,c,b)(3) Move(a,c)4、(1)pv=NIL(2) pv=u(3) vGadju(4) Relax(u,v,w)四、算法明白得题(此题10分)五、（1）8天（2分）：（2）当n=23=8时,循环赛日程表（3分）。六、算法

13、设计题（此题15分）（1）贪婪算法O（nlog（n）1234567 82 14365 8734 127 8 5 6432 187655 67 8123465 872 1437 85 634 12876543 2 1第一计算每种物品单位重量的价值Vi/Wi,然后，依贪婪选择策略，将尽可能多的单位重量价值最高的物品装入背包。假设将这种物品全数装入背包后，背包内的物品总重量未超过C,那么选择单位重量价值次高的物品并尽可能多地装入背包，依此策略一直地进行下去，直到背包装满为止。具体算法可描述如下：voidKnapsack(intn.floatM,floatv(,floatw(.floatx)Sort(

14、iLV,w);inti;for(i=l;i=n;i+)xi=0;floatc=M;for(i=l;ic)break;xi=l；c-=wi;)if(i=n)xi=c/wi;)(2)动态计划法O(nc)m(i,j)是背包容量为j,可选择物品为i,i+1,，n时0-1背包问题的最优值。由0背包问题的最优子结构性质，能够成立计算m(i,j)的递归式如下。max+L/),(，+1Jwf)+匕”吗7。，/)=4m(i+1,/)0jwzynJno0jwnvoidKnapSack(intv4ntwJntc,intn,intmll)intjMax=min(wn-l,c);for(j=O;j=jMax;j+)/*

15、m(nJ)=00=jwn*/for(j=wn;j=wn*/mnj=vn;for(i=n-l;il;i-jintjMax=min(wi-1x);for(j=O;j=jMax;j+)/*m(ij)=m(i+lj)0=jwi*/for(j=wi;j=wn*/mi|j=inax(mi+lj,mi+lj-wi+vi);)mlc=m2c;if(c=wl)mlc=max(mlc,m|2c-wl+vl);)(3)回溯法0(2)cw:当前重量cp:当前价值bestp：当前最优值voidbacktrack(inti)回溯法i初值1if(in)抵达叶结点bestp=cp;return:if(cw+wibestp)搜索右子树backtrack(i+l);七、算