C.(8,13,26,29,44,55)                                                          D.(29,26,8,44,55,13)

13．采用分块查找时，要求数据

A．块内有序                                                                      B.分块有序

C．分块无序                                                                      D.每块中数据个数必须相同

14.下列关于散列函数的说法正确的是

A．散列函数越复杂越好

B.散列函数越简单越好

C．用除余法构造的散列函数是最好的

D.在冲突尽可能少的情况下，散列函数越简单越好

15.下列关于m阶B树的叙述中，错误的是

A．每个结点至多有m棵子树

B.每个结点至多有m-1个关键字

C．所有的叶结点均在同一层上

D.根结点至少有棵子树

非选择题部分

注意事项：

用黑色字迹的签字笔或钢笔将答案写在答题纸上，不能答在试题卷上。

二、填空题（本大题共10小题，每小题2分，共20分）

16．算法的时间复杂度与实现时采用的程序设计语言____________。

17．在长度为n的顺序表的第i(1≤i≤n)个元素之后插入一个元素时，需向后移动___________个元素。

18．设循环队列存放在向量data[0..m-l]中，在出队操作后，队头指针front变化为___________。

19．树的前序遍历序列等同于该树对应二叉树的____遍历序列。

20．一个100×90的整型稀疏矩阵有10个非零元素，设每个整型数占2个字节，则用三元组表存储该矩阵时，所需的字节数是___________。

21．当用二叉链表作为n个结点的二叉树的存储结构时，空指针域的个数是____。

22．采用邻接表表示n个顶点的有向图时，若表结点的个数为m，则该有向图的边数

为___________。

23．对同一个基本有序的待排序列分别进行堆排序、快速排序和冒泡排序，最省时间的

算法是___________。

24．在16个记录的有序顺序表中进行二分查找，最大比较次数是___________。

25．在排序算法中，若排序前后具有相同关键字的记录之间的相对次序保持不变，则称这种排序方法是___________的。

三、解答题（本大题共4小题，每小题5分，共20分）

26．在定义顺序表时，存放表结点的向量空间不宜过大也不宜过小，为什么？

27．画出题27图所示树的孩子链表。

题27图

28．已知一个无向图G如题28图所示，以顶点①为根，且小序号优先，分别画出G的深度优先生成树和广度优先生成树。

题28图

29．判别以下序列是否为堆，若不是，将其调整为大根堆，并画出大根堆。

①(1,5,7,20,18,8,10,40)

②(18,9,5,8,4,17,21,6)

四、算法阅读题（本大题共4小题，每小题5分，共20分）

30．单链表类型定义如下：

typedef  struct  node {

DataType  data;

struct  node   *next;

}ListNode;

typedef  ListNode  *LinkList;

阅读下列算法，并回答问题：

void  f30 (LinklList  head,  DataType  x)

{  ∥head是带头结点的非空单链表的头指针

ListNode   *p，  *q;

p=head;

while（p->next->next）

p=p->next;

q=(ListNode*) malloc (sizeof(ListNode));

q->data=x；

q->next=p->next;

p->next=q；

}

(1)该算法的功能是什么？

(2)若单链表的长度为n，算法的时间复杂度是多少？该时间复杂度和链表的初始状态有关吗？

31．阅读下列算法（假设栈的操作函数都已定义），并回答问题：

void  f31 (   )

{    SeqStack  S；

char  x， y；

x=′c′；

y=′k′；

Push (＆S，x)；

Push (＆S，′a′)；

Push (＆S，y)；

x=Pop(&S)；

Push(＆S，′t′)；

Push(＆S，x)；

x=Pop(＆S);

Push(&S，′s′)；

while  ( !StackEmpty(&S))

{   y=Pop (＆S);

putchar (y)；

}

putchar (x)；

}

(1)自底向上写出执行while语句之前栈S中的元素序列。

(2)写出该函数的最后输出结果。

32．下列算法的功能是在中序线索树中查找结点*p的前趋，填上适当内容使算法完整。

typedef  enum  { Link,Thread }  PointerTag;

∥ 枚举值Link和Thread分别为0和1

typedef  struct  node {

DataType  data;

PointerTag  ltag,  rtag;

Struct  node  *lchild,  *rchild;

}BinThrNode;

BinThrNode*f32 (BinThrNode  *p)

{ ∥ 在中序线索树中找结点*p的中序前趋，设p非空

BinThrNode  *q；

if(p->ltag==Thread)      (1)     ;

else

{

q=p->lchild；

while(q->rtag=Link)        (2)        ；

return q；

}

}

33．分析下列排序算法中语句1和语句2的频度以及此算法的时间复杂度，并指出该算法是属于哪一种排序方法。

void  f33( int  a[ ],int  n )

{  int  i，j，k，t；

for  (i=0；i<n；i++)                     ∥语句1

{  j=i；

for  （k=j+1；k<=n；k++）

if  (a[k]<a[j])  j=k；             ∥语句2

t=a[i];  a[i]=a[j];a[j]=t;

}

}

五、算法设计题（本题10分）

34．二叉排序树的类型定义如下：

typedef  struct  node {

int  data;

struct  node  *lchild,*rchild;

}*BSTree；

编写递归算法从小到大输出二叉排序树T中所有data域值大于m且小于n的数据。

函数原型为void  f34（BSTree  T， int  m， int  n）