算法与分析试题及答案

1、 1、对于下列各组函数f(n)和g(n)，确定f(n)=O(g(n)或或，并简述理由。（12分）(1) (2) (3) 2、试用分治法实现有重复元素的排列问题：设是要进行排列的个元素，其中元素可能相同，试计算的所有不同排列。（13分）3、试用分治法对一个有序表实现二分搜索算法。（12分）4、试用动态规划算法实现0-1闭包问题。（15分）5、试用贪心算法求解下列问题：将正整数n分解为若干个互不相同的自然数之和，使这些自然数的乘积最大。（15分）6、试用动态规划算法实现最大子矩阵和问题：求矩阵A的一个子矩阵，使其各元素之各为最大。（15分）7、试用回溯法解决下列整数变换问题：关于整数的变换和定义如

2、下：。对于给定的两个整数和，要求用最少的变换和变换次数将变为。（18分）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、试用贪心算法求解汽车加油问题：已知一辆汽车加满油后可行驶n公里，而旅途中有若干个加油站。试设计一个有效算法，指出应在哪些加油站停靠加油，使加油次数最少。（12分）6、试

3、用动态规划算法实现下列问题：设A和B是两个字符串。我们要用最少的字符操作，将字符串A转换为字符串B，这里所说的字符操作包括：(1) 删除一个字符。(2) 插入一个字符。(3) 将一个字符改为另一个字符。将字符串A变换为字符串B所用的最少字符操作数称为字符串A到B的编辑距离，记为d(A,B)。试设计一个有效算法，对任给的两个字符串A和B，计算出它们的编辑距离d(A,B)。（16分）7、试用回溯法解决下列整数变换问题：关于整数的变换和定义如下：。对于给定的两个整数和，要求用最少的变换和变换次数将变为。（16分） 1、 解：简答如下： （1），（2），（3）2、 解：解答如下： Template&l

4、t;class Type>void Perm(Type list,int k,int m) if(k= =m) for(int i=0;i<=m;i+) cout<<listi; .（4分） cout<<endl;else for(int i=k;i<=m;i+) if(ok(list,k,i) swap(listk,listi); Perm(list,k+1,m); swap(listk,listi); .（8分） ; 其中ok用于判别重复元素。 Template<class> int ok(Type list,int k,int i)

5、if(i>k) for(int t=k;t<I;t+) if(listt= =listi) return 0; return 1;.（13分）3、 解：解答如下： Template<class> int BinarySearch(Type a,const Type& x,int n)/假定数组a已按非递减有序排列，本算法找到x后返回其在数组a中的位置，/否则返回-1 int left=0,right=n-1; while(left<=right) int middle=(left+right)/2; .（4分） if(x= =amiddle) return

6、 middle+1; if(x>amiddle) left=middle+1; .（8分） else right=middle-1;return -1;.（12分）4、 解：解答如下：Template<class>void Knapsack(Type v,int w,int c,int n,Type *m) Int jMax=min(wn-1,c); for(int j=0;j<=jMax;j+) mnj=0; for(int j=wn;j<=c;j+) mnj=vn; .（5分）for(int i=n-1;i>1;i-) jMax=min(wi-1,c);

7、 for(int j=0;j<=jMax;j+) mij=mi+1j; for(int j=wi;j<=c;j+) mij=max(mi+1j,mi+1j-wi+vi); .（8分）;m1c=m2c;if(c>=w1) m1c=max(m1c,m2c-w1+v1); .（10分）Template<class>Void Traceback(Type *m,int w,int c,int n,int x) for(int i=1;i<n;i+) if(mic= =mi+1c) xi=0; .（12分）else xi=1,c-=wi;xn=(mnc)?1:0;.（

8、15分）5、 解：解答如下：void dicomp(int n,int a) k=1;if(n<3) a1=0;return;if(n<5) ak=1;a+k=n-1;return; .（5分）a1=2;n-=2; while(n>ak) k+; ak=ak-1+1; n-=ak;.（10分）if(n= =ak) ak+;n-;for(int i=0;i<n;i+) ak-i+;.（15分）6、 解：解答如下：int MaxSum2(int m,int n,int *a) int sum=0;int *b=new intn+1;for(int i=1;i<=m;i

9、+) for(int k=1;k<=n;k+) bk=0; .（5分） for(int j=i;j<=m;j+) for(int k=1;k<=n;k+) bk+=ajk; int max=MaxSum(n,b);if(max>sum) sum=max; return sum; .（10分） int MaxSum(int n,int *a) int sum=0,b=0; for(int i=1;i<=n;i+) if(b>0) b+=ai; else b=ai; if(b>sum) sum=b;Return sum; .（15分）7、 解：解答如下：void compute() k=1; while(!search(1,n) k+; if(k>maxdep) break; init();.（6分）if(found) output(); else cout<<”No Solution!”<<endl; .（9分） bool search(int dep,int n) If(dep&