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

admin2021-08-17 60

问题为提高查找效率，对有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://www.kaotiyun.com/show/YH3i777K

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

在OSI参考模型中，同一结点内相邻层之间通过()来进行通信。

一个网络的拓扑结构如图9—2所示。链路旁边注明的数字代表链路的长度(假想单位)。试利用链路状态路由算法求出从结点A到所有其他结点的最短路由，给出计算过程，最短路径图以及下一跳路由。

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

计算机在进行浮点数的相加(减)运算之前先进行对阶操作，若x的阶码大于y的阶码，则应将()。

文件共享可以有多种方式，下列不是文件共享的方式是()。

现代操作系统中，一方面进程具有独立性，另一方面进程之间具有相互制约性，对于任意两个并发的进程，它们的关系是()。

若用户进程访问内存时产生缺页，则下列选项中，操作系统可能执行的操作是Ⅰ．处理越界错Ⅱ．置换页Ⅲ．分配内存

有一结点的关键字序列F={129，72，180，105，147，96，45，69}，散列函数为H(k)=kmod11，其中k为关键字，散列地址空间为0～10。要求：画出相应的散列表。当发生冲突时，以链地址法解决。计算在等概率情况下，查找成功和查找不成功

在一个段式存储管理系统中，逻辑地址为32位，其中高16位为段号，低16位为段内偏移，以下是段表(其中的数据均为十六进制，如表7-1所示)。以下是代码段的内容：试问：语句“movr2,4+(sp)”的功能是什么?

下列不是胃食管反流病诱发因素的是

技术开发合同的成果归属原则是，有约定的按约定，没有约定的应归属于______。

预防阵发性夜间呼吸困难发作，最主要的护理措施是

下列合同中，属于可撤销合同的有()。

注册会计师在审计甲股份有限公司2011年度财务报表时，知悉该公司可能存在重大舞弊行为，则应采取的措施是()。

设y=f(x)由cos(xy)+lny-x=1确定，则=()．

RecentsurveysshowthatJapaneseyouthhavebecomea"MeGeneration"thatrejectstraditionalvalues."Around1980manyJap

Abodyweighs______fromthesurfaceoftheearth.

A、5:20B、5:00C、5.35D、5:45CW:Whattimedidthefilmstartyesterday?M:Itwassupposedtostartataquarterpast5,butit

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

计算机408

学硕统考专业

在OSI参考模型中，同一结点内相邻层之间通过()来进行通信。

一个网络的拓扑结构如图9—2所示。链路旁边注明的数字代表链路的长度(假想单位)。试利用链路状态路由算法求出从结点A到所有其他结点的最短路由，给出计算过程，最短路径图以及下一跳路由。

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

计算机在进行浮点数的相加(减)运算之前先进行对阶操作，若x的阶码大于y的阶码，则应将()。

文件共享可以有多种方式，下列不是文件共享的方式是()。

现代操作系统中，一方面进程具有独立性，另一方面进程之间具有相互制约性，对于任意两个并发的进程，它们的关系是()。

若用户进程访问内存时产生缺页，则下列选项中，操作系统可能执行的操作是Ⅰ．处理越界错Ⅱ．置换页Ⅲ．分配内存

在一个段式存储管理系统中，逻辑地址为32位，其中高16位为段号，低16位为段内偏移，以下是段表(其中的数据均为十六进制，如表7-1所示)。以下是代码段的内容：试问：语句“movr2,4+(sp)”的功能是什么?

下列不是胃食管反流病诱发因素的是

技术开发合同的成果归属原则是，有约定的按约定，没有约定的应归属于______。

预防阵发性夜间呼吸困难发作，最主要的护理措施是

下列合同中，属于可撤销合同的有()。

注册会计师在审计甲股份有限公司2011年度财务报表时，知悉该公司可能存在重大舞弊行为，则应采取的措施是()。

设y=f(x)由cos(xy)+lny-x=1确定，则=()．

RecentsurveysshowthatJapaneseyouthhavebecomea"MeGeneration"thatrejectstraditionalvalues."Around1980manyJap

Abodyweighs______fromthesurfaceoftheearth.

A、5:20B、5:00C、5.35D、5:45CW:Whattimedidthefilmstartyesterday?M:Itwassupposedtostartataquarterpast5,butit

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