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

admin2019-03-15 166

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

学硕统考专业

新文化运动兴起的标志是()。

在周初分封中，分封同姓诸侯国、异姓诸侯国，也分封圣王之后，下面属于圣王之后的封国为()。

下列长征事件的正确顺序是()。①四渡赤水②召开遵义会议③吴起镇会师④飞夺泸定桥

文艺复兴时期，古典文化成为人文艺术家乐于表现的题材。梵蒂冈宫系列壁画中，描绘古典哲学家聚集一堂的作品是()

简述第二次世界大战中各主要战场战略性转折的时间及其代表性战役。

1642年英国内战爆发后，议会民兵武装力量远超王党军队，海军也支持议会，许多港口处于议会控制下，但议会军在战场节节失利，原因是

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

给定页面请求序列RS=cadbebabcd，页框为4，起始为空，写出LRU页面置换过程。

响应外部中断的过程中，中断隐指令完成的操作，除保护断点外，还包括I．关中断Ⅱ．保存通用寄存器的内容Ⅲ．形成中断服务程序人口地址并送PC

（2017年聊城）（）是一种导致局部刺激的意识水平提高的知觉的选择性集中。

一些乡村在变为城镇的过程中，虽然面貌，但很多曾经让人留恋的东西却。人们或多或少有这样的：快速的、大规模的城镇化会不会使“乡愁”无处安放?填入画横线部分最恰当的一项是：

患者，男，45岁。头痛半年，CT检查如下图。该患者最有可能的诊断为

首选下列哪些检查检查后确诊后的最佳选择是

下列对缓控释制剂体内外相关性的叙述中不正确的是()

蜘蛛痣的特征应除外

韵母中的辅音是韵尾，所以说韵母中的韵尾一定是辅音。()

DBF:零件号C(2)，零件名称C(10)，单价N(10)，规格C(8)使用零件.DBF:项目号C(2)，零件号C(2)，数量Ⅰ项目.DBF:项目号C(2)，项目名称C(20)，项目负责人C(10)，电话C(20)查询与项目“s

Whatshouldbethebesttitleforthepassage?ShichahaiisoneoftheinBeijing.

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

计算机408

学硕统考专业

新文化运动兴起的标志是()。

在周初分封中，分封同姓诸侯国、异姓诸侯国，也分封圣王之后，下面属于圣王之后的封国为()。

下列长征事件的正确顺序是()。①四渡赤水②召开遵义会议③吴起镇会师④飞夺泸定桥

文艺复兴时期，古典文化成为人文艺术家乐于表现的题材。梵蒂冈宫系列壁画中，描绘古典哲学家聚集一堂的作品是()

简述第二次世界大战中各主要战场战略性转折的时间及其代表性战役。

1642年英国内战爆发后，议会民兵武装力量远超王党军队，海军也支持议会，许多港口处于议会控制下，但议会军在战场节节失利，原因是

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

给定页面请求序列RS=cadbebabcd，页框为4，起始为空，写出LRU页面置换过程。

响应外部中断的过程中，中断隐指令完成的操作，除保护断点外，还包括I．关中断Ⅱ．保存通用寄存器的内容Ⅲ．形成中断服务程序人口地址并送PC

（2017年聊城）（）是一种导致局部刺激的意识水平提高的知觉的选择性集中。

一些乡村在变为城镇的过程中，虽然面貌________，但很多曾经让人留恋的东西却________。人们或多或少有这样的________：快速的、大规模的城镇化会不会使“乡愁”无处安放?填入画横线部分最恰当的一项是：

患者，男，45岁。头痛半年，CT检查如下图。该患者最有可能的诊断为

首选下列哪些检查检查后确诊后的最佳选择是

下列对缓控释制剂体内外相关性的叙述中不正确的是()

蜘蛛痣的特征应除外

韵母中的辅音是韵尾，所以说韵母中的韵尾一定是辅音。()

DBF:零件号C(2)，零件名称C(10)，单价N(10)，规格C(8)使用零件.DBF:项目号C(2)，零件号C(2)，数量Ⅰ项目.DBF:项目号C(2)，项目名称C(20)，项目负责人C(10)，电话C(20)查询与项目“s

Whatshouldbethebesttitleforthepassage?______Shichahaiisoneofthe______inBeijing.

一些乡村在变为城镇的过程中，虽然面貌，但很多曾经让人留恋的东西却。人们或多或少有这样的：快速的、大规模的城镇化会不会使“乡愁”无处安放?填入画横线部分最恰当的一项是：

Whatshouldbethebesttitleforthepassage?ShichahaiisoneoftheinBeijing.