1． 堆排序的最坏时间复杂度为( )

35． 假设在表示一棵二叉树的二叉链表上增加两个域，双亲域用于指示其双亲结点，标志域flag(可取，0…2)的值，用以区分在遍历过程中到达该结点时继续向左或向右或访问该结点。试以此存储结构编写不用栈进行后序遍历的递推形式的算法。

34． 以下为单链表的建表算法，分析算法，请在______处填上正确的语句。

lklist create_iklist2()   /*直接实现的建表算法。*/

     { head=malloc(size);

       p=head;

       scanf("%",&x);

       while(X!='$')

       { q=malloc(size);

         q—＞data=x;

         p—＞next=q;

         ______;

         scanf("%",&x);

       }

         ______;

         return(head);

       }

  此算法的量级为______。

32． 以下为单链表的删除运算，分析算法，请在______处填上正确的语句。

void delete_lklist(1klist head,int i)

    { p=find_lklist(head,i-1)；

      if(______)

        { q=______;

          p—＞next=q—＞next;

          free(q);

        }

    else error("不存在第i个结点")

  }

33． 以下为顺序表的定位运算，分析算法，请在______处用正确的语句予以填充。

int locate_sqlist(sqlist L,datatype X)

  /*在顺序表L中查找第一个值等于X的结点。若找到回传该结点序号；否则回传0*/{______；

  while((i≤L.last)&&(L.data[i-1]!=x))i++;

  if(______)return(i);

  else return(0);

  }

31． 以下算法假定以线性探测法解决冲突，在闭散列表HL中查找键值为K的结点，成功时回送该位置；不成功时回送标志-1。请分析程序，并在______上填充合适的语句。

int search_closehash(keyt,ype K,closehashHL)

  {d=H(K);   /*计算散列地址*/

    i=d;

    while(HL[i].key!=K&&(i!=d-1)i=______;)/*未成功且未查遍整个HL时继

                                                 续扫描*/

    if(______)return(i);   /*查找成功*/

    else return(-1);       /*查找失败*/

  }

判别下列二序列是否为堆，如不是，按照对序列建堆的思想把它调整为堆，用图表示建堆的过程。

(1,5,7,25,21,8,8,42)

30． (3,9,5,8,4,17,21,6)

27． 已知有一关键字序列为{97,86,53,108,72,34,215,146,11,68}，如果我们采用直接选择排序方法对此序列进行排序(按照升序排列)，请给出每一趟的排序结果。

28． 请根据下面所给出的邻接矩阵画出相应的有向图或者是无向图(顶点v_i表示)。

26． 已知一棵二叉树的前序遍历序列是ABDGCEFH，其中序遍历序列为DGBAECHF。请画出相应的二叉树，并求出对应此二叉树的后序遍历序列，此二叉树是完全二叉树吗?完全二叉树有什么性质(特点)?