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

admin2009-02-15 47

问题设求解某问题的递归算法如下：　　　　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);

程序员上午基础知识考试

软考初级

WindowsNT中，启动系统的选择由文件Boot.ini来设定。假设某台PC机上，文件Boot.ini的内容如下：[bootloader]timeout=30default=multi(0)disk(0)rdisk(0)Par

框架在网页布局中主要起什么作用?手机销售信息查询主页中定义了几个框架，分别显示哪个文档?假设连接的数据记录集当前指向的记录见表6-10。写出以下ASP代码经过IIS服务器解释后的结果。＜tdalign="center"width

框架在网页布局中主要起什么作用?手机销售信息查询主页中定义了几个框架，分别显示哪个文档?手机销售信息查询的网页中使用的数据库连接引擎是什么?连接的后台数据库文件名是什么?

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

A　programmer　must　know　about　a　function’s(74)to　Call　it　correctly．

(74)is　nonprogram　text　embedded　in　a　program　to　explain　its　form　and　function　to　human　readers.

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

与十六进制数AC.E等值的十进制数是(5)，等值的八进制数是(6)。

数据库管理技术是在(20)的基础上发展起来的。数据模型的三要素是数据结构、数据操作和(21)。建立数据库系统的主要目标是减少数据的冗余，提高数据的独立性，并集中检查(22)。

下列电子支付工具中，属于电子货币的是()。

培养学生学习需要的途径有直接发生途径和______。

_是心脏性猝死的直接原因。_是心搏骤停时最常见的心律失常。

《会计法》中所指的会计主管人员与()同义。

影响投资者风险承受能力和收益需求的各项因素有()。

Itisappropriateonananniversaryofthefoundingofauniversitytoremindourselvesofitspurposes.Itisequallyappropriat

周某从迅达汽车贸易公司购买了1辆车，约定周某试用10天，试用期满后3天内办理登记过户手续。试用期间，周某违反交通规则将李某撞成重伤。现周某困难，无力赔偿。关于李某受到的损害，下列说法正确的是

ReadthearticlebelowaboutanewserviceofferedbyanairlinecalledFleetair.Aresentences16-22ontheoppositepage’Ri

MeredithJoneswasaschoolteacher,passionate,fluent,somethingofascholar,roughlygentle,ofremarkablevitalityandafrai

(1)Earlyinthefilm"ABeautifulMind",themathematicianJohnNashisseensittinginaPrincetoncourtyard,hunchedoverap

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

程序员上午基础知识考试

软考初级

WindowsNT中，启动系统的选择由文件Boot.ini来设定。假设某台PC机上，文件Boot.ini的内容如下：[bootloader]timeout=30default=multi(0)disk(0)rdisk(0)Par

框架在网页布局中主要起什么作用?手机销售信息查询主页中定义了几个框架，分别显示哪个文档?假设连接的数据记录集当前指向的记录见表6-10。写出以下ASP代码经过IIS服务器解释后的结果。＜tdalign="center"width

框架在网页布局中主要起什么作用?手机销售信息查询主页中定义了几个框架，分别显示哪个文档?手机销售信息查询的网页中使用的数据库连接引擎是什么?连接的后台数据库文件名是什么?

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

A programmer must know about a function’s(74)to Call it correctly．

(74)is nonprogram text embedded in a program to explain its form and function to human readers.

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

与十六进制数AC.E等值的十进制数是(5)，等值的八进制数是(6)。

数据库管理技术是在(20)的基础上发展起来的。数据模型的三要素是数据结构、数据操作和(21)。建立数据库系统的主要目标是减少数据的冗余，提高数据的独立性，并集中检查(22)。

下列电子支付工具中，属于电子货币的是()。

培养学生学习需要的途径有直接发生途径和______。

_______是心脏性猝死的直接原因。_______是心搏骤停时最常见的心律失常。

《会计法》中所指的会计主管人员与()同义。

影响投资者风险承受能力和收益需求的各项因素有()。

Itisappropriateonananniversaryofthefoundingofauniversitytoremindourselvesofitspurposes.Itisequallyappropriat

周某从迅达汽车贸易公司购买了1辆车，约定周某试用10天，试用期满后3天内办理登记过户手续。试用期间，周某违反交通规则将李某撞成重伤。现周某困难，无力赔偿。关于李某受到的损害，下列说法正确的是

ReadthearticlebelowaboutanewserviceofferedbyanairlinecalledFleetair.Aresentences16-22ontheoppositepage’Ri

MeredithJoneswasaschoolteacher,passionate,fluent,somethingofascholar,roughlygentle,ofremarkablevitalityandafrai

(1)Earlyinthefilm"ABeautifulMind",themathematicianJohnNashisseensittinginaPrincetoncourtyard,hunchedoverap

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

A　programmer　must　know　about　a　function’s(74)to　Call　it　correctly．

(74)is　nonprogram　text　embedded　in　a　program　to　explain　its　form　and　function　to　human　readers.

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

_是心脏性猝死的直接原因。_是心搏骤停时最常见的心律失常。