2010年宁夏回族自治区数据整理加强

1、设有一组初始记录关键字序列（K1，K2， ，Kn），要求设计一个算法能够在O(n)的时间复杂度内将线性表划分成两部分，其中左半部分的每个关键字均小于Ki，右半部分的每个关键字均大于等于Ki。

void quickpass(int r[], int s, int t)

{

int i=s, j=t, x=r[s];

while(i<j){

while (i<j && r[j]>x) j=j-1; if (i<j) {r[i]=r[j];i=i+1;}

while (i<j && r[i]<x) i=i+1; if (i<j) {r[j]=r[i];j=j-1;}

}

r[i]=x;

}

2、设t是给定的一棵二叉树，下面的递归程序count(t)用于求得:二叉树t中具有非空的左,右两个儿子的结点个数N2;只有非空左儿子的个数NL;只有非空右儿子的结点个数NR和叶子结点个数N0。N2、NL、NR、N0都是全局量，且在调用count(t)之前都置为0.

typedef struct node

{int data; struct node *lchild,*rchild;}node;

int N2,NL,NR,N0;

void count(node *t)

{if (t->lchild!=NULL) if (1)___ N2++; else NL++;

else if (2)___ NR++; else (3)__ ;

if(t->lchild!=NULL)(4)____; if (t->rchild!=NULL) (5)____;

}

26.树的先序非递归算法。

void example(b)

btree *b;

{ btree *stack[20], *p；

int top;

if (b!=null)

{ top=1; stack[top]=b;

while (top>0)

{ p=stack[top]; top--;

printf(“%d”,p->data);

if (p->rchild!=null)

{(1)___; (2)___;

}

if (p->lchild!=null)

(3)___; (4)__;

}}}}

3、设t是给定的一棵二叉树，下面的递归程序count(t)用于求得:二叉树t中具有非空的左,右两个儿子的结点个数N2;只有非空左儿子的个数NL;只有非空右儿子的结点个数NR和叶子结点个数N0。N2、NL、NR、N0都是全局量，且在调用count(t)之前都置为0.

typedef struct node

{int data; struct node *lchild,*rchild;}node;

int N2,NL,NR,N0;

void count(node *t)

{if (t->lchild!=NULL) if (1)___ N2++; else NL++; else if (2)___ NR++; else (3)__ ;

if(t->lchild!=NULL)(4)____; if (t->rchild!=NULL) (5)____; }

26.树的先序非递归算法。

void example(b)

btree *b;

{ btree *stack[20], *p；

int top;

if (b!=null)

{ top=1; stack[top]=b;

while (top>0)

{ p=stack[top]; top--;

printf(“%d”,p->data);

if (p->rchild!=null)

{(1)___; (2)___;

}

if (p->lchild!=null)

(3)___; (4)__;

}}}}