首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
设求解某问题的递归算法如下: F(int n){ if(n=-=1){ Move(1); }else{ F(n-1); Move(n);
设求解某问题的递归算法如下: F(int n){ if(n=-=1){ Move(1); }else{ F(n-1); Move(n);
admin
2008-01-15
56
问题
设求解某问题的递归算法如下:
F(int n){
if(n=-=1){
Move(1);
}else{
F(n-1);
Move(n);
F(n-1);
}
}
求解该算法的计算时间时,仅考虑算法Move所做的计算为主要计算,且Move为常数级算法。则算法F的计算时间T(n)的递推关系式为(53):设算法Move的计算时间为k,当n=4时,算法F的计算时间为(54)。
选项
A、T(n)=T(n-1)+1
B、T(n)=2T(n-1)
C、T(n)=2T(n-1)+1
D、T(n)=2T(n+1)+1
答案
C
解析
本题考查对计算杉1算法进行时间复杂度分析的基本方法。直接递归算法的计算时间可以根据递归调用形式对应写出其递推关系式。按照题目中描述的算法形式,可知算法F的计算时间T(n)的递推关系式为T(n)=2T(n-1)+1,其中两次递归调用F(n-1)用时2T(n-1),算法Move的计算时间为常数,计为1。将上述递推关系式中常数1用k替换,求解可得T(n)=2
n-1
T(1)+
,易知 T(1)=k,将n=4代入可得计算时间为15k。
转载请注明原文地址:https://kaotiyun.com/show/GbxZ777K
本试题收录于:
软件设计师上午基础知识考试题库软考中级分类
0
软件设计师上午基础知识考试
软考中级
相关试题推荐
在Linux系统中,DHcP服务默认的配置文件为:(1)。(1)备选答案:A./etc/dhcpd.confB./etc/dhcpd.configC./etc/dhcpc.confD./etc/dhcp.config在Lin
网络A的WWw服务器上建立了一个Web站点,对应的域名是www.abc.edu。DNS服务器1上安装WindowsServer2003操作系统并启用DNS服务。为了解析www服务器的域名,在所示的对话框中,新建一个区域的名称是(1);在图6—4所示的对
根据该网络的需求,防火墙至少需要(14)个百兆接口和(15)个千兆接口。(15)
在客户端可以通过______来测试到Web网站的连通性。A.ping62.35.216.12 B.ping62.35.216.7C.pingmail.test.com D.pingns7.test.com
关于曼彻斯特编码,下面叙述中错误的是(14)。
在某个支持SNMPv2MIB组的代理中,snmpSerialNo对象的当前值为2006。这时,该代理站同时收到两个管理站发来的set请求,这两个set请求的snmpSerialNo值都是2006,当代理站处理完这两个set请求后,其snmpSerialN
收到数据报时,如果本结点是路由结点,则需要(51)。
Virtualization is an approach to IT that pools and shares(71)so that utilization is optimized and supplies automatically meet de
VirtualizationisanapproachtoITthatpoolsandshares(1)sothatutilizationisoptimizedandsuppliesautomaticallymeetd
随机试题
颈鞘由
A.CPEB.CCHFC.TCID50D.LD50E.HFRS与所列英文缩写相对应的是半数细胞培养物感染量
下列关于进出口交易磋商形式说法错误的是:()。
“发展社会生产力是社会主义的根本任务”是由以下哪几种因素决定的?()
一、注意事项1.本试卷由给定资料与作答要求两部分构成。考试时限150分钟。满分100分。2.作答参考时限:阅读资料40分钟作答110分钟。3.仔细阅读给定资料,按作答要求依次作答。答案要写在指定位置。不在指定位置作答的,不得分。4.
某学业成就测验由100道正误题组成,每题1分。如果要从统计上(99%的把握)排除猜测作答的情形,考生正确回答的题目数量至少应该是
WhydidthegirlinviteUncleSmithtodinner?
Theviewthat"whereL1andL2aresimilar,positivetransferwouldoccur,otherwise,negativetransferwouldresult"isderived
Theyhaveconsideredtheirhighstandardoflivinga(n)______forpracticingtheirbasicbeliefs.
Whenyoudrivehome,youcan’tbe______careful.
最新回复
(
0
)