问题
单项选择题
设求解某问题的递归算法如下：
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[*]2i，易知T(1)=k，将n=5代入可得T(n)=2n-1T(1)+k[*]2i=25-1k+k[*]2i=24k+(20+21+22+23)k=31k。