首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
已知一个线性表(16,25,35,43,51,62,87,93),采用散列函数H(Key)=Key mod 7将元素散列到表长为9的散列表中。若采用线性探测的开放定址法解决冲突(顺序地探查可用存储单元),则构造的哈希表为(57),在该散列表上进行等概率成功
已知一个线性表(16,25,35,43,51,62,87,93),采用散列函数H(Key)=Key mod 7将元素散列到表长为9的散列表中。若采用线性探测的开放定址法解决冲突(顺序地探查可用存储单元),则构造的哈希表为(57),在该散列表上进行等概率成功
admin
2009-01-10
32
问题
已知一个线性表(16,25,35,43,51,62,87,93),采用散列函数H(Key)=Key mod 7将元素散列到表长为9的散列表中。若采用线性探测的开放定址法解决冲突(顺序地探查可用存储单元),则构造的哈希表为(57),在该散列表上进行等概率成功查找的平均查找长度为(58)(为确定记录在查找表中的位置,需和给定关键字值进行比较的次数的期望值称为查找算法在查找成功时的平均查找长度)。
选项
A、(5*1+2+3+6)/8
B、(5*1+2+3+6)/9
C、(8*1)/8
D、(8*1)/9
答案
A
解析
本题考查数据结构中哈希表的基础知识。
线性探测法解决冲突的方法是:若在地址r处发生冲突,则探测地址r+1,若已到达表尾,则再从表头出发进行探测。若是插入元素,则找到一个空闲单元为止,若表已满则采用其他策略解决冲突;若是访问元素,则找到元素或一个空闲单元为止。
初始哈希表为空,如表(a)所示。
根据序列(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空闲,所以插入对应元素,如表(b)所示。
②51 mod 7=2,地址2处冲突,因此探测地址3,该单元空闲,因此51存入地址 3。由于62 mod 7=6,地址6处空闲,所以将62插入地址6,如表(c)所示。
③87 mod 7=3,地址3处冲突,因此依次探查地址4、5、地址5空闲,因此87存入地址5;93 mod 7=2,地址2处冲突,因此依次探查地址3、4、5、6、7,地址7空闲,因此93存入地址7,如表(d)所示。
为确定记录在查找表中的位置,需和给定关键字值进行比较的次数的期望值称为查找算法在查找成功时的平均查找长度。
对于含有n个记录的表,查找成功时的平均查找长度定义为:
,其中, Pi为对表中第i个记录进行查找的概率,且
,一般情况下,均认为查找每个记录的概率是相等的,即Pi=1/n;Ci为找到表中其关键字与给定值相等的记录时(为第i个记录),和给定值已进行过比较的关键字个数。
对于本哈希表,平均查找长度ASL=(1+1+1+1+2+1+3+6)/8=2。
转载请注明原文地址:https://kaotiyun.com/show/lBxZ777K
本试题收录于:
软件设计师上午基础知识考试题库软考中级分类
0
软件设计师上午基础知识考试
软考中级
相关试题推荐
文件/etc/sysconfig/network-scripts/eth0用于存储网络配置信息,请根据图2-1填写下面的空缺信息,完成主机的配置。DEVICE=eth0HWADDR=(7)ONBOOT=yesBOOT
文件/etc/sysconfig/network-scripts/eth0用于存储网络配置信息,请根据图2-1填写下面的空缺信息,完成主机的配置。DEVICE=eth0HWADDR=(7)ONBOOT=yesBOOT
在Linux系统中,DNS查询文件内容如下所示,该文件的默认存储位置为(5),当用户做DNS查询时,首选DNS服务器的IP地址为(6)。Serachdomain.test.cnNameserver210.34.0.14
网络存储备份系统的设计目标是什么?
公司内部IP地址分配如下:若调换上面配置中的第3条和第4条规则的顺序,则__________。备选答案:A.安全规则不发生变化B.财务服务器将受到安全威胁C.Web服务器将受到安全威胁D.内网用户将无法
阅读以下说明,回答问题,将解答填入答题纸对应的解答栏内。【说明】图2-1为某公司数据中心拓扑图,两台存储设备用于存储关系型数据库的结构化数据和文档、音视频等非结构化文档,规划采用的RAID组合方式如图2-2、图2-3所示。图2-2所示的RAID方
随机试题
根据系统论的理论,物流系统是有层次的。下列哪种系统之间的关系是协调、配合、竞争的关系?
患者,男,48岁。被诊断为慢性呼吸衰竭,血气分析PaO250mmHg,PaCO270mmHg,吸氧时浓度应为
A.省、自治区、直辖市人民政府(食品)药品监督管理局B.医疗卫生机构中与实施药品不良反应报告制度有关的管理工作C.国家食品药品监督管理局D.药品不良反应监测工作E.应按规定报告所发现的药品不良反应药品生产企业、药品经营企业、医疗卫生机构
男性,55岁,胃溃疡病史8年,近半年来上腹痛加重,无规律。X线钡餐造影示胃黏膜皱襞增粗,胃窦部见3cm×3cm不规则龛影,突出腔外,胃蠕动正常,胃酸正常。印象为
A、胆汁酸B、蟾酥C、麝香酮D、蟾蜍浆E、龙脑具有抗炎、强心和雄性激素样作用的为
T公司为一家大型饲料生产企业,占地面积80000m2,共有员工110人,设有独立的安全部。T公司有生产车间、包装车间、机修车间,以及高大立筒仓、包材库、锅炉房、配电室等设施。为满足内部维修需要,T公司的机修车间配有固定式砂轮机l台、电焊机2台、摇臂钻床1
负债和所有者权益类账户的期末余额一定在贷方。()
以下属于商业票据的特征的是()。
关于世界古代文明,下列说法正确的是:
小刘正在Excel中编辑一个几百人的工资表,他希望在编辑过程中总能看到表明每列数据性质的标题行,最优的操作方法是()
最新回复
(
0
)