首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
用递归算法实现n个不同元素的有序序列的折半查找，采用一个递归工作栈时，该栈的最小容量应为( )。
用递归算法实现n个不同元素的有序序列的折半查找，采用一个递归工作栈时，该栈的最小容量应为( )。
admin
2019-12-10
44
问题
用递归算法实现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://www.kaotiyun.com/show/Um3i777K
本试题收录于：
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
DNS作为一种分布式系统，所基于的模式是()。
由元素序列(27，16，75，38，51)构造平衡二叉树，则首次出现的最小不平衡子树的根(即离插入结点最近且平衡因子的绝对值为2的结点)是()。
已知二叉树采用二叉链表方式存放，要求返回二叉树T的后序序列中的第一个结点的指针，是否可不用递归且不用栈来完成?请简述原因。
某计算机采用页式存储管理，内存中现有1000个页表项，CPU的cache中可以存放N个页表项，该系统中，CPU内存访问的时间为lOOns，对cache访问的时间是5ns，如果希望页表映射的平均时间降到20ns以下，那么cache中的N必须高于(
一个栈的入栈序列是1，2，3，4，5，则栈的不可能的输出序列是()。
设某计算机的逻辑地址空间和物理地址空间均为64KB，按字节编址。若某进程最多需要6页(Page)数据存储空间，页的大小为1KB，操作系统采用固定分配局部置换策略为此进程分配4个页框(PageFrame)。在时刻260前的该进程访问情况见表B一2(访问位即使
某计算机字长为16位，主存地址空间大小为128KB，按字编址。采用单字长指令格式，指令各字段定义如图B-4所示。转移指令采用相对寻址方式，相对偏移量用补码表示，寻址方式定义见表B-1。请回答下列问题：该指令系统最多可有多少条指令?该计算机最多有
单级中断系统中，中断服务程序内的执行顺序是____。I．保护现场Ⅱ．开中断Ⅲ．关中断Ⅳ．保存断点V．中断事件处理Ⅵ．恢复现场Ⅶ．中断返回
某文件占10个磁盘块，现要把该文件磁盘块逐个读入主存缓冲区，并送用户区进行分析，假设一个缓冲区与一个磁盘块大小相同，把一个磁盘块读入缓冲区的时间为100gs，将缓冲区的数据传送到用户区的时间是50μs，CPU对一块数据进行分析的时间为50μs。在单缓冲区和
假定不采用Cache和指令预取技术，且机器处于“开中断”状态，则在下列有关指令执行的叙述中，错误的是____。
随机试题
在氧化还原滴定法中，高锰酸钾法使用的是()。
旋覆花入汤剂的用法是
【2007年第3题】题1～5：某车间有下列用电负荷：(1)机床：80kW，2台；60kW，4台；30kW，15台。(2)通风机：80kW，4台，其中备用1台；60kW，4台，其中备用1台；30kw，12台，其中备用2台。(3)电焊机：三相380V；7
根据《水法》规定，水资源战略规划包括()。
下列个人理财顾问服务的风险提示管理措施合规的是（）
下列资产减值准备中，在符合相关条件时可以转回的有（）。
代理的特征有()。
已知e是自然对数的底数，计算不定积分
从所给的四个选项中，选择最合适的一个填入问号处，使之呈现一定的规律性。
2018年1月8日，国家科学技术奖励大会在北京举行。共同获得2017年度国家最高科学技术奖的是：
最新回复
(
0
)
