一.选择题(每题选择一个答案,将序号填入下划线处,每题2分,共10分)
1.假定初始序列是递增的,并且按递增序排列,则()排序方法花时间最少.
A.快速
B.shell
C.直接插入
D.冒泡
2.二维数组a[0..8,1..10]按行存放时元素a[8,5]的起始地址与按列存放时元素()的起始地址相同.
A.a[8,5]
B.a[3,10]
C.A[5,8]
D.A[0,9]
3.有一棵平衡二叉树,根结点为A,A的右孩子为B,B的左孩为叶结点C,当A,B二结点的平衡因子分别为()时,在结点C下,插入一个新结点后得到的新树是不平衡的.
A.0,0
B.1,0
C.–1,0
D.0,1
4.在循环链表中设立一个头结点的理由是().
A.便于找到链表的首结点
B.可以用头结点记录链表长度
C.可以使得作插入,删去时不必顾及插入的或删去的结点是否链表的首结点.
D.可以把首结点与尾结点公开
5.非空的广义表可与有根有序的有向图对应,如果一个有根的有向图中含有回路,那么它对应的广义表是()
A.线性表
B.纯表
C.再入表
D.递归表

二.填空题(每题2分,共10分)
1.有20个元素的有序表按二分法查找,假定查找每个元素的概率是相等的,则查找成功的平均比较次数为________次.
2.链接栈的结点有二个域:info,link,栈顶指针为st,下列程序段可以把元素x压入栈内:
new(p);p?.inf=x;______;
3.一个好的散列函数的标准是________________.
4.一个循环队列用数组Q[0..100]存贮其元素,已知队头,队尾指针分别为80与50,则当前队列中有_______个元素.
5.用200个不同的数来构造二叉排序树,其高度不会超过_______,但也不会少于_______(假定空二叉树的高度为0).

三.算法应用题(每题6分,共30分)
1.对下图表示的树林,(1)写出它的后根序序列.(2)画出与它对应的二叉树.
A D G

B E H

C F I
2.对序列(26,36,41,38,44,15,68,12,6,51,25)散列存贮于数组A[0..14]中,散列函数为H(R)=Rmod13,用线性探测法解决冲突,请画出散列表的状况.
3.设有关键码序列:51(1),73,47,95,49,51(2).试写出快速排序(从小到大)与堆排序(从大到小)的最终结果.
4.画出下图的邻接表(要求:出边表中的结点按序号由小到大排列),然后使用该邻接表手工执行深度优先算法(从结点6开始),请写出你得到的遍历序列.
1
2 6
3 5
4
5.对下图用用Prim算法从结点6开始构造最小生成树,(1)请用图表示构造的过程.(2)如果从其他结点开始,有没有可能构造出不相同的最小生成树?
(图略)

四.算法设计题(共50分)
1.求带权有向图中每对结点之间的最短路径的Floyd算法如下:
(1)(Path数组置初态)
for I:= 1 to n do
for j:= 1 to n do
if adj[I,j]<? then path[I,j]:=(1)
else path[I,j]:=(2);
(2)(求最短路径)
for k:= 1 to n do
for I:= 1 to n do
for j:= 1 to n do
if adj[I,j]>adj[I,k]+adj[k,j] then
begin adj[I,j]:=(3);path[I,j]:=(4) end
请你解答如下问题(1)完成上述算法填空.(2)矩阵adj的初值是什么?算法结束时,adj[I,j]和path[I,j]的值表示什么意义?(14分)
2.写出按对放序线索化以t为根指针的二叉树的非递归算法.假定用负指针表示线索,并且对栈的基本运算均可调用(12分)
3.写一算法,重排实型数组R[1..n]中元素的顺序,使得所有负数均排在非负数之前.(要求:不排序,附加空间0(1))(10分)
4.有一个带有头结点的循环双链表,表头指针为head,结点有四个域,data,flreg,llink,rlink,其中flreg记录结点数据的访问次数.假定链表的结点已按访问次数不增序排列.(1)画出此链表的结构示意图.(2)写一算法查找链表中是否有值为x的结点,如有,则让该结点的访问次数加1,并且要使链表仍保持不增序,如没有,则不作任何工作.(14分)