itgle.com
有一个线性表(16，25，70，61，52，45)，采用的散列函数为H(Key)=Keymod8，将元素散列到表长为8的哈希表中存储。若采用线性探测的开放定址法解决冲突，则在该散列表上进行等概率成功查找的平均查找长度为(88)；若利用拉链法解决冲突，则在该散列表上进行等概率成功查找的平均查找长度为(89)。A．1.25B．1.33C．2D．2.3
题目
有一个线性表(16，25，70，61，52，45)，采用的散列函数为H(Key)=Keymod8，将元素散列到表长为8的哈希表中存储。若采用线性探测的开放定址法解决冲突，则在该散列表上进行等概率成功查找的平均查找长度为(88)；若利用拉链法解决冲突，则在该散列表上进行等概率成功查找的平均查找长度为(89)。
A．1.25
B．1.33
C．2
D．2.3
相似考题
参考答案和解析
更多“有一个线性表(16,25,70,61,52,45),采用的散列函数为H(Key)=Keymod8,将元素散列到表长为8的哈希表 ”相关问题
-
第1题：
设哈希表长m=14，哈希函数H(key)=key%ll，表中已经有4个结点： addr(13)=4； addr(28)=5 addr(51)=6； addr(77)=7 如果用线性探测再与散列法处理冲突，关键字为49的结点地址为( )。
A．8
B．5
C．9
D．3
正确答案：A
-
第2题：
设哈希表长m=14，哈希函数H（key)=key%11。表中已有4个结点：addr （15)=4; addr （38)=5; addr （61)=6; addr （84)=7。如用二次探测再散列处理冲突，关键字为49的结点的地址是____。
A．8
B．3
C．5
D．9
9 -
第3题：
【单选题】设哈希表长为14，哈希函数是H（key)=key%11,表中已有数据的关键字为15，38，61，84，要将关键字为49的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是（)
A．8
B．3
C．5
D．9
D -
第4题：
已知一个线性表(16，25，35，43，51，62，87，93)，采用散列函数H(Key)=Key mod 7将元素散列到表长为9的散列表中。若采用线性探测的开放定址法解决冲突(顺序地探查可用存储单元)，则在所构造的哈希散列表上进行等概率成功查找的平均查找长度为(60)(为确定记录在查找表中的位置，需和给定关键字值进行比较的次数的期望值，称为查找算法在查找成功时的平均查找长度)。
A．(8×1)/8
B．(8×1)/9
C．(5×1+2+3+6)/8
D．(5×1+2+3+6)/9
正确答案：C
解析：本题考查数据结构中哈希表的基础知识。线性探测法解决冲突的方法是：若在地址r处发生冲突，则探测地址 r+1，若已到达表尾，则再从表头出发进行探测。若是插入元素，则找到一个空闲单元为止。若表已满则采用其他策略解决冲突；若是访问元素，则找到元素或一个空闲单元为止。
初始哈希表为空，根据序列(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空闲，所以插入对应元素。
②51 mod 7=2，地址2处冲突，因此探测地址3，该单元空闲，因此51存入地址3。由于62 mod 7=6，地址6处空闲，所以将62插入地址6。
③87 mod 7=3，地址3处冲突，因此依次探查地址4、5，地址5空闲，因此87存入地址5；93 mod 7=2，地址2处冲突，因此依次探查地址3、4、5、6、7，地址7空闲，因此93存入地址7。
为确定记录在查找表中的位置，需和给定关键字值进行比较的次数的期望值称为查找算法在查找成功时的平均查找长度。对于含有n个记录的表，查找成功时的平均查找长度定义为：
，其中，Pi为对表中第i个记录进行查找的概率，且
，一般情况下，均认为查找每个记录的概率是相等的，即 Pi=1/n。Ci为找到表中其关键字与给定值相等的记录时(为第i个记录)，和给定值已进行过比较的关键字个数。对于本试题所构造的哈希表，平均查找长度ASL=(1+1+1+1+2+1+3+6)/8=2。
-
第5题：
已知一组关键字序列为{5,88,12,56,71,28,33,43,93,17}，哈希表长为13，哈希函数为H（key)=key%13，请用线性探测再散列、二次线性探测再散列以及链地址法解决冲突构造这组关键字的哈希表，并计算查找成功时的平均查找长度。
计算关键字对应的哈希函数值： 关键字26364138441568120651哈希值01021252312612 当发生冲突时，采用线性探查法给与解决，具体存储结果如下：存储位置0123456789101112关键字26124115684406513638