(5)设哈希表的地址范围为0~17,哈希函数为:H(key)=key%16。用线性探测法处理冲突,输入关键字序列:(10,24,32,17,31,30,46,47,40,63,49),构造哈希表,试回答下列问题: ① 画出哈希表的示意图; ② 若查找关键字63,需要依次与哪些关键字进行比较? ③ 若查找关键字60,需要依次与哪些关键字比较? ④ 假定每个关键字的查找概率相等,求查找成功时的平均查找长度。
时间: 2023-10-05 12:13:44 浏览: 114
① 哈希表示意图如下:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 |
|---|---|---|---|---|---|---|---|---|---|----|----|----|----|----|----|----|----|
| | | | | | | | | | | 10 | 31 | 40 | 30 | 46 | 17 | 47 | 24 |
| | | | | | | | | | | 32 | 49 | 63 | | | | | |
② 查找关键字63,需要依次与关键字63进行比较。
③ 查找关键字60,需要依次与关键字0、1、2、3、4、5、6、7、8、9、10、11、12、13、14、15、16、17进行比较。
④ 每个关键字的查找概率相等,成功查找一个关键字的平均查找长度为:
$ASL = \frac{1}{n} \sum_{i=1}^{n} l_i$
其中,$n$为关键字的个数,$l_i$为查找第$i$个关键字时所需的比较次数。
对于这里的哈希函数,每个关键字最多需要比较17次才能找到合适的位置。因此,平均查找长度为:
$ASL = \frac{1}{11} \sum_{i=1}^{11} l_i = \frac{1}{11} (1 + 1 + 1 + 1 + 1 + 1 + 2 + 2 + 2 + 2 + 1) = \frac{14}{11} \approx 1.27$
相关推荐
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![text/x-c](https://img-home.csdnimg.cn/images/20210720083646.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![txt](https://img-home.csdnimg.cn/images/20210720083642.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)