一、单项选择填空（每空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分