首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
为提高查找效率，对有65025个元素的有序顺序表建立索引顺序结构，在最好情况下查找到表中已有元素，需要执行( )次关键字比较。
为提高查找效率，对有65025个元素的有序顺序表建立索引顺序结构，在最好情况下查找到表中已有元素，需要执行( )次关键字比较。
admin
2021-08-17
37
问题
为提高查找效率，对有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
学硕统考专业
相关试题推荐
已知一个线性表为(38，25，74，63，52，48)，假定采用H(K)=Kmod7计算散列地址进行散列存储，若利用线性探测的开放定址法处理冲突，则在该散列表上进行查找的平均查找长度为()；若利用链地址法处理冲突，则在该散列上进行查找的平均查找长度
下列是有关冯.诺依曼结构计算机中指令和数据存放位置的叙述，其中正确的是()。
文件共享可以有多种方式，下列不是文件共享的方式是()。
假定某计算机的CPU主频为80MHz，CPI为4，并且平均每条指令访存1．5次，主存与cache之间交换的块大小为16B，Caehe的命中率为99％，存储器总线宽度为32位。请回答下列问题。为了提高性能，主存采用4体交叉存储模式，工作时每1／4个存储周
若用户进程访问内存时产生缺页，则下列选项中，操作系统可能执行的操作是Ⅰ．处理越界错Ⅱ．置换页Ⅲ．分配内存
一台模型机共有7条指令，主频25MHz，各指令的使用频率与CPI如表2-4所示。该模型机有8位和16位两种指令字长，采用2-4扩展操作码。8位字长指令为寄存器-寄存器(R-R)二地址类型，16位字长指令为寄存器-存储器(R—M)二地址变址寻址类型(-128
给定的有7个顶点v1，v2，…，v7的有向图的邻接矩阵如表5-1所示。若将图看成AOE网，列出其关键活动及相应的有向边＜i，i，w＞，i、i为顶点，w为权值，试问其关键路径的长度是多少?
某计算机的指令流水线由四个功能段组成，指令流经各功能段的时间(忽略各功能段之间的缓存时间)分别为90ns、80ns、70ns、和60ns，则该计算机的CPU时钟周期至少是_______。
“程序与进程”的类比最接近()。
随机试题
A．缺铁性贫血B．巨幼细胞性贫血C．自身免疫性溶血性贫血D．珠蛋白生成障碍性贫血男，22岁，贫血，黄疸，脾肿大。血红蛋白70g/L，白细胞5.5×109/L，网织红细胞计数0.09，Coombs试验阳性
血中铜减少及尿中铜上升时，可能患
以下关于性心理障碍描述正确的是
小脑扁桃体位置变异较大，可突入枕骨大孔，但不超过
A．手术切除B．挂线疗法C．注射硬化剂D．口服抗生素E．胶圈套扎术高位肛瘘主要的治疗方法是
病原与牛病毒性腹泻／黏膜病病毒的抗原性有交叉的疫病是
综合法制备注射用水的工艺流程正确的为
某500t的工程船舶在施工中发生意外伤亡事故，死亡2人，伤2人，直接经济损失200万元。经事故调查，认定为重大事故。问题：简述施工安全事故的处理程序。
对于行政机关作出的行政处罚，当事人要求听证的，应当在行政机关告知后()日内提出。
身份的特点有()。
最新回复
(
0
)
