首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
为提高查找效率，对有65025个元素的有序顺序表建立索引顺序结构，在最好情况下查找到表中已有元素，需要执行( )次关键字比较。
为提高查找效率，对有65025个元素的有序顺序表建立索引顺序结构，在最好情况下查找到表中已有元素，需要执行( )次关键字比较。
admin
2019-03-15
291
问题
为提高查找效率，对有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://www.kaotiyun.com/show/eBCi777K
本试题收录于：
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
二里头文化遗址中，发现()被当做货币使用，这说明交换活动在当时有一定的发展。
汉武帝时期，在民族关系上采取了一系列措施，其中不包括()。
下列属于明朝心学重要代表人物的是()。①陈献章②王守仁③王畿④钱德洪
材料一1870年代初的南部，虽然也不时出现针对黑人的种族暴行，但在日常生活中，黑人基本能与白人同车船、共饭桌、游公园。但这种情况并没有持续多久。随着前白人奴隶主“重新夺回”南部各州政权，许多州在维护社会秩序名义下，制定了各种法律，规定黑人与白人必
秦国统一全国，实行“车同轨”“书同文”的政策，其中文字统一为()。
提出“双重真理”，并认为理性和宗教并不矛盾的阿拉伯哲学家是()。
第一次国共合作采取了共产党员以个人身份加入国民党的“党内合作”方式，最早提出这种方式的是()。
利玛窦与徐光启合作翻译的()，介绍了曾经流行于欧洲的欧几里得平面几何的系统理论，大大地丰富了中国古代几何学的内容。
一个在以太网中的主机试图发送一个帧，当它尝试了16次仍然失败之后，它应该()。
多道程序设计是指()。
随机试题
氢氟酸烧伤应先用大量水冲洗，然后将烧伤处浸入()。
NothingthatIcansee______whatyouhavedescribed.
下列哪项不是慢性盆腔炎的临床表现
建设资金已落实是指()。
中国证监会可以对()等特殊行业上市公司的信息披露作出特别规定。
在进行WAIS—RC的数字广度测验时，施测的具体要求是()。
“书目”在文献等级中属于()。
我国地势呈三级阶梯分布，下列哪些在第二阶梯上?（）
多线程是Java语言的______机制，只能够处理同步共享数据和各种不同的事件。
What’sMissLi?
最新回复
(
0
)
