设有序线性表的长度为n，则在有序线性表中进行二分查找，最坏情况下的比较次数为( )。

admin2022-09-09 71

问题设有序线性表的长度为n，则在有序线性表中进行二分查找，最坏情况下的比较次数为( )。

选项 A、n(n-1)／2
B、n
C、nlog₂n
D、log₂n

答案D

解析有序线性表的长度为n，设被查找元素为z，则二分查找的方法如下：将x与线性表的中间项比较，中间项的值等于x，则说明已查到，查找结束；若x小于中间项的值，则在线性表的前半部分(中间项以前的部分)以相同的方法进行查找；若x大于中间项的值，则在线性表的后半部分(中间项以后的部分)以相同的方法进行查找。这个过程一直进行到查找成功或子表长度为0(说明线性表中没有这个元素)为止。对于长度为n的有序线性表，在最坏情况下，二分查找只需要比较log₂n次。本题选择D选项。

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

本试题收录于：二级Python题库NCRE全国计算机二级分类

二级Python

NCRE全国计算机二级

相关试题推荐

随机试题

最新回复(0)

设有序线性表的长度为n，则在有序线性表中进行二分查找，最坏情况下的比较次数为( )。

二级Python

NCRE全国计算机二级

使用如下数据表：学生．DBF：学号(C，8)，姓名(C，6)，性别(C，2)，出生日期(D)选课．DBF：学号(C，8)，课程号(C，3)，成绩(N，5，1)假定学号的第3、4位为专业代码，要计算各专业学生选修课程号为“101”课程的

下面程序的运行结果是：SETTALKOFFn=1proc1(n)?n+2PROCEDUREproc1PARAMETERSnFORk=2TO4n=n+k

有以下程序：INPUTTOAS=0IFA=10S=1ENDIFS=2?S假定从键盘输入的A值是数值型，则程序的运行结果是

下面的程序的功能是将11到2011之间的素数插入数据库prime，程序中的错误语句是CREATETABLEprime(datf)n=11DOWHILEn

假设职员表已在当前工作区打开，其当前记录的“姓名”字段值为“李彤”(C型字段)。在命令窗口输入并执行如下命令：姓名=姓名-’’出勤’’?姓名屏幕上会显示

设数据库表中有一个C型字段NAME。打开表文件后，要把内存变量NAME的字符串内容输入到当前记录的NAME字段，应当使用命令

下列队列的描述中，正确的是()。

(1)打开“学生管理”数据库，并从中永久删除“学生”表。(2)建立一个自由表“教师”，表结构如下：编号字符型(8)姓名字符型(10)性别字符型(2)职称字符型(8)(3)利用查询设

软件生命周期可分为定义阶段、开发阶段和维护阶段，下面不属于开发阶段任务的是

下列不属于销售与收款业务会计制度设计的目标的是()

贮脂细胞存在于肝血窦内。()

下述哪种情况下肾血流量最多

A．极化B．去极化C．复极化D．电紧张性扩布E．“全或无”现象向正常安静时膜内所处的负值恢复，称作

甲欠乙债款5万久拖不还，乙为了逼甲还债把甲锁在自家地窖3个月，甲称无钱可还，乙很恼火把甲打成重伤，乙的行为构成：()

我们平常都用微波炉加热食物，以下对微波炉加热食物的描述准确的是()。

脱逃罪的主体有()。

Whendidthefilmstart?

A.necessityB.hangingonC.periodD.improvingE.haltedF.botheredG.reasons

Somedayastrangerwillreadyoure-mailwithoutyourpermissionorscanthewebsitesyou’vevisited.Orperhapssomeonewillca