首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
已知一个线性表(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]中,若采用线性探测方法解决冲突,则在该散列表上进行等概率成功查找的平均查找长度为( )。
admin
2019-06-12
46
问题
已知一个线性表(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占据,所以进行线性再散列,线性再散列的公式为:H
i
=(H(key)%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/zbCZ777K
本试题收录于:
软件设计师上午基础知识考试题库软考中级分类
0
软件设计师上午基础知识考试
软考中级
相关试题推荐
采用Kerberos系统进行认证时,可以在报文中加入(44)来防止重放攻击。
IP地址202.117.17.255/22是什么地址?____________
在网络设计和实施过程中要采取多种安全措施,下面的选项中属于系统安全需求措施的是___________。
开放系统的数据存储有多种方式,属于网络化存储的是__________。(2009年下半年试题)
假设系统中进程的三态模型如下图所示,图中的a、b和c的状态分别为__________。(2010年下半年试题)
在Linux系统中,使用ifconfig设置接口的IP地址并启动该接口的命令是__________。
阅读下列说明和c++代码,将应填入(n)处的字句写在答题纸的对应栏内。【说明】现欲构造一文件/目录树,采用组合(Composite)设计模式来设计,得到的类图如6—7所示:【c++代码】#include#include#include
阅读下列说明和Java代码,将应填入(n)处的字句写在答题纸的对应栏内。【说明】某公司的组织结构图如图17—9所示,现采用组合(Composition)设计模式来设计,得到如图17—10所示的类图。其中Company为抽象类,定义了在组织结构图上添
设表达式E=a*(b-c)/(d+e)+f*(g+h),则E的逆波兰表达式为(40),E的波兰表达式为(41)。
结构化分析(Structured Analysis)方法简称SA方法,它是一种面向数据流的需求分析方法,适用于分析大型数据处理系统。SA方法的基本思想是(16)。
随机试题
一般植物都喜欢生长在()的土壤上。
阵发性室性心动过速的心电图改变是
患者男,55岁。因心力衰竭使用洋地黄进行治疗。治疗期间的下列医嘱中,护士应对哪项提出质疑和核对()
双代号时标网络计划的特点之一是()。
在固定资产系统中,折旧分配表是编制记账凭证、把折旧分配到成本和费用的依据。
欧洲联盟的本质是()。
求函数的单调区间,并确定对应曲线的凹凸区间及拐点.
近代以来中华民族面临的两大历史任务,就是争取民族独立、人民解放和实现国家富强、人民富裕。关于两者关系,下列说法正确的有()
设矩阵A=(aij)3×3满足A*=AT,其中A*为A的伴随矩阵,AT为A的转置矩阵.若a11,a12,a13为三个相等的正数,则a11为
TheCulturalRevivalintheByzantineEmpireBetweentheeighthandeleventhcenturiesA.D,theByzantineEmpirestagedana
最新回复
(
0
)