16． 在索引顺序文件中需建立一张指示逻辑记录和物理记录之间的一一对应关系的______。它通常采用______结构来组织。

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。请画出相应的二叉树，并求出对应此二叉树的后序遍历序列，此二叉树是完全二叉树吗?完全二叉树有什么性质(特点)?