用递归算法实现n个相异元素构成的有序序列的二分查找，采用一个递归工作栈时，该栈的最小容量应为______。

admin2013-05-11 32

问题用递归算法实现n个相异元素构成的有序序列的二分查找，采用一个递归工作栈时，该栈的最小容量应为______。

选项 A、n
B、n/2
C、log₂n
D、log₂(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₂(n+1)-1。

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

本试题收录于：软件设计师上午基础知识考试题库软考中级分类

软件设计师上午基础知识考试

软考中级

相关试题推荐

随机试题

最新回复(0)

用递归算法实现n个相异元素构成的有序序列的二分查找，采用一个递归工作栈时，该栈的最小容量应为______。

软件设计师上午基础知识考试

软考中级

在IPv6中，地址类型是由格式前缀来区分的。IPv6可聚合全球单播地址的格式前缀是________。(2010年上半年试题)

下面关于IPv6单播地址的描述中，正确的是__________。(2013年上半年试题)

FTP客户上传文件时，通过服务器建立的连接是(1)，FTP客户端应用进程的端口可以为(2)。(2011年上半年试题)(2)

如果一个公司有2000台主机，则必须给它分配(1)个C类网络。为了使该公司网络在路由表中只占一行，指定给它的子网掩码应该是(2)。(2011年上半年试题)(1)

在一个由多台路由器构成的网络中，一条途经多个路由器的线路断开了，判断是哪一个路由器发生故障的命令是(1)。在发现跨路由器ping不通的情况下，可用配置管理工具收集(2)信息进行分析。(2)

ICMP协议在网络中起到了差错控制和交通控制的作用。在IP数据报的传送过程中，如果出现网络拥塞，则路由器发出__________报文。(2008年上半年试题)

利用__________可以对软件的技术信息、经营信息提供保护。(2010年下半年试题)

SNMPMIB中被管理对象的Access属性不包括__________。(2009年下半年试题)

在关系代数运算中，关系S、SP和R如下表所示。若先(33)，则可以从S和SP获得R。其对应的关系表达式为(34)。如下的SQL语句可以查询销售总量大于1000的部门名。Select部门名FromSWhere部门号in(Selec

急性早幼粒细胞性白血病的分化诱导剂治疗，通常首选下列哪一种?

手术前可以不输液1/2等渗液如3：2：1溶液(3份10%GS：2份NS：1份M/6；乳酸钠)

治疗心悸痰火扰心证的首选方剂是

具有抗早孕作用的药物是(　　)具有抗催乳素作用的药物是(　　)

下列危险废物贮存设施的选址条件中，符合《危险废物贮存污染控制标准》要求的是()。

根据《中华人民共和国城乡规划法》，城市地下空间的开发和利用，应当与经济和技术发展水平相适应，遵循(　　　)的原则。

管理学中的“木桶原理”要求在管理中应注意()。

某派出所接到报案称村里有人聚众赌博，该所民警出警时身着便装，未主动向村民亮明身份，造成村民误会。该派出所民警违背的公务员基本行为规范是()。

建构主义学习观中，教师角色是（）。

Thoughunemployedlongerwhenseekingwork,olderwomenjobhuntharder,holdajoblongerwithlessabsenteeism,performaswel

用递归算法实现n个相异元素构成的有序序列的二分查找，采用一个递归工作栈时，该栈的最小容量应为______。

软件设计师上午基础知识考试

软考中级

在IPv6中，地址类型是由格式前缀来区分的。IPv6可聚合全球单播地址的格式前缀是________。(2010年上半年试题)

下面关于IPv6单播地址的描述中，正确的是__________。(2013年上半年试题)

FTP客户上传文件时，通过服务器建立的连接是(1)，FTP客户端应用进程的端口可以为(2)。(2011年上半年试题)(2)

如果一个公司有2000台主机，则必须给它分配(1)个C类网络。为了使该公司网络在路由表中只占一行，指定给它的子网掩码应该是(2)。(2011年上半年试题)(1)

在一个由多台路由器构成的网络中，一条途经多个路由器的线路断开了，判断是哪一个路由器发生故障的命令是(1)。在发现跨路由器ping不通的情况下，可用配置管理工具收集(2)信息进行分析。(2)

ICMP协议在网络中起到了差错控制和交通控制的作用。在IP数据报的传送过程中，如果出现网络拥塞，则路由器发出__________报文。(2008年上半年试题)

利用__________可以对软件的技术信息、经营信息提供保护。(2010年下半年试题)

SNMPMIB中被管理对象的Access属性不包括__________。(2009年下半年试题)

在关系代数运算中，关系S、SP和R如下表所示。若先(33)，则可以从S和SP获得R。其对应的关系表达式为(34)。如下的SQL语句可以查询销售总量大于1000的部门名。Select部门名FromSWhere部门号in(Selec

急性早幼粒细胞性白血病的分化诱导剂治疗，通常首选下列哪一种?

手术前可以不输液1/2等渗液如3：2：1溶液(3份10%GS：2份NS：1份M/6；乳酸钠)

治疗心悸痰火扰心证的首选方剂是

具有抗早孕作用的药物是( )具有抗催乳素作用的药物是( )

下列危险废物贮存设施的选址条件中，符合《危险废物贮存污染控制标准》要求的是()。

根据《中华人民共和国城乡规划法》，城市地下空间的开发和利用，应当与经济和技术发展水平相适应，遵循( )的原则。

管理学中的“木桶原理”要求在管理中应注意()。

某派出所接到报案称村里有人聚众赌博，该所民警出警时身着便装，未主动向村民亮明身份，造成村民误会。该派出所民警违背的公务员基本行为规范是()。

建构主义学习观中，教师角色是（）。

Thoughunemployedlongerwhenseekingwork,olderwomenjobhuntharder,holdajoblongerwithlessabsenteeism,performaswel

具有抗早孕作用的药物是(　　)具有抗催乳素作用的药物是(　　)

根据《中华人民共和国城乡规划法》，城市地下空间的开发和利用，应当与经济和技术发展水平相适应，遵循(　　　)的原则。