设关键字序列是(19,24,23,17,38,27,51,34),散列表长度是11,散列函数是 H(key)=key MOD 11,计算等概率情况下查找成功的平均查找长度ASLsucc。
时间: 2024-05-18 15:13:32 浏览: 89
根据散列函数 H(key)=key MOD 11,可以将关键字序列散列到如下的散列表中:
0:
1: 51
2: 23
3: 34
4: 24
5: 38
6:
7: 17
8:
9: 19
10:27
接下来,我们可以使用公式 ASLsucc = (Σ(di+1)) / n 来计算等概率情况下查找成功的平均查找长度,其中 n 是关键字序列的长度,di 是第 i 个关键字在散列表中的查找长度。
因此,我们需要先通过散列函数计算出每个关键字在散列表中的位置,然后计算出每个关键字的查找长度 di,最后求和并除以 n。
对于关键字序列中的每一个关键字,我们可以通过 H(key) 计算出它在散列表中的位置:
H(19) = 8
H(24) = 2
H(23) = 1
H(17) = 7
H(38) = 5
H(27) = 5
H(51) = 1
H(34) = 3
因此,关键字的散列表位置和查找长度如下:
key H(key) di
19 8 1
24 2 1
23 1 1
17 7 1
38 5 1
27 5 2
51 1 2
34 3 1
接下来,我们可以计算出 ASLsucc:
ASLsucc = (Σ(di+1)) / n
= (1+1+1+1+1+2+2+1+1) / 8
= 1.375
因此,等概率情况下查找成功的平均查找长度为 1.375。
阅读全文