单选题 设求解某问题的递归算法如下：
void F(int n)
{
if(n==1) Move(1);
else
{
F(n-1);
Move(n);
F(n-1);
}
}
在求解该算法的计算时间时，仅考虑算法Move所做的计算，且Move为常数级算法。算法F的计算时间T(n)的递推关系式为______。
  • 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
【答案解析】[解析] 根据题目中程序代码的递归框架可知，该程序把一个规模为n的问题转化为两个规模为n-1的同样问题外加一个常量复杂度的操作来求解，因此其递推关系为T(n)=2T(n-1)+O(1)，可近似为T(n)=2T(n-1)+1。