首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
为提高查找效率，对有65025个元素的有序顺序表建立索引顺序结构，在最好情况下查找到表中已有元素，需要执行( )次关键字比较。
为提高查找效率，对有65025个元素的有序顺序表建立索引顺序结构，在最好情况下查找到表中已有元素，需要执行( )次关键字比较。
admin
2019-03-15
134
问题
为提高查找效率，对有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
学硕统考专业
相关试题推荐
法国工业革命大发展时期是在()。
简述采邑制的内容及其影响。
高平陵事件
曾在1978年5月10日《理论动态》上发表的《实践是检验真理的唯一标准》一文，以后又在《光明日报》、《人民日报》、《解放军报》转载，这篇文章的初稿作者是()。
关于清代我国疆域的叙述，下列()不正确。
下列哪两个国家是第二次工业革命的发源地和“中心”?
假定有一条通带为100kHz的信道，每路信号的带宽为3．2kHz，各路信号间的防护带宽为0．8kHz。若采用频分多路复用，那么最多可以同时传输()路信号。
在机器数中，正数的符号位用“1”表示的是()。
ICMP协议不具备的功能是()。
假设程序PA和PB单独执行时所需的时间分别用TA和TB表示，并且假设TA=1h，TB=1．5h，其中处理器工作时间分别为TA=18min，TB=27min，如果采用多道程序设计方法，让PA和PB并行工作，假定处理器利用率达到50％，系统开销为15
随机试题
在国际核事件分级表中将较低级别称为事件，包括
A、乳汁管B、分泌道C、油室D、油细胞E、腺鳞荆芥叶组织中有（）
反垄断政策措施主要是从()方面来进行的。
SDH设备平均发送光功率的测试点在()点。
为了了解高校学生对《知识产权法》基本知识的掌握程度，某教育咨询公司在一所高校内部选取了相同年级的两组学生进行了有奖测试。经阅卷分析发现：第一组学生的优秀率达到了60％，而第二组的优秀率仅有20％。咨询公司据此得出结论：该校大学生在对《知识产权法》的了解和掌
我国刑法的基本原则是______。
德商是指一个人的人格和道德品质，其内容包括体贴、尊重、容忍、宽容、诚实、负责、平和、忠心、礼貌、幽默等各种美德。根据上述定义，下列属于德商的是()。
Therearetwobasicwaystoseegrowth:oneasaproduct,theotherasaprocess.Peoplehavegenerallyviewedpersonalgrowtha
Whydoesthemangotothetravelagency?
Seekingtoframehisnewadministrationasonewithafirmfocusonclosingthegapbetweenchildrenfromaffluentandpoorfami
最新回复
(
0
)
