10.经常修改的索引文件宜采用________做索引。
    A.二叉排序树                B.满二叉树
    C.多叉树                    D.B+树

第二部分 非选择题 (共80分)

二、填空题 (本大题共10小题，每空2分，共20分)

  11.某算法需要的辅助空间为s(n)=10log2n+2000/n+5，则该算法的空间复杂度为_______________。
  12.在n个结点的单链表中，在P指向的结点之后插入一个结点的时间复杂度为_______________。
  13.设SQ为循环队列，存储在数组d[m]中，则SQ出队操作对其队头指针front的修改是_______________。
  14.串中所含字符个数称为该串的_______________。
  15.tail(tail(a,b))=_______________。
  16.n(n>0)个结点二叉树对应的森林最多包含_______________棵非空树。
  17.深度为n(n>0)的二叉树最多有_______________个结点。
  18.n(n>0)个结点、(n-1)条边的连通无向图中，顶点度数最大值为_______________。
  19.堆排序的空间复杂度_______________。
  20.倒排文件有_______________和主文件构成。

三、简答题 (本大题共5小题，每小题6分，共30分)

  21.设有函数：
     void fuc(int n)
     {int i;
       for(i=1;i*i*i<=n;i++)
         prinft("%d",i*i*i);
     }
     函数fuc饿时间复杂度是多少？

  22.把1、2、3、4依次进栈（栈初始为空），任何时刻（只要栈不空），都可以出（退）栈，试写出所有可能的出栈序列（如1234）。

  23.若一二叉树有2度结点100个，则其叶结点有多少个？该二叉树可以有多少个1度顶点？

  24.请画出广义表D的图形表示
     D=(D,(a,b),((a,b),c),())

  25.有向图（带权）G如下所示：
     试给出用迪杰斯特拉（Dijkstra）算法求上图A到其它各顶点最短路径得到的数组P各元素值（A、B、C、D、E、F编号依次是1、2、3、4、5）。

四、理解题 (本大题共2小题，每小题6分，共12分)

26.指出下面函数f的功能及返回值的含义。
    int f(char s1[],char s2[])
    {
      int i=0,j=0;
      while(s1[i]&&s2[j]){
        if(s1[i]>s2[j])
          return 1;
        else if(s1[i]          return -1;
        else i++,j++;
      }
      if(s1[i])
         return 1;
      else if(s2[j])
         return -1;
      else return 0;
    }

27.指出下面函数FS的功能。其中，p指向先序线索二叉树的某个结点。