首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
用递归算法实现n个不同元素的有序序列的折半查找，采用一个递归工作栈时，该栈的最小容量应为( )。
用递归算法实现n个不同元素的有序序列的折半查找，采用一个递归工作栈时，该栈的最小容量应为( )。
admin
2019-12-10
19
问题
用递归算法实现n个不同元素的有序序列的折半查找，采用一个递归工作栈时，该栈的最小容量应为( )。
选项
A、n
B、[n／2]
C、[log
2
n]
D、[log
2
n]＋1
答案
D
解析
根据折半查找的过程，由于需要栈结构实现递归算法，栈的容量应该保证能存放查找失败时所有未完成运行的算法的活动记录。
第一次调用该算法时，栈中加入了一条查找记录，表示待查有序表中元素的个数为n；第二次调用时，无论是在前半区还是后半区查找，栈中又加入了一条查找记录，所确定的查找区间中的元素最多为n／2；第三次调用时，栈中又加入了一条查找记录，所确定的查找区间中的元素最多为n／4；依次类推，当所确定的查找区间中的元素为0时，递归调用该算法的次数为[ log
2
n]＋1次，查找结束。
[归纳总结]折半查找法在查找成功时和给定值进行比较的关键字个数至多是[log
2
n]＋1；在查找不成功时和给定值进行比较的关键字个数最多也不超过[log
2
n]＋1。
转载请注明原文地址:https://kaotiyun.com/show/BB3i777K
本试题收录于：
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
若干个等待访问磁盘者依次要访问的柱面为20，44，40，4，80，12，76，假设每移动一个柱面需要3毫秒时间，移动臂当前位于40号柱面，请按下列算法分别计算为完成上述各次访问总共花费的寻找时间。(1)先来先服务算法；(2)最短寻找时间
在一个双链表中，在*p结点之前插入*q结点的操作是()。
序列的“中值记录”指的是：如果将此序列排序后，它是第n／2个记录。试写出一个求中值记录的算法。
操作系统采用页式存储管理方法，要求()。
已知二叉树采用二叉链表方式存放，要求返回二叉树T的后序序列中的第一个结点的指针，是否可不用递归且不用栈来完成?请简述原因。
循环队列用数组A[0．．m～1]存放其元素值，已知其头尾指针分别为front和rear，则当前元素个数为()。
在某一个单处理机的系统中，外接了一台打印机，一台输入设备。当前在系统中有二个进程P0、P1已经就绪，进程P0首先获得处理机运行，调度算法为先来先服务，进程P0、P1的运行要求是这样的：P0：计算100ms，打印信息200ms，继续计算100ms，打印信息
如下图所示为一个带宽为50kbps的卫星信道，它的往返传播延时为500ms。现在有一个网络架设在该信道上，网络使用1000bit长度的帧和停止一等待协议，请回答如下问题：使用回退N帧协议的网络中，如果发送了0～7号帧，而发送端只收到了0、3号帧的回复
接收到的(偶性)汉明码为lOOllolB，其中的信息为()。
在下面关于树的相关概念的叙述中，正确的是()。
随机试题
当用于涂敷生产前的测试结果中有一项试验不满足规定要求时，应再从该批产品中取()追加样品重新进行试验。
回归系数的取值范围是()
极化疗法用于急性心肌梗死的目的是()
张某驾车与李某发生碰撞，交警赶到现场后用数码相机拍摄了碰撞情况，后李某提起诉讼，要求张某赔偿损失，并向法院提交了一张光盘，内附交警拍摄的照片。该照片属于下列哪一种证据?(2014年卷三48题，单选)
下列各级数中发散的是()。
一般来讲，MA能够发出买进信号的市场条件是( )。
小王今年22岁，打算30岁购置一套价值200万元的住房，目前他有现金50万元，若i=8％，试计算他在今后8年中每年应存()万元。
某高校一名大学生，大一、大二两年成绩优秀，大学三年级时因病退学。对于该学生，学校应当()。
最有利于学习效果提高的动机水平为中等的动机水平。()
A.ThankyouforthelessoninartappreciationB.ItleavesmecoolC.Icantellthedifferencebetweenanetchingandalitho
最新回复
(
0
)
