首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
为提高查找效率，对有65025个元素的有序顺序表建立索引顺序结构，在最好情况下查找到表中已有元素，需要执行( )次关键字比较。
为提高查找效率，对有65025个元素的有序顺序表建立索引顺序结构，在最好情况下查找到表中已有元素，需要执行( )次关键字比较。
admin
2019-03-15
276
问题
为提高查找效率，对有65025个元素的有序顺序表建立索引顺序结构，在最好情况下查找到表中已有元素，需要执行( )次关键字比较。
选项
A、10
B、14
C、20
D、21
答案
B
解析
首先需要知道折半查找成功的平均查找长度为log
2
(n+1)-1。
为使查找效率最高，可对有65025个元素的有序顺序表分块，每块有
=255个元素。为每一块建立一个索引项，索引表共255个索引项。若对索引表和每一块都采用折半查找，则查找效率最高，计算可得
ASL
IndexSeqSearch
=ASL
Index
+ASL
Block
=log
2
(255+1)-1+log
2
(255+1)-1=14
下面补充一些关于折半查找的概念。
补充(1)：折半查找的时间复杂度为O(log
2
n)。
补充(2)：折半查找是基于随机存储方式的算法，必须用顺序表而不能用链表。
补充(3)：对于折半查找，假设h表示判定树的高度，如果有n个元素，则判定树的高度为
h=[log
2
(n+1)]或者h=[log
2
(n+1)]+1
转载请注明原文地址:https://kaotiyun.com/show/eBCi777K
本试题收录于：
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
南北议和中，南方的总代表是()。
下列内容，哪些与垄断组织出现有关?()①控制一个或几个部门商品的生产、价格和市场②促进了大工业的发展，在某种程度上适应了生产力发展的需要③干预、控制国家的政治和经济生活④积极向外扩张，从经济上瓜分世界
宋代至清代我国书籍印刷的主要方式是()
在明朝中叶，农业生产发生了一件非常重要的事件——()，对于当时的食物结构产生了重大的影响
关于清代我国疆域的叙述，下列()不正确。
编写一个算法，实现以较高的效率从有序顺序表A中删除其值在x和y之间x≤A[i]≤y的所有元素。
对下列4个序列用快速排序方法进行排序，以序列的第1个元素为基准进行划分。在第1趟划分过程中，元素移动次数最多的是()。
假设某计算机的存储系统由Cache和主存组成j某程序执行过程中访存1000次，其中访问Cache缺失(未命中)50次，则Cache的命中率是()。
多道程序设计是指()。
网络如图所示。链路旁边注明的数字代表链路的长度(假想单位)。试利用Dijkstra算法求出从结点A到所有其他结点的最短路由。
随机试题
Jackcan’tfindhisdictionary.Hemusthave______itintheclassroom.
精神分裂症最常见的幻觉形式是
S=(D1—D2)／H=K／H中，关于H的叙述，错误的是
关于灵敏度和鉴别阈的说法正确的是___________。
在城市规划区内进行建设需要申请用地的，建设单位在依法办理用地批准手续前，必须先取得该工程的()。
请简述导游人员提供心理服务的一般方法。
【2015．河南郑州】陶冶的主要方式有()。
学生的受教育权主要有()。
春节临近，区政府准备开展一次慰问基层工作人员的活动，领导让你组织，你怎么开展?
根据下列资料，回答下列问题。2014年1～6月份，我国民间固定资产投资138607亿元，同比增长20．1％，增速比1～5月份加快0．2个百分点。民间固定资产投资占全国固定资产投资的比重为65．1％，与1～5月份持平。分地区看，东部地区
最新回复
(
0
)
