C．3.4                                                            D．5.5

15．在下列各种文件中，不能进行顺序查找的文件是(       )

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

C．散列文件                                                  D．多重表文件

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

16．抽象数据类型是指数据逻辑结构及与之相关的___________。

17．已知在结点个数大于1的单循环链表中，指针p指向表中某个结点，则下列程序段执行结束时，指针q指向结点*p的___________结点。

              q=p;

         while(q->next!=p)q=q->next;

18．假设S和X分别表示进栈和出栈操作，由输入序列“ABC”得到输出序列“BCA”的操作序列为SSXSXX，则由“a*b+c/d”得到“ab*cd/+”的操作序列为___________。

19．在文本编辑程序中查找某一特定单词在文本中出现的位置，可以利用串的___________运算。

20．假设以行优先顺序将一个n阶的5对角矩阵压缩存储到一维数组Q中，则数组Q的大小至少为___________。

21．在含100个结点的完全二叉树中，叶子结点的个数为___________。

22．在无向图中，若从顶点a到顶点b存在___________，则称a与b之间是连通的。

23．如果排序过程不改变___________之间的相对次序，则称该排序方法是稳定的。

24．索引顺序查找适宜对___________的顺序表进行查找。

25．文件的检索操作可按检索条件不同分为下列四种询问，它们是简单询问、范围询问、函数询问及___________。

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

26．画出下图所示二叉树的中序线索链表的存储表示。

27．已知图G=（V，E），其中：

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

E={(a,b),(b,d),(c,b),(c,d),(d,e),(e,a),(e,c)}。

（1）画出图G；

（2）画出图G的邻接表。

（1）

（2）

28．已知自顶向下的二路归并排序的算法如下所示，按此算法对关键字序列（55，28，73，91，37，64，19，82，46）进行排序，列出算法执行过程中前5次调用Merge函数进行归并之后的关键字序列。

void MergeSorDC(SeqList R, int low, int high)

{// 用分治法对R[low..high]进行二路归并排序}

  int mid;

  if (low<high){                                              //区间长度大于1

    mid=(low+high)/2;                                    //分解

    MergeSortDC(R, low, mid);                       //递归地对R[low..mid]排序

    MergeSortDC(R,mid+1,high);                     //递归地对R[mid+1..high]排序

 &nb