算法与设计六套试卷(3)

iv. v. Endif EndFor

求出满足 v(uj)=max{ v(u1), v(u2),…, v(un)} 的整数j If P < v(uj) then U’={uj} vi.

Output U’

： 号学线 --- --- --- --- --- --- --- --- -- -- - 封 ： -名----姓---- -- - -- - -- - -- - -- - -- - -- - -- - -： 级密 -班---- --- --- --- --- --- --- --- --- --- --- --- ：---程---课---试--考11

、⑴ 证明：令F(N)=O(f),则存在自然数N1、C1，使得对任意的自然数N?N1，有：

F(N)?C1f(N);……………………………..（2分）

同理可令G(N)=O(g), 则存在自然数N2、C2，使得对任意的自然数N?N2，

有： G(N)?C2g(N); ……………………………..（3分）

令 C3=max{C1,C2},N3=max{N1,N2},则对所有的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?g)

因此有：

O(f)+O(g)=O(f+g) ……………………………..（7分）

⑵ 解：① 因为：lim2(3n?10n)?3n3n?10n222n???0;由渐近表达式的定义易知：

3n是3n?10的渐近表达式。……………………………..（3分） ② 因为：lim(21?1/n)?2121?1/n?0;由渐近表达式的定义易知：

2n?? 21是21+1/n的渐近表达式。……………………………..（6分） 2、解：经分析结论为：

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

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

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

3、解：用分治法求解的算法代码如下： int partition(float A[],int p,int r)

12

{

int i=p,j=r+1; float x=a[p]; while (1) {

while(a[++i]x); if(i>=j) break;

a[i]?a[j]; ……………………………..（4分）

};

a[p]=a[j]; a[j]=x;

return j; ……………………………..（7分）

}

void Quicksort( float a[], int p, int r ) {

if( p

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 c[][N]) {

int m=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; else if(c[i-1][j]>=c[i][j-1]) c[i][j]=c[i-1][j];

else c[i][j]=c[i][j-1]; ……………………………..（7分） return c[m][n]; ……………………………..（8分） };

char *build_lcs(char s[],char *a,char *b) {

int k,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分）

13

else if(c[i][j]= =c[i][j-1]) j--; else{

s[--k]=a[i-1]; i--,j--; } }

return s; ……………………………..（15分）

}

5、解：int greedy(vecterx,int n)

{

int sum=0,k=x.size(); for(int j=0;jn){

cout<<”No solution”<

return -1; ……………………………..（6分） }

for(int i=0,s=0;i

if(s>n){ sum++;s=x[i];} ……………………………..（9分） }

return sum; ……………………………..（12分）

}

6、解：此题用动态规划算法求解：

int dist( ) {

int m=a.size( ); int n=b.size( );

vectord(n+1,0);

for(int i=1;i<=n;i++) d[i]=i; ……………………………..（5分）

for(i=1;i<=m;i++){ int y=i-1;

for(int j=1;j<=n;j++){

int x=y; y=d[j];

int z=j>1?d[j-1]:i; ……………………………..（10分） int del=a[i-1]= =b[j-1]?0:1;

d[j]=min(x+del,y+1,z+1); ……………………………..（13分） } }

return d[n]; ……………………………..（16分） }

7、解：解答如下：

void compute() {

14

k=1;

while(!search(1,n)){ k++;

if(k>maxdep) break; init();

};……………………………..（6分）

if(found) output();……………………………..（9分）

else cout<<”No Solution!”<

}

bool search(int dep,int n)

{

if(dep>k) return false; ……………………………..（11分） for(int i=0;i<2;i++){

int n1=f(n,i);t[dep]=I; ……………………………..（13分） if(n1= =m||search(dep+1,n1)){ found=true; out();

return true;

}

return false; ……………………………..（16分）

}

第九章

福建师范大学数学与计算机科学学院 2006 — 2007学年第二学期考试 B 卷

15