16.若一个算法中的语句频度之和为T(n)=3720n+4nlogn，则算法的时间复杂度为________。

17.在如图所示的链表中，若在指针p所指的结点之后插入数据域值相继为a和b的两个结点，则可用下列两个语句实现该操作，它们依次是________和________。

18.假设以S和X分别表示进栈和退栈操作，则对输入序列a,b,c,d,e进行一系列栈操作SSXSXSSXXX之后，得到的输出序列为________。

19.串S=″I am a worker″的长度是________。

20.假设一个10阶的下三角矩阵A按列优顺序压缩存储在一维数组C中，则C数组的大小应为________。

21.在n个结点的线索二叉链表中，有________个线索指针。

22.若采用邻接矩阵结构存储具有n个顶点的图，则对该图进行广度优先遍历的算法时间复杂度为________。

23.对关键字序列(52，80，63，44，48，91)进行一趟快速排序之后得到的结果为________。

24.由10000个结点构成的二叉排序树，在等概率查找的假设下，查找成功时的平均查找长度的最大值可能达到________。

25.若要找出所有工资低于1500元，职称是副教授，及所有工资低于2000元，职称是教授的记录，则查询条件是________。

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

26.已知一个6行5列的稀疏矩阵中非零元的值分别为：-90，41，-76，28，-54，65和-8，它们在矩阵中的列号依次为：1，4，5，1，2，4和5。当以带行表的三元组表作存储结构时，其行表RowTab中的值依次为0，0，2，2，3和5。请写出该稀疏矩阵(注：矩阵元素的行列下标均从1开始)。

27.已知树T的先序遍历序列为ABCDEFGHJKL，后序遍历序列为CBEFDJIKLHGA。请画出树T。

28.对关键字序列(72，87，61，23，94，16，05，58)进行堆排序，使之按关键字递减次序排列。请写出排序过程中得到的初始堆和前三趟的序列状态。

初始堆：________

第1趟：________

第2趟：________

第3趟：________

29.在关键字序列(07，12，15，18，27，32，41，92)中用二分查找法查找和给定值92相等的关键字，请写出查找过程中依次和给定值“92”比较的关键字。

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

30.以下函数中，h是带头结点的双向循环链表的头指针。

  (1)说明程序的功能；

  (2)当链表中结点数分别为1和6(不包括头结点)时，请写出程序中while循环体的执行次数。

  int f(DListNode *h)

  {

    DListNode *p,*q;

    int j=1;

    p=h->next;

    q=h->prior;

    while(p!=q && p->prior!=q)

       if(p->data==q->data)

       {

         p=p->next;

         q=q->prior;

        }

        else j=0;

       return j;

   }

31.设栈S=(1,2,3,4,5,6,7),其中7为栈顶元素。请写出调用algo(&s)后栈S的状态。

   void algo(Stack *S)

   {

     int i=0;

     Queue Q; Stack T;

     InitQueue(&Q);InitStack(&T);

     while (!StackEmpty(S))

     {

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

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

      }

      while(!QueueEmpty(Q))

        Push(&S,DeQueue(&Q));

      while(!StackEmpty(T))

        Push(&S,Pop(&T))；

     }

32.已知带权图的邻接矩阵表示和邻接表表示的形式说明分别如下：

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

   #define INFINITY INT_MAX //INT_MAX为最大整数，表示∞

   typedef struct{

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

     int edges[MaxNum][MaxMum];//权值为整型的邻接矩阵

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

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

   typedef struct node