算法與分析試題及答案

1、 1、對(duì)于下列各組函數(shù)f(n)和g(n)，確定f(n)=O(g(n)或或，并簡(jiǎn)述理由。（12分）(1) (2) (3) 2、試用分治法實(shí)現(xiàn)有重復(fù)元素的排列問(wèn)題：設(shè)是要進(jìn)行排列的個(gè)元素，其中元素可能相同，試計(jì)算的所有不同排列。（13分）3、試用分治法對(duì)一個(gè)有序表實(shí)現(xiàn)二分搜索算法。（12分）4、試用動(dòng)態(tài)規(guī)劃算法實(shí)現(xiàn)0-1閉包問(wèn)題。（15分）5、試用貪心算法求解下列問(wèn)題：將正整數(shù)n分解為若干個(gè)互不相同的自然數(shù)之和，使這些自然數(shù)的乘積最大。（15分）6、試用動(dòng)態(tài)規(guī)劃算法實(shí)現(xiàn)最大子矩陣和問(wèn)題：求矩陣A的一個(gè)子矩陣，使其各元素之各為最大。（15分）7、試用回溯法解決下列整數(shù)變換問(wèn)題：關(guān)于整數(shù)的變換和定義如

2、下：。對(duì)于給定的兩個(gè)整數(shù)和，要求用最少的變換和變換次數(shù)將變?yōu)?。?8分）1、(1) 證明：O(f)+O(g)=O(f+g) （7分）(2) 求下列函數(shù)的漸近表達(dá)式：（6分） 3n2+10n; 21+1/n; 2、對(duì)于下列各組函數(shù)f(n)和g(n)，確定f(n)=O(g(n)或或，并簡(jiǎn)述理由。（15分）(1) (2) (3) 3、試用分治法對(duì)數(shù)組An實(shí)現(xiàn)快速排序。（13分）4、試用動(dòng)態(tài)規(guī)劃算法實(shí)現(xiàn)最長(zhǎng)公共子序列問(wèn)題。（15分）5、試用貪心算法求解汽車加油問(wèn)題：已知一輛汽車加滿油后可行駛n公里，而旅途中有若干個(gè)加油站。試設(shè)計(jì)一個(gè)有效算法，指出應(yīng)在哪些加油站?？考佑?，使加油次數(shù)最少。（12分）6、試

3、用動(dòng)態(tài)規(guī)劃算法實(shí)現(xiàn)下列問(wèn)題：設(shè)A和B是兩個(gè)字符串。我們要用最少的字符操作，將字符串A轉(zhuǎn)換為字符串B，這里所說(shuō)的字符操作包括：(1) 刪除一個(gè)字符。(2) 插入一個(gè)字符。(3) 將一個(gè)字符改為另一個(gè)字符。將字符串A變換為字符串B所用的最少字符操作數(shù)稱為字符串A到B的編輯距離，記為d(A,B)。試設(shè)計(jì)一個(gè)有效算法，對(duì)任給的兩個(gè)字符串A和B，計(jì)算出它們的編輯距離d(A,B)。（16分）7、試用回溯法解決下列整數(shù)變換問(wèn)題：關(guān)于整數(shù)的變換和定義如下：。對(duì)于給定的兩個(gè)整數(shù)和，要求用最少的變換和變換次數(shù)將變?yōu)?。?6分） 1、 解：簡(jiǎn)答如下： （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用于判別重復(fù)元素。 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)/假定數(shù)組a已按非遞減有序排列，本算法找到x后返回其在數(shù)組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&