首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
为提高查找效率,对有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
)