首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
已知一个线性表(16,25,35,43,51,62,87,93),采用散列函数H(Key)=Key mod 7将元素散列到表长为9的散列表中。若采用线性探测的开放定址法解决冲突(顺序地探查可用存储单元),则在所构造的哈希散列表上进行等概率成功查找的平均查找
已知一个线性表(16,25,35,43,51,62,87,93),采用散列函数H(Key)=Key mod 7将元素散列到表长为9的散列表中。若采用线性探测的开放定址法解决冲突(顺序地探查可用存储单元),则在所构造的哈希散列表上进行等概率成功查找的平均查找
admin
2010-01-23
56
问题
已知一个线性表(16,25,35,43,51,62,87,93),采用散列函数H(Key)=Key mod 7将元素散列到表长为9的散列表中。若采用线性探测的开放定址法解决冲突(顺序地探查可用存储单元),则在所构造的哈希散列表上进行等概率成功查找的平均查找长度为(60)(为确定记录在查找表中的位置,需和给定关键字值进行比较的次数的期望值,称为查找算法在查找成功时的平均查找长度)。
选项
A、(8×1)/8
B、(8×1)/9
C、(5×1+2+3+6)/8
D、(5×1+2+3+6)/9
答案
C
解析
本题考查数据结构中哈希表的基础知识。线性探测法解决冲突的方法是:若在地址r处发生冲突,则探测地址 r+1,若已到达表尾,则再从表头出发进行探测。若是插入元素,则找到一个空闲单元为止。若表已满则采用其他策略解决冲突;若是访问元素,则找到元素或一个空闲单元为止。
初始哈希表为空,根据序列(16,25,35,43,51,62,87,93)和哈希函数H(Key)=Key mod 7构造哈希表的过程如下。
①16 mod 7=2 25 mod 7=4 35 mod 7=0 43 mod 7=1,地址2、4、0、1空闲,所以插入对应元素。
②51 mod 7=2,地址2处冲突,因此探测地址3,该单元空闲,因此51存入地址3。由于62 mod 7=6,地址6处空闲,所以将62插入地址6。
③87 mod 7=3,地址3处冲突,因此依次探查地址4、5,地址5空闲,因此87存入地址5;93 mod 7=2,地址2处冲突,因此依次探查地址3、4、5、6、7,地址7空闲,因此93存入地址7。
为确定记录在查找表中的位置,需和给定关键字值进行比较的次数的期望值称为查找算法在查找成功时的平均查找长度。对于含有n个记录的表,查找成功时的平均查找长度定义为:
,其中,Pi为对表中第i个记录进行查找的概率,且
,一般情况下,均认为查找每个记录的概率是相等的,即 Pi=1/n。Ci为找到表中其关键字与给定值相等的记录时(为第i个记录),和给定值已进行过比较的关键字个数。对于本试题所构造的哈希表,平均查找长度ASL=(1+1+1+1+2+1+3+6)/8=2。
转载请注明原文地址:https://kaotiyun.com/show/bqxZ777K
本试题收录于:
软件设计师上午基础知识考试题库软考中级分类
0
软件设计师上午基础知识考试
软考中级
相关试题推荐
阅读以下说明,回答下面问题。【说明】VPN是通过公用网络Internet将分布在不同地点的终端联接而成的专用网络。目前大多采用IPsec实现IP网络上端点间的认证和加密服务。
计算机网络和分布系统中互相通信的(303)间交换信息时必须遵守的规则的集合称之为网络协议。其中,(304)是数据和控制信息的结构或格式;(305)是用于协调和进行差错处理的控制信息;定时是对事件实现顺序的详细说明,而网络体系结构则是(306)。
MultipurposeInternetMailExtension(MIME)is a(46)document messaging standard in the Internet enviroment, with MIME, users can
ATM网为了避免拥塞的出现,采用了许多通信量管理技术,防止网络过载的第一道防线是(119)。
家庭接入Internet可以通过光缆入户,即(30)方式,也可以通过传统的线缆接入。当使用电话线接入时,有多种模式,对称模式的技术有(31)。
PPP使用(38)协议。相对于OSI模型,它提供(39)服务。对于PPP,远程服务器可以为本地客户提供一个(40)IP地址。
VLANtag在OSI参考模型的(50)实现。
在OSI参考模型中,物理层的功能是(25)等。实体在一次交互作用中传送的信息单位称为(26),它包括(27)两部分。上下邻层实体之间的接口称为服务访问点(SAP),网络层的服务访问点也称为(28),通常分为(29)两部分。
边界网关协议BGP的报文(1)传送。一个外部路由器通过发送(2)报文与另一个外部路由器建立邻居关系,如果得到应答,才能周期性地交换路由信息。(2010年上半年试题)(1)
随机试题
特异性投射系统的特点是( )。【2003年考试真题】
A.丙磺舒B.克拉维酸C.舒巴坦钠D.他唑巴坦E.甲氧苄啶因口服吸收差,可与氨苄西林以1:1的形式以次甲基相连,得到舒他西林的药物是()。
下列关于城市消防远程监控系统中用户服务系统软件的使用与检查要求的叙述中,错误的是()。
(操作员:王主管;账套:601账套;操作日期:2015年1月31日)设置固定资产变动方式。固资变动方式编码:06固资变动方式名称:投资者投入变动类型:增加固定资产
对风险进行识别、衡量、分析,并在此基础上有效处置,以最低成本实现最大安全保障的管理方法是()。
下列金融机构中,不属于狭义“影子银行”的是()。
下列各项中,不属于增值税征税范围的是()。
下列注册会计师进行会计分录测试的做法中,错误的是()。
[*]
LearningthroughTestsTakingatestisnotjustapassivemechanismforassessinghowmuchpeopleknow,accordingtonewre
最新回复
(
0
)