设求解某问题的递归算法如下: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
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
计算N!的递归算法如下,求解该算法的时间复杂度时,只考虑相乘操作,则算法的计算时间T(n)的递推关系式为(55);对应时间复杂度为(56)。
int Factorial (int n)
{//计算n!
if(n<=1)return 1;
else return n * Factorial(n-1);
}
(62)
A.T(n)=T(n-1)+1
B.T(n)=T(n-1)
C.T(n)=2T(n-1)+1
D.T(n)=2T(n-1)-1
斐波那契(Fibonacci)数列可以递归地定义为:
用递归算法求解F(5)时需要执行(63)次“+”运算,该方法采用的算法策略是(64)。
A.5
B.6
C.7
D.8
●若一个问题的求解既可以用递归算法,也可以用递推算法,则往往用 (26) 算法,因为 (27) 。
(26) A.先递归后递推
B.先递推后递归
C.递归
D.递推
(27) A.递推的效率比递归高
B.递归宜于问题分解
C.递归的效率比递推高
若一个问题的求解既可以用递归算法,也可以用递推算法,则往往用(14)算法,因为(15)。
A.先递归后递推
B.先递推后递归
C.递归
D.递推
● 斐波那契(Fibonacci)数列可以递归地定义为:
?
用递归算法求解F(5)时需要执行 (63) 次“+”运算,该方法采用的算法策略是 (64) 。
(63)
A. 5
B. 6
C. 7
D. 8
(64)
A. 动态规划
B. 分治
C. 回溯
D. 分支限界
阅读以下算法说明,根据要求回答问题1~问题3。
[说明]
快速排序是一种典型的分治算法。采用快速排序对数组A[p..r]排序的3个步骤如下。
1.分解:选择一个枢轴(pivot)元素划分数组。将数组A[p..r]划分为两个子数组(可能为空)A[p..q-1]和A[q+1..r],使得A[q]大于等于A[p..q-1]中的每个元素,小于A[q+1..r]中的每个元素。q的值在划分过程中计算。
2.递归求解:通过递归的调用快速排序,对子数组A[p..q-1]和A[q+1..r]分别排序。
3.合并:快速排序在原地排序,故无需合并操作。
下面是快速排序的伪代码,请将空缺处(1)~(3)的内容填写完整。伪代码中的主要变量说明如下。
A:待排序数组
p,r:数组元素下标,从p到r
q:划分的位置
x:枢轴元素
i:整型变量,用于描述数组下标。下标小于或等于i的元素的值,小于或等于枢轴元素的值
j:循环控制变量,表示数组元素下标
已知递归函数f的定义如下:
int f(int n)
{
if(n <=1)return 1; //递归结束情况
else return n*f(n-2); //递归}
则函数调用语句f(5)的返回值是【 】。
设有一个递归算法如下: int fact(int n){ if(n<=0)return 1; else return n*fact(n-1); } 下面正确的叙述是(35)。
A.计算fact(n)需要执行n次函数调用
B.计算fact(n)需要执行n+1次函数调用
C.计算fact(n)需要执行n+2次函数调用
D.计算fact(n)需要执行n-1次函数调用
(8 )已知递归函数 f 的定义如下:
int f(int n)
{
if (n <= 1) return 1; // 递归结束情况
else return n * f(n-2); // 递归 }
则函数调用语句 f(5) 的返回值是 【 8 】 。
设有一个递归算法如下 im fact(int n){ if(n<=0)return 1; else return n * fact(n-1); } 下面正确的叙述是(35)。
A.计算fact(n)需要执行n次函数调用
B.计算fact(n)需要执行n+1次函数调用
C.计算fact(n)需要执行n+2次函数调用
D.计算fact(n)需要执行n-1次函数调用