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

admin2021-08-17 29

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

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

下列是有关冯.诺依曼结构计算机中指令和数据存放位置的叙述，其中正确的是()。

在下面的应用中，通常使用栈的是()。　Ⅰ递归调用Ⅱ括号匹配Ⅲ表达式求值

设单链表的表头指针为h，链表中结点构造为(data，next)，其中data域为字符型，链表长度为n。编写算法判断该链表的n个字符是否中心对称。(例如xyx,xyyx都是中心对称。)

流水计算机中，下列语句发生的数据相关类型是()。ADDR1，R2，R3；(R2)+(R3)→R1ADDR4，R1，R5；(R1)+(R5)→R4

下列给出的指令系统特点中，有利于实现指令流水线的是____。I．指令格式规整且长度一致Ⅱ．指令和数据按边界对齐存放Ⅲ．只有Load／Store指令才能对操作数进行存储访问

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

世界贸易组织成立于()

主动脉关闭不全的病因有

霍乱的病理改变主要由哪种因素引起

基准地价修正因素应主要选择影响宗地地价的()。

在职业活动中，诚信之“信”的含义是()。

国家教委强调指出，高等教育进一步改革发展，要解决好“全面提高办学的质量和效益”这一重大问题。请根据你所了解的情况和工作实践，谈谈教育厅应如何抓好高校教育质量的工作。

MarthaGraham’sterritoryofinnumerabledancesandaself-sufficientdancetechniqueisavastbutclosedterritory,sincetoc

Thevalueofchildhoodiseasilyblurredintoday’sworld.Considersomerecentdevelopments:thechild-murderersintheJonesbo

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

计算机408

学硕统考专业

下列是有关冯.诺依曼结构计算机中指令和数据存放位置的叙述，其中正确的是()。

在下面的应用中，通常使用栈的是()。 Ⅰ递归调用Ⅱ括号匹配Ⅲ表达式求值

设单链表的表头指针为h，链表中结点构造为(data，next)，其中data域为字符型，链表长度为n。编写算法判断该链表的n个字符是否中心对称。(例如xyx,xyyx都是中心对称。)

流水计算机中，下列语句发生的数据相关类型是()。ADDR1，R2，R3；(R2)+(R3)→R1ADDR4，R1，R5；(R1)+(R5)→R4

下列给出的指令系统特点中，有利于实现指令流水线的是____。I．指令格式规整且长度一致Ⅱ．指令和数据按边界对齐存放Ⅲ．只有Load／Store指令才能对操作数进行存储访问

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

世界贸易组织成立于()

主动脉关闭不全的病因有

霍乱的病理改变主要由哪种因素引起

基准地价修正因素应主要选择影响宗地地价的()。

在职业活动中，诚信之“信”的含义是()。

国家教委强调指出，高等教育进一步改革发展，要解决好“全面提高办学的质量和效益”这一重大问题。请根据你所了解的情况和工作实践，谈谈教育厅应如何抓好高校教育质量的工作。

MarthaGraham’sterritoryofinnumerabledancesandaself-sufficientdancetechniqueisavastbutclosedterritory,sincetoc

Thevalueofchildhoodiseasilyblurredintoday’sworld.Considersomerecentdevelopments:thechild-murderersintheJonesbo

在下面的应用中，通常使用栈的是()。　Ⅰ递归调用Ⅱ括号匹配Ⅲ表达式求值