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

admin2009-02-15 82

问题设求解某问题的递归算法如下：　　　　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://www.kaotiyun.com/show/XXjZ777K

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

程序员上午基础知识考试

软考初级

相关试题推荐

随机试题

最新回复(0)

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

程序员上午基础知识考试

软考初级

何谓Linux?它与Unix之间有何差异?什么是“内核”?

该商务网站采用Browser/Server三层结构。请根据Browser/Server三层结构的工作过程，将图3-18中(1)～(3)空缺处的内容填写完整。search.asp文件的功能是根据类别、品牌、型号，按照用户输入的关键字进行查询，请为其(

阅读下列说明和HTML文本，分析其中嵌入的JavaScript脚本，[说明]这是一个修改字符串的题目，此题中将字符串“hello，Iamnotastudent，Idonotlikecomputer!”中的"not"去掉，并在

The　basic　concept　of　a　data(72)is　the　difference　between　data　and　information.

For　each　blank,　choose　the　best　answer　from　the　four　choices　and　write　down　on　the　answer　sheet.Web　browser　is　simply　a　terminal

简述无产阶级政党的特征。

男性患者，50岁，进食哽噎感，胸骨后异物感1个月，食管钡餐透视见食管下段黏膜紊乱、断裂、管壁僵硬。要确定诊断最常用的方法是

女性，30岁，排便时肛门部剧痛，并有少许鲜血滴出1周，疼痛于排便后约20分钟渐缓解。根据上述诊断，最恰当的检查是

组成药物中含有干姜、川芎的方剂是

患者，女性，36岁。患狼疮性肾炎3年，肾功能损害严重。昨天患者企图从高层住宅跳下，幸亏被家人发现，当即将患者送往医院接受治疗，以“重度抑郁症”收治入院。对该患者进行入院护理时，以下做法不适合的是

三段论，是指由两个含有一个共同项的性质判断做前提得出一个新的性质判断为结论的演绎推理。根据上述定义，下列属于三段论推理的是：

()是施工安全的责任主体。

输入动物，检出二类传染病、寄生虫病的，退回或者扑杀，同群其他动物在隔离场或者其他指定地点()。

填入下面文字括号处的词语，最恰当的是()。近段时间，多项房地产调控政策()出台，表明国家()房价过快增长的态度异常坚决。

一条计算机指令中，通常应该包含()。

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

程序员上午基础知识考试

软考初级

何谓Linux?它与Unix之间有何差异?什么是“内核”?

该商务网站采用Browser/Server三层结构。请根据Browser/Server三层结构的工作过程，将图3-18中(1)～(3)空缺处的内容填写完整。search.asp文件的功能是根据类别、品牌、型号，按照用户输入的关键字进行查询，请为其(

阅读下列说明和HTML文本，分析其中嵌入的JavaScript脚本，[说明]这是一个修改字符串的题目，此题中将字符串“hello，Iamnotastudent，Idonotlikecomputer!”中的"not"去掉，并在

The basic concept of a data(72)is the difference between data and information.

For each blank, choose the best answer from the four choices and write down on the answer sheet.Web browser is simply a terminal

简述无产阶级政党的特征。

男性患者，50岁，进食哽噎感，胸骨后异物感1个月，食管钡餐透视见食管下段黏膜紊乱、断裂、管壁僵硬。要确定诊断最常用的方法是

女性，30岁，排便时肛门部剧痛，并有少许鲜血滴出1周，疼痛于排便后约20分钟渐缓解。根据上述诊断，最恰当的检查是

组成药物中含有干姜、川芎的方剂是

患者，女性，36岁。患狼疮性肾炎3年，肾功能损害严重。昨天患者企图从高层住宅跳下，幸亏被家人发现，当即将患者送往医院接受治疗，以“重度抑郁症”收治入院。对该患者进行入院护理时，以下做法不适合的是

三段论，是指由两个含有一个共同项的性质判断做前提得出一个新的性质判断为结论的演绎推理。根据上述定义，下列属于三段论推理的是：

()是施工安全的责任主体。

输入动物，检出二类传染病、寄生虫病的，退回或者扑杀，同群其他动物在隔离场或者其他指定地点()。

填入下面文字括号处的词语，最恰当的是()。近段时间，多项房地产调控政策()出台，表明国家()房价过快增长的态度异常坚决。

一条计算机指令中，通常应该包含()。

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

The　basic　concept　of　a　data(72)is　the　difference　between　data　and　information.

For　each　blank,　choose　the　best　answer　from　the　four　choices　and　write　down　on　the　answer　sheet.Web　browser　is　simply　a　terminal