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

admin2009-02-15 38

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

程序员上午基础知识考试

软考初级

FTP协议属于TCP/IP模型中的(1)协议，基于TCP协议在客户端和服务器之间传送所有数据，TCP是一个(2)的协议，其主要特点是(3)，这对于文件传输而言是非常重要的。其中(1)、(2)备选答案：(1)A．应用层B．传输层C．

设置Windows2000的网络属性及添加常用服务(DNS服务和DHCP服务)。Windows2000常用服务：(1)DNS(DomainNameSystem)：域名系统。它为Internet(因特网)上的计算机提供名称(如“www.ab

Internet的服务有哪几种?电子邮件地址的格式是怎样规定的?

Photoshop图像处理软件能够生成PSD、BMP、TIFF、GIF和JPEG格式的图像文件。这些图像文件可以为Flash、Authorware、PowerPoint等多媒体工具软件提供素材。在上述图像文件格式中，哪种格式可以保存图层、通道等图像

WindowsNT中，启动系统的选择由文件Boot.ini来设定。假设某台PC机上，文件Boot.ini的内容如下：[bootloader]timeout=30default=multi(0)disk(0)rdisk(0)Par

为支持网络管理工作站进行SNMP管理，在交换机1中需要完成哪些配置工作?将snmputil复制到该网络管理工作站的操作系统C:/windows/system32目录中。在cmd窗口中输入查询本机系统组变量sysDesc的命令是：snmputilget

(69)is　permanently　stored　in　the　computer　and　provides　a　link　between　the　hardware　and　other　programs　that　run　on　the　PC.

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

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

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

A．抽查检验B．注册检验C．指定检验D．委托检验E．进口检验药品生产企业药品经指定的药品检验所检验才能出厂的检验属于

国华药业有限责任公司是国有独资公司，其董事长应当由以下何种方式产生?()

零售商业物业现场管理计划的费用测算中，设施维护费约占总费用的()。

为了适应我国社会主义市场经济发展和公共行政管理系统对自身财务行政活动实行规范化、制度化管理的需要，近年来我国政府逐渐推广了政府采购制度。政府采购的主要方式是()。

假设某射手的命中率为P(0＜P＜1)，他一次一次地对同一目标独立地射击直到恰好两次命中目标为止，以X表示首次命中已射击的次数，以Y表示射击的总次数，试求：随机变量Y关于X的条件概率分布；

某二叉树的中序序列为DCBAEFG，后序序列为DCBGFEA，则该二叉树的深度（根结点在第1层）为（）。

ThetownofRudbarhadceasedtoexist,withonlyskeletonsofbuildingsremaining.Theunderlinedpartmeans______.

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

程序员上午基础知识考试

软考初级

FTP协议属于TCP/IP模型中的(1)协议，基于TCP协议在客户端和服务器之间传送所有数据，TCP是一个(2)的协议，其主要特点是(3)，这对于文件传输而言是非常重要的。其中(1)、(2)备选答案：(1)A．应用层B．传输层C．

设置Windows2000的网络属性及添加常用服务(DNS服务和DHCP服务)。Windows2000常用服务：(1)DNS(DomainNameSystem)：域名系统。它为Internet(因特网)上的计算机提供名称(如“www.ab

Internet的服务有哪几种?电子邮件地址的格式是怎样规定的?

Photoshop图像处理软件能够生成PSD、BMP、TIFF、GIF和JPEG格式的图像文件。这些图像文件可以为Flash、Authorware、PowerPoint等多媒体工具软件提供素材。在上述图像文件格式中，哪种格式可以保存图层、通道等图像

WindowsNT中，启动系统的选择由文件Boot.ini来设定。假设某台PC机上，文件Boot.ini的内容如下：[bootloader]timeout=30default=multi(0)disk(0)rdisk(0)Par

为支持网络管理工作站进行SNMP管理，在交换机1中需要完成哪些配置工作?将snmputil复制到该网络管理工作站的操作系统C:/windows/system32目录中。在cmd窗口中输入查询本机系统组变量sysDesc的命令是：snmputilget

(69)is permanently stored in the computer and provides a link between the hardware and other programs that run on the PC.

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

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

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

A．抽查检验B．注册检验C．指定检验D．委托检验E．进口检验药品生产企业药品经指定的药品检验所检验才能出厂的检验属于

国华药业有限责任公司是国有独资公司，其董事长应当由以下何种方式产生?()

零售商业物业现场管理计划的费用测算中，设施维护费约占总费用的()。

为了适应我国社会主义市场经济发展和公共行政管理系统对自身财务行政活动实行规范化、制度化管理的需要，近年来我国政府逐渐推广了政府采购制度。政府采购的主要方式是()。

假设某射手的命中率为P(0＜P＜1)，他一次一次地对同一目标独立地射击直到恰好两次命中目标为止，以X表示首次命中已射击的次数，以Y表示射击的总次数，试求：随机变量Y关于X的条件概率分布；

某二叉树的中序序列为DCBAEFG，后序序列为DCBGFEA，则该二叉树的深度（根结点在第1层）为（）。

ThetownofRudbarhadceasedtoexist,withonlyskeletonsofbuildingsremaining.Theunderlinedpartmeans______.

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

(69)is　permanently　stored　in　the　computer　and　provides　a　link　between　the　hardware　and　other　programs　that　run　on　the　PC.

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

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