）
17p－＞
ext－＞
ext
18．进栈和退栈
19．12
20．a48
21．384
22．abefcdg
23．快速排序、堆排序、希尔排序
24．２
25多关键字
三、解答题（本大题共4小题，每小题5分，共20分）
26．
f图1
图2
27．
28．该图的图形为：
深度优先遍历序列为：abdce广度优先遍历序列为：abedc29．（１）对关键字35、20、33和48进行查找的比较次数为３、２、１、１；
（２）平均查找长度ASL321129
5
5
四、算法阅读题（本大题共4小题，每小题5分，共20分）
30．①S1S1－
ext
②s2s2－
ext
③s2或s2NULL或s2s1
④s1或s1NULL或s1s2
⑤retur
0
31（1）查询链表的尾结点
（2）将第一个结点链接到链表的尾部，作为新的尾结点
（3）返回的线性表为（a2a3…a
a1）32①i＋12或1－i
②Q－reari
③Q－reari＋Maxsize
331Leafhead
F
H
G
D∧
（2）中序遍历二叉树，按遍历序列中叶子结点数据域的值构建一个以Leafhead为头指针的逆序单链表（或按二叉树中叶子结点数据自右至左链接成一个链表）。
五、算法设计题（本题共10分）34．（1）该函数的功能是：调整整数数组a中的元素并返回分界值i，使所有＜x的元素均落在a1i上，使所有≥x的元素均落在ai＋1h上。
f（2）i
tfi
tbi
t

或i
tfi
tbi
t



i
tpq；
i
tpq；
parra
geb0
－10；parra
geb0
－11；
qarra
gebp1
－11；qarra
geb0p0；
retur
q－p；
retur
p－q；


20031数据结构试题
一、单项选择题本大题共15小题，每小题2分，共30分。在每小题的四个备选答案中，
选出一个正确答案，并将正确答案的序号填在题干的括号内
1下面程序段的时间复杂度是D
fori0ilt
i
forj1jltmj
Aij0；
AO

BOm
1
COm

DOm

2在单链表中，指针p指向元素为x的结点，实现“删除x的后继”的语句是B
Appgt
ext
Bpgt
extpgt
extgt
ext
Cpgt
extp
Dppgt
extgt
ext
3在头指针为head且表长大于1的单循环链表中，指针p指向表中某个结点，若
pgt
extgt
exthead则D
Ap指向头结点
Bp指向尾结点
Cp的直接后继是头结点DP的直接后继是尾结点
4判定“带头结点的链队列为空”的条件是C
AQfro
tNULL
BQrearNULL
CQfro
tQrear
DQfro
tQrear
5设有两个串T和P，求P在T中首次出现的位置的串运算称作D
A联接
B求子串
C字符定位
D子串定位
6广义表Aabcde的长度为A
A4
B5
C6
D7
7一棵含18个结点的二叉树的高度至少为C
A3
B4
C5
D6
8已知二叉树的先序序列为ABDECF，中序序列为DBEAFCr