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

admin2009-02-15 41

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

程序员上午基础知识考试

软考初级

防火墙包过滤规则的默认策略为拒绝，图7-10给出防火墙的包过滤规则配置界面。若要求内部所有主机能使用IE浏览器访问外部IP地址202.117.118.23的Web服务器，为图7-10中(1)～(4)空缺处选择正确答案。(1)A．允许B．拒绝

结合图3-14所示的网络拓扑结构图及题干的相关描述信息，请将图3-15所示的配置文件中的(1)～(4)空缺处的内容填写完整。在图3-15所示的配置文件中，第14行至第18行实现什么配置功能?

阅读下列说明和HTML文本，分析其中嵌入的JavaScript脚本，将应填(n)处的语句写在对应栏内。[说明]登录Web页时，在Web页中显示“welcometomyhomepage!”，并且文字渐隐渐现，然后显示“hello

阅读下列说明和HTML文本，分析其中嵌入的JavaScrlpt脚本，将应填入＜u＞(n)＜/u＞处的语句写在对应栏内。[说明]本题实现用鼠标拖拽图片在Web页内移动的功能。将鼠标放在图片上，按下左键，移动鼠标便可带动图片一起移动。[

(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

(66)is　a　channel’　s　capacity　which　directly　reflects　the　data　transfer　rate　of　the　channel.(67)functions　in　a　NetWare　network　wh

For　each　blank,　choose　the　best　answer　from　the　four　choices　and　write　down　on　the　answer　sheet.(66)is　a　one-way　function　that

在”人事档案”表文件中，”婚否”是逻辑型字段(已婚为逻辑真值)，“性别”为字符型字段，如果查询“已婚女同志”，应该使用的条件表达式是(32)。

数据结构被形式地定义为(K，R)，其中K是(34)的有限集合，R是K上(35)的有限集合。

依据股票基金所持有的全部股票的(　　)等指标可以对股票基金的投资风格进行分析。

根据下图所示网络结构回答问题。　若在windows主机192．168．64．215上探测数据包传输路径：从本机到主机192．168．66．195，应使用的命令是，数据包经过的第2个路由器为。

用天然气置换空气阶段是最危险的时间，因此置换速度一定要慢，按规定用氮气进行置换。()

海南杂忆茅盾我们到了那有名的“天涯海角”。原以为这个地方是一条陆地，突入海中，碧涛澎湃，前无去路。但是错了，完全不是那么一回事。所谓“天涯海角”就在公路旁边

输尿管的第3处狭窄位于

张某与王某最初订立合同时存在什么法律关系?()。张某与孙某之间存在什么法律关系?()。

一般进出口通关程序分哪些?

下列实体的联系中，属于一对一联系的是()。

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

程序员上午基础知识考试

软考初级

防火墙包过滤规则的默认策略为拒绝，图7-10给出防火墙的包过滤规则配置界面。若要求内部所有主机能使用IE浏览器访问外部IP地址202.117.118.23的Web服务器，为图7-10中(1)～(4)空缺处选择正确答案。(1)A．允许B．拒绝

结合图3-14所示的网络拓扑结构图及题干的相关描述信息，请将图3-15所示的配置文件中的(1)～(4)空缺处的内容填写完整。在图3-15所示的配置文件中，第14行至第18行实现什么配置功能?

阅读下列说明和HTML文本，分析其中嵌入的JavaScript脚本，将应填(n)处的语句写在对应栏内。[说明]登录Web页时，在Web页中显示“welcometomyhomepage!”，并且文字渐隐渐现，然后显示“hello

阅读下列说明和HTML文本，分析其中嵌入的JavaScrlpt脚本，将应填入＜u＞(n)＜/u＞处的语句写在对应栏内。[说明]本题实现用鼠标拖拽图片在Web页内移动的功能。将鼠标放在图片上，按下左键，移动鼠标便可带动图片一起移动。[

(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

(66)is a channel’ s capacity which directly reflects the data transfer rate of the channel.(67)functions in a NetWare network wh

For each blank, choose the best answer from the four choices and write down on the answer sheet.(66)is a one-way function that

在”人事档案”表文件中，”婚否”是逻辑型字段(已婚为逻辑真值)，“性别”为字符型字段，如果查询“已婚女同志”，应该使用的条件表达式是(32)。

数据结构被形式地定义为(K，R)，其中K是(34)的有限集合，R是K上(35)的有限集合。

依据股票基金所持有的全部股票的( )等指标可以对股票基金的投资风格进行分析。

根据下图所示网络结构回答问题。 若在windows主机192．168．64．215上探测数据包传输路径：从本机到主机192．168．66．195，应使用的命令是________，数据包经过的第2个路由器为________。

用天然气置换空气阶段是最危险的时间，因此置换速度一定要慢，按规定用氮气进行置换。()

海南杂忆茅盾我们到了那有名的“天涯海角”。原以为这个地方是一条陆地，突入海中，碧涛澎湃，前无去路。但是错了，完全不是那么一回事。所谓“天涯海角”就在公路旁边

输尿管的第3处狭窄位于

张某与王某最初订立合同时存在什么法律关系?()。张某与孙某之间存在什么法律关系?()。

一般进出口通关程序分哪些?

下列实体的联系中，属于一对一联系的是()。

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

(66)is　a　channel’　s　capacity　which　directly　reflects　the　data　transfer　rate　of　the　channel.(67)functions　in　a　NetWare　network　wh

For　each　blank,　choose　the　best　answer　from　the　four　choices　and　write　down　on　the　answer　sheet.(66)is　a　one-way　function　that　

依据股票基金所持有的全部股票的(　　)等指标可以对股票基金的投资风格进行分析。

根据下图所示网络结构回答问题。　若在windows主机192．168．64．215上探测数据包传输路径：从本机到主机192．168．66．195，应使用的命令是，数据包经过的第2个路由器为。