问答题采用散列函数H(k)=3×k MOD 13并用线性探测开放地址法处理冲突，在数列地址空间[0..12]中对关键字序列22，41，53，46，30，13，1，67，51

问答题构造散列表(画示意图)；

【正确答案】各关键字的散列函数值如下表1所列：

表1
key	22	41	53	46	30	13	1	67	51

H(key)	1	6	3	8	12	0	3	6	10

　采用线性探测法再散列法处理冲突，所构造的散列表见表2：

表2
下标	0	1	2	3	4	5	6	7	8	9	10	11	12
关键字	13	22		53	1		41	67	46		51		30
探查次数	1	1		1	2		1	2	1		1		1

【答案解析】

问答题装填因子；

【正确答案】装填因子=关键字总数/表长=9/13≈0.7。

【答案解析】

问答题等概率情况下查找成功的平均查找长度；

【正确答案】设查找成功在每个关键字上是等概率的，则查找每个关键字的概率为1/9，各关键字的探查次数见表3：

表3
关键字	13	22	53	1	41	67	46	51	30
成功时的探查次数	1	1	1	2	1	2	1	1	1

所以有，ASL_succ=(1+1+1+2+1+2+1+1+1)/9=11/9。

【答案解析】

问答题等概率情况下查找失败的平均查找长度。

【正确答案】设不成功的查找在每个地址上发生的概率相同，平均概率为1/13，对每个位置不成功查找的探查次数见表4：

表4
下标	0	1	2	3	4	5	6	7	8	9	10	11	12
关键字	13	22		53	1		41	67	46		51		30
不成功时的探查次数	3	2	1	3	2	1	4	3	2	1	2	1	4

以散列地址在位置2的关键字为例，由于此处关键字为空，只需比较1次就可确定本次查找不成功；以散列地址在位置3的关键字为例，若该关键字不在散列表中，需要将它与从位置3开始向后直至位置5的关键字相比较，由于位置5的关键字为空，所以不再向后比较，共比较3次，其他的类推得到。
所以有，ASL_unsucc=(3+2+1+3+2+1+4+3+2+1+2+1+4)/13=29/13。

【答案解析】[解析] 用线性探测法解决冲突构造散列表，并对查找性能进行分析，具体解题步骤如下。