首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
已知一个线性表(38,25,74,63,52,48),假定采用散列函数h(key)=key%7计算散列地址,并散列存储在散列表A[0,…,6]中,若采用线性探测方法解决冲突,则在该散列表上进行等概率成功查找的平均查找长度为(27)。
已知一个线性表(38,25,74,63,52,48),假定采用散列函数h(key)=key%7计算散列地址,并散列存储在散列表A[0,…,6]中,若采用线性探测方法解决冲突,则在该散列表上进行等概率成功查找的平均查找长度为(27)。
admin
2019-06-12
32
问题
已知一个线性表(38,25,74,63,52,48),假定采用散列函数h(key)=key%7计算散列地址,并散列存储在散列表A[0,…,6]中,若采用线性探测方法解决冲突,则在该散列表上进行等概率成功查找的平均查找长度为(27)。
选项
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占据,所以进行线性再散列,线性再散列的公式为:H
i
=(key)+d
i
)%m,其中的d
i
=1,2,3, 4,…,所以H
1
=(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占据,所以进行线性再散列H
1
=(3+1)%7=4,但4号单元也被占据了,所以再次散列H
2
=(3+2)%7=5,但5号单元也被占据了,所以再次散列H
3
=(3+3)%7=6,6号单元为空,所以把52存入6号单元,如图1-11所示。
最后存入第6个元素48,由于h(48)=48%7=6,此时的6号单元已被占据,所以进行线性再散列H
1
=(6+1)%7=0,但0号单元也被占据了,所以再次散列H
2
=(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://jikaoti.com/ti/ceG7FFFM
本试题收录于:
软件设计师上午基础知识考试题库软考中级分类
0
软件设计师上午基础知识考试
软考中级
相关试题推荐
下列选项中,同属于报文摘要算法的是__________。(2011年上半年试题)
TCP协议在建立连接的过程中可能处于不同的状态,用netstat命令显示出TCP连接的状态为SYN—SEND,则这个连接正处于__________。(2009年上半年试题)
配置POP3服务器时,邮件服务器的属性对话框如下图所示,其中默认情况下“服务器端口”文本框应填入_____。
在Linux系统中,命令______用于管理各项软件包。
一台主机的浏览器无法访问域名为www.sohu.com的网站,并且在这台计算机执行tracert命令时有如下信息:根据以上信息,造成这种现象的原因可能是(49)。
管理站用SetRequest在RMON表中产生一个新行,如果新行的索引值与表中其他行的索引值不冲突,则代理产生一个新行,其状态对象的值为(47)。
在Windows操作系统中,远程桌面使用的默认端口是__________。
ARP表用于缓存设备的IP地址与MAC地址的对应关系,采用ARP表的好处是__________。(2011年下半年试题)
阅读下列说明和图,回答问题1至问题4,将解答填入答题纸的对应栏内。【说明】某会议中心提供举办会议的场地设施和各种设备,供公司与各类组织机构租用。场地包括一个大型报告厅、一个小型报告厅以及诸多会议室。这些报告厅和会议室可提供的设备有投影仪、白板、视频播放
为下列文法选择最准确的答案:文法G[S]属于(12):S→CDAb→bAC→aCABa→aBC→bCBBb→bBAD→aDC→sBD→bDD→cAa→bDL(G)={ww|w
随机试题
智力的二因素论,将智力分为普通因素和特殊因素,首先提出这一理论的是()
男性,55岁。出现黄疸、发热、呕吐,查体可见皮肤黏膜出血点。该患者可能是
秦皮的主要成分是洋金花的主要化学成分是
能够引起灰婴综合征的药物是()。
某银行以某公司未偿还贷款为由向法院起诉,法院终审判决认定其请求已过诉讼时效,予以驳回。某银行向某县政府发函,要求某县政府落实某公司的还款责任。某县政府复函:“请贵行继续依法主张债权,我们将配合做好有关工作。”尔后,某银行向法院起诉,请求某县政府履行职责。法
玻璃钢衬里中,在设备表面处理后,为了防止返锈而涂覆的涂层是()。
犯罪后自动投案是认定为自首的必要条件。下列情形中,应当视为自动投案的有()。
班级日常管理有哪些内容?()
地球表面的绿色植物通过光合作用,将太阳的辐射能量转化成能被其他生物利用的有机化合能。下面说法错误的是()。
TheAsian(1)hastakenitstollonHongKong’stouristindustry,(2)offoreignexchangeforthearea.VOAHongKongcorrespond
最新回复
(
0
)