首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
已知一个线性表(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
50
问题
已知一个线性表(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
软件设计师上午基础知识考试
软考中级
相关试题推荐
交换机的所有端口在缺省配置的情况下(52)。如果属于同一VLAN的数据帧是连接在不同交换机上的,必须通过(53)传输。
对一路信号进行频移键控(FSK)调制时,若载波频率为fc,调制后的信号频率分别为f1和f2(f1<f2),则三者的关系是(17)。当对多路信号进行调制时,调制后各信号的频谱(18)。信号到达接收端后通过(19)分离各路信号。WDM与FDM工作方式很相似,
以下Windows命令中,可以用于验证端系统地址的是(52);可以用于识别分组传送路径的是(53);如果要终止一个ping会话,正确的操作是(54)。以下应用中,对网络带宽性能影响最大的应用上(55)。OSPF和RIP都是Internet中的路由协议,与R
关于TCP/IP与OSI模型的说法中,正确的是(24)。
某种中继设备提供运输层及运输层以上各层之间的协议转换,这种中继设备是(19),从OSI协议层次来看,用以实现不同网络间的地址翻译、协议转换和数据格式转换等功能的路由器属于(20)范畴,当采用数据报服务时,负责端到端的流量控制的是(21),路由器的主要功能是
在FDM中,主要通过(37)技术,使各路信号的带宽(38)。使用FDM的所有用户(39)。从性质上说,FDM比较适合于传输(40),FDM的典型应用是(41)。
OSI网络管理标准定义了网管的五大功能。比如对每一个被管理对象的每一个属性设置阈值、控制域值检查和告警的功能属于(54);接收报警信息、启动报警程序、以各种形式发出警报的功能属于(55);接收告警事件、分析相关信息、及时发现正在进行的攻击和可疑迹象的功能属
N模冗余系统如图1所示,由/V(N=2n+1)个相同部件的副本和一个(n+1)/N表决器组成,表决器把N个副本中占多数的输出作为系统的输出。设表决器完全可靠,且每个副本的可靠性为R,则该N模冗余系统的可靠性R=(8)。若R0(下标)=e-λt,当kt=(9
以下关于进程的描述,错误的是(7)。
国际标准化组织制定的OSI网络管理协议是(1)。IAB制定的网络管理协议是(2)。运行在(3)上的网络管理系统可以通过SNMP协议查阅被管理的网络节点(4)中的内容。在以下网络管理系统中,(5)是第一个重要的基于UNIX的网络管理系统,也是第一个提供分布式
随机试题
根据《法律援助条例》规定,请求支付劳动报酬的,向()的法律援助机构提出申请。
治疗湿热黄疽可选用
痢疾初起治疗当忌
肢端肥大症患者血钙较高时常提示
实验室测定血清总钙的参考方法是
下列关于磁共振图像矩阵的叙述,正确的是
某公司去年有员工830人,今年男员工人数比去年减少6%,女员工人数比去年增加5%,员工总数比去年增加3人,问今年男员工有多少人?()
下面是某求助者MMPI-2的测验结果24项版本的HAMD量表,其因子数量为()。(A)2(B)3(C)5(D)7
案例:某学校初二年级的数学备课组针对“勾股定理”一课的教学进行讨论,拟定了如下的教学目标:①掌握勾股定理的内容,体会数形结合思想;②学会运用勾股定理。为了落实上述教学目标,甲、乙两位教师对此给出了不同的教学思路。
纯粹从阅读角度看,今天我们的阅读数量是很可观的。我们每天看微博,看新闻客户端,看微信朋友圈,看QQ日志……这最终都能累积为每天的阅读量。碎片化的阅读,确实便利了信息获取,但若是从人文涵养的角度看,碎片化本身意味着不全面,再加上网络阅读的简化,人们由此实现的
最新回复
(
0
)