2. 计算机
  3. 已知一个线性表(38，25，74，63，52，48)，假定采用散列函数h(key)=key％7计算散列地址，并散列存储在散列表A[0，…，6]中，若采用线性探测方法解决冲突，则在该散列表上进行等概率成功查找的平均查找长度为( )。

已知一个线性表(38，25，74，63，52，48)，假定采用散列函数h(key)=key％7计算散列地址，并散列存储在散列表A[0，…，6]中，若采用线性探测方法解决冲突，则在该散列表上进行等概率成功查找的平均查找长度为( )。

admin2019-06-12  40
问题 已知一个线性表(38，25，74，63，52，48)，假定采用散列函数h(key)=key％7计算散列地址，并散列存储在散列表A[0，…，6]中，若采用线性探测方法解决冲突，则在该散列表上进行等概率成功查找的平均查找长度为(    )。
选项 A、1．5
B、1．7
C、2．0
D、2．3
答案C
解析 要计算散列表上的平均查找长度，首先必须知道在建立这个散列表时，每个数据存储时进行了几次散列。这样就知道哪一个元素的查找长度是多少。散列表的填表过程如下：
首先存入第1个元素38，由于h(38)=38％7=3，又因为3号单元现在没有数据，所以把38存入3号单元，如图1-7所示。

接着存入第2个元素25，由于h(25)=25％7=4，又因为4号单元现在没有数据，所以把25存入4号单元，如图1-8所示。

接着存入第3个元素74，由于h(74)=74％7=4，此时的4号单元已经被25占据，所以进行线性再散列，线性再散列的公式为：Hi=(H(key)％m，其中的di=1，2，3，4，…，所以H1=(4+1)％7=5，此时的单元5没有存数据，所以把74存入到5号单元，如图1-9所示。

接着存入第4个元素63，由于h(63)=63％7=0，此时的0号单元没有数据，所以把63存入0号单元，如图1-10所示。

接着存入第5个元素52，由于h(52)=52％7=3，此时的3号单元已被38占据，所以进行线性再散列H1=(3+1)％7=4，但4号单元也被占据了，所以再次散列H2=(3+2)％
7=5，但5号单元也被占据了，所以再次散列H3=(3+3)％7=6，6号单元为空，所以把52存入6号单元，如图1-11所示。

最后存入第6个元素48，由于h(48)=48％7=6，此时的6号单元已被占据，所以进行线性再散列H1=(6+1)％7=0，但0号单元也被占据了，所以再次散列H2=(6+2)％7=1，1号单元为空，所以把48存入1号单元，如图1-12所示。

如果一个元素存入时，进行了N次散列，相应的查找次数也是N，所以38，25，63这三个元素的查找长度为1，74的查找长度为2，48的查找长度为3，52的查找长度为4。平均查找长度为(1+1+1+2+3+4)／6=2。
转载请注明原文地址:https://kaotiyun.com/show/zbCZ777K
本试题收录于： 软件设计师上午基础知识考试题库软考中级分类
0

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

软考中级

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