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

admin2019-12-10 27

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

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

(1)以太网采用了曼彻斯特编码，一个比特的数据需要两个信号来传输，那么为了达到100Mbps的数据传送速率，需要线路达到200Mbps的带宽。(2)以太网的最小帧长度是64字节，那么发送一个最小帧需要的时间T1=64×8／(100×106)，

真值0在原码、反码和补码机器数形式下()。

在集中式总线仲裁中，()方式响应时间最快。

若某浮点机基数为4，尾数采用补码表示，则该浮点机的规格化尾数形式为()。

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

某机字长32位，总线数据线宽度是16位，一个总线周期占用4个时钟周期，总线时钟频率为10MHz，则总线带宽是()。

若线性表最常用的运算是查找第i个元素及其前驱的值，则采用()存储方式节省时间。

四季豆中的毒性成分是________。

子宫肌瘤发生红色样变常见于

患者女，56岁，因“先天性心脏病、心房颤动、左侧肢体偏瘫”住院治疗。此脉搏属于()

期货市场上套期保值的效果主要是由()决定的。

某市科技开发公司2011年12月份取得技术开发收入120万元、与之相关的咨询收入20万元；另开发转让一专利技术并附样机一台，合同注明技术专利80万元，样机不含税价30万元，则下列说法正确的有()。

企业发行分期付息、一次还本债券时实际收到款项小于债券票面价值的差额采用实际利率法进行摊销，各期确认的实际利息费用会逐期增加。()

下列选项中属于控制小组进程技巧的是(　　)。

TheTheoryofContinentalDrifthashadalongandturbulenthistorysinceitwasfirstproposedbyAlfredWegenerin1910.(46)

RuiningtheRuinsAcidrain(酸雨)isnowafamiliarproblemintheindustrializedcountriesinEurope.Harmfulgasesareproduc

appear,competitive,corporate,corrupt,differ,ethics,interest,nation,present,sponsor,volunteer,co-workerAsurp

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

计算机408

学硕统考专业

(1)以太网采用了曼彻斯特编码，一个比特的数据需要两个信号来传输，那么为了达到100Mbps的数据传送速率，需要线路达到200Mbps的带宽。(2)以太网的最小帧长度是64字节，那么发送一个最小帧需要的时间T1=64×8／(100×106)，

真值0在原码、反码和补码机器数形式下()。

在集中式总线仲裁中，()方式响应时间最快。

若某浮点机基数为4，尾数采用补码表示，则该浮点机的规格化尾数形式为()。

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

某机字长32位，总线数据线宽度是16位，一个总线周期占用4个时钟周期，总线时钟频率为10MHz，则总线带宽是()。

若线性表最常用的运算是查找第i个元素及其前驱的值，则采用()存储方式节省时间。

四季豆中的毒性成分是________。

子宫肌瘤发生红色样变常见于

患者女，56岁，因“先天性心脏病、心房颤动、左侧肢体偏瘫”住院治疗。此脉搏属于()

期货市场上套期保值的效果主要是由()决定的。

某市科技开发公司2011年12月份取得技术开发收入120万元、与之相关的咨询收入20万元；另开发转让一专利技术并附样机一台，合同注明技术专利80万元，样机不含税价30万元，则下列说法正确的有()。

企业发行分期付息、一次还本债券时实际收到款项小于债券票面价值的差额采用实际利率法进行摊销，各期确认的实际利息费用会逐期增加。()

下列选项中属于控制小组进程技巧的是( )。

TheTheoryofContinentalDrifthashadalongandturbulenthistorysinceitwasfirstproposedbyAlfredWegenerin1910.(46)

RuiningtheRuinsAcidrain(酸雨)isnowafamiliarproblemintheindustrializedcountriesinEurope.Harmfulgasesareproduc

appear,competitive,corporate,corrupt,differ,ethics,interest,nation,present,sponsor,volunteer,co-workerAsurp

　　患者女，56岁，因“先天性心脏病、心房颤动、左侧肢体偏瘫”住院治疗。此脉搏属于()

下列选项中属于控制小组进程技巧的是(　　)。