首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
为提高查找效率,对有65025个元素的有序顺序表建立索引顺序结构,在最好情况下查找到表中已有元素,需要执行( )次关键字比较。
为提高查找效率,对有65025个元素的有序顺序表建立索引顺序结构,在最好情况下查找到表中已有元素,需要执行( )次关键字比较。
admin
2019-03-15
290
问题
为提高查找效率,对有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
学硕统考专业
相关试题推荐
二里头文化遗址中,发现()被当做货币使用,这说明交换活动在当时有一定的发展。
阅读材料,回答以下问题:第四章总统第二十九条临时大总统、副总统由参议院选举之。以总员四分之三以上出席,得票满投票总数三分之二以上者为当选。第三十条临时大总统代表临时政府,总揽政务,公布法律。第三十一条临时大总统为执行法律或基于法
阅读史料回答以下问题:天既哀大地生人之多艰,黑帝乃降精而救民患,为神明,为圣王,为万世作师,为万民作保,为大地教主。生于乱世,乃据乱世而立三世之法,而垂精太平。乃因其所生之国,而立三世之义,而注意于大地远近、大小若一之大一统。乃立元以统天,以天为
三国时期,魏、蜀、吴三国灭亡的历史顺序是()。
下列各组条约的时间排列顺序正确的是()。①《布列斯特条约》②《色佛尔条约》③《九国公约》④《洛桑条约》
试析第三次科学技术革命对人类社会和历史进程的影响。
太平天国在1853年冬颁布的纲领性文件是()。
对斯大林时期形成的高度集中的社会主义经济政治体制的叙述,不确切的是()。
42.设有带头结点的循环双链表表示的线性表L=(a1,a2,……,an-1,an)。设计在时间和空间上都尽可能高效的算法,将L改造成L=(a1,a2,……,an,……a4,a2)。要求:(1)给出算法的基本设计思想。(2)根据设计思想,
一131的1字节、2字节补码分别是()。
随机试题
难复性疝应为()
A.气虚B.气陷C.气滞D.气闭症见胀满疼痛,甚则引起瘀血、痰饮,属于
A.肿瘤区B.临床靶区C.计划靶区D.治疗区E.照射区肿瘤临床灶和转移的淋巴结及其他转移病灶
喷射性呕吐伴头痛、视乳头水肿常见于喷射性呕吐伴眩晕、眼震常见于
对罐壁焊接工艺要求的表述中不正确的是()。
某汽车库,建筑面积3999m2,地下1层,层高3.30m,地下汽车库地面标高至室外地面的距离不大于10m。车库可停车101辆,划分1个防火分区,2个防烟分区。车库设人员疏散口2个,设汽车疏散口2个,汽车出入口均设防火卷帘。该汽车库消防供电负荷为二级,并设
在股指期货投资者适当性制度中,关于法人投资者特殊操作要求的描述,下列正确的有()。[2010年11月真题]
根据合伙企业法律制度的规定,合伙企业债权人在清算结束后,对于未能清偿的债务,由原合伙人继续承担连带清偿责任,但是,如果债权人在法定期限内未向债务人提出清偿请求的,则债务人的清偿责任归于消灭。该法定期限为()。
根据劳动合同法律制度的规定,下列有关劳务派遣的表述中,正确的有()。
很认同网友的一段话:文明的意义除了不当街便溺,还有善意与宽容。前者是表象,后者才是______。真正的文明,是碰到这样的情况,走过去善意咨询那位母亲是否需要帮忙,或者指引她找到厕所,而不是冷漠地拍照当成______大陆人素质低下的又一个证据。大陆人的素质的
最新回复
(
0
)