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

admin2021-08-17 31

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

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

答案B

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

=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/YH3i777K

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

已知一组关键字为(26，36，41，38，44，15，68，12，6，5l，25)，用链地址法解决冲突。假设装填因子a=0．75，散列函数的形式为H(K)=KMODP，回答下列问题：画出散列表。

在一个顺序循环队列中删除元素时，首先需要()。

设计一个判别表达式中左右括号是否配对出现的算法，采用()数据结构最佳。

设森林F中有三棵树，第一、第二、第三棵树的结点个数分别为N1，N2和N3。与森林F对应的二叉树根结点的右子树上的结点个数是()。

以下关于校验码的叙述中，正确的是()。Ⅰ校验码的码距必须大于2Ⅱ校验码的码距越大检错纠错能力越强Ⅲ增加奇偶校验位的位数可以提高奇偶校验的正确性Ⅳ采用奇偶校验可检测出一位数据错误的位置并加以纠正Ⅴ采用

指令流水线将一条指令的执行过程分为四步，其中第1、2和4步的经过时间为△t，如下图5-1所示。若该流水线顺序执行，50条指令共用153At，并且不考虑相关问题，则该流水线的瓶颈第3步的时间是()。

某磁盘的转速为10000转／分，平均寻道时间是6ms，磁盘传输速率是20MB／s，磁盘控制器延迟为0．2ms，渎取一个4KB的扇区所需的平均时间约为

能增加细胞接触面积的是()

大黄素型和茜草素型主要区别于

患者，男性，36岁。平素体健。淋雨后发热，咳嗽2天，右上腹痛伴气急、恶心1天。为明确诊断，应进行的检查是

电力系统总备用容量由负荷备用、事故备用和检修备用组成，在水、火电联合运行系统中，它们是按何种原则进行分配的?

具有下列()项特征的土可初判为膨胀土。

下列因素中，可能引起白血病的因素是()。

借款人如果需要调整借款期限，应当具备以下条件()。

在宗法观念盛行的社会，姓氏也有贵贱之分。据《百家姓》中的排序“赵钱孙李”，“赵”姓并不是中国最大的姓氏，却排第一，由此可推断出《百家姓》最早可能出现在：

Thelifeoflivingindormitoryisquitedifferentfromthatoflivingathome.Howtokeepaharmoniousrelationshipwithroomm