福建农林大学考试试卷 (A)卷(3)

福建农林大学考试试卷 (A)卷

int lch,rch; //lch指向左子树，rch指向右子树 } tree[n0+l];

int root; //根结点指针

下面是先序遍历二叉树的非递算法。一维数组s作为栈，t为栈顶指针。 void preorder（）

{ int s[n0+l],t= ; int p=root;

while(p || ) if( p )

{ printf(“%c”, ) s[++t]= tree[p].rch; p= tree[p]. ; }

else p=s[ ]; }

12. 以下mergeSort是归并排序算法，merge是将两个相邻有序表归并的算法，mergepass是一趟归并的算法，填空完成算法。

void meger(Element R[], Element S[], int a, int b, int c) { int i=a, j=b+1, k=a;

while( i<=b && j<=c ) if( R[i].key<R[j].key ) S[k++]=R[i++]; else S[k++]=R[j++]; while(i<=b)S[k++]=R[i++]; while(j<=c)S[k++]=R[j++]; }

void megerPass(Element R[], Element S[], int m) { int i=1;

while( ) { meger(R, S, i, i+m-1, i+2*m-1 ); i += ; }

if(i+m-1<n) meger(R, S, ); else while( i<=n) S[i]= ; }

void megerSort() { Element S[n0+1]; int m=1; while(m<n)

{ megerPass(R,S,m); m*=2;

m*=2; } }