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

admin2009-02-15 69

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

程序员上午基础知识考试

软考初级

阅读下列广域网路由基本技术的应用，分析路由器的配置命令，将应填入(n)处的内容写在对应栏内。实例：通过Cisco2501连接A局域网与B局域网，如图2所示。假设实验条件如下：A网：202．96．199．0，202．96．1

请根据网页显示的效果图和网页中的元素说明，将HTML文本中(n)处的解答填入对应栏中。[说明]在IE浏览器中输入yoyo电子邮局主页地址并回车后，网页的显示效果如图3-1所示。[网页中的元素说明]见表3-1。

该商务网站有一个购物车模块，购物车模块中自定义的两个Session属性如下。①CID用来记录用户选择的商品。②CNUM用来记录相应商品的数量。请根据表6-23所列的购物情况，将(1)～(3)空缺处对session对象处理方式的内容填

请根据网页显示的效果图和网页中的元素说明完成HTML文本中______处的内容。【源代码】＜html＞＜head＞(1)＜metahttp-equiv=Content-Typecontent="text/html;charset=

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

A　word　processor　enables　you　to　create　a(70),　store　it　electronically　on　a　disk,　display　it　on　a　screen,　modify　it　by　entering　c

A　word　processor　enables　you　to　create　a(66),　store　it　electronically　on　a　disk,　display　it　on　a　screen,　modify　it　by　entering　c

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

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

卡方检验要求每个单元格的理论次数不得小于5，如果小于5应该采用以下的哪些处理办法?()

在真核DNA复制时合成引物的是

中华人民共和国的武装力量属于军队。()

以“余弦定理”教学为例，简述数学定理教学的主要环节。

()是中国工人阶级的先锋队，同时是中国人民和中华民族的先锋队。

按时间先后排序，蒙学教材出现的时间排序正确的是

上市公司股票的清算价格是()。

burdenofproof

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

程序员上午基础知识考试

软考初级

阅读下列广域网路由基本技术的应用，分析路由器的配置命令，将应填入(n)处的内容写在对应栏内。实例：通过Cisco2501连接A局域网与B局域网，如图2所示。假设实验条件如下：A网：202．96．199．0，202．96．1

请根据网页显示的效果图和网页中的元素说明，将HTML文本中(n)处的解答填入对应栏中。[说明]在IE浏览器中输入yoyo电子邮局主页地址并回车后，网页的显示效果如图3-1所示。[网页中的元素说明]见表3-1。

该商务网站有一个购物车模块，购物车模块中自定义的两个Session属性如下。①CID用来记录用户选择的商品。②CNUM用来记录相应商品的数量。请根据表6-23所列的购物情况，将(1)～(3)空缺处对session对象处理方式的内容填

请根据网页显示的效果图和网页中的元素说明完成HTML文本中______处的内容。【源代码】＜html＞＜head＞(1)＜metahttp-equiv=Content-Typecontent="text/html;charset=

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

A word processor enables you to create a(70), store it electronically on a disk, display it on a screen, modify it by entering c

A word processor enables you to create a(66), store it electronically on a disk, display it on a screen, modify it by entering c

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

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

卡方检验要求每个单元格的理论次数不得小于5，如果小于5应该采用以下的哪些处理办法?()

在真核DNA复制时合成引物的是

中华人民共和国的武装力量属于军队。()

以“余弦定理”教学为例，简述数学定理教学的主要环节。

()是中国工人阶级的先锋队，同时是中国人民和中华民族的先锋队。

按时间先后排序，蒙学教材出现的时间排序正确的是

上市公司股票的清算价格是()。

burdenofproof

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

A　word　processor　enables　you　to　create　a(70),　store　it　electronically　on　a　disk,　display　it　on　a　screen,　modify　it　by　entering　c

A　word　processor　enables　you　to　create　a(66),　store　it　electronically　on　a　disk,　display　it　on　a　screen,　modify　it　by　entering　c

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