算法设计与分析考试题及

1.一个算法就是一个有穷规则的会合，此中之规则规定认识决某一特殊种类问题的一系列运算，其余，算法还应拥有以下五个重要特性:________,_______,_______,_________,___。___2._______________________

算法的复杂性有

和_

之_

分，权衡一个算法好坏的标准是___________________。__某一问题可用动向规划算法求解的明显特点是若序列X={B,C,A,D,B,C,D}，Y={A,C,B,A,B,D,C,D}，请给出序列X和Y的一个最长公共子序列___________________________。___用回溯法解问题时，应明确立义问题的解空间，问题的解空间最少应包括_________。_6.动向规划算法的基本思想是将待求解问题分解成若干_，_先求解___________，_此后从这些__的_解获取原问题的解。7.________________________________________________以深度优先方式系统找寻问题解的算法称为________________________。_背包问题的回溯算法所需的计算时间为_______________用_,动向规划算法所需的计算时间为__________。_9.动向规划算法的两个基本因素是__________和_______。_二分找寻算法是利用_____________实_现的算法。二、综合题（50分）写出设计动向规划算法的主要步骤。流水作业调动问题的johnson算法的思想。3.若n=4，在机器M1和M2上加工作业i所需的时间分别为ai和bi，且(ai,a2,a3,a4)=(4,5,12,10),(bi,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)，并画出其解空间树，计算其最优值及最优解。设S={Xi,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]={X,Xi+iX}最优值为m[i][j],ijW[i][j]=ai-i+bi++bj+aj,则m[i][j](1＜二i＜二jv二n)递归关系表达式为何描绘0-1背包问题。三、简答题(30分)流水作业调动中,已知有n个作业,机器M1和M2上加工作业i所需的时间分别为a和b，请写出流水作业调动问题的johnson法例中对aiii和bi的排序算法。(函数名可写为sort(s,n))2.最优二叉找寻树问题的动向规划算法(设函数名binarysearchtree))答案：一、填空1．确立性有穷性可行性0个或多个输入一个或多个输出时间复杂性空间复杂性时间复杂度高低该问题拥有最优子结构性质{BABCD}或{CABCD}或{CADCD}一个(最优)解6.子问题子问题子问题回溯法o(n*2n)o(min{nc,2n})9.最优子结构重叠子问题动向规划法二、综合题1?①问题拥有最优子结构性质；②结构最优值的递归关系表达式；③最优值的算法描绘；④结构最优解；2.①令Ni二{i|ai<bi}，N2={i|a>=bi};②将Ni中作业按ai的非减序排序获取Ni'将N2中作业按bi的非增序排序获取N2'③Ni'中作业接N2'中作业就构成了知足Johnson法例的最优调动。3.步骤为：Ni={i，3}，N2={2，4}；Ni'={i，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)}解空间树为:该问题的最优值为：16最优解为：(1,1,0)n5.二叉树T的均匀路长P=i1

nbi*(1Ci)+aj*djj0m[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.已知一个背包的容量为C,有n件物件，物件i的重量为Wi,价值为Vi，求应如何选择装入背包中的物件，使得装入背包中物件的总价值最大。三、简答题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;<s[j].b)k=j;swap(s[i].index,s[k].index);ag,s[k].tag);}}2.voidbinarysearchtree(inta[],intb[],intn,intm,intw)s,int{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)S=①Q=V[G]Q<>①dou=min(Q)S=SU{u}foreachvertex3do4____________四、算法理解题（此题10分）依据优先行列式分支限界法，求以下列图中从v1点到v9点的单源最短路径，请画出求得最优解的解空间树。要求中间被舍弃的结点用X标志，获取中间解的结点用单圆圈O框起，最优解用双圆圈◎框起。五、算法理解题（此题5分）设有n=2k个运动员要进行循环赛，现设计一个知足以下要求的竞赛日程表：①每个选手必然与其余n-1名选手竞赛各一次；②每个选手一天至多只好赛一次；③循环赛要在最短时间内达成。1）若是n=2k，循环赛最少需要进行几日；2）当n=23=8时，请画出循环赛日程表。六、算法设计题（此题15分）分别用贪婪算法、动向规划法、回溯法设计0-1背包问题。要求:说明所使用的算法策略；写出算法实现的主要步骤；分析算法的时间。七、算法设计题（此题10分）经过键盘输入一个高精度的正整数n（n的有效位数w240），去掉此中随意s个数字后，剩下的数字按原左右序次将构成一个新的正整数。编程对给定的n和s,找寻一种方案，使得剩下的数字构成的新数最小。【样例输入】178543S=4【样例输出】13答案：一、填空题(此题15分，每题1分)1．规则一系列运算2.随机存取机RAM(RandomAccessMachine)；随机存取储蓄程序机RASP(RandomAccessStoredProgramMachine)；图灵机(TuringMachine)算法效率时间、空间、时间复杂度、空间复杂度5．2n6．最好局部最精选择7.贪婪选择最优子结构二、简答题(此题25分，每题5分)1、分治法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题，这些子问题相互独立且与原问题同样；对这k个子问题分别求解。若是子问题的规模仍旧不够小，则再区分为k个子问题，这样递归的进行下去，直到问题规模足够小，很简单求出其解为止；将求出的小规模的问题的解归并为一个更大规模的问题的解，自底向上逐渐求出本来问题的解。2

