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

admin2009-02-15 59

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

程序员上午基础知识考试

软考初级

把一个消息排队之后收到一个错误消息，指出与服务器连接时有错，该如何解决?我能向对方发消息，对方也能向我发消息，但当对方响应我发出的消息时，我却什么也收不到，这晕为什么?

安装Linux之前需要知道哪些必要的数据信息?Linux的网络管理包括哪些方面?

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

阅读下列说明和HTML文本，分析其中嵌入的JavaScdpt脚本，将应填入(n)处的语句对应栏内。[说明]这是一个修改字符串的题目，此题中将字符串“hello，Iamnotastudent，Idonotlikecompute

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

Functional　testing　tests　whether　the　output　is　the　expected(75)with　the　valid　input.

在7位的ASCII码的最高位增加一位奇校验位就构成8位奇校验码。若大写字母K的十六进制奇校验码为CB，则大写字母E的十六进制奇校验码为(5)。

麻醉前用药中，使用麻醉性镇痛剂(吗啡等)的主要目的是下述哪项

下列关于桥梁技术术语说法正确的是()。

招标委员会的成员中，技术、经济等方面的专家不得少于()。

为了使断路器各断口上的电压分布接近相等，常在断路器多断口上加装()。

在Excel中，通过（　　）可以将整个工作表全部选中。

就同一种类型的债券而言，长期债券的利率比短期债券要低，因为长期债券获利的时间更长。(　　)

销售费用与管理费用相比，销售费用通常具有的特点有()。

令a◎b＝3a＋2b，现有输入值a、b、c一个各不相同的正整数。a、b、c经过算符a◎(b◎c)运算后得到输出值23，问b为：

Atfirst,PetersonfeelsthatEnglishlearningisveryboring.Atfirst,Petersonfinds______tostudyEnglish.

Fortyyearsagonoonewasconcernedaboutthehealthoftheocean,inspiteofthefactthatmanyfisheries(渔业)werebeingoverh

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

程序员上午基础知识考试

软考初级

把一个消息排队之后收到一个错误消息，指出与服务器连接时有错，该如何解决?我能向对方发消息，对方也能向我发消息，但当对方响应我发出的消息时，我却什么也收不到，这晕为什么?

安装Linux之前需要知道哪些必要的数据信息?Linux的网络管理包括哪些方面?

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

阅读下列说明和HTML文本，分析其中嵌入的JavaScdpt脚本，将应填入(n)处的语句对应栏内。[说明]这是一个修改字符串的题目，此题中将字符串“hello，Iamnotastudent，Idonotlikecompute

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

Functional testing tests whether the output is the expected(75)with the valid input.

在7位的ASCII码的最高位增加一位奇校验位就构成8位奇校验码。若大写字母K的十六进制奇校验码为CB，则大写字母E的十六进制奇校验码为(5)。

麻醉前用药中，使用麻醉性镇痛剂(吗啡等)的主要目的是下述哪项

下列关于桥梁技术术语说法正确的是()。

招标委员会的成员中，技术、经济等方面的专家不得少于()。

为了使断路器各断口上的电压分布接近相等，常在断路器多断口上加装()。

在Excel中，通过（ ）可以将整个工作表全部选中。

就同一种类型的债券而言，长期债券的利率比短期债券要低，因为长期债券获利的时间更长。( )

销售费用与管理费用相比，销售费用通常具有的特点有()。

令a◎b＝3a＋2b，现有输入值a、b、c一个各不相同的正整数。a、b、c经过算符a◎(b◎c)运算后得到输出值23，问b为：

Atfirst,PetersonfeelsthatEnglishlearningisveryboring.Atfirst,Petersonfinds______tostudyEnglish.

Fortyyearsagonoonewasconcernedaboutthehealthoftheocean,inspiteofthefactthatmanyfisheries(渔业)werebeingoverh

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

Functional　testing　tests　whether　the　output　is　the　expected(75)with　the　valid　input.

在Excel中，通过（　　）可以将整个工作表全部选中。

就同一种类型的债券而言，长期债券的利率比短期债券要低，因为长期债券获利的时间更长。(　　)