设散列表地址空间为0到10,散列表函数为h(k)=k mod 11,用线性探查法解决碰撞.现从空的散列表开始,依次插按键码值95,14,27,68,82,则最后一个关键码82的地址是多少?求详细解题过程及原理,要详细呀!
来源:学生作业帮助网 编辑:作业帮 时间:2024/07/05 21:01:36
![设散列表地址空间为0到10,散列表函数为h(k)=k mod 11,用线性探查法解决碰撞.现从空的散列表开始,依次插按键码值95,14,27,68,82,则最后一个关键码82的地址是多少?求详细解题过程及原理,要详细呀!](/uploads/image/z/10227753-9-3.jpg?t=%E8%AE%BE%E6%95%A3%E5%88%97%E8%A1%A8%E5%9C%B0%E5%9D%80%E7%A9%BA%E9%97%B4%E4%B8%BA0%E5%88%B010%2C%E6%95%A3%E5%88%97%E8%A1%A8%E5%87%BD%E6%95%B0%E4%B8%BAh%28k%29%3Dk+mod+11%2C%E7%94%A8%E7%BA%BF%E6%80%A7%E6%8E%A2%E6%9F%A5%E6%B3%95%E8%A7%A3%E5%86%B3%E7%A2%B0%E6%92%9E.%E7%8E%B0%E4%BB%8E%E7%A9%BA%E7%9A%84%E6%95%A3%E5%88%97%E8%A1%A8%E5%BC%80%E5%A7%8B%2C%E4%BE%9D%E6%AC%A1%E6%8F%92%E6%8C%89%E9%94%AE%E7%A0%81%E5%80%BC95%2C14%2C27%2C68%2C82%2C%E5%88%99%E6%9C%80%E5%90%8E%E4%B8%80%E4%B8%AA%E5%85%B3%E9%94%AE%E7%A0%8182%E7%9A%84%E5%9C%B0%E5%9D%80%E6%98%AF%E5%A4%9A%E5%B0%91%3F%E6%B1%82%E8%AF%A6%E7%BB%86%E8%A7%A3%E9%A2%98%E8%BF%87%E7%A8%8B%E5%8F%8A%E5%8E%9F%E7%90%86%2C%E8%A6%81%E8%AF%A6%E7%BB%86%E5%91%80%21)
设散列表地址空间为0到10,散列表函数为h(k)=k mod 11,用线性探查法解决碰撞.现从空的散列表开始,依次插按键码值95,14,27,68,82,则最后一个关键码82的地址是多少?求详细解题过程及原理,要详细呀!
设散列表地址空间为0到10,散列表函数为h(k)=k mod 11,用线性探查法解决碰撞.现从空的散列表开始,依次插
按键码值95,14,27,68,82,则最后一个关键码82的地址是多少?
求详细解题过程及原理,要详细呀!
设散列表地址空间为0到10,散列表函数为h(k)=k mod 11,用线性探查法解决碰撞.现从空的散列表开始,依次插按键码值95,14,27,68,82,则最后一个关键码82的地址是多少?求详细解题过程及原理,要详细呀!
哈希存储的基本原理是将元素的值(如95、14等)进行哈希计算得到哈希地址,再将其存储到指定地址.如果该地址已有元素,称之为存在“冲突”,再采用冲突检测法处理冲突,如线性探测再散列法.
如元素的值为95时,采用哈希函数h(k)=k mod 11时,得到的哈希地址为7,即h(95) = 95 % 11 = 7.
针对本题:
(1)构造哈希表,有11个地址空间(0~10);
(2)计算各个元素的哈希地址,若没有冲突,则直接存储到相应地址的哈希表中:
h(95) = 95 % 11 = 7 没有冲突
h(14) = 14 % 11 = 3 没有冲突
h(27) = 27 % 11 = 5 没有冲突
h(68) = 68 % 11 = 2 没有冲突
h(82) = 82 % 11 = 5 有冲突(因为地址5已经被值为27的元素占用了)
(3)对于有冲突的元素,发生冲突后必须马上处理(采用线性探查法),不能到最后一起处理:
h(82) = (5 + 1) % 11 = 6 没有冲突
(4)最后哈希表0~10的11个地址空间依次存储的元素为:
0 1 2 3 4 5 6 7 8 9 10
N N 68 14 N 27 82 95 N N N
其中N表示此处为空.