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

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)定义为： 2、解：经分析结论为：

2logn(logn5);………………………….（5分） （1）

2logn(n)；………………………….（10分） （2）

1n2n(logn)；………………………….（15分） （3）

3、解：用分治法求解的算法代码如下： int partition(float A[],int p,int r)

{

int i=p,j=r+1; float x=a[p]; while(1){ while(a[++i]x); if(i>=j) break;

a[i]←→a[j]……………………………..（4分） }; a[p]=a[j]; a[j]=x;

return j;……………………………..（7分） }

void Quicksort(float a[],int p,int r) { if(pint q=partition(a,p,r);……………………………..（10分） Quicksort(a,p,q-1); Quicksort(a,q+1,r); } };

Quicksort(a,0,n-1);……………………………..（13分） 4、解：用动态规划算法求解的算法代码如下： int lcs_len(char* a,char* b,int c[][N]) {

int m=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[j-1])c[i][j]=c[i-1][j-1]+1; else if(c[i-1][j]>=c[i][j-1]) c[i][j]=c[i-1][j];

elsec[i][j]=c[i][j-1];……………………………..（7分） return c[m][n];……………………………..（8分） };

char* build_lcs(char s[],char* a,char* b) {

int k,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分） else if(c[i][j]==c[i][j-1])j--; else{ s[--k]=a[i-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”<for(int i=0,s=0;iif(s>n){sum++;s=x[i];}……………………………..（9分） }

return sum;……………………………..（12分） }

6、解：此题用动态规划算法求解： int dist() {

int m=a.size(); int n=b.size(); vector d(n+1,0);

for(int i=1;i<=n;i++)d[i]=i;……………………………..（5分） for(i=1;i<=m;i++){ int y=i-1;

for(int j=1;j<=n;j++){

int x=y; y=d[j];

int z=j>1?d[j-1]:i;……………………………..（10分） int del=a[i-1]==b[j-1]?0:1;

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

return d[n];……………………………..（16分） }

7、解：解答如下： void compute() { k=1;

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

if(k>maxdep)break; init();

};……………………………..（6分）

if(found)output();……………………………..（9分） else cout<<”NoSolution!”<bool search(int dep,int n) {

if(dep>k)return false;……………………………..（11分） for(int i=0;i<2;i++){

int n1=f(n,i);t[dep]=I;……………………………..（13分） if(n1==m||search(dep+1,n1)){ found=true; out(); return true; }

return false;……………………………..（16分） }