08—期末考试算法设计与分析试卷B及答案

1、武汉工业学院工商学院2008 2009学年第 1 学期算法分析考试试卷（B卷）课程名称 算法分析 编号 03080121 题号一二三四五六七总分得分评阅人注：1、考生必须填写班级、姓名、学号；2、试题纸共 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)或或，并简述理由。（15分）(1) (2) (3) 3、试用分治法对数组An实现快速排序。（13分）4、试用动态规划算法实现最长公共子序列问题。（15分）5、试用贪心算法求解汽车加油问

2、题：已知一辆汽车加满油后可行驶n公里，而旅途中有若干个加油站。试设计一个有效算法，指出应在哪些加油站停靠加油，使加油次数最少。（12分）6、试用动态规划算法实现下列问题：设A和B是两个字符串。我们要用最少的字符操作，将字符串A转换为字符串B，这里所说的字符操作包括：(1) 删除一个字符。(2) 插入一个字符。(3) 将一个字符改为另一个字符。将字符串A变换为字符串B所用的最少字符操作数称为字符串A到B的编辑距离，记为d(A,B)。试设计一个有效算法，对任给的两个字符串A和B，计算出它们的编辑距离d(A,B)。（16分）7、试用回溯法解决下列整数变换问题：关于整数的变换和定义如下：。对于给定的两

3、个整数和，要求用最少的变换和变换次数将变为。（16分） 附表5：考试课程： 班级： 姓名： 学号： - 密 - 封 - 线 - - 密 - 封 - 线 - 、 证明：令F(N)=O(f),则存在自然数N1、C1，使得对任意的自然数N，有： F(N).（2分） 同理可令G(N)=O(g), 则存在自然数N2、C2，使得对任意的自然数N，有： G(N) .（3分） 令 C3=maxC1,C2,N3=maxN1,N2,则对所有的N，有： F(N) G(N) .（5分） 故有： O(f)+O(g)=F(N)+G(N) 因此有： O(f)+O(g)=O(f+g) .（7分） 解： 因为：由渐近表达式的定

4、义易知： 的渐近表达式。.（3分） 因为：由渐近表达式的定义易知： 21是21+1/n的渐近表达式。.（6分）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+i<x&&i<r); while(a-j>x); if(i>=j) break; ai .（4分） ; ap=aj; aj=x; return j; .（7分） voi

5、d Quicksort( float a, int p, int r ) if( p<r) int 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 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分） f

6、or(i=1;i<=m;i+) for(j=1;j<=n;j+) if(ai-1= =bj-1) cij=ci-1j-1+1; else if(ci-1j>=cij-1) cij=ci-1j; else cij=cij-1; .（7分） return cmn; .（8分） ; char *build_lcs(char s,char *a,char *b) int k,i=strlen(a),j=strlen(b),cNN; k=lcs_len(a,b,c); sk=0; while(k>0) if(cij= =ci-1j) i-;.（11分） else if(cij=

7、=cij-1) j-; else s-k=ai-1; i-,j-; return s; .（15分） 5、解：int greedy(vecter<int>x,int n) int sum=0,k=x.size();for(int j=0;j<k;j+) if(xj>n) cout<<”No solution”<<endl; return -1; .（6分）for(int i=0,s=0;i<k;i+) s+=xi; if(s>n) sum+;s=xi; .（9分） return sum; .（12分）6、解：此题用动态规划算法求解：i

8、nt dist( ) int m=a.size( ); int n=b.size( ); vector<int>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;j<=n;j+) int x=y; y=dj; int z=j>1?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、试用回溯法解决下列整数变换问题：关于整数的变换和定义如下：。对于给定的两个整数和，要求用最少的变换和变换次数将变为。（16分）7、解：解答如下：void compute() k=1; while(!search(1,n) k+; if(k>maxdep) break; init();.（6分）if(found) output();.（9分） else cout<<”No Solution!”<<endl; bool search(int dep,int n) if(dep>k) return false;