首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
已知一个线性表(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
44
问题
已知一个线性表(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
软件设计师上午基础知识考试
软考中级
相关试题推荐
目前,通过移动电话接入互联网所采用的主要技术是什么?公司网络中的设备或系统(包括:存储商业机密的数据库服务器、邮件服务器,存储资源代码的PC机、应用网关、存储私人信息的PC机、电子商务系统)哪些应放在DMZ中,哪些应放在内网中?并给予简要说明。
根据我国相关法律的规定,实用新型专利和外观设计专利的保护期为(20)年,单位软件产品的著作权保护期为(21)年。
在帧中继网络的拥塞控制功能中,采用显式信令控制时,如果LAP-D帧中的PBCN比特置1,则表示(118)。
Socket的通信方式包括(62),(63)是最常用的套接字类型。
N模冗余系统如图1所示,由/V(N=2n+1)个相同部件的副本和一个(n+1)/N表决器组成,表决器把N个副本中占多数的输出作为系统的输出。设表决器完全可靠,且每个副本的可靠性为R,则该N模冗余系统的可靠性R=(8)。若R0(下标)=e-λt,当kt=(9
ARP的帧类型域中的值是(24)。
配置WWW服务器是UNIX操作系统平台的重要工作之一,而Apache是目前应用最为广泛的Web服务器产品之一,(59)是Apache的主要配置文件。URL根目录与服务器本地目录之间的映射关系是通过指令(60)设定;指令ServerAdmin的作用
码是一些码字组成的集合。一对码字之间的海明距离是(30),一个码的海明距离是所有不同码字的海明距离的(31)。如果要检查出d位错,那么码的海明距离是(32)。如果信息长度为5位,要求纠正1位错,按照海明编码,需要增加的校验位是(33)。以太网中使用的校验码
网络连接如下页图所示,要使计算机能访问到服务器,在路由器R1中配置路由表的命令是(34)。
在BGP4协议中,(1)报文建立两个路由器之间的邻居关系,(2)报文给出了新的路由信息。(2012年下半年试题)(2)
随机试题
关于骨骼肌兴奋一收缩耦联,错误的是
人民法院作出的除权判决,其效力有()。
检验检疫机构对检验检疫不合格的人境货物签发《入境货物检验检疫证明》。()
公司减少注册资本的决议作出后,应于()日内通知债权人。
定向发行资产支持证券必须进行信用评级。
儿童自我意识包括自我认识、______和______三个方面。
某学校以提高办公效率、科学管理学校为由,禁止教师在员工代表大会上发言,也禁止教师对学校的管理、行政工作提出不同意见,此举令老师们觉得办公氛围不自由,很压抑。该学校的做法()。
婷婷、天天、乐乐和明明同时到学校医务室,找医生治疗。婷婷打针要6分钟,天天检查要5分钟,乐乐吃药要3分钟,明明换药要4分钟。医务室只有一个医生。统筹安排四人治病的先后顺序,使四位同学在医务室停留的总时间最短为多久?
考生文件夹下存在一个数据库文件“samp3.accdb”,里面已经设计了表对象“tEmp”、查询对象“qEmp”、窗体对象“fEmp”和宏对象“mEmp”。同时,给出窗体对象“fEmp”上一个按钮的单击事件代码,试按以下功能要求补充设计。功能:单击“刷
A、Fashion.B、Style.C、Beauty.D、Comfort.D对话中,男士说虽然最近短发很流行,他还是觉得女士留长发比较好看,女士则说长发虽好看,但在夏天让人很不舒服,即使她买了conditioner(空调)还是觉得长发很烦。因此,女
最新回复
(
0
)