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

admin2009-02-15 83

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

程序员上午基础知识考试

软考初级

阅读以下说明，回答问题1至问题5，将解答填入对应栏内。[说明]某大学要拟建一个小型局域网，如图10-5所示，PCI、PC3、PC5的IP地址分别为10.244.80.2，10.244.80.3，10.244.80.4子网掩码是255.255

在InternetExplorer中怎样消除网页的背景音乐?假如你想每次启动浏览器时，都能自动打开A公司的主页，但你又不知道A公司的主页地址，请问如何实现这一功能?

In　C　language，functions　are　important　because　they　provide　a　way　to(69)code　so　that　a　large　complex　program　can　be　written　by　co

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

(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

与十六进制数9EE等值的十进制数是(3)。

某计算机字长16位的机器码1111　1111　00000000，表示无符号的整数时对应的十进制表达式为(5)，表示一个带符号整数的反码时，该机器码表示的十进制表达式为(6)。该数的补码是(7)。

女，68岁。胃癌根治术后8天，剧烈咳嗽时，突然出现切口疼痛，并流出少量淡红色液体。病人最可能出现了()

血检微丝蚴采血适宜的时间是

实行防水混凝土自防水的技术途径有(　　)。

公募基金管理人、基金托管人属于中国基金业协会的()。

货银对付原则是证券结算的一项基本原则，可以将证券结算中的违约交收风险降低到最小程度。()

下列说法正确的是()。

现阶段我国民族工作的主题是()。

钱能够起到无条件刺激的作用，与其他条件刺激建立条件反射。能够对此进行解释的是

GreenhouseEffectI.【T1】_ofthegreenhouseeffectA.About【T2】___ofthesunlightreachestheplanet’ssurfaceandisr

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

程序员上午基础知识考试

软考初级

阅读以下说明，回答问题1至问题5，将解答填入对应栏内。[说明]某大学要拟建一个小型局域网，如图10-5所示，PCI、PC3、PC5的IP地址分别为10.244.80.2，10.244.80.3，10.244.80.4子网掩码是255.255

在InternetExplorer中怎样消除网页的背景音乐?假如你想每次启动浏览器时，都能自动打开A公司的主页，但你又不知道A公司的主页地址，请问如何实现这一功能?

In C language，functions are important because they provide a way to(69)code so that a large complex program can be written by co

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

(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

与十六进制数9EE等值的十进制数是(3)。

某计算机字长16位的机器码1111 1111 00000000，表示无符号的整数时对应的十进制表达式为(5)，表示一个带符号整数的反码时，该机器码表示的十进制表达式为(6)。该数的补码是(7)。

女，68岁。胃癌根治术后8天，剧烈咳嗽时，突然出现切口疼痛，并流出少量淡红色液体。病人最可能出现了()

血检微丝蚴采血适宜的时间是

实行防水混凝土自防水的技术途径有( )。

公募基金管理人、基金托管人属于中国基金业协会的()。

货银对付原则是证券结算的一项基本原则，可以将证券结算中的违约交收风险降低到最小程度。()

下列说法正确的是()。

现阶段我国民族工作的主题是()。

钱能够起到无条件刺激的作用，与其他条件刺激建立条件反射。能够对此进行解释的是

GreenhouseEffectI.【T1】_____ofthegreenhouseeffectA.About【T2】_______ofthesunlightreachestheplanet’ssurfaceandisr

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

In　C　language，functions　are　important　because　they　provide　a　way　to(69)code　so　that　a　large　complex　program　can　be　written　by　co

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

(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

某计算机字长16位的机器码1111　1111　00000000，表示无符号的整数时对应的十进制表达式为(5)，表示一个带符号整数的反码时，该机器码表示的十进制表达式为(6)。该数的补码是(7)。

实行防水混凝土自防水的技术途径有(　　)。

GreenhouseEffectI.【T1】_ofthegreenhouseeffectA.About【T2】___ofthesunlightreachestheplanet’ssurfaceandisr