题20

题20

题目

Q:【2018 统考真题】现有长度为 7、初始为空的散列表 HT，散列函数 , 用线性探测再散列法解决冲突.
将关键字 22,43,15 依次插入 HT 后, 查找成功的平均查找长度是 ( ).
A. 1.5
B. 1.6
C. 2
D. 3

分析

A:根据题意, 得到的 HT 如下:

0	1	2	3	4	5	6
	22	43	15

[[刷题/408做题本/25王道/25数据结构-王道/第 7 章 查找/7.5 散列表/题6]]中涉及了一个ASL的公式，但是为什么这里不能用  这里，三个元素模上17都等于1，第一个元素，探测一次，直接落座，第二个元素，准备在1号位上，但是有人了，所以又探测一次，这就算是两次，第三个元素15，还是为1，探测两次后，一共三次才能在3号位上落座，这就是这里的1+2+3的原因。 ### 解 D ${\mathrm{{ASL}}}_{\text{成功 }} = ( {1 + 2 + 3}) /3 = 2$ 。