设散列表的长度为8,散列函数h(k)=kmod7
时间: 2023-11-30 10:00:51 浏览: 160
散列表的长度为8意味着散列表中有8个存储位置。散列函数h(k)=kmod7表示对关键字k进行取模运算并将结果作为存储位置的索引值。
具体来说,当我们向散列表中插入一个关键字时,我们首先对关键字进行散列函数计算,得到的结果为k对7取模的值。例如,如果关键字k=15,那么h(k)=15mod7=1,意味着关键字15会被存储在散列表的第1个位置上。
散列表的长度为8,散列函数h(k)=kmod7,意味着散列表中的存储位置索引值的范围是0到7。实际上,对于当前的散列函数和散列表长度,任意关键字经过散列函数计算后得到的结果都在0到6之间,这样就可以保证插入时能够找到对应的存储位置。
在使用散列函数h(k)=kmod7时,需要注意关键字的选择和散列表的大小,以保证散列函数计算的结果能够均匀地分布在散列表中,从而避免发生过多的冲突。当发生冲突时,可以采用开放定址法、链地址法等方法进行解决。
总而言之,散列表的长度为8,散列函数h(k)=kmod7,通过合理的关键字选择和冲突解决方法,可以有效地进行散列表的插入、查找和删除等操作。
相关问题
6、设散列表长度为11,散列函数H(k)=k MOD 11,若输入顺序为(2,4,18,23,26,7,12,33,66,34)。试用链地址法解决冲突构造散列表。
首先根据散列函数H(k)=k mod 11计算每个关键字的散列地址,得到以下结果:
2→0,4→4,18→7,23→1,26→4,7→7,12→1,33→0,66→0,34→1
然后按照散列地址将关键字分别存入对应的链表中,得到以下散列表:
0:2→33→66
1:23→12→34
2:
3:
4:4→26
5:
6:
7:18→7
8:
9:
10:
注:箭头→表示链表中的指针指向下一个元素。
最终得到的散列表如上所示,其中每个链表中的元素按照输入顺序依次存储。如果需要查询某个关键字对应的值,则可以先计算其散列地址,然后在对应的链表中进行查找。如果存在多个关键字映射到同一个散列地址,则需要在对应的链表中进行顺序查找,直到找到目标元素或者链表结束。
2、设散列表的长度为8,散列函数H(k)=k mod 7,初始记录关键字序列为(25,31,8,37,13,40),要求分别计算出用线性探测法和链地址法作为解决冲突方法的平均查找长度。
首先,根据散列函数H(k)=k mod 7,可以得到关键字的散列地址如下:
25 -> 4
31 -> 3
8 -> 1
37 -> 2
13 -> 6
40 -> 5
1. 线性探测法:
用线性探测法解决冲突时,如果发生冲突,就顺序往后查找空闲位置,直到找到一个空闲位置为止。因此,对于每个插入的关键字,需要计算出它的探测序列,即依次查找的位置序列,直到找到该关键字或一个空闲位置为止。插入时,如果探测序列长度超过散列表长度,则认为插入失败。下面是每个关键字的探测序列:
25 -> 4
31 -> 3, 4, 5, 6, 0, 1
8 -> 1
37 -> 2
13 -> 6, 0, 1, 2, 3
40 -> 5, 6, 0, 1, 2
根据探测序列,可以得到每个关键字的平均查找长度,即查找次数除以插入的关键字数。这里,插入的关键字数为6。计算结果如下:
ASL = (1 + (1+4+1) + 1 + 1 + (1+4+1+1+1)/5 + (1+4+1+1+1)/5) / 6 = 2.17
因此,用线性探测法作为解决冲突方法的平均查找长度为2.17。
2. 链地址法:
用链地址法解决冲突时,将散列到同一个地址的关键字存储在一个链表中,每个链表的头节点存储在散列表对应的地址中。因此,对于每个插入的关键字,需要将它插入到对应链表的末尾。下面是每个地址对应链表的情况:
0 -> NULL
1 -> 8 -> NULL
2 -> 37 -> NULL
3 -> 31 -> NULL
4 -> 25 -> NULL
5 -> 40 -> NULL
6 -> 13 -> NULL
根据链表长度,可以得到每个地址的平均查找长度,即链表长度除以插入到该链表中的关键字数。这里,插入的关键字数为6。计算结果如下:
ASL = ((0+1+1+1+1+1)/6 + (0+1)/2 + (0+1)/2 + (0+1)/2 + (0+1)/2 + (0+1)/2 + (0+1)/2) / 6 = 0.5
因此,用链地址法作为解决冲突方法的平均查找长度为0.5。
综上所述,用链地址法的平均查找长度更小,因此更适合解决该问题。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_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)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)