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

admin2021-08-17 74

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

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

已知某CPU有16根地址线、8根数据线，并用阼为访存控制信号(低电平有效)。现有下列存储芯片：1K×4位ROM、2K×4位ROM、4K×8位ROM、4K×8位RAM、8K×4位RAM、8K×8位RAM和非门、与非门、或非门若干，如下图所示。试对该机存储

下图所示为一个局域网的连接图，每个计算机的IP地址和物理地址如下表所示：假设该局域网采用了以太网，需要达到100Mbps的数据传送率，那么线路的带宽最小为多少?

某计算机系统中，各个主设备得到总线使用权的机会基本相等，则该系统采用的总线判优控制方式一定不是()。

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

UNIX文件系统中，索引节点(i-node)其本质是()。

一个快速以太网交换机的端口速率为100Mbps，若该端口可以支持全双工传输数据，那么该端口实际的传输带宽是()。

一棵二叉树的繁茂度定义为R层结点数的最大值与树的高度的乘积。编写一个算法求二叉树的繁茂度。

通过对方格中每个点设置相应的CMYK值就可以将方格涂上相应的颜色。以下3个程序段都可实现对一个8×8的方格涂上黄色的功能。假设Cache的数据区大小为512B，采用直接映射，块大小为32B，存储器按字节编址，sizeof(int)=4

指令流水线中，不同的指令在指令流水的不同功能段中可以()。

()是由一些液压元件组成并能完成某项特定功能的典型油路结构。

下列哪项不属于晕针的表现

慢性支气管炎患者，今晨突感左上胸短暂刺痛，逐渐感呼吸困难，不能平卧，心率120次／分，律不齐，左肺呼吸音明显减弱，考虑出现了

下列哪项不属于气管内插管用具

关于流脑的叙述，错误的是

异常支气管肺泡呼吸音见于下列情况，除外

弹琴式持针法适用于针刺马

银行需要研究的重点是()。