数据结构-哈希表

3（5）

假设有一个哈希存储的查找表{59，34，19，28，76，63}，有哈希地址[0，1，2，3……10]，使用哈希函数H(key)=key%11，将查找表存储在哈希地址中，然后解决下列问题： a. 将67，14，92，43插入上面的表中，使用线性探测法解决冲突。 解：

H(59)=59mod11=4 H(34)=34mod11=1 H(19)=19mod11=8 H(28)=28mod11=6 H(76)=76mod11=10 H(63)=63mod11=8 H(67)=67mod11=1 H(14)=14mod11=3 H(92)=92mod11=4 H(43)=43mod11=10 43 0 34 1 67 2 14 3 59 4 92 5 28 6 7 19 8 63 9 76 10 b. 计算是否有冲突出现，冲突出现的次数是多少？ 答：冲突出现的次数一共是4次。 c. 查询43的比较次数是多少？ 答：比较次数是2次

d. 请计算查找成功的ASL。

解：查找成功的ASL=（2+1+2+1+1+2+1+1+2+1）/9=14/9

3（6）

对下列关键字序列（87，25，310，08，27，132，68，96，187，133，70，63，47，135）构造散列表，假设散列函数为h（hey）=key%13，用链地址法解决冲突。 a. 画出散列表；

解：h（87）=87%13=9 h（25）=25%13=12 h（310）=310%13=11 h（08）=08%13=8 h（27）=27%13=1 h（132）=132%13=2 h（68）=68%13=3 h（96）=96%13=5 h（187）=187%13=5 h（133）=133%13=3 h（70）=70%13=5 h（63）=63%13=11 h（47）=47%13=8 h（135）=2135%13=5

由于散列表的链地址物理上不是

相邻的，所以最好不要像这样挨 着画。 HLL

0 1 2 3 4 5 6 7 8 9 Λ Λ Λ Λ 27 Λ 132 Λ 133 135 47 87 63 25 Λ 310 Λ Λ 08 Λ 68 70 187 96

Λ Λ

10 Λ 11 12

b. 求等概率情况下查找成功的平均查找长度ASL； 解：ASL=（1+1+1+1+1+1+2+2+4+3+2+1+2+1）/14=23/14

c. 写出删除值为70的关键字所需进行的关键字比较次数。 答：比较次数为2次。