第一部分 选择题 (共20分)

一、单项选择题 (本大题共8小题，每小题2分，共16分)
   1.某算法的空间花费s(n)=100nlog2n+0.5n1.5+1000n+2000,其空间复杂度为 [    ]
　　A.O(1)                       B.O(n)
     C.O(n1.5)                    D.O(nlog2n)

   2.在单项链表中删除一个指定结点的后继的时间复杂度为 [    ]
　　A.O(n)                       B.O(nlog2n)
     C.O(1)                       D.O(√n)

   3.在n(n>0)个元素的顺序栈中删除1个元素的时间复杂度为 [    ]
　　A.O(1)                       B.O(√n)
     C.O(nlog2n)                  D.O(n)

   4.对长度为n的字符串进行字符定位运算的时间复杂度为 [    ]
     A.O(1)                       B.O(√n)
     C.O(nlog2n)                  D.O(n)

   5.广义表的深度是 [    ]
     A.广义表中子表个数            B.广义表括号个数
     C.广义表展开后所含的括号层数 D.广义表中元素个数

   6.高度为h(h>0)的二叉树最少有________个结点 [    ]
     A.h                           B.h-1
     C.h+1                         D.2h

   7.n个顶点的带权无向连通图的最小生成树包含________个顶点 [    ]
     A.n-1                         B.n
     C.n/2                         D.n+1

   8.冒泡排序在最好情况下时间复杂度为 [    ]
　　A.O(1)                       B.O(nlog2n)
     C.O(n)                       D.O(n2)

    9.采用拉链法解决冲突的散列表中，查找的平均查找长度 [    ]
     A.直接与关键字个数有关       B.直接与装填因子a有关
     C.直接与表的容量有关         D.直接与散列函数有关

   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]<s2[j])
           return -1;
         else i++,j++;
       }
       if(s1[i])
          return 1;
       else if(s2[j])
          return -1;
       else return 0;
     }

27.指出下面函数FS的功能。其中，p指向先序线索二叉树的某个结点。
     typedef enum{LINK,THERAD}flag;
     typedef char DataType;
     typedef struct node{
       DataType data;
       flag ltag,rtag;
       struct node * lchild, * rchild;
     }BinNode;
     BinNode * FS(BinNode *p)
     {
       if(p->ltag==LINK)
         return p->lchild;
       else
         return p->rchild;
     }

五、算法填充题 (本大题共1小题，18分)
28.下面函数diff的功能是：根据两个由整数（都大于-32768）按升序构成的单链表L1和L2（分别由A，B指向）构造一个单链表L3（由*r指向），要求L3中的所有整数都是L1并且不是L2中的整数，还要求L3中的所有整数都两两不等。在空缺处填上适当字句，使其能正确工作。
     #include <malloc.h>
     typedef struct node {
       int d;
       struct node *next
     } Node;
     void diff (Node *A, Node *B, Node **r)
     {
       int lastnum;
       Node * p;
       *r=NULL;
       if(!A)return;
       while(_____________)
         if (A->d < B->d)
            _____________;
            p=(Node*) malloc (sizeof(Node));
            p->d=lastnum;
            p->next=*r,_____________;
            do A=A->next;while(_____________);
         }
         else if (A->d > B->d)
            B=B->next
         else {
              _____________;lastnum=A->d;
              while (A&&A->d==lastnum)A=A->next;
            }
        while (A) {
          lastnum=A->d;
          p=(Node*) malloc (sizeof(Node));
          p->d=lastnum;
         _____________,*r=p;
         while (A&&A->d==lastnum) A=A->next;
       }
     }