为提高查找效率，对有65025个元素的有序顺序表建立索引顺序结构，在最好情况下查找到表中已有元素，需要执行( )次关键字比较。

admin2021-08-17 64

问题为提高查找效率，对有65025个元素的有序顺序表建立索引顺序结构，在最好情况下查找到表中已有元素，需要执行( )次关键字比较。

选项 A、10
B、14
C、20
D、21

答案B

解析首先需要知道折半查找成功的平均查找长度为log₂(n+1)-1。为使查找效率最高，可对有65 025个元素的有序顺序表分块，每块有

=255个元素。为每一块建立一个索引项，索引表共255个索引项。若对索引表和每一块都采用折半查找，则查找效率最高，计算可得 ASL_{IndexSeqSearch}=ASL_Index+ASL_Block=log₂(255+1)一1+log₂(255+1)一1=14
下面补充一些关于折半查找的概念。
补充(1)：折半查找的时间复杂度为O(log₂n)。
补充(2)：折半查找是基于随机存储方式的算法，必须用顺序表而不能用链表。
补充(3)：对于折半查找，假设h表示判定树的高度，如果有n个元素，则判定树的高度为 h=[log₂(n+1)]或者h=[log₂(n+1)]+1

转载请注明原文地址:https://kaotiyun.com/show/YH3i777K

本试题收录于：计算机408题库学硕统考专业分类

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

为提高查找效率，对有65025个元素的有序顺序表建立索引顺序结构，在最好情况下查找到表中已有元素，需要执行( )次关键字比较。

计算机408

学硕统考专业

MS-DOS中的文件物理结构采用()。

某指令流水线如下图所示，共分4个过程段：IF(取指)、ID(译码)、EX(执行)、WB(写回)，它们执行所需时间分别为80ns、100ns、60ns、90ns。试回答。若四个过程段的执行所需时间都为85ns，则加速比又为多少?

下列关于客户／服务器模型的描述中，错误的是()。　Ⅰ客户端和服务器必须都事先知道对方的地址，以提供请求和服务　ⅡHTTP基于客户／服务器模型，客户端和服务器端的默认端口号都是80Ⅲ浏览器显示的内容来自服务器

已知二叉树采用二叉链表方式存放，要求返回二叉树T的后序序列中的第一个结点的指针，是否可不用递归，且不用栈来完成?请简述原因。

下列选项中，不能改善磁盘设备I／0性能的是

某磁盘的转速为10000转／分，平均寻道时间是6ms，磁盘传输速率是20MB／s，磁盘控制器延迟为0．2ms，渎取一个4KB的扇区所需的平均时间约为

[x]补=1．x1x2)x3x4，则当满足()时，x>一1／2成立。

女性，52岁，胆囊切除术后4天，病人突然出现体温升高39℃，呼吸困难，听诊肺部呼吸音减弱，有湿啰音。应考虑病人出现了（）

A．收缩压≥140mmHg，舒张压＜90mmHgB．收缩压≥160mmHg，舒张压＜90mmHgC．收缩压140～159mmHg，舒张压90～99mmHgD．收缩压160～179mmHg，舒张压100～109mmHgE．收缩压≥180mmHg，舒张

A、间二硝基苯试剂反应B、三氯化锑反应C、过碘酸-对硝基苯胺反应D、α-萘酚-浓硫酸反应E、三氯化铁反应作用于甾体母核的反应是（）

结构构件、装修、设备基本完好，成色略旧并有少量或微量损坏，基本能正常使用的房屋属于()

关于高强度螺栓连接质量验收的说法，正确的有()。

以下关于曲线段中桩桩距的描述，正确的是()。

不能用于数据表单元格导航的键是________。

Asthe2lstcenturybegins,anumberofleadersinpolitics,education,andotherprofessionsbelievethattheUnitedStatesmus

A=TheImperialPalaceB=TheTempleofHeavenC=PotalaPalaceD=JokhangTempleWhichpalaceortemple...isthespiritualc

A、Atapostoffice.B、Inaclassroom.C、Atanairport.D、Atabank.C

为提高查找效率，对有65025个元素的有序顺序表建立索引顺序结构，在最好情况下查找到表中已有元素，需要执行( )次关键字比较。

计算机408

学硕统考专业

MS-DOS中的文件物理结构采用()。

某指令流水线如下图所示，共分4个过程段：IF(取指)、ID(译码)、EX(执行)、WB(写回)，它们执行所需时间分别为80ns、100ns、60ns、90ns。试回答。若四个过程段的执行所需时间都为85ns，则加速比又为多少?

下列关于客户／服务器模型的描述中，错误的是()。 Ⅰ客户端和服务器必须都事先知道对方的地址，以提供请求和服务 ⅡHTTP基于客户／服务器模型，客户端和服务器端的默认端口号都是80Ⅲ浏览器显示的内容来自服务器

已知二叉树采用二叉链表方式存放，要求返回二叉树T的后序序列中的第一个结点的指针，是否可不用递归，且不用栈来完成?请简述原因。

下列选项中，不能改善磁盘设备I／0性能的是

某磁盘的转速为10000转／分，平均寻道时间是6ms，磁盘传输速率是20MB／s，磁盘控制器延迟为0．2ms，渎取一个4KB的扇区所需的平均时间约为

[x]补=1．x1x2)x3x4，则当满足()时，x>一1／2成立。

女性，52岁，胆囊切除术后4天，病人突然出现体温升高39℃，呼吸困难，听诊肺部呼吸音减弱，有湿啰音。应考虑病人出现了（）

A．收缩压≥140mmHg，舒张压＜90mmHgB．收缩压≥160mmHg，舒张压＜90mmHgC．收缩压140～159mmHg，舒张压90～99mmHgD．收缩压160～179mmHg，舒张压100～109mmHgE．收缩压≥180mmHg，舒张

A、间二硝基苯试剂反应B、三氯化锑反应C、过碘酸-对硝基苯胺反应D、α-萘酚-浓硫酸反应E、三氯化铁反应作用于甾体母核的反应是（）

结构构件、装修、设备基本完好，成色略旧并有少量或微量损坏，基本能正常使用的房屋属于()

关于高强度螺栓连接质量验收的说法，正确的有()。

以下关于曲线段中桩桩距的描述，正确的是()。

不能用于数据表单元格导航的键是________。

Asthe2lstcenturybegins,anumberofleadersinpolitics,education,andotherprofessionsbelievethattheUnitedStatesmus

A=TheImperialPalaceB=TheTempleofHeavenC=PotalaPalaceD=JokhangTempleWhichpalaceortemple...isthespiritualc

A、Atapostoffice.B、Inaclassroom.C、Atanairport.D、Atabank.C

下列关于客户／服务器模型的描述中，错误的是()。　Ⅰ客户端和服务器必须都事先知道对方的地址，以提供请求和服务　ⅡHTTP基于客户／服务器模型，客户端和服务器端的默认端口号都是80Ⅲ浏览器显示的内容来自服务器　