首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
为提高查找效率，对有65025个元素的有序顺序表建立索引顺序结构，在最好情况下查找到表中已有元素，需要执行( )次关键字比较。
为提高查找效率，对有65025个元素的有序顺序表建立索引顺序结构，在最好情况下查找到表中已有元素，需要执行( )次关键字比较。
admin
2019-12-10
24
问题
为提高查找效率，对有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
(25 5+1)—1=14
下面补充一些关于折半查找的概念。
补充(1):折半查找的时间复杂度为O(log
2
n)。
补充(2):折半查找是基于随机存储方式的算法，必须用顺序表而不能用链表。
补充(3):对于折半查找，假设h表示判定树的高度，如果有n个元素，则判定树的高度为
h=[log
2
(n+1)]或者h=[log
2
(n+1)]+1
例1：在具有15个记录的有序连续顺序文件上采用折半查找法查找一个文件中不存在的记录，需要进行( )次关键字的比较。
A．0 B．4
C．5
D．1 5
解析：此题可以利用补充(3)的判定树的高度来解答。由于n=15，可知判定树的高度为4。一棵高度为4，具有15个结点的二叉树为一棵满二叉树，所以查找一个不存在的结点需要比较4次。
例2：对一个长度为50的有序表进行折半查找，最多比较( )次就能查找出结果。
A．6
B.7
C.8
D.9
解析：与例1类似，可以得到判定树的高度为6，所以最多比较6次就能查找出结果。
转载请注明原文地址:https://jikaoti.com/ti/HZDjFFFM
本试题收录于：
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
隋唐五代时期是中国古代商品经济发展史上的一个重要阶段，种类多，交换规模大，交换方式多。试回答问题：下列关于隋唐钱币的表述，不正确的是()
(1)以太网采用了曼彻斯特编码，一个比特的数据需要两个信号来传输，那么为了达到100Mbps的数据传送速率，需要线路达到200Mbps的带宽。(2)以太网的最小帧长度是64字节，那么发送一个最小帧需要的时间T1=64×8／(100×106)，
在一个8级中断的系统中，硬件中断响应从高到低的优先顺序是1→2→3→4→5→6→7→8，通过中断屏蔽技术，将中断处理优先顺序设置为1→3→5→7→2→4→6→8，如果CPU在执行一个应用程序时有5、6、7、8级的四个中断同时到达，CPU在按优先顺序处理到第
什么是域名解析?域名解析中采取了什么措施提高效率?对同一个域名向DNS服务器发出多次的DNS请求报文后，得到IP地址都不一样，可能吗?为什么?
Demandpaging算法是paging算法在虚拟存储空间管理的扩展。其主要的改进是：仅当需要访问某页面时，如果它不在内存，把它调入内存。按照这个思路，将segmentation算法(段式存储管理算法)扩展到虚拟存储空间管理，也可以产生类似的算法，不妨
某计算机采用微程序控制方式，微指令字长32位，采用字段直接编码的控制方式，共有55个微命令，可分为6个互斥组，分别包含1、3、7、8、12、24个微命令。另外，该机共有5个可判定的外部条件，采用断定方式形成后续微指令地址。(1)设计该机微指令的格式，
图的D搜索类似于BFS，不同之处在于使用栈代替BFS中的队列，入／出队列的操作作为入／出栈的操作，即当一个顶点的所有邻接结点被搜索后，下一个搜索出发点应该是最近入栈(栈顶)的顶点。(1)用邻接表作为存储结构，写一个D搜索算法；(2)用D搜索方法
著名的网络OSI七层模型是由()组织提出来的。
就绪队列中有n个进程等待使用一个CPU，那么，如果采用不同的调用算法，就有()种调度顺序。
随机试题
人民当家作主是社会主义民主政治的（）
在心肺脑复苏的后期复苏阶段，有关药物治疗的描述中，错误的是
下列不属于医疗辅助部门的是()。
某歌厅购买了若干正版卡拉OK光盘后，未经任何人的许可，直接将该光盘用于其经营活动。对该歌厅的行为应如何定性?()
根据建造师注册管理的规定，应批准()人员的注册申请。
多式联运合同区别于其他合同的最显著特征是()。
流程性材料通常是有形产品，其量具有()的特性。
血液中红细胞数与()量低于正常值，称为贫血。
夏天从冰箱里取出一瓶啤酒，发现啤酒瓶外面“出汗”。对这种现象正确的解释是()。
下列哪个不是古代帝王用于自称的称谓?()
最新回复
(
0
)
