2． 长度为12的有序表：Apr，Aug，Dec，Feb，Jan，Jul，Jun，Mar，May，Nov，Oct，Sep，按折半查找法对该表进行查找。在表内各元素等概率情况下查找成功所需的平均比较次数为( )

34． 对一个有t个非零值元素的m×n矩阵，用B[0..t,1..3]的数组来表示，其中第0行的三个元素分别是m,n,t，从第一行开始到最后一行，每行表示一个非零元素，第一列为矩阵元素行号，第二列为其列号，第三列为其元素量，对这样的表示法，试编写一个算法确定任意一个元素A[i][j]的位置，并考虑若修改其元素值须用多少时间?(设B中第1列原行号是递增的)

33． 基于三元组的稀疏矩阵转置的处理方法有两种，以下运算按照矩阵A的三元组a.data的次序进行转置(快速转置)，请在______处用适当的语句予以填充。

Fast_Trans_Sparmat(SpMatrixTpa,SpMatrixTp*b)

    { (*b)．mu=a.nu;(*b).nu=a.mu;(*b).tu=a.tu;

      if(a.tu)

  {for(col)=1;______col++)unm[col]=0

    for(t=1;t＜=a.tu;t++)num[a.data[t].j]++;

    cpot[1]=1;

    for(col=2;col＜=a.nu;col++)cpot[col]=______;

    for(p=1;p＜=a.tu;p++)

      { col=a.data[p].j;

        q=cpot[col];

    (*b).data[q].i=a．data[p].j;

    (*b).data[q].j=a.data[p].i;

    (*b).data[q].v=a.data[p].v;

        ______;

      }

    }

  }

32． 以下为冒泡排序的算法。请分析算法，并在______处用适当的语句予以填充。

void bubblesort(int n,list r) /*fiag为特征位，定义为布尔型*/

  {for(i=1;i＜=______，i++)

       {______;

         for(j=1;j＜=______;j++)

           if(r[j+1].key＜r[j].key){flag=0;p=r[j];r[j]=r[j+1];r[j+1]=P;}

         if(flag)return;

       }

  }

30． 以下运算实现在循环队上的入队列，请在______处用适当的语句予以填充。

int EnCycQueue(CycquetaeTp*sq,DataType x)

        { if((sq—＞rear+1)%maxsize==______)

               {error("队满");return(0);)

          else{______;

               ______;

          return(1);

          }

       }

31． 以下程序段采用先根遍历方法求二叉树的叶子数，请在______处填充适当的语句。

void countleaf(bitreptr t,int*count)/*根指针为t，假定叶子数count的初值为0*/

       { if(t!=NULL)

          { if((t—＞lchild==NULL)&&(t—＞rchild==NULL))______;

             countleaf(1—＞lehild,count);

          ______;

          }

       }

28． 已知：S='XYZ*+' T='(X+Z)*Y'，试利用串的各种基本运算将S转换为T。

29． 令s=‘aaab’，t=‘abcabaa’，u=‘abcaabbabcabaacbacba’，分别求出它们的next值。

27． 对如图所示的有向图G，请给出其广度优先遍历序列，并画其DFS子树(以A为源点)。

26． 设某文件有14个记录，其关键字分别为{25,75,125,93,241,203,19,198,121,173,218，80，214，329}。桶的容量M=3，此时采用除留余数法构造散列函数，且散列函数为h(k)=k%5，画出该散列文件的结构图，并说明如何对其进行删除或插入、检索等操作。

25． 任意一棵具有n个结点的二叉树，若它有m个叶子，则该二叉树上度数为1的结点为______个。