答案及解析：[单选题]设有一组关键字{9,01,23,14,55,20,84,27}，采用哈希函数：H（key）=key mod 7 ，表长为10，用开放地址法的二次探测再散列方法Hi=(H(key)+di) mod 10

问题：

[单选题]设有一组关键字{9,01,23,14,55,20,84,27}，采用哈希函数：H（key）=key mod 7 ，表长为10，用开放地址法的二次探测再散列方法Hi=(H(key)+di) mod 10(di=1,4,9,…,)解决冲突。要求：对该关键字序列构造哈希表，并计算查找成功的平均查找长度。下面正确的是（）
A.

H(9)=9%7=2；H(01)=1%7=1；H(23)=23%7=2冲突 H1(23)=(2+1)%7=3；

H(14)=14%7=0；H(55)=55%7=6；H(20)=20%7=6冲突H1(20)=(6+1)%7=0；冲突

H2(20)=(6+2)%7=1冲突，H3(20)=(6+3)%7=2冲突；H4(20)=(6+4)%7=3冲突

H5(20)=(6+5)%7=4

H(84)=84%7=0 冲突 H1(84)=(0+1)%7=1 H2(84)=(0+2)%7=2；冲突H3(84)=(0+3)%7=3;冲突

H6(84)=(0+4)%7=4冲突;H7(84)=(0+5)%7=5

H(27)=27%7=6 冲突 H1(27)=(6+1)%7=7 冲突 H2(27)=(6+2)%7=1冲突

H3(27)=(6+3)%7=2冲突;H4(27)=(6+4)%7=3冲突;H5(27)=(6+5)%7=4冲突

H6(27)=(6+6)%7=5冲突; H7(27)=(6+7)%7=6;冲突H8(27)=(6+8)%7=0冲突无解

__________________________________

地址： |0 |1 |2 |3 |4 |5 |6 |7 |8 | 9 |

——————————————————

关键字： |14 |1 |9 |23|20|84|55| | | |

——————————————————

查找次数： |1 |1 |1 | 2 |6 |6 |1 | | | |

____________________________________________

H(9)=9%7=2；H(01)=1%7=1；H(23)=23%7=2冲突 H1(23)=(2+1)%10=3；

H(14)=14%7=0；H(55)=55%7=6；H(20)=20%7=6冲突H1(20)=(6+1)%10=7；H(84)=84%7=0 冲突 H1(84)=(0+1)%10=1 H2(84)=(0+2)%10=2；H3(84)=(0+3)%10=3

H4(84)=(0+4)%10=4

H(27)=27%7=6 冲突 H1(27)=(6+1)%10=7 冲突 H2(27)=(6+2)%10=8

H(9)=9%7=2；H(01)=1%7=1；H(23)=23%7=2冲突 H1(23)=(2+1)%10=3；

H(14)=14%7=0；H(55)=55%7=6；H(20)=20%7=6冲突H1(20)=(6+1)%10=7；H(84)=84%7=0 冲突 H1(84)=(0+1)%10=1 H2(84)=(0+4)%10=4；

H(27)=27%7=6 冲突 H1(27)=(6+1)%10=7 冲突 H2(27)=(6+4)%10=0

冲突 H3(27)=(6+9)%10=5。

平均查找长度：ASLsucc=（1+1+1+2+3+4+1+2）/8=15/8
_______________________________________

地址： |0 |1 |2 |3 |4 |5 |6 |7 |8 | 9 |

——————————————————

关键字： |14 |1 |9 |23|84|27|55|20| | |

——————————————————

查找次数： |1 |1 |1 | 2 |3 |4 |1 |2 | | |

____________________________________________
D.

H(9)=9%7=2；H(01)=1%7=1；H(23)=23%7=2冲突 H1(23)=(2+1)%7=3；

H(14)=14%7=0；H(55)=55%7=6；H(20)=20%7=6冲突H1(20)=(6+1)%7=0；

H2(20)=(6+4)%7=3 H3(20)=(6+9)%7=1 H4(20)=(6+16)%7=1

无解

___________________________________________

地址： |0 |1 |2 |3 |4 |5 |6 |7 |8 | 9 |

——————————————————

关键字： |14 |1 |9 |23| | |55| | | |

——————————————————

查找次数： |1 |1 |1 | 2 | | |1 | | | |

____________________________________________

平均查找长度：ASLsucc=（1+1+1+2+5+4+1+2+3）/8=20/8=2.5

___________________________________________

地址： |0 |1 |2 |3 |4 |5 |6 |7 |8 | 9 |

——————————————————

关键字： |14 |1 |9 |23|84|27|55|20| 27 | |

——————————————————

查找次数： |1 |1 |1 | 2 |5 |4 |1 |2 | 3 | |

____________________________________________

Tags：中国大学MOOC(慕课)电子科技大学数据结构与算法单元测验题答案

答案解析：

╋纠错

您可能感兴趣的问题