设求解某问题的递归算法如下：　　　　F(int　n){　　　　　　　　if　n==1{　　　　　　　　　　　　Move(1);　　　　　　　　}　　　　　　　　else{　　　　　　　　　　　　F(n-1);　　　　　　　　　　　　Move(n);　　　　

admin2009-02-15 29

问题设求解某问题的递归算法如下：　　　　F(int　n){　　　　　　　　if　n==1{　　　　　　　　　　　　Move(1);　　　　　　　　}　　　　　　　　else{　　　　　　　　　　　　F(n-1);　　　　　　　　　　　　Move(n);　　　　　　　　　　　　F(n-1);　　　　　　　　}　　　　}　　　　求解该算法的计算时间时，仅考虑算法Move所进行的计算为主要计算，且Move为常数级算法，设算法Move的计算时间为k，当n=5时，算法F的计算时间为(42)。

选项 A、7k
B、15k
C、31k
D、63k

答案C

解析直接递归算法的计算时间可以根据递归调用形式对应写出其递推关系式。按照题目中描述的算法形式可知，算法F的计算时间T(n)的递推关系式为T(n)=2T(n-1)+1，其中两次递归调用F(n-1)用时2T(n-1)，算法Move的计算时间为常数，计为1。将上述递推关系式中常数1用k替换，求解可得T(n)=2n^-1T(1)+k

2ⁱ，易知T(1)=k，将n=5代入可得T(n)=2n^-1T(1)+k

2ⁱ=2^5-1k+k

2ⁱ=2⁴k+(2⁰+2¹+2²+2³)k=31k。

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

本试题收录于：程序员上午基础知识考试题库软考初级分类

程序员上午基础知识考试

软考初级

相关试题推荐

随机试题

最新回复(0)

设求解某问题的递归算法如下：　　　　F(int　n){　　　　　　　　if　n==1{　　　　　　　　　　　　Move(1);　　　　　　　　}　　　　　　　　else{　　　　　　　　　　　　F(n-1);　　　　　　　　　　　　Move(n);

程序员上午基础知识考试

软考初级

FTP协议属于TCP/IP模型中的(1)协议，基于TCP协议在客户端和服务器之间传送所有数据，TCP是一个(2)的协议，其主要特点是(3)，这对于文件传输而言是非常重要的。其中(1)、(2)备选答案：(1)A．应用层B．传输层C．

如何设置httpd.conf，使得Apache服务器监听在特定的端口?如何屏蔽来自某个Internet地址的用户访问Apache服务器?

Internet的服务有哪几种?电子邮件网关的工作过程是怎样的?

请根据网页显示效果图的网页中的元素说明，将HTML文本中上处的解答填入对应的解答栏内。请根据网页显示效果图的网页中的元素说明，将HTML文本中上处的解答填入对应的解答栏内。[说明]下图是一个关于Sony公司2006年两款DV产

阅读以下说明，回答下列问题，将解答填入答题纸对应的解答栏内。【说明】某局域网采用DHCP服务器自动分配IP地址，网络结构如图2-1所示。依据图2-3的结果，租约期限为(8)天。

(66)is　a　one-way　function　that　takes　an　arbitrarily　long　piece　of　plaintext　and　from　it　computes　a　fixed,length　bit　string.(67)i

________不属于线性的数据结构。

为了描述某公司n名程序员之间的同学关系，可用(37)这一数据结构表示。

李斯在《谏逐客书》中说：“太山不让土壤，故能成其大；河海不择细流，故能就其深；王者不却众庶，故能明其德。”这里所采用的修辞手法和论证方法不包括()

A．脂肪坏死B．液化性坏死C．两者皆有D．两者皆无中枢神经系统的坏死常常表现为

崩漏的主要病因是

下列除哪项外，均可使用培元补肾法()

A．国家食品药品监督管理部门B．省级食品药品监督管理部门C．省以上食品药品监督管理部门D．设区的市食品药品监督管理部门E．直辖市设的县食品药品监督管理部门负责GSP认证

生态影响调查结论是全部调查工作的结论，编写时重点概括说明（），在此基础上，对环境保护措施提出改进措施和建议。

在规定装运期条文时，如使用了“立即装运”、“即刻装”、“尽速装运”或类似词句者，按《UCP600》规定，银行将不予置理。()

公司债券的违约风险一般通过()标示。

资产负债表日，提供劳务结果不能可靠估计，且已经发生的劳务成本预计部分能够得到补偿的，应按能够得到部分补偿的劳务成本金额确认劳务收入，并结转已经发生的劳务成本。()(2013年)

Onetypeofpersonthatiscommoninmanycountriesistheonewhoalwaystriestodoaslittleaspossibleandtogetasmuch【C

设求解某问题的递归算法如下： F(int n){ if n==1{ Move(1); } else{ F(n-1); Move(n);

程序员上午基础知识考试

软考初级

FTP协议属于TCP/IP模型中的(1)协议，基于TCP协议在客户端和服务器之间传送所有数据，TCP是一个(2)的协议，其主要特点是(3)，这对于文件传输而言是非常重要的。其中(1)、(2)备选答案：(1)A．应用层B．传输层C．

如何设置httpd.conf，使得Apache服务器监听在特定的端口?如何屏蔽来自某个Internet地址的用户访问Apache服务器?

Internet的服务有哪几种?电子邮件网关的工作过程是怎样的?

请根据网页显示效果图的网页中的元素说明，将HTML文本中上处的解答填入对应的解答栏内。请根据网页显示效果图的网页中的元素说明，将HTML文本中上处的解答填入对应的解答栏内。[说明]下图是一个关于Sony公司2006年两款DV产

阅读以下说明，回答下列问题，将解答填入答题纸对应的解答栏内。【说明】某局域网采用DHCP服务器自动分配IP地址，网络结构如图2-1所示。依据图2-3的结果，租约期限为(8)天。

(66)is a one-way function that takes an arbitrarily long piece of plaintext and from it computes a fixed,length bit string.(67)i

________不属于线性的数据结构。

为了描述某公司n名程序员之间的同学关系，可用(37)这一数据结构表示。

李斯在《谏逐客书》中说：“太山不让土壤，故能成其大；河海不择细流，故能就其深；王者不却众庶，故能明其德。”这里所采用的修辞手法和论证方法不包括()

A．脂肪坏死B．液化性坏死C．两者皆有D．两者皆无中枢神经系统的坏死常常表现为

崩漏的主要病因是

下列除哪项外，均可使用培元补肾法()

A．国家食品药品监督管理部门B．省级食品药品监督管理部门C．省以上食品药品监督管理部门D．设区的市食品药品监督管理部门E．直辖市设的县食品药品监督管理部门负责GSP认证

生态影响调查结论是全部调查工作的结论，编写时重点概括说明（），在此基础上，对环境保护措施提出改进措施和建议。

在规定装运期条文时，如使用了“立即装运”、“即刻装”、“尽速装运”或类似词句者，按《UCP600》规定，银行将不予置理。()

公司债券的违约风险一般通过()标示。

资产负债表日，提供劳务结果不能可靠估计，且已经发生的劳务成本预计部分能够得到补偿的，应按能够得到部分补偿的劳务成本金额确认劳务收入，并结转已经发生的劳务成本。()(2013年)

Onetypeofpersonthatiscommoninmanycountriesistheonewhoalwaystriestodoaslittleaspossibleandtogetasmuch【C

设求解某问题的递归算法如下：　　　　F(int　n){　　　　　　　　if　n==1{　　　　　　　　　　　　Move(1);　　　　　　　　}　　　　　　　　else{　　　　　　　　　　　　F(n-1);　　　　　　　　　　　　Move(n);　　　　

(66)is　a　one-way　function　that　takes　an　arbitrarily　long　piece　of　plaintext　and　from　it　computes　a　fixed,length　bit　string.(67)i