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

本文格式为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