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

admin2019-03-15 223

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

学硕统考专业

典型的西欧封建庄园对农民采用的剥削方式是()。

南北议和中，南方的总代表是()。

“二战”后主要资本主义国家经济恢复和发展的杠杆是()。①政府采取宏观调控政策②发展国家垄断资本主义③充分利用科技成果④加强国际经济联系

明清时期，我国边疆地区得到进一步开发的前提条件是()。

为了加强对地方的控制，唐太宗根据山川形势，把全国划分成10个()，经常派官员监察地方官吏。

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

一个使用选择性重传协议的数据链路层协议，如果采用了5位的帧序列号，那么可以选用的最大窗口是()。

在隧道内超车应注意安全。

下列对《战国策》解说正确的有()

男性，50岁，间断腹痛、腹泻20余年，加重3个月，大便4～5次/天。纳差，体重下降。化验便潜血(±～＋)，有脓细胞、红细胞。血Hb104g/L以下项目提示可能为器质性疾病，但不包括

支气管哮喘患者查体未闻及哮鸣音，表示病情控制良好。()

B公司与D公司就运输途中平板电脑的所有权产生了争议，D公司将争议诉诸中国某法院。根据我国有关法律适用的规定，关于平板电脑所有权的法律适用，下列选项正确的是？（2011年卷一第98题）

任何企业的年度财务会计报告均包括会计报表和会计报表附注。()

除基本工资以外，管理人员还可获得下列薪酬()。为了保证薪酬的公平性，人力资源部应进行()。

下列关于道德的论述不正确的是()。

如果想在运行表单时，向TEXT2中输入字符，回显字符显示的是“*’号，则可以在Forml的Init事件中加入语句（）。