2002年中科院网络中心数据结构考研试卷
一、单项选择填空（每空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)}，要选取下一权值最小的边，应当从
  （ ）组中选取。
   ∞  2   12  10  ∞
   2   ∞  8   ∞  9
   12  8   ∞  6   3
   10  ∞  6   ∞  7
   ∞  9   3   7   ∞
   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分