我要招人

去企业版

首页 > 试题广场 >

假定有k个关键字互为同义词，若用线性探测法把这k个关键字存入

[单选题]

假定有k个关键字互为同义词，若用线性探测法把这k个关键字存入散列表中，至少要进行多少次探测？( )

```
k-1次
```
```
k次
```
```
k+1次
```
```
k（k+1）/2次
```

查看正确选项

笨小孩k

线性探测法：通过散列函数hash(key)，找到关键字key在线性序列中的位置，如果当前位置已经有了一个关键字，就长生了哈希冲突，就往后探测i个位置（i小于线性序列的大小），直到当前位置没有关键字存在。

互为同义词可以理解为都hash到同一个位置上，如果不是第一个到达该位置的值，我们就需要以某一策略（这里理解为每次往后面移一个位置即可）依次往后面查找，直到找到空位置，所以总的查找次数就是 1+2+...+k=k(k+1)/2

发表于 2017-10-17 15:52:25 回复(0)

李茶芽

实际就是求平均查找长度一次就找到的为1，最后一个为k 总的为(1+2+...+k)=k*(k+1)/2

发表于 2019-03-29 15:43:31 回复(0)

ggjggs

以开放定址法为例

Hi=(H(key)+Di) MOD m,i=1,2,3,4,...,k(k<=m-1)

其中H(Key)为哈希函数,m为哈希表长度，Di为增量序列。

以线性探测法把这K个关键字存储散列表。

如果哈希函数为H(key)=key

那么Hi=(key+Di) MOD m

由于K个关键字互为同义词，则可假设K个关键字均为1，即有K个1

对于第一个1，散列表为空，探测一次，直接填入。

对于第二个1，这个1的位置被前一个1给占用了，所以要进行线性探测再散列，探测次数至少为2

对于第三个1，同理，探测次数至少为3。

。。。

对于第K个1，探测次数至少为K。

则总的探测次数至少为为1+2+。。+K=k（k+1）/2

更具体讲解，请参考严蔚敏数据结构257页

发表于 2017-05-23 14:08:17 回复(0)

难中难之难上加难

之前做的一道题是n*(n-1)/2...将第一个元素存入哈希表时位置为空直接存入即可为什么探测次数是1...不是0吗

发表于 2019-01-16 14:20:16 回复(1)

GalaxyKris

至少需要多少次，难道不是假设每一次都不需要经过开放定址方法mod每次都没有被占用吗？

发表于 2017-06-13 20:35:18 回复(1)

都好都好

实际就是求平均查找长度一次就找到的为1，最后一个为k 总的为(1+2+...+k)=k*(k+1)/2

发表于 2019-08-07 06:49:30 回复(0)

夜陌201903291015573

关键字互为同义词没看到

发表于 2019-04-16 16:21:19 回复(0)

SUN_tel

线性探测法依次添加且为同义词,就是词的值是一样的.

那么正常的散列,就可以直接进入固定的空格.

但是因为有多个相同值的数要存储,所以肯定要依次往后存储.

第一个数:放入散列出的位置一次操作

第二个相同值的数: 一次操作,发现被占用了,那再次散列探测,没被占用,存入

第三个也是依次探测

最后:1+2+3.....+k=k(k+1)/2

发表于 2018-04-03 10:36:03 回复(0)

海边听风

注意使用的是线性探测法。

发表于 2017-05-30 21:15:26 回复(0)

阿狸不是猫

还是不能理解线性探测法的原理，求解！

发表于 2017-05-22 10:27:00 回复(0)

提交观点

问题信息

数组

上传者：Letitia

难度：

10条回答 467收藏 16051浏览

假定有k个关键字互为同义词，若用线性探测法把这k个关键字存入

问题信息

热门推荐

相关试题