首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
为提高查找效率，对有65025个元素的有序顺序表建立索引顺序结构，在最好情况下查找到表中已有元素，需要执行( )次关键字比较。
为提高查找效率，对有65025个元素的有序顺序表建立索引顺序结构，在最好情况下查找到表中已有元素，需要执行( )次关键字比较。
admin
2019-03-15
155
问题
为提高查找效率，对有65025个元素的有序顺序表建立索引顺序结构，在最好情况下查找到表中已有元素，需要执行( )次关键字比较。
选项
A、10
B、14
C、20
D、21
答案
B
解析
首先需要知道折半查找成功的平均查找长度为log
2
(n+1)-1。
为使查找效率最高，可对有65025个元素的有序顺序表分块，每块有
=255个元素。为每一块建立一个索引项，索引表共255个索引项。若对索引表和每一块都采用折半查找，则查找效率最高，计算可得
ASL
IndexSeqSearch
=ASL
Index
+ASL
Block
=log
2
(255+1)-1+log
2
(255+1)-1=14
下面补充一些关于折半查找的概念。
补充(1)：折半查找的时间复杂度为O(log
2
n)。
补充(2)：折半查找是基于随机存储方式的算法，必须用顺序表而不能用链表。
补充(3)：对于折半查找，假设h表示判定树的高度，如果有n个元素，则判定树的高度为
h=[log
2
(n+1)]或者h=[log
2
(n+1)]+1
转载请注明原文地址:https://kaotiyun.com/show/eBCi777K
本试题收录于：
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
简述采邑制的内容及其影响。
下列社会主义运动代表人物属于工联主义的是()。
材料一1870年代初的南部，虽然也不时出现针对黑人的种族暴行，但在日常生活中，黑人基本能与白人同车船、共饭桌、游公园。但这种情况并没有持续多久。随着前白人奴隶主“重新夺回”南部各州政权，许多州在维护社会秩序名义下，制定了各种法律，规定黑人与白人必
《中国人民解放军宣言》发表的具体时间是（）。
下列有关《布列斯特和约》的说法中，错误的一项是()。
标志着抗日战争进入战略相持阶段的是()。
下列各组古代民族，其语言都属于印欧语系的是()
阅读下面史料，回答问题：材料一各缔约国主力舰替换总吨位按照标准排水量计算不得超过如下：合众国525000吨；英帝国525000吨；法国175000吨；意大利175000吨；日本315000吨。
桌上有一空盘，只允许放入一个水果。爸爸专向盘中放苹果，妈妈专向盘中放橘子，女儿专等着吃盘中的苹果，儿子专等着吃盘中的橘子。试用P，V原语实现爸爸、妈妈、儿子和女儿间能同步的程序。
网络如图所示。链路旁边注明的数字代表链路的长度(假想单位)。试利用Dijkstra算法求出从结点A到所有其他结点的最短路由。
随机试题
我国发展城市社区卫生服务，将社区卫生服务机构列为定点医疗机构，要求首诊在社区，实行逐级转诊制度，这是体现了社区卫生服务的哪种特点
失真度是指影像的
针具的消毒以何种为佳
某机电产品国际招标项目采用综合评价法评标，评标委员成员对综合排名及推荐中标结果存在分歧时的处理原则与方法不正确的是()
良性病毒不但会占有系统CPU资源，也会破坏系统数据，会使系统瘫痪。()
在咨询中，咨询师对待求助者的问题应该持有()态度。
阅读《罗布泊，消逝的仙湖》教学实录的片段，按要求答题。师：以前碧波荡漾的罗布泊现在没有一只鸟，没有一条溪，成了荒凉的痛苦的罗布泊，成了恐怖的罗布泊。这究竟是什么原因呢?师：这么多同学举手啊，请大家畅所欲言。(师示意学生发言)
研究生考试是全体考生________的舞台，个别考生的破格录取似乎是一种惜才爱才之举，但严格来说，为维护研究生考试的公平，破格资格还应慎重给予。尺度一旦把握不好，就会落人口实、________。填入画横线部分最恰当的一项是()。
TCP和UDP的—些端口保留给—些特定的应用使用。下列为POP3协议保留的端口号为______。
Muchoftoday’sscienceofphysicsisbasedonNewton’sdiscoveryofthethreelawsofmotionandhistheoryofgravity(引力).Ne
最新回复
(
0
)
