首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
为提高查找效率，对有65025个元素的有序顺序表建立索引顺序结构，在最好情况下查找到表中已有元素，需要执行( )次关键字比较。
为提高查找效率，对有65025个元素的有序顺序表建立索引顺序结构，在最好情况下查找到表中已有元素，需要执行( )次关键字比较。
admin
2019-03-15
253
问题
为提高查找效率，对有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
学硕统考专业
相关试题推荐
鉴于汉匈关系的状况，汉初向汉高祖提出和亲政策的是()。
佛教在从印度向外传播的过程中分为两大流派，其中小乘佛教又称为()。
中华人民共和国恢复在联合国合法席位的时间是()。
欧洲历史上第一部系统完备的法典是（）。
下列关于马略军事改革的叙述，不正确的是()。
下列选项中，控制了西域政权的是()。
乾隆时期，明确规定了驻藏大臣的地位与达赖班禅同等，并实行“金瓶掣签”制度的文件是()。
某网络的拓扑结构由下图所示，其中顶点表示路由器。该网络的路由器采用了链路状态路由算法，在某一时刻各个路由器发送的链路状态如下：A：B(1)，D(3)B：A(1)，D(1)，C(3)，E(5)C：B(3)，D(1)D：A(3)，B(1
一个使用选择性重传协议的数据链路层协议，如果采用了5位的帧序列号，那么可以选用的最大窗口是()。
在单CPU和两台输入／输出设备(11，12)的多道程序设计环境下，同时投入3个作业J1、J2和J3运行。这3个作业对CPU和输入／输出设备的使用顺序和时间如下所示。J1：12(30ms)；CPU(10ms)；11(30ms)；CPU(10ms)；
随机试题
油罐焊接完毕后，检查罐壁严密性试验的方法一般采用()。
消防给水管网施工完成后，要进行试压和冲洗。系统试压前选用试压用的压力表不少于2只，精度不低于1．5级，量程为试验压力值的()倍。
根据《证券法》的规定，上市公司的下列情形中，属于应当由证券交易所决定终止其股票上市交易的有()。
我国《公司法》规定，向发起人、国家授权投资的机构、法人发行的股票，应为()。
下列关于风险评估的理解中，不正确的有()。
新安江城的“三绝”是指()。
由于受市场经济负面影响，省直机关有些党员干部思想上出现了个人主义、拜金主义、享乐主义的苗头，缺乏讲大局、讲奉献的精神，你作为省直机关工作委员会副书记，认为应该采取什么措施加强机关干部思想建设?
刑警队需要充实缉毒组的力量，到底由谁来参加，已商定以下意见：(1)如果甲参加，则乙也参加；(2)如果丙不参加，则丁参加；(3)如果甲不参加或丙参加，则队长戊参加；(4)队长戊和副队长己不能都参加；(5)上级决定副队长己参加。根据以上规定，下列推理完全
根据我国有关规定，实行定时工时制的用人单位，休息日安排劳动者工作又不能安排补休的，支付不低于工资的（）的工资报酬。
把y看作自变量，x为因变量，变换方程
最新回复
(
0
)
