首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
为提高查找效率,对有65025个元素的有序顺序表建立索引顺序结构,在最好情况下查找到表中已有元素,需要执行( )次关键字比较。
为提高查找效率,对有65025个元素的有序顺序表建立索引顺序结构,在最好情况下查找到表中已有元素,需要执行( )次关键字比较。
admin
2019-03-15
205
问题
为提高查找效率,对有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、1243B、4312C、2134D、3214D图的BFS遍历。D选项,首先访问结点3,与3邻接的结点4、2都未曾访问过,故3后面因该为2、4(或4、2),故D错。
假设某计算机的存储系统由Cache和主存组成j某程序执行过程中访存1000次,其中访问Cache缺失(未命中)50次,则Cache的命中率是()。
给定序列{3,5,7,9,11,13,15,17),(1)按表中元素的顺序依次插入一棵初始为空的二叉排序树,画出插入完成后的二叉排序树,并求在等概率情况下查找成功的平均查找长度。(2)按表中元素的顺序构造一棵平衡二叉树,并求其在等概率情
通过改变载波信号的相位值来表示数字信号1、0的方法是()。
设有一个由正整数组成的无序(后向)单链表,编写能够完成下列功能的算法:(1)找出最小值结点,且打印该数值。(2)若该数值为奇数,则将其与直接后继结点的数值交换。(3)若该数值为偶数,则将其直接后继结点删除。
随机试题
哮病的发生为痰伏于肺,其诱因是下列哪项因素
手、足三阳经在头部的分布规律是()
施工组织设计分类主要三种___________、___________和___________。
根据《风景名胜区条例》的规定,在风景名胜区内从事禁止范围以外的建设活动,未经风景名胜区管理机构审核的,对单位处()的罚款。
凡经过注册会计师审计的会计报表,必须将审计报告和财务会计报告一并报送有关方面。()
市场环境分析的SWOT、方法中,S、W、O、T分别代表()
在房地产市场状况分析中,需求分析主要包括()。
下列项目中,属于A公司合并范围的有()。
生活中,一个好的心态,可以使你乐观豁达;一个好的心态,可以使你战胜面临的苦难;一个好的心态,可以使你淡泊名利,过上真正快乐的生活。人类几千年的文明史告诉我们,积极的心态能帮助我们获取健康、幸福和财富。以上这段文字告诉我们()。
设则f(x,y)在(0,0)处()。
最新回复
(
0
)