首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
已知一个线性表(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
52
问题
已知一个线性表(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
软件设计师上午基础知识考试
软考中级
相关试题推荐
由我国信息产业部批准发布,在信息产业部门范围内统一使用的标准,称为(24)。
目前,通过移动电话接入互联网所采用的主要技术是什么?进行一次查询的数据信息见表4.1,网络的基本通信服务费用见表4.2,总费用=网络租用费+通信费。根据表中给出的数据,试计算销售员每月至少应进行多少次查询,才能使得使用移动电话的总费用比使用PDA的总
对一路信号进行频移键控(FSK)调制时,若载波频率为fc,调制后的信号频率分别为f1和f2(f1<f2),则三者的关系是(17)。当对多路信号进行调制时,调制后各信号的频谱(18)。信号到达接收端后通过(19)分离各路信号。WDM与FDM工作方式很相似,
TCP是一个面向连接的协议,它提供连接的功能是(14)的,采用(15)技术实现可靠数据流的传送。为了提高效率,又引入了滑动窗口协议,协议规定重传(16)的分组,这种分组的数量最多可以(17),TCP协议采用滑动窗口协议来解决了(18)。
在windows2000操作系统中,配置IP地址的命令是(59)。若用ping命令来测试本机是否安装了TCP/IP协议,则正确的命令是(60)。如果要列出本机当前建立的连接,可以使用的命令是(61)。
OSI网络管理标准定义了网管的五大功能。比如对每一个被管理对象的每一个属性设置阈值、控制域值检查和告警的功能属于(54);接收报警信息、启动报警程序、以各种形式发出警报的功能属于(55);接收告警事件、分析相关信息、及时发现正在进行的攻击和可疑迹象的功能属
软件能力成熟度模型CMM(CapabilityMaturityModel)描述和分析了软件过程能力的发展与改进的程度,确立了一个软件过程成熟程度的分级标准。在初始级,软件过程定义几乎处于无章可循的状态,软件产品的成功往往依赖于个人的努力和机遇。在(7)
国际标准化组织制定的OSI网络体系管理协议是(58),另外,ISO还定义了5个管理功能域,(59)属于性能管理域。IAB制定的网络管理协议是SNMP,在SNMP管理框架中使用的管理信息库为(60)。管理站(Manager)通过GetRequest命令查询代
曼彻斯特编码的特点是(),它的编码效率是()。
公用数据网对于外部用户提供的界面大多采用国际标准,这个标准是CCITT制订的(36)。
随机试题
高压绝缘棒主要用来闭合或()。
演示或演讲的目标有很多,但不包括
下列有关次级生产力的说法不正确的是()
A.肱动脉损伤B.胭动脉损伤C.尺神经损伤D.桡神经损伤E.股骨头缺血性坏死股骨下1/3骨折可出现
以部位命名的外科疾病是()
建设工程项目施工成本考核的主要指标有()。
甲将一汇票背书转让给乙,但该汇票上未记载乙的名称。其后,乙在该汇票被背书人栏内记载了自己的名称。根据票据法律制度的规定,下列有关该汇票背书与记载效力的表述中,正确的是()。
算法的时间复杂度是指
Embroidery(刺绣)isabrilliantpearlinChineseart.(81)FromthemagnificentDragonRobeswornbyemperorstotoday’sfashions
Throughouthistorymanhasobservedsuchnaturalcyclesastherisingandsettingofthesun,theebbandflowoftheoceantide
最新回复
(
0
)