算法设计与分析试卷及答案[001]

1、算法设计与分析1、(1)证明：O(f)+O(g)=O(f+g)(7分)(2)求下列函数的渐近表达式：(6分) 3n2+10n; 21+1/n;2、对于下列各组函数f(n)和g(n),确定f(n)=O(g(n)或f(n)=Q(g(n)或f(n)=0(g(n),并简述理由。(15分)(1)f(n)2logn;g(n)logn5;f(n)logn2;g(n)、n;f(n)n;g(n)log2n;3、试用分治法对数组An实现快速排序。(13分)4、试用动态规划算法实现最长公共子序列问题。(15分)5、试用贪心算法求解汽车加油问题：已知一辆汽车加满油后可行驶n公里，而旅途中有若干个加油站。试设计一个有效

2、算法，指出应在哪些加油站停靠加油，使加油次数最少。(12分)6、试用动态规划算法实现下列问题：设A和B是两个字符串。我们要用最少的字符操作，将字符串A转换为字符串B,这里所说的字符操作包括：(1) 删除一个字符。(2) 插入一个字符。(3) 将一个字符改为另一个字符。将字符串A变换为字符串B所用的最少字符操作数称为字符串A到B的编辑距离，记为d(A,B)。试设计一个有效算法，对任给的两个字符串A和B,计算出它们的编辑距离d(A,B)。(16分)7、试用回溯法解决下列整数变换问题：关于整数i的变换f和g定义如下：f(i)3i;g(i)i/2。对于给定的两个整数n和m，要求用最少的变换f和g变换次

3、数将n变为m。(16分)1、(1)证明：令F(n)=0,则存在自然数ni、ci,使得对任意的自然数n>ni,有：F(n)wcif(n).(2分)同理可令G(n)=O(g)则存在自然数n2、C2,使得对任意的自然数nn2,有：G(n)<C2g(n).(3分)令C3=maxci,C2,n3=maxni,n2，则对所有的nn3,有：F(n)wcif(n)Wc3f(n)G(n)<C2g(n)wag(n).(5分)故有：O(f)+O(g)=F(n)+G(n)<c3f(n)+C3g(n)=c3(f(n)+g(n)因此有：O(f)+O(g)=O(f+g).(7分)解：(3n210n)

4、3n2nlim20;因为n3n10n由渐近表达式的定义易知：3n2是3n2+10n的渐近表达式。.(3分)12121因为亍0,n，由渐近表达式的定义易知:21-n.(6分)21是211的渐近表达式nT(n)t(n)0,n说明：函数T(n)的渐近表达式t(n)定义为:T(n)2、解：经分析结论为:(1)logn2(logn5);(5分)logn2Cn)(10分)(3)n(log2n)(15分)3、解：用分治法求解的算法代码如下：intpartition(floatA,intp,intr)inti=p,j=r+1;floatx=ap;while(1)while(a+i<x);while(a-

5、j>x);if(i>=j)break;aiaj.(4分);ap=aj;aj=x;returnj;.(7分)voidQuicksortfloata,intp,intr)if(p<r)intq=partition(a,p,r);.(10分)Quicksort(a,p,q-1);Quicksort(a,q+1,r);Quicksort(a,0,n-1);.(13分)4、解：用动态规划算法求解的算法代码如下：intlcs_len(char*a,char*b,intcN)intm=strlen(a),n=strlen(b),i,j;for(i=0;i<=m;i+)ci0=0;fo

6、r(j=1;j<=n;j+)c0j=0;.(4分)for(i=1;i<=m;i+)for(j=1;j<=n;j+)if(ai-1=bj-1)cij=ci-1j-1+1;elseif(ci-1j>=cij-1)cij=ci-1j;elsecij=cij-1;.(7分)returncmn;.(8分);char*build_lcs(chars,char*a,char*b)intk,i=strlen(a),j=strlen(b),cNN;k=lcs_len(a,b,c);sk='0'while(k>0)if(cij=ci-1j)i-;.(11分)elsei

7、f(cij=cij-1)j-;elses-k=ai-1;i-,j-;returns;.(15分)5、解：intgreedy(vecter<int>x,intn)intsum=0,k=x.size();for(intj=0;j<k;j+)if(xj>n)cout<<”Nosolution”<<endl;return-1;.(6分)for(inti=0,s=0;i<k;i+)s+=xi;if(s>n)sum+;s=xi;.(9分)returnsum;.(12分)6、解：此题用动态规划算法求解：intdist()intm=a.size();

8、intn=b.size();vector<int>d(n+1,0);for(inti=1;i<二n;i+)di=i;.(5分)for(i=1;i<=m;i+)inty=i-1;for(intj=1;j<=n;j+)intx=y;y=dj;intz=j>1?dj-1:i;.(10分)intdel=ai-1=bj-1?0:1;dj=min(x+del,y+1,z+1);.(13分)returndn;.(16分)7、解：解答如下：voidcompute()k=1;while(!search(1,n)k+;if(k>maxdep)break;init();；.(6分)if(found)output();.(9分)elsecout<<”NoSolution!”<<endl;boolsearch(intdep,intn)if(dep>k)retu