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

admin2013-05-11 14

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

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

答案D

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

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

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

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

软考中级

相关试题推荐

随机试题

最新回复(0)

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

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

软考中级

RIP是一种基于(1)的路由协议，RIP规定，通路上经过的最大路由器数是(2)。(2008年下半年试题)(1)

以下关于加密算法的叙述中，正确的是__________。(2010年上半年试题)

设信道带宽为3400Hz，采用PCM编码，采样周期为125μs，每个样本量化为128个等级，则信道的数据速率为__________。(2009年上半年试题)

M软件公司的软件产品注册商标为M，为确保公司在市场竞争中占据优势，对员工进行了保密约束。此情形下该公司不享有__________。(2012年下半年试题)

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

已知图G＝(V,E)，其中V＝(a，b，c，d，e，f)，E：{＜a，b＞，＜a，d＞，＜a，e＞，＜d，e＞，＜e，　b＞，＜c，b＞，＜c，e＞，＜c，b，＜f，e＞}，则从该图的顶点a出发的深度优先遍历序列是(51)，广度优先遍历序列是(52)，其深

甲国有企业的债权人于2004年6月1日向法院申请宣告甲企业破产，2004年6月5日法院受理了破产中请，2004年9月1日法院宣告甲企业破产，甲企业的下列行为无效的是：()

慢性粒细胞白血病出现(　　)再生障碍性贫血出现(　　)

多重共线性的补救措施主要有()。Ⅰ．剔除变量法Ⅱ．变换模型形式Ⅲ．利用非样本先验信息Ⅳ．加权最小二乘法

进口货物的增值税纳税义务发生时间为()。

学校及其他教育机构中最基本、最主要的活动是()。

创建于1879年的美国第一个托拉斯是()

我不在犯罪现场。如果我在，那么，我没有犯罪。如果我犯了罪，那么，一定是我神志不清。以下哪项与上述论证最相似?

Whenyouopenyourelectronicmail,youmayfindinformationabouthowtobuymedicine,cheapairlinetickets,books,computerp

Googlemustbethemostambitiouscompanyintheworld.Itsstatedgoal,"toorganizetheworld’sinformationandmakeituniver

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

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

软考中级

RIP是一种基于(1)的路由协议，RIP规定，通路上经过的最大路由器数是(2)。(2008年下半年试题)(1)

以下关于加密算法的叙述中，正确的是__________。(2010年上半年试题)

设信道带宽为3400Hz，采用PCM编码，采样周期为125μs，每个样本量化为128个等级，则信道的数据速率为__________。(2009年上半年试题)

M软件公司的软件产品注册商标为M，为确保公司在市场竞争中占据优势，对员工进行了保密约束。此情形下该公司不享有__________。(2012年下半年试题)

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

已知图G＝(V,E)，其中V＝(a，b，c，d，e，f)，E：{＜a，b＞，＜a，d＞，＜a，e＞，＜d，e＞，＜e， b＞，＜c，b＞，＜c，e＞，＜c，b，＜f，e＞}，则从该图的顶点a出发的深度优先遍历序列是(51)，广度优先遍历序列是(52)，其深

甲国有企业的债权人于2004年6月1日向法院申请宣告甲企业破产，2004年6月5日法院受理了破产中请，2004年9月1日法院宣告甲企业破产，甲企业的下列行为无效的是：()

慢性粒细胞白血病出现( )再生障碍性贫血出现( )

多重共线性的补救措施主要有()。Ⅰ．剔除变量法Ⅱ．变换模型形式Ⅲ．利用非样本先验信息Ⅳ．加权最小二乘法

进口货物的增值税纳税义务发生时间为()。

学校及其他教育机构中最基本、最主要的活动是()。

创建于1879年的美国第一个托拉斯是()

我不在犯罪现场。如果我在，那么，我没有犯罪。如果我犯了罪，那么，一定是我神志不清。以下哪项与上述论证最相似?

Whenyouopenyourelectronicmail,youmayfindinformationabouthowtobuymedicine,cheapairlinetickets,books,computerp

Googlemustbethemostambitiouscompanyintheworld.Itsstatedgoal,"toorganizetheworld’sinformationandmakeituniver

已知图G＝(V,E)，其中V＝(a，b，c，d，e，f)，E：{＜a，b＞，＜a，d＞，＜a，e＞，＜d，e＞，＜e，　b＞，＜c，b＞，＜c，e＞，＜c，b，＜f，e＞}，则从该图的顶点a出发的深度优先遍历序列是(51)，广度优先遍历序列是(52)，其深

慢性粒细胞白血病出现(　　)再生障碍性贫血出现(　　)