首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
为提高查找效率,对有65025个元素的有序顺序表建立索引顺序结构,在最好情况下查找到表中已有元素,需要执行( )次关键字比较。
为提高查找效率,对有65025个元素的有序顺序表建立索引顺序结构,在最好情况下查找到表中已有元素,需要执行( )次关键字比较。
admin
2021-08-17
47
问题
为提高查找效率,对有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
学硕统考专业
相关试题推荐
下列只读存储器中,可编程且可以实现字擦除的是()。
由于CPU内部的操作速度较快,而CPU访问一次主存所花的时间较长,因此机器周期通常用()来规定。
图1-2是某存储芯片的引脚图,请回答:(1)这个存储芯片的类型(是RAM还是ROM)?这个存储芯片的容量?(2)若地址线增加一根,存储芯片的容量将变为多少?(3)这个芯片是否需要刷新?为什么?刷新和重写有什么区别?(
考虑有三个吸烟者进程和一个经销商进程的系统中,每个吸烟者连续不断地制作烟卷并将其做好的烟卷消费掉(即吸烟)。制烟和吸烟过程需要烟草、烟纸和火柴三种原料。这三个吸烟者自己分别掌握有烟草、烟纸和火柴中的一种。经销商能源源不断地提供上述三种原料,每次经销商会提供
设某多道程序系统中有用户使用的内存1000M,打印机1台。系统采用可变分区动态分配算法管理内存,而对打印机采用静态分配。假设输入输出操作时间忽略不计,采用最短剩余时间优先的进程调度算法,进程最短剩余时间相同时采用先来先服务的算法,进程调度时机选择在进程执
在文件的逻辑组织中,不属于记录文件的是()。
现有一种解决无向连通图的最小生成树的方法:将图中所有边按权重从大到小排序为(e1,e2,…,em);i=1;while(所剩边数≥顶点数){从图中删去ei;若图不再连通,则恢复ei;i++;
图6—5所示为一个局域网的连接图,每个计算机的IP地址和物理地址见表6—2。假设该局域网采用了以太网,需要达到100Mbit/s的数据传输率,那么线路的带宽最小为多少?如果信号在网络中的传播速度是200000km/s,那么该网络的最大长度应该为多少
一个系统具有150存储单元,在T0时刻系统按下表所示分配给3个进程。对下列请求应用银行家算法分别分析判定是否安全?(1)第四个进程P4到达,最大需求60个存储单元,当前请求分配25个单元。(2)第四个进程P4到达,最大需求50个存储单元,当
[x]补=1.x1x2)x3x4,则当满足()时,x>一1/2成立。
随机试题
西方资本主义民主政治的三大支柱有()
企业采取国际产品标准化策略的原因包括()
社会规律是通过人们的活动表现出来的,这表明社会规律不具有客观性,是可以被创造或消灭的。
患者,女,24岁。产后大出血,继则冷汗淋漓,甚则晕厥。其病机是()
A、润湿剂B、反絮凝剂C、絮凝剂D、助悬剂E、稳定剂混悬剂中使微粒Zeta电位增加的电解质是()。
空心砖是指孔洞率不小于10%的砖。()
下列场所中,应在疏散走道和主要疏散路径的地面上增设能保持视觉连续的疏散指示标志的是()。
甲乙两个国有企业作为发起人,准备设立一家股份有限公司。问:(1)发起人的人数是否符合公司法的法规?(2)这类公司应采用什么方式设立?(3)申请设立登记,应准备哪些必备文件?
海关总署或海关总署授权机构受理海关行政裁定。()
Weanticipate______thefirstphaseoftheprojectwilltakeapproximatelytwoweekstocomplete.
最新回复
(
0
)