问题:已知一个线性表(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
分析:利用该散列函数散列存储结果为
68|48 | |38|25|74|52
位置 0 1 2 3 4 5 6
平均查找长度=总的查找次数/元素数=(1*3+2*1+3*1+4*1)/6=2.0
参考答案:(52)C
能分析一下具体怎么解答吗???
要计算散列表上的平均查找长度,我们首先必须要知道在建立这个散列表时,每个数据存储时进行了几次散列。这样就知道哪一个元素,查找的长度是多少。
散列表的填表过程如下:首先存入第一个元素38,由于h(38)=38%7=3,又因为3号单元现在没有数据,所以把38存入3号单元。 接着存入第二个元素25,由于h(25)=25%7=4,又因为4号单元现在没有数据,所以把25存入4号单元。 接着存入第三个元素74,由于h(74)=74%7=4,此时的4号单元已经被25占据,所以进行线性再散列,线性再散列的公式为:Hi=(H(key)+di)% m ,其中的di=1,2,3,4...。所以H1=(4+1)%7=5,此时的单元5没有存数据,所以把74存入到5号单元。 接着存入第四个元素63,由于h(63)=63%7=0,此时的0号单元没有数据,所以把63存入0号单元。 接着存入第五个元素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号单元。 最后存入第六个元素48,由于h(48)=48%7=6,此时的6号单元已被占据,所以进行线性再散列:H1=(6+1)%7=0,但0号单元也被占据了,所以再次散列:H2=(6+2)%7=1,1号单元为空,所以把48存入1号单元。 如果一个元素存入时,进行了N次散列,相应的查找次数也是N,所以38,25,63这三个元素的查找长度为1,74的查找长度为2,48的查找长度为3,52的查找长度为4。所以平均查找长度为:(1+1+1+2+3+4)/6=2。
相关推荐
散列表,也称为哈希表。根据设定的哈希函数H(key)和处理冲突的方法将一组... 处理冲突的方法:1)开放定址法(线性探测再散列,二次探测再散列,伪随机探测再散列) 2)再哈希法 3)链地址法 4)建立一 公共溢出区
c代码实现哈希表线性探测再散列。关键字均为纯数字。查找时为单次查找,未加入循环
山东大学软件学院数据结构课程设计线性开型寻址散列源代码
选取哈西函数h(k)=k%11,用线性探测在散列方法处理冲突。是在0-10的散列地址中,对关键序列(22,41,53,46,30,01,67)构造哈希表并求等概率情 况下查找成功与不成功过的平均查找长度
非线性离散散列
线性代数六百证明题详解,这是很好的学习线性代数,有助于初学者的理解辅导。
线性代数课后习题答案全)习题详解,非常详细,有具体的步骤含答案
非线性稀疏散列
这是数据结构中关于线性开行寻址散列的源代码,用java语言编写
居于马线性代数学习,内含教材详解及课后习题答案,内容丰富。
散列表(Hash table,也叫哈希表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。
同济大学线性代数答案详解 最新版本
解决了几乎所有考试会考到的矩阵和线性代数的问题
注意详情:线性代数(北大社周勇版)课后习题答案大全,包括从第一章到最后一章答案
线性规划与非线性规划问题线性规划与非线性规划问题
线性代数的试卷和答案,难度中等,题型丰富
这是线性代数的课后答案详解~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
机 器 学习中的线性学习方法, 资料整理搜集来自网络。
线性回归方程——非线性方程转化为线性方程.pdf
用户可以根据自己的需求输入一个顺序表(哈希表) 通过用除留余数法构造哈希函数,并用开放地址的二次探测再散列解决冲突。 在经过排序后显示该哈希表。 程序执行的命令包括: (1)创建哈希表 (2)输出哈希表 (3...