首页 > 试题广场 >

等概率情况下查找成功平均查找长度为?

[单选题]

设哈希表长度为11,哈希函数H(K)=(K的第一个字母在字母表中的序号)MOD11,若输入顺序为(D,BA,TN,M,CI,I,K,X,TA),采用内散列表,处理冲突方法为线性探测法,要求构造哈希表,在等概率情况下查找成功平均查找长度为()

```
4
```
```
3
```
```
20/9
```
```
23/9
```

查看正确选项

TikTok-DataBP

一步错，步步错……

发表于 2016-12-15 22:25:38 回复(0)

Pandora

线性探测：本位置x被占据，就寻找下一位x+1，直至找到空位置，所以：

（注意看清题目“K的第一个字母在字母表中的序号 ”）

D=4mode11=4，1次

B=2mod11=2，1次

T=20mod11=9，1次

M=13mod11=2->3，2次

C=3mod11=3->4->5，3次

I=9mod11=9->10，2次

K=11mod11=0，1次

X=24mod11=2->3->4->5->6，5次

T=20mod11=9->10->0->1，4次

9个数字，共20次，所以20/9。

编辑于 2016-09-22 11:25:39 回复(6)

瓦塔西瓦TOTO

发表于 2017-03-28 16:35:19 回复(0)

花斩

这题根本就是在考字母表！！！

发表于 2017-11-18 18:56:52 回复(4)

牛客781393260号

懒人选择直接写代码

const int TABLE_LEN = 11;//表的长度
int main(){
    vector<string> a({"D","BA","TN","M","CI","I","K","X","TA"});
    vector<string> h(11,"");
    int total = a.size();//total：总的查找次数，每个变量至少查找一次，所以至少为a.size()
    for(auto it=a.begin();it!=a.end();it++)
    {
        char c = (*it)[0];
        int index = (c - 'A')%TABLE_LEN;
        while(!h[index].empty()) {
            index = index+1>=TABLE_LEN?0:index+1;//注意，index有可能超出h的边界，这时回到h.begin()
            total++;
        }
        h[index] = *it;
    }
    //输出hash表
    for(int i=0;i<h.size();i++)
        std::cout<<(h[i].empty()?"空":h[i])<<" ";
    std::cout<<std::endl;
    //输出平均查找次数
    std::cout<<total<<"/"<<a.size();
}

发表于 2021-03-06 11:20:19 回复(1)

漕河泾

冲突：两个不同的键占用同一个存储空间，基本这个意思...

哈希函数：H(k) = 每个元素第一个字母在字母表中的顺序 % 11 。

线性探测：a.该值是所要插入元素的关键码，不进行插入。 H(k) 的值等于关键码
b.产生冲突，依次查看其后的下一个桶，如果发现空位置插入新元素

因此：D在字母表中第4个,4%11 = 4，BA的第一个字母B在字母表中第2个，2%11 = 2，..................

加下来就插入到哈希表中，上面得到的H(k)的值就是在哈希表中要插入的地址，具体如下：

长度为11的哈希表。

0	1	2	3	4	5	6	7	8	9	10
K(7)	TA(9)	BA(2)	M(4)	D(1)	CI(5)	X(8)			TN(3)	I(6)

按照这个输入顺序依次插到相应位置(D,BA,TN,M,CI,I,K,X,TA)

D-->4 ,4位置空的，因此D放到4位置,(1)表示放入的顺序号,只查找的1次就插入了，因为没有产生任何冲突，故次数为 1

BA--->2,2位置空的，插入...，和上一个一样一次成功，次数 1

TN--> 9，不冲突，次数 1

M-->3 ,不冲突，次数 1

CI-->3,与M的值一样为3，产生了冲突，因此放到3的后一个位置4，此时4位置上是D，又冲突了继续往后走到5，不冲突，插入，次数3--4--4,故次数为3次

I-->9,与TN冲突，后移到10,9--10，共2次

K-->0,不冲突，1次

X-->2,冲突，2--3---4--5--6,6位置空插入，共5次

TA-->9,冲突，9--10--0--1,1位置空，共4次，

9个元素总共走了1+1+...+5+4 = 20，那么平均查找长度为 20/9次。

发表于 2019-05-14 09:21:51 回复(0)

菜鸟ding

发表于 2023-09-21 21:39:38 回复(0)

本命年的Offer！

下次要记住啦，线性探测法就是看下一个坑是不是没人占，有的话就继续找下一个坑，知道找到为止！

发表于 2017-10-07 23:03:47 回复(0)

VagrantYang

有没有算的是17/9.

得出这个答案的原因我们在算TA时，它的索引值为9，然后索引为9的位置已经有了TN，可能有的人认为他们第一个字母相同，所以不冲突，查找成功。可是他们的实际键值是不一样，即还是发生冲突。所以我们要继续考察索引的下一个位置，直到找到TA或空位置，就put

发表于 2017-09-30 07:48:49 回复(1)

josan

根据下表可知，平均查找成功长度跟平均查找失败长度如下：

ASL_suc=（1+4+1+2+1+3+5+1+2）/9 = 20/9

ASL _fail=（7+6+5+4+3+2+1+1+1+9+8）/11 = 47/11

散列表	0	1	2	3	4	5	6	7	8	9	10
散列元素	K	TN	BA	M	D	CI	X			TA	I
查找成功次数	1	4	1	2	1	3	5			1	2
查找失败次数	7	6	5	4	3	2	1	1	1	9	8

发表于 2017-07-09 15:18:52 回复(1)

闪电利剑

给我数半天

发表于 2022-03-15 21:09:38 回复(0)

牛客717691号

果然一步错步步错

发表于 2017-08-13 11:33:58 回复(0)

有梦为马，随处可栖

内散列表？

发表于 2017-07-20 13:30:30 回复(0)

吴缺

不懂，怎么来的

发表于 2016-03-05 17:22:10 回复(1)

提交观点

问题信息

哈希

来自：百度2016研发工程师...

难度：

14条回答 943收藏 17102浏览

等概率情况下查找成功平均查找长度为?

问题信息

热门推荐

相关试题