算法设计和分析试题(卷)与答案解析

算法设计和分析试题(卷)与答案解析

ID:20365557

大小:56.00 KB

页数:8页

时间:2018-10-12

算法设计和分析试题(卷)与答案解析_第1页
算法设计和分析试题(卷)与答案解析_第2页
算法设计和分析试题(卷)与答案解析_第3页
算法设计和分析试题(卷)与答案解析_第4页
算法设计和分析试题(卷)与答案解析_第5页
资源描述:

《算法设计和分析试题(卷)与答案解析》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库

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、试用分治法对数组A[n]实现快速排序。(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)。Word可编辑资料专业分享(16分)7、试用回溯法解决下列整数变换问题:关于整数的变换和定义如下:。对于给定的两个整数和,要求用最少的变换和变换次数将变为。(16分

3、)Word可编辑资料专业分享1、⑴证明:令F(n)=O(f),则存在自然数n1、c1,使得对任意的自然数n≥n1,有:F(n)≤c1f(n)……………………………..(2分)同理可令G(n)=O(g),则存在自然数n2、c2,使得对任意的自然数n≥n2,有:G(n)≤c2g(n)……………………………..(3分)令c3=max{c1,c2},n3=max{n1,n2},则对所有的n≥n3,有:F(n)≤c1f(n)≤c3f(n)G(n)≤c2g(n)≤c3g(n)……………………………..(5分)故有:O(f)+O(g)=F(n)+G(n)≤c3f(n)

4、+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、解:经分析结论为:Word可编辑资料专业分享(1)………………………….(5分)(2);………………………….(10分)(3);………………………….(15分)3、解:用分治法求解的算法代码如下:int

5、partition(floatA[],intp,intr){inti=p,j=r+1;floatx=a[p];while(1){while(a[++i]x);if(i>=j)break;a[i]←→a[j]……………………………..(4分)};a[p]=a[j];a[j]=x;returnj;……………………………..(7分)}voidQuicksort(floata[],intp,intr){if(p

6、1);Quicksort(a,q+1,r);Word可编辑资料专业分享}};Quicksort(a,0,n-1);……………………………..(13分)4、解:用动态规划算法求解的算法代码如下:intlcs_len(char*a,char*b,intc[][N]){intm=strlen(a),n=strlen(b),i,j;for(i=0;i<=m;i++)c[i][0]=0;for(j=1;j<=n;j++)c[0][j]=0;……………………………..(4分)for(i=1;i<=m;i++)for(j=1;j<=n;j++)if(a[i-1]==b

7、[j-1])c[i][j]=c[i-1][j-1]+1;elseif(c[i-1][j]>=c[i][j-1])c[i][j]=c[i-1][j];elsec[i][j]=c[i][j-1];……………………………..(7分)returnc[m][n];……………………………..(8分)};char*build_lcs(chars[],char*a,char*b){intk,i=strlen(a),j=strlen(b),c[N][N];k=lcs_len(a,b,c);s[k]=’’;while(k>0){if(c[i][j]==c[i-1][j]

8、)i--;……………………………..(11分)Word可编辑资料专业分享else

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。