15．便于进行布尔查询的文件组织方式是（　　　）

A．顺序文件                                                    B．索引文件

C．散列文件                                                    D．多关键字文件

二、填空题（本大题共10小题，每小题2分，若有两个空格，每个空格1分，共20分）

请在每个空格中填上正确答案。错填、不填均无分。

16．数据的链式存储结构的特点是借助________表示数据元素之间的逻辑关系。

17．如果需要对线性表频繁进行________或________操作，则不宜采用顺序存储结构。

18．如图所示，可以利用一个向量空间同时实现两个类型相同的栈。其中栈1为空的条件是top1=0，栈2为空的条件是top2=n-1，则“栈满”的判定条件是________。

19．静态存储分配的顺序串在进行插入、置换和________等操作时可能发生越界。

20．广义表L=（a，（b，( )））的深度为________。

21．任意一棵完全二叉树中，度为1的结点数最多为________。

22．求最小生成树的克鲁斯卡尔(Kruskal)算法耗用的时间与图中________的数目正相关。

23．在5阶B-树中，每个结点至多含4个关键字，除根结点之外，其他结点至少含________个关键字。

24．若序列中关键字相同的记录在排序前后的相对次序不变，则称该排序算法是________的。

25．常用的索引顺序文件是________文件和________文件。

三、解答题(本大题共4小题，每小题5分，共20分)

26．如图所示，在n×n矩阵A中，所有下标值满足关系式i+j＜n+l的元素a_ij的值均为0，现将A中其它元素按行优先顺序依次存储到长度为n(n+1)/2的一维数组sa中，其中元素a_1，n存储在sa［0］。

(1)设n=10，元素a_4，9存储在sa［p］，写出下标p的值；

(2)设元素a_i，j存储在sa［k］中，写出由i,j和n计算k的一般公式。

27．由字符集{s，t，a，e，I}及其在电文中出现的频度构建的哈夫曼树如图所示。已知某段电文的哈夫曼编码为111000010100，请根据该哈夫曼树进行译码，写出原来的电文。

28．已知无向图G的邻接表如图所示，

(1)画出该无向图；

(2)画出该图的广度优先生成森林。

29．对序列(48，37，63，96，22，31，50，55，11)进行升序的堆排序，写出构建的初始(大根)堆及前两趟重建堆之后的序列状态。

初始堆：

第1趟：

第2趟：

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

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

(1)无向图G如图所示，写出算法

f30(&G)的返回值；

(2)简述算法f30的功能。

#define  MaxNum  20

int  visited[MaxNum]；

void  DFS(Graph  *g，int  i)；

/*从顶点v_i出发进行深度优先搜索，访问顶点v_j时置visited[j]为1*/

int  f30(Graph  *g)

{  int  i，k；

for  (i=0；  i<g->n；  i++)／*g->n为图g的顶点数目*／

visited[i]=0；

for  (i=k=0；  i<g->n;  i++)

if  (visited[i]= =0)

{  k++；

DFS(g，i)；

}

return k；

}

31．假设学生成绩按学号增序存储在带头结点的单链表中，类型定义如下：

typedef  struct  Node  {

int  id;            /*学号*/

int  score；       /*成绩*/

struct  Node   *next；

}  LNode，  *LinkList；

阅读算法f31，并回答问题：

(1)设结点结构为 ，成绩链表A和B如图所示，画出执行算法

f31(A，B)后A所指的链表；

(2)简述算法f31的功能。

void  f31(LinkList A,  LinkList B)

{  LinkList  p, q;

p=A->next;

q=B->next;

while  (p && q)

{  if  (p->id<q->id)

p=p->next;

else  if (p->i