`
- 浏览:
161387 次
- 性别:
- 来自:
成都
-
已知一个线性表(38,25,74,63,52,48),假定采用散列函数h(key)=key%7计算散列地址,并散列存
储在散列表A[0..6]中,若采用线性探测方法解决冲突,则在该散列表上进行等概率成功查找的平均查找长度为__________.
(52)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。
分享到:
Global site tag (gtag.js) - Google Analytics
相关推荐
对于给定的一组整数和散列函数,分别采用线性探测法和拉链法处理冲突构造散列表,并在这两种方法构建的散列表中查找整数K,比较两种方法的时间和空间性能。
选取哈西函数h(k)=k%11,用线性探测在散列方法处理冲突。是在0-10的散列地址中,对关键序列(22,41,53,46,30,01,67)构造哈希表并求等概率情 况下查找成功与不成功过的平均查找长度
散列表,也称为哈希表。根据设定的哈希函数H(key)和处理冲突的方法将一组... 处理冲突的方法:1)开放定址法(线性探测再散列,二次探测再散列,伪随机探测再散列) 2)再哈希法 3)链地址法 4)建立一 公共溢出区
从键盘输入各记录,以用户名为关键字建立哈希表, 哈希函数用除留取余数法构造, 采用线性探测法解决冲突。可以插入、查找、删除并显示给定用户名的记录, 并计算查找长度, 哈希表保存到文件中。 测试数据: 取自己...
哈希表中线性探查法解决冲突,查找,删除、插入关键字等操作
数据结构 杂凑表编程实现 完美运行 完美注释
1.给定一关键字序列,用除留余数法构造hash函数,用线性探测再散列解决冲突构造hash表; 2.给定一个关键字进行查找,返回其位序(如不存在返回0值);
散列表散列表散列表散列表散列表散列表散列表散列表散列表散列表
要求:用除留余数法构造哈希函数,用二次探测再散列解决冲突。 需求分析 用户可以根据自己的需求输入一个顺序表(哈希表) 通过用除留余数法构造哈希函数,并用开放地址的二次探测再散列解决冲突。 在经过排序后显示...
设定哈希函数 H(key) = key MOD 11 ( 表长=11 ),输入一组关键字序列,根据线性探测再散列解决冲突的方法建立哈希表的存储结构,显示哈希表,任意输入关键字,判断是否在哈希表中。
课程设计 哈希表做的课程设计 课程设计 哈希表做的课程设计课程设计 哈希表做的课程设计
c _primer_plus(第六版)第二至第六章课后编程练习全部答案
从键盘输入各记录,以用户名为关键字建立哈希表,哈希函数用除留取余数法构造,采用线性探测法解决冲突。可以插入、查找、删除并显示给定用户名的记录,并计算查找长度, 哈希表保存到文件中,并能从文件中读取数据。...
哈希查找: 1、 哈希表类的哈希函数采用...2、 解决哈希冲突的函数采用开放定址法中的线性探察法。 3、 建立一个由10个数据元素组成的集合; 4、 测试哈希表长度m=13和m=11两种情况下的哈希表,并查找其中的几个元素。
从键盘输入各记录,以用户名为关键字建立哈希表,哈希函数用除留取余数法构造,采用线性探测法解决冲突。可以插入、查找、删除并显示给定用户名的记录,并计算查找长度, 哈希表保存到文件中,并能从文件中读取数据。...
1. 随机产生一组关键字,已知散列函数为H(key)=key%p(p为自定的常数),冲突处理方法为线性探测法实现散列表的建立(利用插入算法实现); 2.编写从散列表中查找一个元素的算法。
1)设计几个不同的哈希函数,比较他们的地址冲突率(可以用更大的名字集合做实验)。...(3)在哈希函数确定的前提下尝试各种不同处理冲突的方法,考察平均查找长度的变化和造好的哈希表中关键字的聚集性。
(1) 采取除留余数法构造哈希表; (2) 采用线性探测再散列方法解决冲突,输出哈希表结果; (3) 采用链地址法处理冲突,输出哈希表结果; (4) 考查两种冲突方法的平均查找长度。
mfc编程 哈希表的实现,包括创建插入删除清空等,采用了线性探测和哈希函数解决冲突
要求:将哈希函数和处理冲突方法分别封装为2个函数。 提交实验报告/ 程序分析 1、将姓名表各个名字得ASCII码相加求和。 2、创建哈希表,将ASCII码取余得KEY值,若未发生冲突存入哈希表 3、发生冲突调用冲突函数。...