山东大学网络教育《数据结构》( A 卷)(4)

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

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说教育文库山东大学网络教育《数据结构》( A 卷)(4)在线全文阅读。