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

admin2008-01-15  52
问题 设求解某问题的递归算法如下：
   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)=2n-1T(1)+，易知　T(1)=k，将n=4代入可得计算时间为15k。
转载请注明原文地址:https://www.kaotiyun.com/show/GbxZ777K
本试题收录于： 软件设计师上午基础知识考试题库软考中级分类
0

软件设计师上午基础知识考试

软考中级

相关试题推荐
随机试题
最新回复(0)