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

《算法设计和分析试卷与答案.docx》由会员分享，可在线阅读，更多相关《算法设计和分析试卷与答案.docx（5页珍藏版）》请在第壹文秘上搜索。

1、算法设计与分析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公里,而旅途中有假设干个加油站。试设计一个有效算法，指出应在哪些加

2、油站停靠加油，使加油次数最少。(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),

3、那么存在自然数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分)2

4、1H21因为-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+ix);if(i=j)break;aik-aj(4分)；ap=aj;aj=x;returnj;(7分)voidQuicksort(floata,intp,

5、intr)if(pr)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=cij-l)ciU=ci-lj;eisecij=cij-l;(7分)returncmn;(8分

6、)char*buildjcs(chars,char*a,char*b)(intk4=strien（八）j=strIen(b),cNN;k=lcsjen(a,b,c);sk=,O,;while(k0)if(cij=cM)i.-;(11分)elseif(cij=cij-l)j-;elses-k=ai-l;)returns;(15分)5、解：intgreedy(vecterx411tn)(intsum=OJc=x.size();for(intj=0;jn)COUtVvNosolutionzzendl;return-1;(6分)for(inti=0=0;in)sum+;s=xi;(9分)returns

7、um;(12分)6、解：此题用动态规划算法求解：intdist()(intm=a,size();intn=bsize();vectord(n+1,0);fbr(inti=l;i=n;i+)di=i;(5分)for(i=l;i=m;i+)inty=i-l;for(intj=l;jl?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(kmaxdep)break;init();；(6分)if(found)output();(9分)elsecoutzrNoSohition!k)returnfalse;(11分)for(inti=0;i2;i+)mtnl=f(n4)；tdep=I;(13分)if(nl=msearch(dep+l,nl)found=true;out();returntrue;returnfalse;(16分)