问题
单项选择题
已知一个线性表(16，25，35，43，51，62，87，93)，采用散列函数H(Key)=Key mod 7将元素散列到表长为9的散列表中。若采用线性探测的开放定址法解决冲突(顺序地探查可用存储单元)，则构造的哈希表为 (15) ，在该散列表上进行等概率成功查找的平均查找长度为 (16) (确定为记录在查找表中的位置，需和给定关键字值进行比较的次数的期望值称为查找算法在查找成功时的平均查找长度)。
（16）处填（）。
A．(5*1+2+3+6)/8
B．(5*1+2+3+6)/9
C．(8*1)/8
D．(8*1)/9
答案
参考答案：A
解析：
[分析]： 哈希表的构造是软件设计师常考知识点，考生需重点掌握。在本题中，表长为9的散列表初始时为空，散列函数为：H(Key)=Key mod 7根据哈希表的构造方法有：H(16)=16 mod 7=2; H(25)=25 mod 7=4; H(35)=35 mod 7=0; H(43)=43 mod 7=1。
前4个数都不冲突，可以直接填入散列表的相应位置，即：
继续取第五个元素51，有：H(51)=51mod 7=2，第2个单元已经填入16了，冲突了，所以要进行第一次线性探索，即：H(51)=(51+1)mod 7=3，第三单元为空，可以填入51。
依次往下做，做到第八个元素93的时候得到的散列表如C选项所示。
根据自己的解题过程，每个元素冲突的次数是显然的，所以在该散列表上进行等概率成功查找的平均查找长度为：(5*1+2+3+6)/8。
