算法設(shè)計(jì)與分析試卷及答案

本文格式為Word版，下載可任意編輯——算法設(shè)計(jì)與分析試卷及答案算法設(shè)計(jì)與分析

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))或f(n)=Ω(g(n))或f(n)=θ(g(n))，并簡(jiǎ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、試用分治法對(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ù)i的變換f和g定義如下：f(i)?3i;g(i)??i/2?。對(duì)于給定的兩個(gè)整數(shù)n和m，要求用最少的變換f和g變換次數(shù)將n變?yōu)閙。（16分）

1、⑴證明：令F(n)=O(f),則存在自然數(shù)n1、c1，使得對(duì)任意的自然數(shù)n≥n1，有：F(n)≤c1f(n)……………..（2分）

同理可令G(n)=O(g),則存在自然數(shù)n2、c2，使得對(duì)任意的自然數(shù)n≥n2，有：G(n)≤c2g(n)……………..（3分）令c3=max{c1,c2},n3=max{n1,n2},則對(duì)所有的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①由于由漸近表達(dá)式的定義易知：

3n2是3n2+10n的漸近表達(dá)式。……………..（3分）②由于

21?1?21n?0,n??，由漸近表達(dá)式的定義易知：121?n21是21?的漸近表達(dá)式?！?.（6分）說(shuō)明：函數(shù)T(n)的漸近表達(dá)式t(n)定義為：

T(n)?t(n)?0,n??T(n)1n2、解：經(jīng)分析結(jié)論為：

2logn??(logn?5);………….（5分）（1）

2（2）logn??(n)；………….（10分）2n??(logn)；………….（15分）（3）

3、解：用分治法求解的算法代碼如下：intpartition(floatA[],intp,intr){

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

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

returnj;……………..（7分）}

voidQuicksort(floata[],intp,intr){if(p=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(vecterx,intn){

intsum=0,k=x.size();for(intj=0;jn){

coutn){sum++;s=x[i];}……………..（9分）}

returnsum;……………..（12分）}

6、解：此題用動(dòng)態(tài)規(guī)劃算法求解：intdist()

{

intm=a.size();intn=b.size();vectord(n+1,0);

for(inti=1;i1?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)br