首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
为提高查找效率，对有65025个元素的有序顺序表建立索引顺序结构，在最好情况下查找到表中已有元素，需要执行( )次关键字比较。
为提高查找效率，对有65025个元素的有序顺序表建立索引顺序结构，在最好情况下查找到表中已有元素，需要执行( )次关键字比较。
admin
2021-08-17
76
问题
为提高查找效率，对有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
学硕统考专业
相关试题推荐
已知一组关键字为(26，36，41，38，44，15，68，12，6，5l，25)，用链地址法解决冲突。假设装填因子a=0．75，散列函数的形式为H(K)=KMODP，回答下列问题：构造散列函数。
设计一个判别表达式中左右括号是否配对出现的算法，采用()数据结构最佳。
假定某采用页式虚拟存储管理的计算机系统中，主存储器容量为1GB，被分为262144块物理块，物理块号为0，1，2，…，262143。某进程的地址空间占4页，逻辑页号为0，1，2，3，被分配到主存储器的第20，45，101，58号物理块中。回答：
已知AOE网中顶点v1，v2，v3，…v7分别表示7个时间，有向线段a1，a2，a3，…a10。分别表示10个活动，线段旁的数值表示每个活动花费的天数，如图10-1所示。请填写表10-1、表10-2两个表格，并用顶点序列表示出关键路径，给出关键活动。
某大学的阅览室共有300个座位，同学进入时必须先在管理处用学生证换取座位牌，若座位满了，同学就要在阅览室外等候。当有同学离开时，要到管理处用座位牌换回学生证。请画出流程图，试用一种类语言，利用信号量和P、V操作，描述同学进入和离开阅览室的过程。
主机H通过快速以太网连接到某网络中，H与服务器S使用TCP通信时，在H上捕获的其中2个IP分组如表7—3(a)所列： 请回答下列问题。 (1)表7—3(a)中的IP分组中，是应用层哪种协议?主机H和服务器的IP地址分别是多少? (2)假如
通道是一种IO设备，它用于传输数据的是()。
生成多项式为x3+x+1，则数据信息10101的CRC编码是()。
排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一趟排序。下列排序方法中，每一趟排序结束时都至少能够确定一个元素最终位置的方法是I．简单选择排序Ⅱ．希尔排序Ⅲ．快速排序Ⅳ．堆排序V．二路归并排序
[x]补=1．x1x2x4)，则当满足()时，x＞-1．／2成立。
随机试题
说“肺为娇脏”的主要依据是
临床上最可靠用于确诊二尖瓣狭窄的辅助检查是
为保证场(厂)内机动车辆的使用安全，使用单位应定期对其进行检查。定期检查包括日检、月检和年检。下列检查中，不属于月检内容的是()。
下列项目中，属于负债要素特点的有()。
由出票人签发，委托付款人在见票时或在指定日期无条件支付确定金额给收款人或持票的票据称为()。
下列各项对产品成本的分析方法中，属于构成比率分析的是()。
某跨国公司在A国的子公司成本控制的绩效非常突出，该跨国公司其他子公司纷纷向A国的子公司学习，这属于()。
阅读《天净沙·秋思》(选自部编版义务教育教科书《语文》七年级上册)原文，完成一篇教学设计。天净沙·秋思马致远枯藤老树昏鸦，小桥流水人家，古道西风瘦
单独使用支出变更政策调节内外均衡，在有些情况下可能导致内部均衡和外部均衡对政策要求的矛盾，这被称为()。
判定级数与级数的敛散性。
最新回复
(
0
)
