C．41                                                                    D．62

15．ISAM文件的周期性整理是为了空出（　　　）

A．磁道索引                                                         B．柱面索引

C．柱面基本区                                                      D．柱面溢出区

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

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

16．数据类型按其值能否分解,通常可分为_________两种类型。

17．队列的修改是按_________的原则进行的。

18．两个串相等的充分必要条件是两个串的长度相等且_________。

19．数组采用顺序存储方式表示是因为通常不对数组进行_________操作。

20．用广义表的取表头head和取表尾tail的运算，从广义表LS=(b,c,(f),((d)))中分解出原子c的操作为_________。

21．结点数为20的二叉树可能达期的最大高度为_________。

22．带权连通图的生成树的权是该生成树上_________。

23．所谓“就地排序”，是指排序算法辅助空间的复杂度为_________的排序方法。

24．5阶B树的根结点至少含有_________个关键字。

25．索引文件中的索引表指示记录的关键字与_________之间一一对应的关系。

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

26．假设以有序对<p,c>表示从双亲结点到孩子结点的一条边，若已知树中边的集合为{<a,b>,<a,d>,<a,c>,<c,e>,<c,f>,<c,g>,<c,h>,<e,i>,<e,j>,<g,k>},请回答下列问题：

（1）哪个结点是根结点？

（2）哪些结点是叶子结点？

（3）哪些结点是k的祖先？

（4）哪些结点是j的兄弟？

（5）树的深度是多少？

（1）

（2）

（3）

（4）

（5）

27．已知有向图G的深度优先生成森林和广度优先生成森林如下。请写出该图的深度优先遍历序列和广度优先遍历序列。

28．当将两个长度均为n的有序表A=（a₁，a₂，…，a_n）与B=（b₁，b₂，…，b_n）(a_i≠b_j,

1≤i,j≤n)归并为一个有序表C=（c₁, c₂,…,c_2n）时，所需进行的元素比较次数最少可达n,最多可达2n-1。

（1）假设有序表C=（2，4，5，6，7，9），试举出两组A与B的例子，使它们在归并过程中进行的元素比较次数分别达到最少和最多；

（2）写出一般情况下，使归并所需进行的元素比较次数分别达到最少和最多时，A与B中的元素应满足的条件。

（1）

（2）

29．对下列关键字序列（33，25，48，59，36，72，46，07，65，20）构造表长为19的散列表。假设散列函数为h(key)=key%13,用开放地址法解决冲突，探查序列为d=h(key),d+1²,d-1²，d+2 ²,d-2 ²,d+3²，d-3²，…，等等。

（1）画出该散列表；

（2）计算该散列表的装填因子α；

（3）求出等概率情况下查找成功的平均查找长度ASL。

（1）

（2）

（3）

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

30．已知head为带头结点的单循环链表的头指针，链表中的数据元素依次为（a₁，a₂,a₃,a₄,…,a_n）,A为指向空的顺序表的指针。阅读以下程序段，并回答问题：

（1）写出执行下列程序段后的顺序表A中的数据元素；

（2）简要叙述该程序段的功能。

if(head->next!=head)

{

p=head->next;

A->length=0;

while(p->next!=head)

{

p=p->next;

A->data[A->length ++]=p->data;

if(p->next!=head)p=p->next;

}

}

(1)

(2)

31．已知链串的存储结构描述如下：

#define NodeSize   4

typedef struct Node {

char data [NodeSize];

struct      Node * next;

} * LinkStr;

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

（1）t1和t2的串值分别为″Chinese″和″China″时，写出f31(t1,t2)的返回值；

（2）t1和t2的串值分别为″Japan″和″Japanese″时，写出f31(t1,t2)的返回值；

（3）t1和t2的串值都为″stri