}

}     //MergeSortDC

29．由于元素的插入先后次序不同，所构成的二叉排序树可能有多种形态。请画出4棵含1，2，3，4，5，6六个元素且以1为根、深度为4的二叉排序树。

四、算法阅读题(本大题共4小题，每小题5分，共20分)

30．L为一个带头结点的循环链表。函数f30的功能是删除L中数据域data的值大于c的所有结点，并由这些结点组建成一个新的带头结点的循环链表，其头指针作为函数的返回值。请在空缺处填入合适的内容，使其成为一个完整的算法。

LinkList f30(LinkList L, int c)

{

  LinkList Lc,p,pre;

  pre=L;

  p=     (1)     ;

  Lc=(LinkList) malloc(sizeof(ListNode));

  Lc->next=Lc;

  while(p!=L)

if(p->data>c)

{

 pre->next=p->next;

     (2)     ;

 Lc->next=p;

 p=pre->next;

}

else

{

 pre=p;

    (3)     ;

}

  return Lc;

}

(1)

(2)

(3)

31．设栈S=(1,2,3,4,5,6,7),其中7为栈顶元素。

（1）写出调用f31(&S)后的S；

（2）简述函数f31中第1个循环语句的功能。

void f31 (Stack *S)

{

  Queue Q;

  Stack T;

  int i=0;

  InitQueue(&Q);

  InitStack(&T);

while(!StackEmpty(S))

if ((i=!t)!=0) Push(&T,Pop(S));

else EnQueue(&Q, Pop(S));

  while(!StackEmpty(&T))

Push(S,PoP(&T));

  while(!QieueEmpty(&Q))

Push(S,DeQueue(&Q));

}

(1)

(2)

32．图的邻接矩阵表示描述如下：

#define MaxNum      20                                       //图的最大顶点数

typedef struct  {

  char vexs[MaxNum];                                           //字符类型的顶点表

  int edges[MaxNum][MaxNum];                             //邻接矩阵

  int n, e;                                                               //图的顶点数和边数

} MGraph;                           //图的邻接矩阵结构描述

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

（1）对于下列图G的邻接矩阵，写出函数调用f32(&G,3)的返回值；

（2）简述函数f32的功能；

（3）写出函数f32的时间复杂度。

int f32(MGraph *G, int i)

{

  int d=0,j;

  for(j=0;j<G->n;j++)

  {

if (G->edges[i][j]) d++;

if (G->edges[j][i]) d++;

  }

  ret