首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
已知一个线性表(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
79
问题
已知一个线性表(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://kaotiyun.com/show/5zCZ777K
本试题收录于:
软件设计师上午基础知识考试题库软考中级分类
0
软件设计师上午基础知识考试
软考中级
相关试题推荐
OSPF网络被划分为各种区域,其中作为区域之间交换路由信息的是()。
配置FTP服务器的属性窗口如下图所示,默认情况下“本地路径”文本框中的值为__________。(2011年下半年试题)
路由器命令Router>sh int的作用是(51)。
IEEE802.11g标准支持的最高数据速率可达______Mb/s。
默认情况下,远程桌面用户组(RemoteDesktopUsers)成员对终端服务器______。
主机host1和host2进行域名查询的过程如下图所示,下列说法中正确的是__________。(2013年上半年试题)[*]2
如果要测试目标10.0.99.221的连通性并进行反向名字解析,则在DOS窗口中输入命令__________。(2009年上半年试题)
运行OSPF协议的路由器用(20)报文来建立和更新它的拓扑数据库。
在结构化分析方法中,数据字典是重要的文档。对加工的描述是数据字典的组成内容之一,常用的加工描述方法(14)。
根据题意回答以下问题:设某商业集团数据库中有3个实体集:一是“商店”实体集,属性有商店编号,商店名,地址等;二是“商品”实体集,属性有商品号,商品名,规格,单价等;三是“职工”实体集,属性有职工编号,姓名,性别,业绩等。商店与商品间存在“销售”联系
随机试题
马克思主义中国化的实质是()
小脑幕裂孔疝与枕骨大孔疝的根本区别是
关于抗凝血酶Ⅲ的叙述,错误的是
A.犬细小病毒B.犬瘟热病毒C.狂犬病病毒D.伪狂犬病病毒E.犬传染性肝炎病毒能致犬肠炎,可引起双相热病征的病毒是
某上市公司的股票价格已经连续三个月高于15元,而其发行的可转换债券的转股价格为10元,则该公司可能会行使下列何种条款?()
某施工单位与建设单位按《公路工程标准施工招标文件》(2018年版)签订了施工承包合同,合同工期400天,合同总价5000万元。施工前监理工程师已批准了施工单位提交的施工进度计划,其中的施工进度网络计划如图4—2所示。该工程在施工过程中出现了如下
交易型开放式指数基金的特征包括()。Ⅰ.被动操作的指数基金Ⅱ.独特的实物申购、赎回机制Ⅲ.独特的现金申购、赎回机制Ⅳ.实行一级市场与二级市场并存的交易制度
证券具有极高的流动性必须满足的条件有()。Ⅰ.很容易变现Ⅱ.变现的交易成本极小Ⅲ.本金保持相对稳定Ⅳ.变现的交易成本较高
成本计算平行结转分步法能提供各个步骤半成品的成本资料。()
下列各项中,不属于特定减免关税的是()。
最新回复
(
0
)