2. 计算机
  3. 已知一个线性表(16，25，35，43，51，62，87，93)，采用散列函数H(Key)=Key　mod　7将元素散列到表长为9的散列表中。若采用线性探测的开放定址法解决冲突(顺序地探查可用存储单元)，则构造的哈希表为(57)，在该散列表上进行等概率成功

已知一个线性表(16，25，35，43，51，62，87，93)，采用散列函数H(Key)=Key　mod　7将元素散列到表长为9的散列表中。若采用线性探测的开放定址法解决冲突(顺序地探查可用存储单元)，则构造的哈希表为(57)，在该散列表上进行等概率成功

admin2009-01-10  69
问题 已知一个线性表(16，25，35，43，51，62，87，93)，采用散列函数H(Key)=Key　mod　7将元素散列到表长为9的散列表中。若采用线性探测的开放定址法解决冲突(顺序地探查可用存储单元)，则构造的哈希表为(57)，在该散列表上进行等概率成功查找的平均查找长度为(58)(为确定记录在查找表中的位置，需和给定关键字值进行比较的次数的期望值称为查找算法在查找成功时的平均查找长度)。
选项 A、(5*1+2+3+6)/8
B、(5*1+2+3+6)/9
C、(8*1)/8
D、(8*1)/9
答案A
解析 本题考查数据结构中哈希表的基础知识。
   线性探测法解决冲突的方法是：若在地址r处发生冲突，则探测地址r+1，若已到达表尾，则再从表头出发进行探测。若是插入元素，则找到一个空闲单元为止，若表已满则采用其他策略解决冲突；若是访问元素，则找到元素或一个空闲单元为止。
   初始哈希表为空，如表(a)所示。
  
根据序列(16，25，35，43，51，62，87，93)和哈希函数H(Key)=Key mod 7构造哈希表的过程如下：
　　①16 mod 7=2 25 mod 7=4 35 mod 7=0 43 mod 7=1，地址2、4、0、1空闲，所以插入对应元素，如表(b)所示。

②51 mod 7=2，地址2处冲突，因此探测地址3，该单元空闲，因此51存入地址 3。由于62 mod 7=6，地址6处空闲，所以将62插入地址6，如表(c)所示。

③87 mod 7=3，地址3处冲突，因此依次探查地址4、5、地址5空闲，因此87存入地址5；93 mod 7=2，地址2处冲突，因此依次探查地址3、4、5、6、7，地址7空闲，因此93存入地址7，如表(d)所示。

为确定记录在查找表中的位置，需和给定关键字值进行比较的次数的期望值称为查找算法在查找成功时的平均查找长度。
   对于含有n个记录的表，查找成功时的平均查找长度定义为：，其中， Pi为对表中第i个记录进行查找的概率，且，一般情况下，均认为查找每个记录的概率是相等的，即Pi=1/n；Ci为找到表中其关键字与给定值相等的记录时(为第i个记录)，和给定值已进行过比较的关键字个数。
   对于本哈希表，平均查找长度ASL=(1+1+1+1+2+1+3+6)/8=2。
转载请注明原文地址:https://kaotiyun.com/show/lBxZ777K
本试题收录于： 软件设计师上午基础知识考试题库软考中级分类
0

软件设计师上午基础知识考试

软考中级

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