路
D一棵树
15用Dijkstra算法求一个带权有向图G中从顶点0出发的最短路径，在算法执行的
某时刻，S0234，下一步选取的目标顶点可能是
。
A顶点2
B顶点3
C顶点4
D顶点7
16哈希表中出现冲突是指
。
A两个元素具有相同的序号
B两个元素的关键字不同，而其他属性相同
C数据元素过多
D两个元素的关键字不同，而对应的哈希函数值（存储地址）相同
17适合于折半查找的数据组织方式是A以链表存储的线性表C以链表存储的有序线性表
。B以顺序表存储的任意线性表D以顺序表存储的有序线性表
18对有
个记录的表进行直接插入排序，在最好情况下需比较
次关键字。
A
1
B
1
C
2
D
12
19若数据元素序列1112157892315是采用下列排序方法之一得到的第二趟排
序后的结果，则该排序算法只能是
。
A冒泡排序
B直接插入排序
C选择排序
D二路归并排序
20对一组数据258421471527683520进行排序，前3趟的排序结果如下：第1趟：20，15，21，25，47，27，68，35，84
f第2趟：15，20，21，25，35，27，47，68，84
第3趟：15，20，21，25，27，35，47，68，84
则所采用的排序方法是
。
A简单选择排序
B希尔排序
C二路归并排序
二、问答题（共4小题，共计35分）
D快速排序
1（10分）对于如图1所示的带权无向图，直接给出利用普里姆算法（从顶点0开始
构造）和克鲁斯卡尔算法构造出的最小生成树的结果（注意：按求解的顺序给出最小生成
树的所有边，每条边用i，j表示）。
1
17
3
4
0526
4
2
5
38
图1一个带权无向图G
2（10分）假设一棵二叉排序树的关键字为单个字母，其后序遍历序列为ACDBFIJHGE，回答以下问题：
（1）画出该二叉排序树。（6分）（2）求在等概率下的查找成功的平均查找长度。（2分）（3）求在等概率下的查找不成功的平均查找长度。（2分）
3（8分）已知序列1551622582091812，给出采用二路归并排序法对该序列作升序排序时的每一趟的结果。
4（7分）简要回答下列关于堆排序中堆的一些问题：（1）通常堆采用顺序还是链式存储结构？（3分）（2）设有一个小根堆，即堆中任意结点的关键字均小于它的左孩子和右孩子的关键字。其中具有最大关键字的结点可能在什么地方？（4分）
三、算法设计题（共2小题，共计25分）
1（10分）某带头结点的非空单链表L中所有元素为整数，结点类型定义如下：
typedefstruct
odei
tdata
struct
ode
extLi
kNode
设计一个尽可能高效的算法，将所有小于零的结点移到所有大于等于零的结r