首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
为提高查找效率,对有65025个元素的有序顺序表建立索引顺序结构,在最好情况下查找到表中已有元素,需要执行( )次关键字比较。
为提高查找效率,对有65025个元素的有序顺序表建立索引顺序结构,在最好情况下查找到表中已有元素,需要执行( )次关键字比较。
admin
2021-08-17
45
问题
为提高查找效率,对有65025个元素的有序顺序表建立索引顺序结构,在最好情况下查找到表中已有元素,需要执行( )次关键字比较。
选项
A、10
B、14
C、20
D、21
答案
B
解析
首先需要知道折半查找成功的平均查找长度为log
2
(n+1)-1。 为使查找效率最高,可对有65 025个元素的有序顺序表分块,每块有
=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/YH3i777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
一个系统具有150个存储单元,在T0时刻系统按下表所示分配给3个进程。对下列请求应用银行家算法分别分析判定是否安全?(1)第4个进程P4到达,最大需求60个存储单元,当前请求:分配25个单元。(2)第4个进程P4到达,最大需求50个存储单元,当前请
由于CPU内部的操作速度较快,而CPU访问一次主存所花的时间较长,因此机器周期通常用()来规定。
设主存容量1MB,有16KB直接相联映像的Cache,假定该Cache的块为8个32位的字。解答下列问题:(1)写出Cache的地址格式;(2)写出主存的地址格式;(3)块表的容量有多大;(4)主存地址为DE8F8H的单元在Ca
某一个磁盘共有16个盘面,每个盘面上从外到内共有30000个磁道(或称30000个柱面),每个磁道有250个扇区。假定存储信息以一个扇区作为一个存储块,盘面号(磁头号)、磁道号和扇区号均从0开始编号,那么,盘块号1002578对应的盘面号、磁道号和扇区号是
主机H通过快速以太网连接到某网络中,H与服务器S使用TCP通信时,在H上捕获的其中2个IP分组如表7—3(a)所列: 请回答下列问题。 (1)表7—3(a)中的IP分组中,是应用层哪种协议?主机H和服务器的IP地址分别是多少? (2)假如
对于设计实时操作系统,不属于其设计目标的是()。
假设5个进程P0、P1、P2、P3、P4共享三类资源R1、R2、R3,这些资源总数分别为18、6、22。T0时刻的资源分配情况如下表所示,此时存在的一个安全序列是
用户程序发出磁盘I/O请求后,系统的处理流程是:用户程序→系统调用处理程序→设备驱动程序→中断处理程序。其中,计算数据所在磁盘的柱面号、磁头号、扇区号的程序是
假设一个主频为1GHz、CPI为5的CPU需要从某个成块传送的I/O设备读取1000B的数据到主存缓冲区中,该I/O设备一旦启动即按50KB/s的数据传输率向主机传送1000B数据,每个字节的读取、处理并存入内存缓冲区需要1000个时钟周期,则以下4种
随机试题
金属表面与周围介质发生化学作用而引起的破坏称为表面腐蚀。()
A.精囊B.前列腺C.睾丸D.附睾E.阴茎海绵体属于输精管道的是【】
男性患者,18岁,着凉后出现发热,咳嗽,咳黄痰,未及时治疗,1d前出现高热,咳铁锈色痰。该患者的诊断最可能为
稳定型心绞痛发作时的首选药是
患者女性,50岁,心慌气短10余年,2日前突然咯血,呈鲜红色混有泡沫,既往有关节肿痛病史。体检:面部轻度发绀,心率86次/分,二尖瓣区闻及舒张期隆隆样杂音。心电图提示“P”波呈双峰状。应首先考虑的疾病是
在以下关于信号和信息关系的说法中,正确的是()。
下列关于施工机械安拆费及场外运费的表述中,正确的有()。
在代理的种类中属于全权代理,代理人原则上应代理被代理人的有关财产方面的一切民事法律行为和其他允许代理的行为是()。
按照《个人外汇管理办法》,对经常项目个人外汇管理描述错误的是()。
许多国际政治和经济观察家曾_______地认为,非洲所拥有的大量自然资源,必将促使这块热带大陆在21世纪实现经济起飞,最终保证其繁荣和稳定。然而在雷诺看来,这些天赐之物却_______了一场“丰饶的动乱”,并最终成为这些绵延不休的战火背后的助燃剂。
最新回复
(
0
)