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

admin2019-12-10 30

问题为提高查找效率，对有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₂(25 5+1)—1=14
下面补充一些关于折半查找的概念。
补充(1):折半查找的时间复杂度为O(log₂n)。
补充(2):折半查找是基于随机存储方式的算法，必须用顺序表而不能用链表。
补充(3):对于折半查找，假设h表示判定树的高度，如果有n个元素，则判定树的高度为
h=[log₂(n+1)]或者h=[log₂(n+1)]+1
例1：在具有15个记录的有序连续顺序文件上采用折半查找法查找一个文件中不存在的记录，需要进行( )次关键字的比较。
A．0 B．4
C．5
D．1 5
解析：此题可以利用补充(3)的判定树的高度来解答。由于n=15，可知判定树的高度为4。一棵高度为4，具有15个结点的二叉树为一棵满二叉树，所以查找一个不存在的结点需要比较4次。
例2：对一个长度为50的有序表进行折半查找，最多比较( )次就能查找出结果。
A．6
B.7
C.8
D.9
解析：与例1类似，可以得到判定树的高度为6，所以最多比较6次就能查找出结果。

转载请注明原文地址:https://kaotiyun.com/show/9s3i777K

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

设磁盘的扇区大小为4KB，磁盘转速为15000r／min，磁盘平均寻道时间为4ms，最大数据传输速率为40MB／s，磁盘控制器开销时问为1ms，计算读写一个扇区所需平均时间(不考虑I／O请求队列中的等待时间)。

IP数据报的报文格式如下图所示。在没有选项和填充的情况下，报头长度域的值为()。

高度为4的4阶B树最多可容纳()个关键字(根是第1层)。

某机字长32位，主存容量32MB，按字节编址；该机的Cache采用4路组相联映射方式，Cache容量为16KB，块长为4个字，试回答下列问题：(1)主存地址位数为多少?(2)画出主存地址格式示意图，注明各字段名称及位数。(3)设该Ca

在处理三种职权关系时，要充分发挥参谋职权的作用，目的在于（）

B细胞表面最重要的标志为(　　　)。

甲与乙、丙成立一合伙企业，并被推举为合伙事务执行人，乙、丙授权甲在3万元以内的开支及30万元内的业务可以自行决定。甲在任职期间内实施的下列行为哪些是法律禁止或无效的行为？

《中华人民共和国公司法》规定，公司的形式有()。

大体积混凝土养护，不仅要满足其强度增长需要，还应通过()控制，防止其开裂。

会计师事务所对首次公开发行股票的公司进行专项复核后，出具的专项复核报告至少应包括(　　)。

简述新课程倡导的学生观。

Windows　2000　IIS服务的安全认证不包含(54)。

以下程序运行后的输出结果是【　】。main(){intp=30;printf("%d\n",(p/3>0?p/10:p%3));}

Thepartoftheenvironmentalmovementthatdrawsmyfirm’sattentionisthedesignofcities，buildingsandproducts.Whenwede

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

计算机408

学硕统考专业

设磁盘的扇区大小为4KB，磁盘转速为15000r／min，磁盘平均寻道时间为4ms，最大数据传输速率为40MB／s，磁盘控制器开销时问为1ms，计算读写一个扇区所需平均时间(不考虑I／O请求队列中的等待时间)。

IP数据报的报文格式如下图所示。在没有选项和填充的情况下，报头长度域的值为()。

高度为4的4阶B树最多可容纳()个关键字(根是第1层)。

某机字长32位，主存容量32MB，按字节编址；该机的Cache采用4路组相联映射方式，Cache容量为16KB，块长为4个字，试回答下列问题：(1)主存地址位数为多少?(2)画出主存地址格式示意图，注明各字段名称及位数。(3)设该Ca

在处理三种职权关系时，要充分发挥参谋职权的作用，目的在于（）

B细胞表面最重要的标志为( )。

甲与乙、丙成立一合伙企业，并被推举为合伙事务执行人，乙、丙授权甲在3万元以内的开支及30万元内的业务可以自行决定。甲在任职期间内实施的下列行为哪些是法律禁止或无效的行为？

《中华人民共和国公司法》规定，公司的形式有()。

大体积混凝土养护，不仅要满足其强度增长需要，还应通过()控制，防止其开裂。

会计师事务所对首次公开发行股票的公司进行专项复核后，出具的专项复核报告至少应包括( )。

简述新课程倡导的学生观。

Windows 2000 IIS服务的安全认证不包含(54)。

以下程序运行后的输出结果是【 】。main(){intp=30;printf("%d\n",(p/3>0?p/10:p%3));}

Thepartoftheenvironmentalmovementthatdrawsmyfirm’sattentionisthedesignofcities，buildingsandproducts.Whenwede

B细胞表面最重要的标志为(　　　)。

会计师事务所对首次公开发行股票的公司进行专项复核后，出具的专项复核报告至少应包括(　　)。

Windows　2000　IIS服务的安全认证不包含(54)。

以下程序运行后的输出结果是【　】。main(){intp=30;printf("%d\n",(p/3>0?p/10:p%3));}