08-09年期末考試算法設(shè)計(jì)與分析試卷B及答案

武漢工業(yè)學(xué)院工商學(xué)院2008武漢工業(yè)學(xué)院工商學(xué)院2008–2009學(xué)年第1學(xué)期算法分析考試試卷（B卷）課程名稱算法分析編號(hào)03080121題號(hào)一二三四五六七總分得分評(píng)閱人注：1、考生必須填寫班級(jí)、姓名、學(xué)號(hào)；2、試題紙共1頁(yè)。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ù)組A[n]實(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、試用動(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分）考試課程：考試課程：班級(jí)：姓名：學(xué)號(hào)：-------------------------------------------------密----------------------------------封-----------------------------線----------------------------------------------------------------------------------------------------------密----------------------------------封-----------------------------線---------------------------------------------------------、=1\*GB2⑴證明：令F(N)=O(f),則存在自然數(shù)N1、C1，使得對(duì)任意的自然數(shù)N，有：F(N)……………..（2分）同理可令G(N)=O(g),則存在自然數(shù)N2、C2，使得對(duì)任意的自然數(shù)N，有：G(N)……………..（3分）令C3=max{C1,C2},N3=max{N1,N2},則對(duì)所有的N，有：F(N)G(N)……………..（5分）故有：O(f)+O(g)=F(N)+G(N)因此有：O(f)+O(g)=O(f+g)……………..（7分）=2\*GB2⑵解：=1\*GB3①因?yàn)椋河蓾u近表達(dá)式的定義易知：的漸近表達(dá)式?！?.（3分）=2\*GB3②因?yàn)椋河蓾u近表達(dá)式的定義易知：21是21+1/n的漸近表達(dá)式?！?.（6分）2、解：經(jīng)分析結(jié)論為：（1）………….（5分）（2）；………….（10分）（3）；………….（15分）3、解：用分治法求解的算法代碼如下：intpartition(floatA[],intp,intr){inti=p,j=r+1;floatx=a[p];while(1){while(a[++i]<x);while(a[--j]>x);if(i>=j)break;a[i]……………..（4分）};a[p]=a[j];a[j]=x;returnj;……………..（7分）}voidQuicksort(floata[],intp,intr){if(p<r){intq=partition(a,p,r);……………..（10分）Quicksort(a,p,q-1);Quicksort(a,q+1,r);}};Quicksort(a,0,n-1);……………..（13分）4、解：用動(dòng)態(tài)規(guī)劃算法求解的算法代碼如下：intlcs_len(char*a,char*b,intc[][N]){intm=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;elseif(c[i-1][j]>=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(vecter<int>x,intn){intsum=0,k=x.size();for(intj=0;j<k;j++)if(x[j]>n){cout<<”Nosolution”<<endl;return-1;……………..（6分）}for(inti=0,s=0;i<k;i++){s+=x[i];if(s>n){sum++;s=x[i];}……………..（9分）}returnsum;……………..（12分）}6、解：此題用動(dòng)態(tài)規(guī)劃算法求解：intdist(){intm=a.size();intn=b.size();vector<int>d(n+1,0);for(inti=1;i<=n;i++)d[i]=i;……………..（5分）for(i=1;i<=m;i++){inty=i-1;for(intj=1;j<=n;j++){intx=y;y=d[j];intz=j>1?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)break;init();};……………..（6分）if(found)output();……………..（9分）elsecout<<”NoSolution!”<<endl;}boolsearch(intdep,intn){if(dep>k)returnfalse;……