QueueNode  *rear；／／队尾指针

}LinkQueue；

void f 31(LinkQueue*Q) {

      QueueNode*p，*s；

      p=    (1)    ；

while(p！=NULL) {

      s=p；

p=p->next;

free (s);

________(2)       =NULL;

      Q->rear=_______(3)_______；

}

(1)

(2)

(3)

32.假设采用动态存储分配的顺序串HString作为串的存储结构。该类型实现的串操作函数原型说明如下：

void strinit(HString s)；／／置s为空串

int strlen(HString s)；／／求串s的长度

void strcpy(HString to，HString from)；／／将串from复制到串to

void strcat(HString to，HString from)；／／将串from联接到串to的末尾

int strcmp(HString sl，HString s2)；

／／比较串sl和s2的大小，当s1<s2，s1=s2或s1>s2时，

／／返回值小于0，等于0或大于0

HString substr(HString s，int i，int m)；

／／返回串s中从第i(0≤I≤strlen(s)-m)个字符起长度为m的子串

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

(1)设串S=″abcdabcd″，T=″bcd″，V=″bcda″，写出执行f 32(S，T，V)之后的S；

(2)简述算法f 32的功能。

void f 32 (HString S, HString T, HString V) {

         int m, n, pos, i;

         HString news;

         strinit (news) ;

         n=strlen(S);

         m=strlen(T);

         pos=i=0;

         while (i<=n-m) {

            if( stremp(substr(S,i,m),T)! =0)i++;

            else{

               strcat(news,substr(S, pos, i-pos)) ;

               strcat(news, V) ;

pos=i=i+m;

}

}

        strcat(news,substr(S,pos,n-pos)) ;

        strcpy(S,news)

}

(1)

(2)

33.假设以二叉链表作为二叉树的存储结构，其类型定义如下：

typedef struct node {

         char data;

         struct node  *lchild, *rchild; ／／左右孩子指针

} BinTNode,*BinTree；

阅读下列算法f 33，并回答问题：

(1)已知如图所示的二叉树以T为指向根结点的指针，画出执行f 33(T)后的二叉树；

(2)简述算法f 33的功能。

void f33(BinTree T) {

      if (T) {

        f 33 (T - > lchild) ;

        f 33(T - > rchild) ;

        if ( ( !T - > lchild) && T->rchild) {

          T - > lchild=T->rchild;

          T - > rchild=NULL;

}

}

}

(1)

(2)

五、算法设计题(本大题10分)

34.假设以带头结点的单链表表示有序表，单链表的类型定义如下：

       typedef struct node {

       int data；

       struct node*next；

     } LinkNode，*LinkList；

   编写算法，输入n个