21.已知一棵二叉树的先序序列为ABCD，中序序列为BCAD，则它的后序序列为______。

22.在含n个顶点的连通图中，任意两个不同顶点之间的一条简单路径最多包含______条边。

23.对关键字序列(50，34，92，19，11，68，56，41，79)进行直接插入排序，当将第7个关键字56插入到当前的有序子表中时，为寻找插入位置需进行______次关键字之间的比较。

24.对有序表进行二分查找的过程可用判定树来描述，其判定树的形态只取决于______。

25.将有序表中n个元素依次插入到一棵空的二叉排序树中，则在等概率查找的情况下，该二叉排序树在查找成功时的平均查找长度是______。

三、解答题(本大题共4小题，每小题5分，共20分)

26.(1)写出右侧图形表示的广义表L。

(2)画出其表头与表尾均为(a,(b,c))的广义表L₁的图形表。

(1)

(2)

27.试推导一棵满k叉树上的叶子结点数a与非叶子结点数b之间满足以下关系：

    a=(k-1)b+1

28.假设用迪杰斯特拉(Dijkstra)算法求下列图中从顶点a到其余各顶点的最短路径，按求解过程依次写出各条最短路径及其长度。

29.已知关键字序列在R[1..8]中的初始状态为

  写出在将它调整为大根堆的过程中每一次筛选后R的状态。

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

30.如果希望循环队列中的向量单元都能得到利用，则可设置一个标志域tag,每当尾指针和头指针值相同时，以tag的值为0或1来区分队列状态是“空”还是“满”。请对下列函数填空，使其分别实现与此结构相应的入队列和出队列的算法。

int EnQueue(CirQueue *Q,DataType x){

if(   (1)   ) return 0;

Q->data[Q->rear]=x;

Q->rear=(Q->rear+1)% MAXQSIZE

   (2)  

return 1;

}

int DeQueue(CirQueue *Q,DataType *x){

if(   (3)   ) return 0;

*x=Q->data[Q->front];

Q->front=   (4)   ;

   (5)   ;

return 1;

}

(1)

(2)

(3)

(4)

(5)

31.已知具有n个结点的完全二叉树采用顺序存储结构存储在向量BT[1..n]中，结点的数据元素为字符类型，请阅读下列算法，并回答问题：

(1)假设向量BT中的内容为：

写出执行f31(BT,6)后的输出结果；

(2)说明该算法的功能。

void f31(char BT[],int n)

{ int  i=1;

  while(i>0)

    if(i<=n) {

      printf(″%c″,  BT[i]);

      i=i*2;

    }else{

      do {i=i/2;} while(i%2);

      if(i>0) i++;

    }

}

(1)

(2)

32.设数组f的初始元素序列为：

f[1..9]=(1,3,2,3,3,2,1,2,1)

阅读下列算法，并回答问题。其中算法f32中调用的函数swap(a,b)用以完成交换a和b的值。

(1)写出执行f32(f,9,3,1)之后f[1..9]中的元素序列，并写出在执行过程中调用swap函数的次数。

(2)简述算法f32的功能。

void f32(int f[],int n,int x,int y) {

  int i=1,j=1,k=n;

  while (j<=k)

    if (f[j]==y)j++;

    else if (f[j]==x)

            { swap(f[i],f[j]);i++;j++;}

         else {swap(f[k],f[j];k--;}

}

(1)

(2)

33.下列算法利用二分查找方法在有序表r中插入元素x，并保持表r的有序性，其中参数*n为表r的长度。请在空缺处填入合适的内容，使其成为一个完整的算法。

void BinInsert(SeqList r,int *n,DataType x)

{ int low=1,high=*n,mid,i;

while(low<=high)

{ mid=   (1)   ;

if (x.key<r[mid].key)high=mid-1;

else    (2)   ;

}

for(i=*n;   (3)   ;i--)

r[i+1]=r[i];

   (4)   ;

*n++;

}

(1)

(2)

(3)

(4)

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

34.假设一元多项式以循环链表表示，链表的结点结构为：

typedef struct PNode {

float coef;   //系数

int  exp;     //指数

struct PNode *next;

}*LinkList;

现需要将一个用循环链表h表示的代数多项式拆分成两个多项式循环链表h1和h2，其中h1仅含多项式的奇次项，h2仅含多项式的偶次项。要求利用原链表中的结点构成链表h1和h2。例如多项式7x⁸+5x³-4x的循环链表为

经拆分之后的情况应是：

请编写完成上述拆分的算法