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

admin2013-05-11 7

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

选项 A、n
B、[n/2]
C、[log₂n]
D、[log₂(n+1)]

答案D

解析根据二分查找的过程，由于需要栈结构实现递归算法，栈的容量应该要保证能存放查找失败时所有未完成运行的算法的活动记录。第一次调用该算法时，栈中加入了一条查找记录，表示待查有序表中元素的个数为n：第二次调用时，无论是在前半区还是在后半区进行查找，栈中又加入了一条查找记录，所确定的查找区间中的元素最多为n/2：第三次调用时，栈中又加入了—条查找记录，所确定的查找区间中的元素最多为n/4。依次类推，当所确定的查找区间中的元素为。时，递归调用该算法的次数为log₂(n+1)次，查找结束。

转载请注明原文地址:https://jikaoti.com/ti/EHf7FFFM

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

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

软考中级

相关试题推荐

随机试题

最新回复(0)

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

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

软考中级

网络管理系统的配置管理最主要的功能是(1)。下列选项中不属于网络管理系统安全管理部分功能的是(2)，不属于网络管理协议的是(3)。(3)

__________指可以不经著作权人许可，无需支付报酬，使用其作品。(2011年下半年试题)

近年来，在我国出现的各类病毒中，__________病毒通过木马形式感染智能手机。(2013年上半年试题)

在Windows环境下，DHCP客户端可以使用(1)命令重新获得IP地址，这时客户机向DHCP服务器发送一个(2)数据包来请求租用IP地址。(2008年上半年试题)(1)

网络由6个路由器互联而成，路由器之间的链路费用如下图所示，从PC到服务器的最短路径是(1)，通路费用是(2)。(20lO年下半年试题)(2)

Flynn分类法基于信息流特征将计算机分成4类，其中()只有理论意义而无实例。

确定软件的模块划分及模块之间的调用关系是__________阶段的任务。(2011年下半年试题)

在Windows命令中，命令(14)可以用于验证端系统地址；(15)可以用于识别分组传送路径；执行操作(16)可以终止一个ping会话。应用(17)—对网络带宽性能影响最大。OSPF和RIP都是Internet中的路由协议，与RIP相比，OSPF有许多优点

A.unnecessaryB.completeC.lightestD.safeE.flammableF.reactiveMRImaymakeoperatingonthepatient______.

下列哪一种情况下可发生冠状动脉明显舒张

血浆晶体渗透压的主要参与形成者是血浆胶体渗透压的主要参与形成者是

申请设立保险公估机构时其持有《保险公估从业人员资格证书》的员工人数应当在(　　)以上。

研究者必须知道每次观察的重点和方式，特别是要按照研究的目的认真选择典型观察对象、环境条件和工具。这是观察研究的()原则。

下列命题正确的是()．

Youshouldspendabout20minutesonQuestions27-40,whicharebasedonReadingPassage3below.SourceofKnowledgeAWhatcou

A、Helikesitmuchbetter.B、Hedoesn’tlikeit.C、Hedoesn’tknow.D、Hepreferstheblueone.A观点态度题。对话中女士对男士说想穿蓝色裙子去参加晚会，可男士建议

Ishallhavearoommateinthehouseafterallthese______years.

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

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

软考中级

网络管理系统的配置管理最主要的功能是(1)。下列选项中不属于网络管理系统安全管理部分功能的是(2)，不属于网络管理协议的是(3)。(3)

__________指可以不经著作权人许可，无需支付报酬，使用其作品。(2011年下半年试题)

近年来，在我国出现的各类病毒中，__________病毒通过木马形式感染智能手机。(2013年上半年试题)

在Windows环境下，DHCP客户端可以使用(1)命令重新获得IP地址，这时客户机向DHCP服务器发送一个(2)数据包来请求租用IP地址。(2008年上半年试题)(1)

网络由6个路由器互联而成，路由器之间的链路费用如下图所示，从PC到服务器的最短路径是(1)，通路费用是(2)。(20lO年下半年试题)(2)

Flynn分类法基于信息流特征将计算机分成4类，其中()只有理论意义而无实例。

确定软件的模块划分及模块之间的调用关系是__________阶段的任务。(2011年下半年试题)

在Windows命令中，命令(14)可以用于验证端系统地址；(15)可以用于识别分组传送路径；执行操作(16)可以终止一个ping会话。应用(17)—对网络带宽性能影响最大。OSPF和RIP都是Internet中的路由协议，与RIP相比，OSPF有许多优点

A.unnecessaryB.completeC.lightestD.safeE.flammableF.reactiveMRImaymakeoperatingonthepatient______.

下列哪一种情况下可发生冠状动脉明显舒张

血浆晶体渗透压的主要参与形成者是血浆胶体渗透压的主要参与形成者是

申请设立保险公估机构时其持有《保险公估从业人员资格证书》的员工人数应当在( )以上。

研究者必须知道每次观察的重点和方式，特别是要按照研究的目的认真选择典型观察对象、环境条件和工具。这是观察研究的()原则。

下列命题正确的是()．

Youshouldspendabout20minutesonQuestions27-40,whicharebasedonReadingPassage3below.SourceofKnowledgeAWhatcou

A、Helikesitmuchbetter.B、Hedoesn’tlikeit.C、Hedoesn’tknow.D、Hepreferstheblueone.A观点态度题。对话中女士对男士说想穿蓝色裙子去参加晚会，可男士建议

Ishallhavearoommateinthehouseafterallthese______years.

申请设立保险公估机构时其持有《保险公估从业人员资格证书》的员工人数应当在(　　)以上。