一、单项选择填空（每空2分，共20分）
    
    1，设两算法的执行时间分别是T1=2n2+10n1.01+300nlog2n和T2=1.5n2+100n1.01+3nlog2  n，若要比较他们的时间性能，较为合适的表示是（ ）。
    
    a) T1=2n2+O(n1.01),T2=1.5n2+O(n1.01)
    
    b) T1=2n2+O(nlog2n),T2=1.5n2+O(nlog2n)
    
    c) T1=O(n2),T2=O(n2)
    
    d) T1=2n2+O(300nlog2n),T2=1.5n2+O(3nlog2n)
    
    2，以数组Q[0..m-1]存放循环队列中的元素，若变量front和qulen分别指示循环队列中队头元素的实际位置和当前队列的长度，则队尾元素的实际位置是（ ）。
    
    a) front+qulen-1
    
    b) (front+qulen) mod m
    
    ]  c) (front+qulen-1) mod m
    
    d) front+qulen
    
    3，设结点x和y是二叉树中的任意两结点，若在该树的先根、中根和后根序列里，x和y中的一个结点皆在另一个结点之前，则它们的关系是（ ）。
    
    a) x和y必互为兄弟
    
    b) x和y必是树叶
    
    c) 一个是另一个的祖先
    
    d) 彼此无祖先和后代的关系
    
    4，若将数据结构中的数据元素称为结点，则一般没有开始结点和终端结点的数据结构是（ ）。
    
    a) 树 b) 图 c) 多维数组 d) 线性表
    
    5，用prim算法求下述邻接矩阵表示的连通带权图的最小生成树，在算法执行的某一时刻，已选取的顶点集合为U={1,2}，边的集合TE={(1,2)}，要选取下一权值最小的边，应当从  （ ）组中选取。
    
    ∞  212  10  ∞
    
    2∞  8∞  9
    
    12  8∞  63
    
    10  ∞  6∞  7
    
    ∞  937∞
    
    a) {(1,4)，(2,3)，(2,5)}
    
    b) {(3,5)，(3,4)，(4,5)}
    
    c) {(1,3)，(3,4)，(3,5)}
    
    d) {(2,3)，(3,4)，(2,5)}
    
    6，设根的层数为0。n个结点的m叉树的高度至少是（ ）。
    
    a) └logm(n(m-1))┘+1
    
    b) ┌logm(n(m-1))┐
    
    c) ┌logm(n(m-1))┐+1
    
    d) ┌logm(n(m-1))┐-1
    
    7 ，在下列各种数据结构中，查找操作低效的是（ ）。
    
    a) 二叉排序树 b) AVL树 c) 有序的顺序表 d) 堆
    
    8，在一棵高度为h的2-3树中（设根的层数为1），叶子的数目至少应为（ ），至多应为（ ）。
    
    a) 2h-1 b) 2h-1 c) 2h d) 2h-1-1 e) 3h-1 f) 3h-1 g) 3h h) 3h-1-1 9，
    
    用直接选择排序方法分别对序列S1=(1,2,3,4,5,6,7)和序列S2=(7,5,3,2,4,1,6)进行排序，关键字比较次数（ ）。
    
    a) 相同 b) 前者大于后者 c) 前者小于后者
    
    二、简要回答下述问题（共15分）。
    
    1，当m阶B－树用于内查找时，通常m取3，为什么？
    
    2，设有两个算法运行于同一台机器上，其执行时间分别是1024n2和2n，要使前者快于后者，n要多大？
    
    3，三层、四层二叉树有多少种形态？请给出求n层二叉树形态数递推公式。
    
    三、阅读程序并填空（共20分）
    
    1，以下C程序的功能是将整数n转换为相应的字符串，请在空白处填上正确的C语句
    
    void itoa(int n,char* s)
    
    { int sign;
    
      char c,*t = s;
    
      if((sign = n)<0)
    
      ___①___;
    
      do { *t++ = n%10 + '0'; }
    
      while ___②___;
    
      if(sign < 0)
    
      *t++ = '-';
    
      *t = '/0';
    
      for(___③___;  s < t;  s++,t--)
    
      { c = *s;
    
     *s = *t;
    
     *t = c;
    
      }
    
    }
    
    该算法的时间复杂度是___④___;
    
    2，以下的C程序是一个既可以做升序又可以做降序排序算法，请在空白处填上正确的C语句或表达式。这里的Comp是一个什么指针？请给出它所对应函数，以及对QuickSort的调用语句，
    
    完成对整数数组R[0..n-1]的升序排序。
    
    void QuickSort(int A[], int start, int end, int(*Comp)(int x, int y))
    
    { int low = start; int high = end; int separator = A[low];
    
      if(start < end)
    
      { while(low < high)
    
     { while(low < high && ((*Comp)(A[high], separator)))
    
    high--;
    
    if(low < high)
    
    A[low++] = A[high];
    
    while(low < high && ___①___)
    
    low++ ___②___;
    
     }
    
     A[low] = separator;
    
     QuickSort(___③___);
    
     QuickSort(___④___);
    
    四、算法题（每题15分，共45分，要求写注解或设计思想）。
    
    1，设主串和子串分别存放在字符数组S[0..n-1]和T[0..n-1]中， 写一串匹配算法，输出T在S中所有的匹配位置（例如，若S="This is a list",T="is"，则输出2，5和11）并给出算法的时间复杂度。
    
    2，对有向图进行拓扑排序可通过不断地删除出度为0的顶点来实现， 试以邻接表为存储结构写一算法实现之。要求输出的顶点序列是拓扑序列。
    
    3， 设有n个班皆要在同一个活动中心举行元旦晚会，且所有班的时间表均以确定。第i(1 ≤ i ≤ n) 个班的晚会开始时间和结束时间分别为Si和Fi，这里Si≤Fi。试写一个算法，安排尽可能多的时间不冲突的班使用活动中心。
    
    参考答案
    
    一、单项选择填空（每空2分，共20分）
    
    1,a 2,c 3,d 4,b 5,a
    
    7,d 8,b,f 9,a
    
    二、简要回答下述问题（共15分）。
    
    1，因为B－树的高度为O(logtn),这里t = ┌ m/2 ┐。
    
    当B－树用于内查找时，其时间为O(mlogtn)，这里m是结点内的查找时间。而 O(mlogtn) = O(log2n(m/log2t))), 这里O(log2n)是平衡的二叉排序树的查找时间，当m较大时，m/log2t远大于1，因此B－树用于内查找的时间也远远大于平衡的二叉排序树的查找时间。
    
    2，19
    
    3，假设n-1层二叉树的形态数为f(n-1)，则n层二叉树的形态数为：
    
    f(n) = f(n-1) * f(n-1) + 2 * f(n-1) *(f(n-2) + ... + f(1) + 1)
    
    f(1) = 1; f(2) = 3; f(3) = 21; f(4) = 651;
    
    三、阅读程序并填空（每空2分，共20分）
    
    1,① n = -n ② ((n /= 10) > 0) ③ t-- (或--t,t=t-1)
    
    ④ O(log10n)
    
    2,① ((*Comp)(separator,A[low])) ② if(low < high) A[high--] = A[low]
    
    ③ A, start, high - 1, Comp ④ A, low + 1, end, Comp
    
    Comp是一个函数指针 //1分
    
    int CompAscending(int x, int y) { return x >= y; } //2分
    
    调用: QuickSort(R, 0, n - 1, CompAscending); //1分