4
前序序列：A, B, C, D, E, F, G, H, I, J 中序序列：C, B, A, E, F, D, I, H, J, G 后序序列：
解：后序序列：C, B, F, E, I, J, H, G, D, A
4. 已知一个有序表 ( 15, 26, 34, 39, 45, 56, 58, 63, 74, 76, 83, 94 ) 顺序存储于
一维数组a[12]中，根据折半搜索过程填写成功搜索下表中所给元素34, 56, 58, 63, 94时的比较次数。
元素值
比较次数
4. 解：元素值 比较次数
5. 设散列表为HT[17], 待插入关键码序列为 { Jan, Feb, Mar, Apr, May, June, July,
Aug, Sep, Oct, Nov, Dec }，散列函数为H (key) = ?i / 2?，其中，i 是关键码第一个字母在字母表中的序号。现采用线性探查法解决冲突。 (1) 试画出相应的散列表；
(2) 计算等概率下搜索成功的平均搜索长度； 解： H(Jan) = ?10/2? = 5，成功.
H(Feb) = ?6/2? = 3，成功.
H(Mar) = ?13/2? = 6，成功.
H(Apr) = ?1/2? = 0，成功.
H(May) = ?13/2? = 6，= 7，成功， H(June) = ?10/2? = 5，= 6，= 7，=8，成功. H(July) = ?10/2? = 5，= 6，= 7，= 8，= 9，成功.
34 56 58 63 94 34 56 58 63 94
02 1 3 4 4