用递归算法实现n个不同元素的有序序列的折半查找，采用一个递归工作栈时，该栈的最小容量应为( )。

admin2019-12-10 37

问题用递归算法实现n个不同元素的有序序列的折半查找，采用一个递归工作栈时，该栈的最小容量应为( )。

选项 A、n
B、[n／2]
C、[log₂n]
D、[log₂n]+1

答案D

解析根据折半查找的过程，由于需要栈结构实现递归算法，栈的容量应该保证能存放查找失败时所有未完成运行的算法的活动记录。
第一次调用该算法时，栈中加入了一条查找记录，表示待查有序表中元素的个数为n；第二次调用时，无论是在前半区还是后半区查找，栈中又加入了一条查找记录，所确定的查找区间中的元素最多为n／2；第三次调用时，栈中又加入了一条查找记录，所确定的查找区间中的元素最多为n／4；依次类推，当所确定的查找区间中的元素为0时，递归调用该算法的次数为[log₂n]+1次，查找结束。
折半查找法在查找成功时和给定值进行比较的关键字个数至多是[log₂n]+1；在查找不成功时和给定值进行比较的关键字个数最多也不超过[log₂n]+1。

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

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

用递归算法实现n个不同元素的有序序列的折半查找，采用一个递归工作栈时，该栈的最小容量应为( )。

计算机408

学硕统考专业

操作系统为了管理文件，设计了文件控制块(FCB)，文件控制块的建立是()。

在因特网中，IP数据报的传输需要经由源主机和中途路由器到达目的主机，下面说法正确的是()。

一个栈的入栈序列是1，2，3，4，5，则栈的不可能的输出序列是()。

现有一个解决无向连通图的最小生成树的一种方法如下：将图中所有边按权重从大到小排序为(e1，e2．…，em)；i＝l；while(所剩边数>＝顶点数){从图中删去ei；若图不再连通，则恢复ei；i＝i＋l；

Access2010数据库对象中，不能用来修改数据表中的数据，但能对数据表中的记录浏览、印的是________。

教育是社会主义现代化建设的基础，国家保障教育事业()。

Theinjectionthatthegirlhadbeengivenwasbeginningtowork.Herhead【C1】______heavy,andshewasverysleepy.Oncesheope

下列凭证，免征印花税的有()。

在建筑安装工程费用中，工会经费应列入()。

参与组织预算支出执行的机关主要有()。

5，5，15，75，()。

四人两两进行五子棋比赛，其中一人胜了两局，一人平了三局。若胜者得3分，败者得0分，平局双方各得1分。则最高分与最低分差距至少为：

μC／OS—Ⅱ能够提供周期性时钟信号(即所谓的时钟节拍)，用于实现任务的正确延时和超时确认。节拍率应在什么范围内?

TheBusinessofMediaViolence[A]In2001,peoplearoundtheworldspentUS$14billiongoingtoseefilms.TheUSdomesticbox