、“最优化原理”用数学化的语言来描绘：假定为认识决某一优化问题，需要挨次作出n个决议D1,D2，，Dn,如若这个决议序列是最优的，关于任何一个整数k，1<k<n，无论前面k个决议是如何的，此后的最优决议只取决于由前面决议所确立的目前状态，即此后的决议Dk+1，Dk+2

，，

Dn

也是最优的。3、某个问题的最优解包括着其子问题的最优解。这类性质称为质。

最优子结构性4、回溯法的基本思想是在一棵含有问题所有可能解的状态空间树进步行深度优先找寻，解为叶子结点。找寻过程中，每抵达一个结点时，则判断该结点为根的子树能否含有问题的解，若是能够确立该子树中不含有问题的解，则放弃对该子树的找寻，退回到上层父结点，连续下一步深度优先找寻过程。在回溯法中，其实不是先结构出整棵状态空间树，再进行找寻，而是在找寻过程，逐渐构造出状态空间树，即边找寻，边结构。5、

NP

P(Polynomial问题)：也即是多项式复杂程度的问题。就是Non-deterministicPolynomial的问题，也即是多项式复杂程度

的非确定性问题。NPC(NPComplete)问题，这类问题只有把解域里面的所有可能都穷举了才能得出答案，这样的问题是NP里面最难的问题，这类问题就是题。三、算法填空(此题20分，每题5分)

此后NPC问1、n后问题回溯算法!M[j]&&!L[i+j]&&!R[i-j+N]M[j]=L[i+j]=R[i-j+N]=1;try(i+1,M,L,R,A)A[i][j]=0M[j]=L[i+j]=R[i-j+N]=02、数塔问题。(1)c<=rt[r][c]+=t[r+1][c]t[r][c]+=t[r+1][c+1]3、Hanoi算法move(a,c)Hanoi(n-1,a,c,b)Move(a,c)4、(1)p[v]=NILp[v]=uv?adj[u]Relax(u,v,w)四、算法理解题(此题10分)123456782143658五、(1)8天(2分)；7(2)当n=23=8时，循环赛日程表(3分)六、算法设计题(此题15分)(1)贪婪算法0(nlog(n))第一计算每种物件单位重量的价值Vi/Wi，此后，依贪婪选择策略，将尽可能多的单位重量价值最高的物件装入背包。若将这类物件所有装入背包可能多地装入背包。依此策略向来地进行下去，直到背包装满为止详细算法可描绘以下：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)动向规划法0(nc)m(i,j)是背包括量为j,可选择物件为i,i+1,，n时0-1背包问题的最优值。由0-1背包问题的最优子结构性质，能够成立计算m(i,j)的递归式以下。max{m(i1,j),m(i1,jwjv}jw：m(i,j)0jWim(i1,j)m(n,j)Vnjwn00jwnvoidKnapSack(intv[],intw[],intc,intn,intm[][11]){intjMax=min(w[n]-1,c);for(j=0;j<=jMax;j++)/*m(n,j)=00=<j<w[n]*/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=<j<w[i]*/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：目前最优值voidbacktrack(inti)回溯法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分)为了尽可能地迫近目标，我们采纳的贪婪策略为：每一步老是选择一个