。
答案：根据前序序列和中序序列能得到唯一的二叉树，所得A二叉树如图：
BF
E
C
G
D
H
J
I、
这棵二叉树的后序遍历序列为：EDCBIHJGFA15、在结点个数为
1的各棵树中，高度最小的树的高度是多少？它有多少个叶结点？多少个分支结点？高度最大的树的高度是多少？它有多少个叶结点？多少个分支结点？答案：结点个数为
时，高度最小的树的高度为1，有2层；它有
1个叶结点，1个分支结点；高度最大的树的高度为
1有
层；它有1个叶结点，
1个分支结点。16、对于一个高度为h的AVL树，其最少结点数是多少？反之，对于一个有
个结点的AVL树其最大高度是多少最小高度是
f多少答案：设高度为h空树的高度为1的AVL树的最少结点为Nh，则NhFh31。Fh是斐波那契数。又设AVL树有
个结点，则其最大高度不超过32log2
1最小高度为「log2
1┐1。17、77设有序顺序表中的元素依次为017094154170275503509512553612677765897908。试画出对其进行折半搜索时的判定树并计算搜索成功的平均搜索长度和搜索不成功的平均搜索长度。答案：折半搜索时的判定树为：
509
154
677
017
275
553
897
094170503512612765908
ASLSUCC114（1223447）4514ASLUNSUCC115（31414）5915
五、算法分析题6、请读下列程序，该程序是在单链表中删
f除一个结点的算法，为空出的地方填上正确
的语句。（7分）
voiddemo2Li
kList
headListNodep
head是带头结点的单链表，
删除P指向的结点
ListNodeqhead
whileqq
extp

qq
ext
ifqError“p
oti

head”
q
extp
ext
freep

10、判断一个带表头结点的双向循环链表L
是否对称相等的算法如下所示，请在算法的
处填入正确的语句。
i
tsymmetryDblListDL
i
tsym1
DblNode
pDLrLi
kqDLlLi
k
WhilepqplLi
kq
sym1
ifpdataqdata
fpprLi
kqqlLi
k
elsesym0retur
sym
fr