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

admin2021-08-17 45

问题为提高查找效率，对有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

学硕统考专业

由于CPU内部的操作速度较快，而CPU访问一次主存所花的时间较长，因此机器周期通常用()来规定。

设主存容量1MB，有16KB直接相联映像的Cache，假定该Cache的块为8个32位的字。解答下列问题：(1)写出Cache的地址格式；(2)写出主存的地址格式；(3)块表的容量有多大；(4)主存地址为DE8F8H的单元在Ca

对于设计实时操作系统，不属于其设计目标的是()。

假设5个进程P0、P1、P2、P3、P4共享三类资源R1、R2、R3，这些资源总数分别为18、6、22。T0时刻的资源分配情况如下表所示，此时存在的一个安全序列是

用户程序发出磁盘I／O请求后，系统的处理流程是：用户程序→系统调用处理程序→设备驱动程序→中断处理程序。其中，计算数据所在磁盘的柱面号、磁头号、扇区号的程序是

金属表面与周围介质发生化学作用而引起的破坏称为表面腐蚀。()

A.精囊B.前列腺C.睾丸D.附睾E.阴茎海绵体属于输精管道的是【】

男性患者，18岁，着凉后出现发热，咳嗽，咳黄痰，未及时治疗，1d前出现高热，咳铁锈色痰。该患者的诊断最可能为

稳定型心绞痛发作时的首选药是

患者女性，50岁，心慌气短10余年，2日前突然咯血，呈鲜红色混有泡沫，既往有关节肿痛病史。体检：面部轻度发绀，心率86次／分，二尖瓣区闻及舒张期隆隆样杂音。心电图提示“P”波呈双峰状。应首先考虑的疾病是

在以下关于信号和信息关系的说法中，正确的是()。

下列关于施工机械安拆费及场外运费的表述中，正确的有()。

在代理的种类中属于全权代理，代理人原则上应代理被代理人的有关财产方面的一切民事法律行为和其他允许代理的行为是()。

按照《个人外汇管理办法》，对经常项目个人外汇管理描述错误的是()。

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

计算机408

学硕统考专业

由于CPU内部的操作速度较快，而CPU访问一次主存所花的时间较长，因此机器周期通常用()来规定。

设主存容量1MB，有16KB直接相联映像的Cache，假定该Cache的块为8个32位的字。解答下列问题：(1)写出Cache的地址格式；(2)写出主存的地址格式；(3)块表的容量有多大；(4)主存地址为DE8F8H的单元在Ca

主机H通过快速以太网连接到某网络中，H与服务器S使用TCP通信时，在H上捕获的其中2个IP分组如表7—3(a)所列： 请回答下列问题。 (1)表7—3(a)中的IP分组中，是应用层哪种协议?主机H和服务器的IP地址分别是多少? (2)假如

对于设计实时操作系统，不属于其设计目标的是()。

假设5个进程P0、P1、P2、P3、P4共享三类资源R1、R2、R3，这些资源总数分别为18、6、22。T0时刻的资源分配情况如下表所示，此时存在的一个安全序列是

用户程序发出磁盘I／O请求后，系统的处理流程是：用户程序→系统调用处理程序→设备驱动程序→中断处理程序。其中，计算数据所在磁盘的柱面号、磁头号、扇区号的程序是

金属表面与周围介质发生化学作用而引起的破坏称为表面腐蚀。()

A.精囊B.前列腺C.睾丸D.附睾E.阴茎海绵体属于输精管道的是【】

男性患者，18岁，着凉后出现发热，咳嗽，咳黄痰，未及时治疗，1d前出现高热，咳铁锈色痰。该患者的诊断最可能为

稳定型心绞痛发作时的首选药是

患者女性，50岁，心慌气短10余年，2日前突然咯血，呈鲜红色混有泡沫，既往有关节肿痛病史。体检：面部轻度发绀，心率86次／分，二尖瓣区闻及舒张期隆隆样杂音。心电图提示“P”波呈双峰状。应首先考虑的疾病是

在以下关于信号和信息关系的说法中，正确的是()。

下列关于施工机械安拆费及场外运费的表述中，正确的有()。

在代理的种类中属于全权代理，代理人原则上应代理被代理人的有关财产方面的一切民事法律行为和其他允许代理的行为是()。

按照《个人外汇管理办法》，对经常项目个人外汇管理描述错误的是()。