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

admin2009-02-15 55

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

程序员上午基础知识考试

软考初级

某单位拟建立一个Intranet，建立自己的Web服务器、DNS服务器、Email服务器和内部业务服务器，有一批客户机联网，要求这些计算机有的可以连接到Internet，但只允许访问自己的Web服务器。请做出规划，解决如下问题。

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

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

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

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

该车道路面导向箭头指示前方道路仅可直行。

主板上芯片组中_______桥芯片是存储控制中心，用于调整连接CPU、内存条、显卡等部件。

医院内获得性肺炎，最常见的致病菌是

关于细菌毒力，正确的是

男性28岁因外伤致脾破裂，血压急剧下降，95/45mmHg，予紧急输血。约5分钟后患者突然出现烦躁不安，伴寒战、胸闷，腰背剧痛，皮肤发绀，呼吸困难。立即停止输血

职业道德一般由行业协会或专业资格认证机构制订、监督执行，它没有法律法规宽泛严格。()

唯物辩证法要求我们坚持两点论与重点论相统一的方法。下列说法体现这一方法的是()。

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

程序员上午基础知识考试

软考初级

某单位拟建立一个Intranet，建立自己的Web服务器、DNS服务器、Email服务器和内部业务服务器，有一批客户机联网，要求这些计算机有的可以连接到Internet，但只允许访问自己的Web服务器。请做出规划，解决如下问题。

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

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

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

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

该车道路面导向箭头指示前方道路仅可直行。

主板上芯片组中_______桥芯片是存储控制中心，用于调整连接CPU、内存条、显卡等部件。

医院内获得性肺炎，最常见的致病菌是

关于细菌毒力，正确的是

男性28岁因外伤致脾破裂，血压急剧下降，95/45mmHg，予紧急输血。约5分钟后患者突然出现烦躁不安，伴寒战、胸闷，腰背剧痛，皮肤发绀，呼吸困难。立即停止输血

职业道德一般由行业协会或专业资格认证机构制订、监督执行，它没有法律法规宽泛严格。()

唯物辩证法要求我们坚持两点论与重点论相统一的方法。下列说法体现这一方法的是()。

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

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

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