为提高查找效率，对有65025个元素的有序顺序表建立索引顺序结构，在最好情况下查找到表中已有元素，需要执行( )次关键字比较。

admin2019-03-15 290

问题为提高查找效率，对有65025个元素的有序顺序表建立索引顺序结构，在最好情况下查找到表中已有元素，需要执行( )次关键字比较。

选项 A、10
B、14
C、20
D、21

答案B

解析首先需要知道折半查找成功的平均查找长度为log₂(n+1)-1。
为使查找效率最高，可对有65025个元素的有序顺序表分块，每块有

=255个元素。为每一块建立一个索引项，索引表共255个索引项。若对索引表和每一块都采用折半查找，则查找效率最高，计算可得
ASL_{IndexSeqSearch}=ASL_Index+ASL_Block=log₂(255+1)-1+log₂(255+1)-1=14
下面补充一些关于折半查找的概念。
补充(1)：折半查找的时间复杂度为O(log₂n)。
补充(2)：折半查找是基于随机存储方式的算法，必须用顺序表而不能用链表。
补充(3)：对于折半查找，假设h表示判定树的高度，如果有n个元素，则判定树的高度为
h=[log₂(n+1)]或者h=[log₂(n+1)]+1

转载请注明原文地址:https://www.kaotiyun.com/show/eBCi777K

本试题收录于：计算机408题库学硕统考专业分类

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

为提高查找效率，对有65025个元素的有序顺序表建立索引顺序结构，在最好情况下查找到表中已有元素，需要执行( )次关键字比较。

计算机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．照射区肿瘤临床灶和转移的淋巴结及其他转移病灶

喷射性呕吐伴头痛、视乳头水肿常见于喷射性呕吐伴眩晕、眼震常见于

对罐壁焊接工艺要求的表述中不正确的是()。

在股指期货投资者适当性制度中，关于法人投资者特殊操作要求的描述，下列正确的有()。[2010年11月真题]

根据劳动合同法律制度的规定，下列有关劳务派遣的表述中，正确的有()。