首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
为提高查找效率，对有65025个元素的有序顺序表建立索引顺序结构，在最好情况下查找到表中已有元素，需要执行( )次关键字比较。
为提高查找效率，对有65025个元素的有序顺序表建立索引顺序结构，在最好情况下查找到表中已有元素，需要执行( )次关键字比较。
admin
2019-03-15
92
问题
为提高查找效率，对有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
学硕统考专业
相关试题推荐
反映近代资产阶级政治思想萌芽的著名代表人物是()。
亚历山大二世签署废除农奴制法令的根本目的是()。
三国时期，魏、蜀、吴三国灭亡的历史顺序是()。
请根据下面材料，结合相关知识，分析其内容及意义。他命令所有罗马人都进行登记并用银对自己的财产估价，按照习惯宣誓保证所报各项均属真实，全部财产均已按最高价格估价，并陈报父亲系何人，自己的年龄，自己的妻子和子女的名字，每人的籍贯隶属市中哪个部落或乡间
下列著作被人们称为17世纪物理学、数学的百科全书，并标志着经典力学体系的完成的是()。
下列选项中，不是由晁错提出的是()。
下列关于后三头同盟的叙述，正确的是()。
假设某计算机的存储系统由Cache和主存组成j某程序执行过程中访存1000次，其中访问Cache缺失(未命中)50次，则Cache的命中率是()。
有如下的文件目录结构。使用目录E的用户与对文件I加以保护，不许别人使用，如何实现?
某多道程序设计系统配有一台处理器和两台外设IO1、IO2，现有3个优先级由高到低的J1、J2、J3都已装入了主存，它们使用资源的先后顺序和占用时间分别是：J1：IO2(30ms)，CPU(10ms)；IO1(30ms)，CPU(10ms)
随机试题
患者，男性，12岁，因腹痛、脓血便2个月来诊。患者2个多月前从农村回到城市后突然发热达38℃，无寒战，同时有腹痛、腹泻，大便每日10余次，为少量脓血便，伴里急后重，曾到附近医院化验大便有多数白细胞，口服几次庆大霉素和黄连素好转，以后虽间断服用黄连素，但仍有
关于牙周袋临床表现与组织病理关系哪项是错误的
下列除哪项外，均可出现口臭
A．小便赤热，尿时灼痛B．排尿时突然中断，尿道窘迫疼痛C．少腹满闷胀痛，小便艰涩疼痛，尿后余沥不尽D．尿道热涩疼痛，尿色如米泔水E．小便量少，排出不畅，点滴而短少膏淋的主症特点是
银监会《商业银行房地产贷款风险管理指引》中要求：商业银行应着重考核借款人还款能力，应将借款人住房贷款的月房产支出与收入比控制在()以下。
某行政单位于2020年经批准后对外无偿调出一套设备，该设施账面余额300000元，已经计提折旧120000元。设备调出过程中该单位以银行存款支付了运费1500元。其账务处理应为()。
由于官宦专权导致灭亡的朝代有()。
有人认为，只有那些试图宣泄不满的民众才需要监督权，对于生活安逸的人来说，监督权可有可无。请结合宪法学原理对此看法进行评析。
y＝eχ在χ＝0处的曲率半径为R＝_______．
ThedeathofHarambe,theendangeredlowlandgorilla(大猩猩)shotattheCincinnatiZooaftera4-year-oldcrawledthroughabarri
最新回复
(
0
)
