8． 如果我们采用二分查找法查找一个长度为n的有序表，则查找每个元素的平均比较次数( )对应的判定树的高度(假设树高h≥2)。

33． 以下将a_h，…a_m，和a_m+1…a_n，两个有序序列(它们相应的关键字值满足K_h≤K_m，K_m+1≤…K_n，)合并成一个有序序列R_h，…，R_n，(使其关键字值满足K_h，'≤…≤K_n，')。请分析算法，并在______上填充适当的语句。

void merge(list a,list R,int h,int m,int n)

  {i=h;k=h;j=m+1;

    while((i＜m)&&(j＜=n))

    { if(a[i].key<=a[i].key){R[k]=______;______;}

      else{R[k]=______;______;}

    k++;

    }

    while(i＜=______){R[k]=a[i];i++;k++;)

    while(j＜=______){R[k]=a[j];j++;k++;}

  }

  此算法的执行时间为______。

34． 有两个磁盘文件A、B，各存放一行字母，要求把这两个文件中的信息按字母顺序排列合并，输出到一个新文件C中。

31． 以下运算实现在链队上的出队列，请在______处用适当的语句予以填充。

int OutQueue(QueptrTp*lq,DataType*x)

    { LqueueTp*s;

      if(1q—＞front==lq—＞rear){error("队空");return(0);}

      else{ s=(lq—＞front)—＞next;

            ______=s—＞data;

            (lq—＞front)—＞next______;

            if(s—＞next==NULL)lq—＞rear=lq—＞front;

            free(s);

            return(1);

          }

  }

32． 以下运算实现在链栈上的进栈，请在______处用适当的语句予以填充。

void Push(LStackTp*ls,DataType x)

    { LStackTp*p;p=malloc(sizeof(LStackTp));

      ______;

      p—＞next=ls;

      ______;

  }

30． 以下算法实现若开散列表HP中无键值为K的结点，则插入一个这样的结点。请分析程序，并在______上填充合适的语句。

void insert_openhash(keytype K,openhash HP)

  { if(research_openhash(K,HP)==NULL)

       { i=H(K);

         q=malloc(size);q—＞key=______;   /*生成新结点*/

         ______=HP[i];HP[i]=______;   /*前插法链入新结点*/

       }

  }

29． 对于如图所示的二叉树，请画出其顺序存储结构图。

28． 假设在树中，如果结点x是结点y的双亲时，用(x,y)来表示树边，已知一棵树的树边的集合为{(i,m)，(i,n)，(e,i)，(b,e)，(b,d)，(a,b)，(g,j)，(g,k)，(c,g)，(c,f)，(h,l)，(c,h)，(a,c))，请用树形结构画出此树，并回答下面的问题。

(1)哪个是根结点?

(2)哪些是叶结点?

(3)哪个是g的双亲?

(4)哪些是g的祖先?

(5)哪些是g的孩子?

(6)哪些是e的子孙?

(7)哪些是e的兄弟?

(8)树的深度是多少?

(9)树的度数是多少?

27． 已知下面的一个图，请根据普里姆算法构出它的一棵最小生成的树。

26． 对于散列文件来说，其存储单位是什么?对于一个能存储m个桶，若需要存放的同义词大于m，则需要如何处理?现在假设一个文件有18个记录，其关键字分别为：30,11,27,04,19,86,73,89,32,05,103,58,45,67,77,81,08,48，假设桶的容量m=3，桶数b=7，现在要求用除余法做散列函数H(key)=key%7，请给出该散列文件的表示方法。

25． 无向图的邻接矩阵是______，并且主对角线上的元素的值为______。