《算法设计与分析试卷及答案(共8页).doc》由会员分享,可在线阅读,更多相关《算法设计与分析试卷及答案(共8页).doc(8页珍藏版)》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
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)c
3、1f(n).(2分)同理可令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
4、(n)定义为:2、解:经分析结论为:(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);
5、Quicksort(a,0,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=strl
6、en(b),cNN;k=lcs_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
7、m=a.size();int 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分)专心-专注-专业