设有一个用线性探测法解决冲突得到的散列表:散列函数为H(k)=kmod 11,若查找元素14,则探测的次数(

题目

设有一个用线性探测法解决冲突得到的散列表:散列函数为H(k)=kmod 11,若查找元素14,则探测的次数(比较的次数)为

A.8

B.9

C.3

D.6

如果没有搜索结果或未解决您的问题,请直接 联系老师 获取答案。
相似问题和答案

第1题:

设散列函数为h(k)=kmod7,现欲将关键码23,14,9,6,30,12,18依次散列于地址0~6中,用线性探测法解决冲突,则在地址空间0~6中,得到的散列表是( )。

A)14,6,23,9,18,30,12

B)14,l8,23,9,30,12,6

C)14,12,9,23,30,18,6

D)6,23,30,14,18,12,9


正确答案:B
待插入的各关键码的散列地址分别为2, 0,2,6,2,5,4。存储前2个时无冲突,当存关键码9时与23冲突,此时后移一位存储地址到3,存储6时无冲突,存储30与23、9关键码冲突了,后移两位到4,依次类推,可知B)选项是正确的。

第2题:

设散列函数H(key)=key MOD 7,用线性探测再散列法解决冲突。对关键字序列{13,28,72,5,16,8,7,9,11,29}在地址空间为0-10的散列区中建散列表,画出此表,并求等概率情况下查找成功时的平均查找长度。


参考答案:

第3题:

设有两个散列函数H1(k)=kmod 13和H2(k)=kmod 11+1,散列表为T[0…12],用二次散列法解决冲突。函数H1用来计算散列地址,当发生冲突时,H2作为计算下一个探测地址的地址增量。假定某一时刻散列表的状态为:

下一个被插入的关键码为42,其插入位置应是( )。

A.0

B.1

C.3

D.4


正确答案:A

第4题:

设有一个用线性探测法解决冲突得到的散列表,该表共有0~10个地址单元,其中地址单元2~8中的内容依次为13,25,80,16,17,6,14。散列函数为: H(k)=k mod 11 若要查找元素14,探测(比较)的次数是( )。

A.8

B.9

C.3

D.6


正确答案:D
解析:由散列函数为:H(k)=k mod11可计算出13,25,80,16,17,6, 14的散列地址依次为2、3、3、5、6、6、3,在存储14时,2、3、4、5、6、7连续6个单元已经被占用,如表13-17所示。而14的散列地址为3,因此在查找时需从地址为3的位置开始比较,一直到14存储的地址8(包括8),共比较了6次。

第5题:

下列问题是基于下列描述:散列表的地址区间为0~17,散列函数为H(K)=Kmod 17采用线性探测法处理冲突,并将关键字序列26、25、72、38、8、18、59依次存储到散列表中。

元素59存放在散列表中的地址是( )。

A.8

B.9

C.10

D.11


正确答案:D
解析:各元素的散列地址分别为9,8,4,4,8,1,8。在存放8这个元素时,由于这个存储位置已存放了25,根据处理冲突的方法——线性探测法,需后退一个位置到9,但9这个位置也已存放了26这个元素,所以还需移至10,10这个位置是空的,所以8就存放在10。对59,它的散列地址为8,需按上述方法依次经过8,9,10,最后到达11。

第6题:

已知一个线性表(38,25,74,63,52,48),采用的散列函数为H(Key)=Key mod 7,将元素散列到表长为7的哈希表中存储。若采用线性探测的开放定址法解决冲突,则在该散列表上进行等概率成功查找的平均查找长度为(41);若利用拉链法解决冲突,则在该散列表上进行等概率成功查找的平均查找长度为(42)。

A.1.5

B.1.8

C.2

D.2.3


正确答案:C
解析:根据题意,使用线性探测的开放定址法,各数的位置分别是(0,63),(1,48),(3,38),(4,25),(5,74),(6,52)。平均查找长度为(1+3+1+1+2+4)/6=2.0;使用拉链法,0和6地址下有一个节点,3和4地址下有两个节点,即平均查找长度为(1+1+1+1+2+2)/6=4/3。

第7题:

设有两个散列函数H1(k)=kmod 13和H2(k)=kmodll+1,散列表T[0...12],用双重散列解决冲突。函数H1用来计算散列地址,当发生冲突时,H2作为计算下一个探测地址的增量,假定在某一时刻表T的状态为:

下一个被插入的关键码是42,其插入的位置是【 】。


正确答案:×
0 解析:根据H1,42的插入位置应该是42 mod 13,即3,但位置3有冲突,用H2探测地址增量:42 mod 11+ 1=10,所以其插入位置应该是3+10=13,很显然T的最大位置是12,所以其插入位置为0。

第8题:

已知一个线性表(38,25,74,63,52,48),假定采用散列函数h(key)=key%7计算散列地址,并散列存储在散列表A[0…6]中,若采用线性探测法解决冲突,则在该散列表上进行等概率成功查找的平均查找长度为(63)。

A.1.4

B.1.6

C.2.0

D.2.2


正确答案:C
解析:按照散列函数h(key)=key%7和线性探测方法解决冲突将线性表 (38,25,74,63,52,48)散列存储在散列表A[0…6]中如图3-15所示。

在该散列表上进行等概率成功查找的平均查找长度

第9题:

设有一个用线性探测法解决冲突得到的散列表:

0 1 2 3 4 5 6 7 8 9 10

散列函数为H(k)=k mod 11若查找元素15,则探测的次数(比较的次数)为( )。

A)7

B)9

C)3

D)6


正确答案:C
根据散列函数H(k)=kmod11,我们知道15本应该存放在索引号为4的位置上,但这里已经存放了50,根据线性探测法,它的存放位置必须往后延,所以采用线性探测法查找15就会从索引号4开始一直往后比较,直到找到15时已经比较了3次。

第10题:

设有一个用线性探测法解决冲突得到的散列表:

散列函数为H(k)=k mod 11,若查找元素14,则探测的次数(比较的次数)为________。

A.8

B.9

C.3

D.6


正确答案:D
解析:根据散列函数H(k)=k mod 11,待查找元素14的哈希地址H(14)=3,但该地址已经存放了元素25,根据线性探测法,得第一次冲突处理后的地址H1=(3+1)mod 11=4,而该地址已经存放了元素80,则找第二次冲突处理后的地址H2=(3+2)mod 11=5,该地址已经存放了元素16,依次类推,直到第五次冲突处理后的地址 H5=8,该地址存放的是元素14,即查找成功,因此探测的次数为6次。

更多相关问题