《算法设计与分析试卷及答案》由会员分享，可在线阅读，更多相关《算法设计与分析试卷及答案（8页珍藏版）》请在装配图网上搜索。
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)=(g(n)或f(n)=(g(n)，并简述理由。（15分）(1)(2)(3)3、试用分治法对数组An实现迅速排序。（13分）4、试用动态规划算法实现最长公共子序列问题。（15分）5、试用贪心算法求解汽车加油问题：已知一辆汽车加满油后可行驶n公里，而旅途中有若干个加油站。试设计一种有效算法，指出应在哪些加油站停靠加油，使加油次数至少。（12分）6、试用动态规划算法实现下列问题：
2、设A和B是两个字符串。我们要用至少的字符操作，将字符串A转换为字符串B，这里所说的字符操作涉及：(1)删除一种字符。(2)插入一种字符。(3)将一种字符改为另一种字符。将字符串A变换为字符串B所用的至少字符操作数称为字符串A到B的编辑距离，记为d(A,B)。试设计一种有效算法，对任给的两个字符串A和B，计算出它们的编辑距离d(A,B)。（16分）7、试用回溯法解决下列整数变换问题：有关整数的变换和定义如下：。对于给定的两个整数和，规定用至少的变换和变换次数将变为。（16分）1、证明：令F(n)=O(f),则存在自然数n1、c1，使得对任意的自然数nn1，有：F(n)c1f(n).（2分）同理可
3、令G(n)=O(g),则存在自然数n2、c2，使得对任意的自然数nn2，有：G(n)c2g(n).（3分）令c3=maxc1,c2,n3=maxn1,n2,则对所有的nn3，有：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(f)+O(g)=O(f+g).（7分） 解： 由于由渐近体现式的定义易知：3n2是3n2+10n的渐近体现式。.（3分） 由于，由渐近体现式的定义易知：21是的渐近体现式。.（6分）阐明：函数T(n)的渐近体现式t(n)定义为：2、解：经分
4、析结论为：（1）.（5分）（2）；.（10分）（3）；.（15分）3、解：用分治法求解的算法代码如下：int partition(float A,int p,int r)int i=p,j=r+1;float x=ap;while(1)while(a+ix);if(i=j) break;aiaj.（4分）;ap=aj;aj=x;return j;.（7分）void Quicksort(float a,int p,int r)if(pr)int q=partition(a,p,r);.（10分）Quicksort(a,p,q-1);Quicksort(a,q+1,r);Quicksort(a,0
5、,n-1);.（13分）4、解：用动态规划算法求解的算法代码如下：int lcs_len(char* a,char* b,int cN)int m=strlen(a),n=strlen(b),i,j;for(i=0;i=m;i+)ci0=0;for(j=1;j=n;j+)c0j=0;.（4分）for(i=1;i=m;i+)for(j=1;j=cij-1)cij=ci-1j;elsecij=cij-1;.（7分）return cmn;.（8分）;char* build_lcs(char s,char* a,char* b)int k,i=strlen(a),j=strlen(b),cNN;k=l
6、cs_len(a,b,c);sk=0;while(k0)if(cij=ci-1j)i-;.（11分）else if(cij=cij-1)j-;elses-k=ai-1;i-,j-;return s;.（15分）5、解：int greedy(vecter x,int n)int sum=0,k=x.size();for(int j=0;jn)cout”Nosolution”endl;return-1;.（6分）for(int i=0,s=0;in)sum+;s=xi;.（9分）return sum;.（12分）6、解：此题用动态规划算法求解：int dist()int m=a.size();in
7、t n=b.size();vector d(n+1,0);for(int i=1;i=n;i+)di=i;.（5分）for(i=1;i=m;i+)int y=i-1;for(int j=1;j1?dj-1:i;.（10分）int del=ai-1=bj-1?0:1;dj=min(x+del,y+1,z+1);.（13分）return dn;.（16分）7、解：解答如下：void compute()k=1;while(!search(1,n)k+;if(kmaxdep)break;init();.（6分）if(found)output();.（9分）else cout”NoSolution!”k)return false;.（11分）for(int i=0;i2;i+)int n1=f(n,i);tdep=I;.（13分）if(n1=m|search(dep+1,n1)found=true;out();return true;return false;.（16分）
算法设计与分析试卷及答案
