2. 考研
  3. 假设初始为空的散列表的地址空间为(0…10)，散列函数为H (key) =key mod 11，采用线性探测再散列法处理冲突，若依次插入关键字37、95、27、14、48，则最后一个关键字值48的插入位置是( )。

假设初始为空的散列表的地址空间为(0…10)，散列函数为H (key) =key mod 11，采用线性探测再散列法处理冲突，若依次插入关键字37、95、27、14、48，则最后一个关键字值48的插入位置是( )。

admin2019-12-10  62
问题 假设初始为空的散列表的地址空间为(0…10)，散列函数为H (key) =key mod 11，采用线性探测再散列法处理冲突，若依次插入关键字37、95、27、14、48，则最后一个关键字值48的插入位置是(    )。
选项 A、4
B、5
C、6
D、8
答案C
解析 首先通过散列函数H(key) =key mod 11的计算得知，37、95、27、14分别插入到散列表中的4、7、5、3的位置。而48 mod 11=4，但是此时4已经有元素了，根据线性探测再散列法处理冲突的原则，依次探测位置4的下一个地址，直到此地址为空，发现6为空则插入，故选C选项。
补充：如果此题改为使用平方探测法，则又应该选择哪一个选项？
解析：平方探测法的原理是设发生冲突的地址为d，则平方探测法的探测序列为d+12，d_12，d+22，d_22，…。位置4不空时，下一个探测的位置应该为5，发现又不空，则下一个探测的位置应该是3，发现又不空。接着再探测位置8，发现为空，将元素插入，故选D选项。
平方探测法是一种较好的处理冲突的方法，可以避免出现堆积问题。它的缺点是不能探测到散列表上的所有单元，但至少能探测到一半单元。
转载请注明原文地址:https://www.kaotiyun.com/show/i63i777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

相关试题推荐
随机试题
最新回复(0)