13.下列排序方法中,最好与最坏时间复杂度不相同的排序方法是 A.冒泡排序 B.直接选择排序 C.堆排序 D归并排序 14.已知含10个结点的二叉排序树是一棵完全二叉树,则该二叉排序树在等概率情况下查找成功的平均查 找长度等于() A.1.0 B.2.9 C.3.4 15在下列各种文件中,不能进行顺序查找的文件是() A.顺序文件 B索引文件 C散列文件 D多重表文件 第二部分非选择题(共70分) 填空题(本大题共10小题,每小题2分,共加0分)请在每小题的空格中填上正确答案。错填、不填 均无分 6抽象数据类型是指数据逻辑结构及与之相关的 17.已己知在结点个数大于1的单循环链表中,指针p指向表中某个结点,则下列程序段执行结束时,指针q 指向结点*p的 结点 qp while(q->nextI=p)q=p->next 18假设S和Ⅹ分别表示进栈和出栈操作,由输入序列“ABC”得到输出序列“BCA”的操作序列为 SSXSXX, 则由“a*b+cd得到“ab*cd/+”的操作序列为」 19在文本编辑程序中查找某一特定单词在文本中出现的位置,可以利用串的 运算 20.假设以行优先顺序将一个n阶的5对角矩阵压缩存储到一维数组Q中,则数组Q的大小至少 为 21在含100个结点的完全二叉树中,叶子结点的个数为 2在无向图中,若从顶点a到顶点b存在 则称a与b之间是连通的 23如果排序过程不改变 之间的相对次序,则称该排序方法是稳定的 24索引顺序查找适宜对 的顺序表进行查找 25文件的检索操作可按检索条件不同分为下列四种询问,它们是简单询问、范围询问、函数询问 及 三、解答题(本大题共4小题,每小题5分,共20分) 26画出下图所示二叉树的中序线索链表的存储表示 27已知图G=(V,E),其中 V=fa, b, c, d, el E={(a,b),b,d),cb),c,d),(de),(e,a)e,c)}。 (1)画出图G (2)画出图G的邻接表 28已知自顶向下的二路归并排序的算法如下所示,按此算法对关键字序列(55,28,73,91,37,64,19 82,46)进行排序,列出算法执行过程中前5次调用 Merge函数进行归并之后的关键字序列 void Merge SortDC(SeqListR, int low, int high) {用分治法对R[ow.high进行二路归并排序 int mid- if (low<high ∥区间长度大于1 mid=(low+high)/2 ∥分解 MergeSortDO(Rlow,mid);∥递归地对Rlow.mid]排序 MergeSort(Rmid+l,high),∥递归地对R[mid+1.high排序 Merge(r, low, mid, high); ∥组合,将两个有序区归并为一个有序区13.下列排序方法中，最好与最坏时间复杂度不相同的排序方法是（ ） A.冒泡排序 B.直接选择排序 C.堆排序 D.归并排序 14.已知含 10 个结点的二叉排序树是一棵完全二叉树，则该二叉排序树在等概率情况下查找成功的平均查 找长度等于（ ） A.1.0 B.2.9 C.3.4 D.5.5 15.在下列各种文件中，不能进行顺序查找的文件是（ ） A.顺序文件 B.索引文件 C.散列文件 D.多重表文件 第二部分 非选择题（共 70 分） 二、填空题（本大题共 10 小题，每小题 2 分，共 20 分）请在每小题的空格中填上正确答案。错填、不填 均无分。 16.抽象数据类型是指数据逻辑结构及与之相关的 。 17.已知在结点个数大于 1 的单循环链表中，指针 p 指向表中某个结点，则下列程序段执行结束时，指针 q 指向结点*p 的 结点。 q=p; while (q-＞next!=p)q=p-＞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 的邻接表。 28.已知自顶向下的二路归并排序的算法如下所示，按此算法对关键字序列（55，28，73，91，37，64，19， 82，46）进行排序，列出算法执行过程中前 5 次调用 Merge 函数进行归并之后的关键字序列。 void MergeSortDC(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]排序 Merge(R,low,mid,high); //组合，将两个有序区归并为一个有序区 F A B C D E K