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

admin2019-03-15 303

问题为提高查找效率，对有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://kaotiyun.com/show/eBCi777K

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

下列条约中，哪一个是由协约国提出的灭亡土耳其的奴役性条约?()

典型的西欧封建庄园对农民采用的剥削方式是()。

第三次科技革命对社会经济结构的影响是()。

下列著作被人们称为17世纪物理学、数学的百科全书，并标志着经典力学体系的完成的是()。

下列有关《布列斯特和约》的说法中，错误的一项是()。

阅读下面史料，回答问题：材料一各缔约国主力舰替换总吨位按照标准排水量计算不得超过如下：合众国525000吨；英帝国525000吨；法国175000吨；意大利175000吨；日本315000吨。

假设系统的所有资源是同类型的，系统中的进程每次申请资源数最多1个，那么，下面列出的4种情况中，()可能发生死锁。情况序号系统中进程数资源总量

—棵二叉树的后序遍历序列为DABEC，中序遍历序列为DFBAC，则先序遍历序列为()。

在请求分页存储管理中，若采用FIFO的页面淘汰算法，当分配的页面数增加时，缺页中断的次数()。

已知有向图G=(V，A)，其中V={a，b，c，d，e)，A={，，，，，}，对该图进行拓扑排序，下面序列中不是拓扑排序的是()。

某患者，男，28岁，阵发性心慌3年，每次心慌突然发生，持续半小时至3小时不等。本次发作时心律齐，200次／分，按摩颈动脉窦心律能突然减慢至正常；心电图QRS波形态正常，P波不明显。诊断为()

房屋征收评估应当选用()等方法中的一种或者多种，方法选用前应当进行适用性分析。

金融市场的主要参与者不包括()。

根据支付结算法律制度的规定，下列违反结算纪律的行为中，应由单位和个人承担法律责任的是()。(2015年)

李小姐在成衣店加工连衣裙两条。取连衣裙时，李小姐因钱没带够，遂将手表留下，说过两天来交加工费一并取回。店主同意。成衣店对李小姐的手表享有()

联系实际，谈谈加强教师职业道德修养的意义与具体内容。

下列选项中，属于唐律“十恶”罪中有关违反封建伦理性犯罪的有()。

设循环队列为Q(1:m)，其初始状态为front=rear=m。经过一系列入队与退队运算后，front=20，rear=15。现要在该循环队列中寻找最小值的元素，最坏情况下需要比较的次数为

Manywhothinktheyhavefoodallergies(过敏)actuallydonot.Anewreport,commissionedbythefederalgovernment,findsthefiel