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

C.直接存取文件                                               D.间接存取文件

二、填空题(本大题共10小题，每小题2分，共20分)

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

16.数据的逻辑结构描述数据元素之间的_________________，与存储方式无关。

17.在一个长度为100的顺序表中删除第10个元素时，需移动___________________个元素。

18.队列的队尾位置通常是随着______________操作而变化的。

19.两个空串联接得到的串的长度为___________________。

20.设对称矩阵A压缩存储在一维数组B中，其中矩阵的第一个元素a₁₁存储在B[0]，元素a₅₂存储在B[11]，则矩阵元素a₃₆存储在B[______________]中。

21.已知一棵哈夫曼树含有60个叶子结点，

则该树中共有________________个非叶子结点。

22.如图所示的有向图中含有

_______________个强连通分量。

23.已知一组关键字为{15，36，28，97，24，78，47，52，13，86}，其中每相邻两个关键字构成一个有序子序列。对这些子序列进行一趟两两归并的结果是______________。

24.从空树起，依次插入关键字1l，27，35，48，52，66和73构造所得的二叉排序树，在等概率查找的假设下，查找成功时的平均查找长度为____________________。

25.控制区间和控制区域是________________文件的逻辑存储单位。

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

26.利用广义表的head和tail操作，可从广义表

           L=((a，b)，(c，d))

   中分解得到原子c，其操作表达式为

           head(head(tail(L)))；

   分别写出从下列广义表中分解得到b的操作表达式。

   (1)L1=(a.，b，c，d)；

   (2)L2=(((a)，(b)，(c)，(d)))。

   (1)

   (2)

27.画出与如图所示森林对应的二叉树。

28.已知有向图G的定义如下：

    G=(V，E)

    V={a，b，c，d，e}

    E={<a，b>， <a，c>，<b，c>，<b，d>，<c，d>，<e，c>，<e，d>}

    (1)画出G的图形；

    (2)写出G的全部拓扑序列。

    (1)

    (2)

29.已知3阶B-树如图所示。

    (1)画出将关键字88插入之后的B-树；

    (2)画出将关键字47和66依次插入之后的B-树。

(1)

(2)

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

30.假设某个不设头指针的无头结点单向循环链表的长度大于1，s为指向链表中某个结点的指针。算法f 30的功能是，删除并返回链表中指针s所指结点的前驱。请在空缺处填入合适的内容，使其成为完整的算法。

  typedef struct node {

  DataType data；

  struct node  *next；

  }*LinkList；

  DataType f 30(LinkList s) {

  LinkList pre，p；

  DataType e；

    pre=s；    ’

    p=s->next；

    while(    (1)    ){

pre=p;

____________(2)             ;

}

pre ->next=      (3)      ;

e=p->data;

free(p);

return e;

}

(1)

(2)

(3)

31.算法f31的功能是清空带头结点的链队列Q。请在空缺处填入合适的内容，使其成为一个完整的算法。

typedef struct node{

      DataType data；

struct node  *next；

}QueueNode；

typedef struct {