算法设计与分析试卷及答案_第1页
算法设计与分析试卷及答案_第2页
算法设计与分析试卷及答案_第3页
算法设计与分析试卷及答案_第4页
算法设计与分析试卷及答案_第5页
全文预览已结束

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

本文格式为Word版,下载可任意编辑——算法设计与分析试卷及答案算法设计与分析

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分)

2f(n)?logn;g(n)?logn?5;(1)

2f(n)?logn;g(n)?n;(2)

2f(n)?n;g(n)?logn;(3)

3、试用分治法对数组A[n]实现快速排序。(13分)4、试用动态规划算法实现最长公共子序列问题。(15分)

5、试用贪心算法求解汽车加油问题:已知一辆汽车加满油后可行驶n公里,而旅途中有若干个加油站。试设计一个有效算法,指出应在哪些加油站停靠加油,使加油次数最少。(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变换次数将n变为m。(16分)

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)+c3g(n)=c3(f(n)+g(n))因此有:

O(f)+O(g)=O(f+g)……………..(7分)⑵解:

(3n2?10n)?3n2lim?0;2n??3n?10n①由于由渐近表达式的定义易知:

3n2是3n2+10n的渐近表达式。……………..(3分)②由于

21?1?21n?0,n??,由渐近表达式的定义易知:121?n21是21?的渐近表达式。……………..(6分)说明:函数T(n)的渐近表达式t(n)定义为:

T(n)?t(n)?0,n??T(n)1n2、解:经分析结论为:

2logn??(logn?5);………….(5分)(1)

2(2)logn??(n);………….(10分)2n??(logn);………….(15分)(3)

3、解:用分治法求解的算法代码如下:intpartition(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=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]=’\\0’;while(k>0){

if(c[i][j]==c[i-1][j])i--;……………..(11分)

elseif(c[i][j]==c[i][j-1])j--;else{s[--k]=a[i-1];i--,j--;}}

returns;……………..(15分)}

5、解:intgreedy(vecterx,intn){

intsum=0,k=x.size();for(intj=0;jn){

coutn){sum++;s=x[i];}……………..(9分)}

returnsum;……………..(12分)}

6、解:此题用动态规划算法求解:intdist()

{

intm=a.size();intn=b.size();vectord(n+1,0);

for(inti=1;i1?d[j-1]:i;……………..(10分)intdel=a[i-1]==b[j-1]?0:1;

d[j]=min(x+del,y+1,z+1);……………..(13分)}}

returnd[n];……………..(16分)}

7、解:解答如下:voidcompute(){k=1;

while(!search(1,n)){k++;

if(k>maxdep)br

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论