首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
已知一个线性表(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
55
问题
已知一个线性表(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
软件设计师上午基础知识考试
软考中级
相关试题推荐
Internet是全球最大的、开放的、由众多网络互联而形成的计算机网络,狭义Internet是指由上述提到网络中采用IP协议的网络互联而成的,广义Internet是指狭义Internet加上所有(92)的网络。Internet体系结构具有良好扩充性的主要原
x.25实际上是DCE与分组交换网(PSN)的之间的一组接口协议,x.25协议定义了(102)个层次。
对于不支持TCP/IP的设备(64)用SNMP进行管理。在SNMPv3中,以前叫做管理站和代理的东西现在统一叫做(65)。
下面有关NTFS文件系统优点的描述中,(5)是不正确的。要把FAT32分区转换为NTFS分区,并且保留原分区中的所有文件,不可行的方法是(6)。
对欲访问特定信息的发起者的身份或者对传送的报文完整性进行合法性审查或核实的行为称为(50)。在日常生活中,我们可以用手写签名来防止否认的发生。在计算机通信中,要解决这类问题,可采用的方法是(51)。关于客户/服务器应用模式,说法正确的是(52)。在理论上,
UML提供了一系列的图支持面向对象的分析与设计,其中(13)给出系统的静态设计视图;(14)对系统的行为进行组织和建模是非常重要的;(15)和(16)都是描述系统动态视图的交互图,其中(15)描述了以时间顺序组织的对象之间的交互活动,(16)强调收发消息的
一个复杂的系统可由若干个简单的系统串联或并联构成。已知两个简单系统I和J的失效率分别为λI=25×10-5/h和λJ=5×10-4/h,则由I和J经如图1所示的串联和并联构成的复合系统P和Q的失效率分别为πP=(5)/h和πQ=(6)/h,平均无故障时间分
网络系统设计过程中,物理网络设计阶段的任务是__________。(2012年下半年试题)
下一代IP协议IPv6的基本报头包含(203)个字节,并包含多个可扩展报头。基本报头中的(204)字段指明了一个特定的源站向一个特定目标站发送的分组序列。一个数据流由(205)命名。在IPv6中,地址被扩充为128位。按照IPv6的地址表示方法,以下地址中
国际标准化组织制定的OSI网络管理协议是(1)。IAB制定的网络管理协议是(2)。运行在(3)上的网络管理系统可以通过SNMP协议查阅被管理的网络节点(4)中的内容。在以下网络管理系统中,(5)是第一个重要的基于UNIX的网络管理系统,也是第一个提供分布式
随机试题
A.脐部圆形包块,加腹压后包块突出,平卧时包块消失B.卵黄管的脐端未闭,遗留较短的盲管C.脐带周围发生缺损,腹腔内脏脱出体外D.出生后见胃肠突出于腹壁外,脐和脐带正常,腹壁裂孔在脐的右侧并为纵向E.卵黄管的脐端有残留的黏膜形成息肉样红色突起,少量液
A、祛暑利湿,补气生津B、祛暑除湿,和胃消食C、祛暑解表,清热生津D、解表化湿,理气和中E、清热解毒,利湿化浊六合定中丸的功效()。
第二类精神药品处方印刷用纸为
抢救青霉素过敏性休克的首选药物是
EVA、PE类聚合物改性沥青混合料的废弃温度为()。
某公司为获得一项工程合同,拟向工程发包方的有关人员支付好处费8万元,公司市场部持公司的批示到财务部领取该笔款项。财务部经理谢某认为该项支出不符合有关规定,但考虑到公司主要领导已作了批示,遂同意拨付了款项。对谢某做法的下列认定中正确的是()。
我国对资本主义工商业进行社会主义改造的政策是和平赎买。()
小刚在一次演讲比赛中有五名裁判给他打分,除去最低分外,他的平均成绩是96分;加上最低分,它的平均成绩下降了3分。问其中打的最低分是多少?()
设f(x)连续,其中V={(x,y,z)|x2+y2≤t2,0≤z≤h}(t>0),求其中,[x]表示不超过x的最大整数.
WhatcanbecitedtoshowMr.Eliasson’sunderstandingoftotal-immersionart?
最新回复
(
0
)