}

(1)

(2)

31.阅读下列算法，并回答问题：

（1）Q、Q1和Q2都是队列结构，设队列Q=（1，0，-5，2，-4，-6，9），其中1为队头元素，写出执行f31 (&Q,&Q1,&Q2)之后队列Q、Q1和Q2的状态；

（2）简述算法f31的功能。

（注：lnitQueue、EnQueue、DeQueue和QueueEmpty分别是队列初始化、入列、出队和判队空的操作）

void  f31 (Queue*Q, Queue*Q1, Queue*Q2) {

int  e;

lnitQueue (Q1);

lnitQueue (Q2);

while (!QueueEmpty (Q)) {

e=DeQueue (Q);

if (e>=0) EnQueue (Q1,e);

else EnQueue (Q2,e)

}

}

（1）

（2）

32.阅读下列算法，并回答问题：

（1）假设串由合法的英文字母和空格组成，并以’\0’作结束符。设串s=”⊔⊔|⊔am⊔a⊔⊔⊔student”(⊔表示空格符)，写出f32（s）的返回值；

（2）简述算法f32的功能。

int f32 (char*s){

int  i, n, inword;

n=inword=0;

for (i=0;s[i]!=’\0’;i++)

if (s[i]!=’⊔’&& inword==0){

inword=1;

n++;

}

else if (s[i]==’⊔’&& inword==1)

inword=0;

return  n;

}

（1）

（2）

33.阅读下列对正整数关键字序列L操作的算法，并回答问题：

（1）设L=(28,19,27,49,56,12,10,25,20,50),写出f33 (L,4)的返回值；

（2）简述函数f33的功能。

int  Partition (SeqList*L, int low, int high);

∥对L[low..high]做划分，返回基准记录的位置，并使左部的关键字

∥都小于或等于基准记录的关键字，右部的关键字都大于基准记录的关键字

int  f33 (SeqList  L, int k){

int  low, high, pivotpos;

low=1;

high=L.length;

if (k<low || k>high)

return-1;

do {

pivotpos=Partition (&L, low, high);∥调用快速排序的划分算法

if (pivotpos<k)

low=pivotpos+1;

else if (pivotpos>k)

high=pivotpos-1;

}while (pivotpos!=k);

return L.data [pivotpos];

}

（1）

（2）

五、算法设计题（本题10分）

34.二叉排序树的类型定义如下：

typedef struct BSTNode {∥ 二叉排序树的结点结构

int    data;    ∥数据域

struct  BSTNode  *lchild, *rchild; ∥左、右孩子指针

}BSTNode,*BSTree;

设计递归算法，统计一棵二叉排序树T中值小于a的结点个数。