首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
用递归算法实现n个相异元素构成的有序序列的二分查找,采用一个递归工作栈时,该栈的最小容量应为______。
用递归算法实现n个相异元素构成的有序序列的二分查找,采用一个递归工作栈时,该栈的最小容量应为______。
admin
2013-05-11
20
问题
用递归算法实现n个相异元素构成的有序序列的二分查找,采用一个递归工作栈时,该栈的最小容量应为______。
选项
A、n
B、n/2
C、log
2
n
D、log
2
(n+1)
答案
D
解析
二分查找亦称折半查找,其基本思想:设查找表的元素存储在一维数组r[1..n]中,首先将待查的key值与表r中间位置上(下标为mid)的记录的关键字进行比较,若相等,则查找成功:若key>r[mid].key,则说明待查记录只可能在后半个子表r[mid+1..n](注意:是mid+1,而不是mid)中,下一步应在后半个子表中再进行折半查找,若key<r[mid].key,则说明待查记录只可能在前半个子表r[1..mid-1](注意:是mid-1,而不是mid)中,下一步应在前半个子表中再进行折半查找,这样通过逐步缩小范围,直到查找成功或予表为空时失败为止。
在表中的元素已经按关键字递增(或递减)的方式排序的情况下,才可进行折半查找。
等概率情况下顺序查找成功的平均查找长度为:
当n值较大时,ASLbs≈log
2
(n+1)-1。
转载请注明原文地址:https://kaotiyun.com/show/dnRZ777K
本试题收录于:
软件设计师上午基础知识考试题库软考中级分类
0
软件设计师上午基础知识考试
软考中级
相关试题推荐
PC机不能接入因特网,这时采用抓包工具捕获的以太网接口发出的信息如下:可以看出该PC机的IP地址为(68),默认网关的IP地址为(69)。PC不能接入Internet的原因可能是(70)。(69)
POP3协议采用(1)模式,当客户机需要服务时,客户端软件(OutlookExpress或Fox.Mail)与POP3服务器建立(2)连接。(2011年下半年试题)(2)
下列不是集成服务模型的优点的是__________。
假设用户Q1有2000台主机,则必须给他分配(1)个C类网络,如果分配给用户Q1的超网号为200.9.64.0,则指定给Q1的地址掩码为(2);假设给另一用户Q2分配的C类网络号为200.0.16.0~200.9.31.0,如果路由器收到一个目标地址为11
网络172.21.136.0/24和172.21.143.0/24汇聚后的地址是__________。(2010年下半年试题)
路由欺骗是在(1),直接修改(2),使某些报文被转到其他处,而不能到达目标主机。DNS欺骗位于(3),其修改的是(4),使得用户在访问域名时被引到错误的站点。(2)
X.509证书标准是一种由发布者数字签名的用于绑定(1)和其持有者身份的数据结构。发布者是证书的颁发者,它(2);(3)和公开密钥的绑定是证书的核心内容。它们的绑定是通过(垒)实现的。(2)
在SNMP管理模型中,关于管理信息库MIB的说法,正确的是(1)。SNMP实现管理功能的方式是(2)。SNMP网络管理模型中关于管理代理与委托代理的说法正确的是(3)。SNMP将一个值存储到指明变量中去使用(4)命令,而有关get操作命令的目的是(5)。
如下图所示,若路由器C的e0端口状态为down,则当主机A向主机C发送数据时,路由器C发送__________。(2013年上半年试题)
下列网络管理软件中不需要SNMP支持的是__________。
随机试题
烧伤早期出现的休克多为
镜面舌可见于()
下列有关一般法和特别法的表述,正确的是哪一或哪些选项?()
低压厂用电系统的短路电流计算中,下列叙述不正确的是哪项?
地图内容的“三要素”是()。
建设期内建设与()可能同步进行。
阅读以下材料,回答问题。材料一:“就吾最近几年间的经验,用吾最近几个月的思考,觉得职业学校有最要紧的一点,譬如人身中的灵魂,‘得之则生,弗得则死’,是什么东西呢?从其本质来说,就是社会性;从其作用来说,就是社会化。”材料二:“我们的职业教育社,自从
Internet上有许多应用,其中主要用来游览网页信息的是( )
选取“月平均气温统计表”的A2:G2和A6:G6单元格区域,建立“簇状圆柱图”,标题为“月平均气温统计图”,图例位置靠上,将图插入到表的A8:G20单元格区域内,保存EXCEL.xlsx文件。
Sincethedawnofhumaningenuity,peoplehavedevisedevermorecunningtoolstocopewithworkthatisdangerous,boring,burd
最新回复
(
0
)