算法设计和分析试卷与答案.docx

算法设计与分析1、(1)证明：O(f)+O(g)=O(f+g)(7分)求以下函数的渐近表达式：(6分)3n2+10n;21+1/n;2、对于以下各组函数f(n)和g(n),确定f(n)=O(g(n)或f(n)=Q(g(n)或f(n)=(g(n),并简述理由。(15分)/()=logn2;(n)=log+5;/()=IOg;g(n)=n;(3)/5)=，；g()=log2；3、试用分治法对数组An实现快速排序。(13分)4、试用动态规划算法实现最长公共子序列问题。(15分)5、试用贪心算法求解汽车加油问题：一辆汽车加满油后可行驶n公里,而旅途中有假设干个加油站。试设计一个有效算法，指出应在哪些加油站停靠加油，使加油次数最少。(12分)6、试用动态规划算法实现以下问题：设A和B是两个字符串。我们要用最少的字符操作，将字符串A转换为字符串B,这里所说的字符操作包括:删除一个字符。插入一个字符。将一个字符改为另一个字符。将字符串A变换为字符串B所用的最少字符操作数称为字符串A到B的编辑距离，记为d(A,B)°试设计一个有效算法，对任给的两个字符串A和B,计算出它们的编辑距离d(A,B)o(16分)7、试用回溯法解决以下整数变换问题：关于整数/的变换/和定义如T:/=3=1.2jo对于给定的两个整数和机，要求用最少的变换/和g变换次数将变为(16分)1、(l)ffi明：令F(II)=O(f),那么存在自然数m、c1,使得对任意的自然数nn,有：F(n)cf(n)(2分)同理可令G(II)=O值),那么存在自然数112、C2,使得对任意的自然数n2i2,有：G(n)C2g(n)(3分)令C3=maxCl,C2,n3=maxniJl2,那么对所有的IINII3,有:F(n)c1f(n)c3f(n)G(n)c2g(n)c3g(n)(5分)故有：O(f)+O(g)=F(n)+G(n)c3f(n)+c3g(n)=c3(f(n)+g(n)因此有：O(D+O(g)=O(f+g)(7分)(2解:11m(3+K)"f2因为-3/+10由渐近表达式的定义易知：3?是3i?+lOn的渐近表达式。(3分)21H21因为-5->0,"8,由渐近表达式的定义易知：21+-n21是21+'的渐近表达式。(6分)说明：函数T(II)的渐近表达式t(n)定义为:2、解：经分析结论为：logn2=6(log+5);(5分)(2) log"?=O(M);(10分)(3) "=Q(log2");(15分)3、解：用分治法求解的算法代码如下：intpartition(floatAJntp,intr)inti=pj=r+l;floatx=ap;while(l)while(a+i<x);while(a-j>x);if(i>=j)break;aik->aj(4分)；ap=aj;aj=x;returnj;(7分)voidQuicksort(floata,intp,intr)if(p<r)intq=partition(a,p,r);(10分)Quicksort(a,p,q-1);Quicksort(a,q+l,r);)；Quicksort(a,0,n-1);(13分)4、解：用动态规划算法求解的算法代码如下：intlcs-len(char*a,char*b411tcN)(intm=strlen（八）,n=strlen(b)4j；for(i=0;i<=m;i+)ci0=0;for(j=l;j<=ny+)c0j=0;(4分)fbr(i=l;i<=m;i+)fbr(j=lg<=ng+)if(ai-l=bU-l)cij=cl-lO-l+l;elseif(ci-lj>=cij-l)ciU=ci-lj;eisecij=cij-l;(7分)returncmn;(8分)char*buildjcs(chars,char*a,char*b)(intk4=strien（八）j=strIen(b),cNN;k=lcsjen(a,b,c);sk=,O,;while(k>0)if(cij=cM)i.-;(11分)elseif(cij=cij-l)j-;elses-k=ai-l;)returns;(15分)5、解：intgreedy(vecter<int>x411tn)(intsum=OJc=x.size();for(intj=0;j<k;j+)if(xl>n)COUtVv"Nosolutionzz<<endl;return-1;(6分)for(inti=0=0;i<k;i+)s+=xi;if(s>n)sum+;s=xi;(9分)returnsum;(12分)6、解：此题用动态规划算法求解：intdist()(intm=a,size();intn=bsize();vector<int>d(n+1,0);fbr(inti=l;i<=n;i+)di=i;(5分)for(i=l;i<=m;i+)inty=i-l;for(intj=l;j<=n;j+)intx=y;y=dj;intz=j>l?dj-l:i;(10分)mtdel=ai-l=bj-l?O:l;dj=min(x+del,y+l+l);(13分)returndn;（16分）7、解：解答如下：voidcompute()k=l;while(!search(l,n)k+;if(k>maxdep)break;init();；(6分)if(found)output();(9分)elsecout<<zrNoSohition!"<<endl;boolsearch(intdep,intn)(if(dep>k)returnfalse;(11分)for(inti=0;i<2;i+)mtnl=f(n4)；tdep=I;(13分)if(nl=msearch(dep+l,nl)found=true;out();returntrue;returnfalse;(16分)