首页 › 题库 › GESP编程能力等级认证 › 5.1 递推思想

GESP-C++四级 题库

共 13 道题 · 按题型筛选,点「查看答案」核对解析
章节 5.1 递推思想 清除
1 单选题 适中 GESP编程能力等级认证 ·GESP-C++四级 · 5.1 递推思想

以下关于递推算法基本思想的描述,正确的是?( )

A
递推算法通过将问题分解为相互独立的子问题来解决。
B
递推算法从已知的基础情况出发,通过某种关系逐步推导出更大规模问题的解。
C
递推算法通常用于穷举所有可能的解决方案。
D
递推算法适用于在每一步做出局部最优选择以达到全局最优。
答案与解析
正确答案:B

选项A,是分治;

选项C,是枚举;

选项D,是贪心;

本题答案为选项B。

题目详情
2 单选题 适中 GESP编程能力等级认证 ·GESP-C++四级 · 5.1 递推思想

小杨正在爬楼梯,需要爬n 阶才能到达楼顶。如果每次可以爬 1个或 2个台阶,下面代码采用递推算法来 计算 —共有多少种不同的方法可以爬到楼顶,则横线上应填写( )。

int f(int n) {
	if (n == 1 || n == 2)
		return n;
	int f1 = 1;
	int f2 = 2;
	int res = 0;
	for (int i = 3; i <= n; i++) {
		_________________________________     // 在此处填入代码
	}
	return res;
}
A
res += f1 + f2;
f1 = f2;
f2 = res;
B
res = f1 + f2;
f1 = f2;
f2 = res;
C
res += f1 + f2;
f2 = res;
f1 = f2;
D
res = f1 + f2;
f2 = res;
f1 = f2;
答案与解析
正确答案:B

res表示当前到达第i层的方法数, f1表示到达前—层的方法数, f2表示到达上—层的方法数,所以本题选 择B 。

题目详情
3 单选题 适中 GESP编程能力等级认证 ·GESP-C++四级 · 5.1 递推思想

下面代码采用递推算法来计算斐波那契数列 f(n)=f(n−1)+f(n−2),则横线上应填写( )。

int fib(int n) {
	if (n == 0 || n == 1)
		return n;
	
	int f1 = 0;
	int f2 = 1;
	int result = 0;
	for (int i = 2; i <= n; i++) {
		________________________________ // 在此处填入代码
	}
	return result;
}
A
result = f1 + f2;
f1 = f2;
f2 = result;
B
result += f1 + f2;
f1 = f2;
f2 = result;
C
result += f1 + f2;
f2 = result;
f1 = f2;
D
result = f1 + f2;
f2 = result;
f1 = f2;
答案与解析
正确答案:A
这道题暂未补解析。
题目详情
4 单选题 适中 GESP编程能力等级认证 ·GESP-C++四级 · 5.1 递推思想

下面代码采用递推算法来实现整数 n 的阶乘 (ni=n×(n−1)×...×2×1),则横线上应填写( )。

int factorial(int n) {
	int result = 1;
	for (int i = 2; i <= n; i++) {
		________________________________ // 在此处填入代码
	}
	return result;
}
A
result *= i;
B
result += i;
C
result *= result;
D
result += result;
答案与解析
正确答案:A

阶乘的定义是:n! = n * (n-1) * (n-2) * … * 1。

在循环中,从2 到n,每次应将result 乘以当前的i,所以正确的填入应该是result *= i;。

题目详情
5 单选题 适中 GESP编程能力等级认证 ·GESP-C++四级 · 5.1 递推思想

下面关于递推的说法不正确的是( )。

A
递推表现为自己调用自己
B
递推是从简单问题出发,一步步的向前发展,最终求得问题。是正向的
C
递推中,问题的n要求是在计算中确定,不要求计算前就知道n
D
斐波那契数列可以用递推实现求解
答案与解析
正确答案:A

自己调用自己是递归的表现,而不是递推,注意区分。

题目详情
6 判断题 偏易 GESP编程能力等级认证 ·GESP-C++四级 · 5.1 递推思想

考虑用如下递推方式计算斐波那契数列,时间复杂度是 O(n)。

int n = 10; 
int f[20]; 
f[0] = 0; 
f[1] = 1; 
for (int i = 2; i <= n; i++) 
    f[i] = f[i - 1] + f[i - 2];
A
对
B
错
答案与解析
正确答案:对
使用数组存储斐波那契数列前n项,通过循环从第2项开始逐项计算,每一项由前两项相加得到。循环执行n-1次,每次操作时间复杂度为O(1),整体时间复杂度为O(n)。数组下标与数列项一一对应,初始值f[0]=0、f[1]=1作为递推起点。循环变量i从2开始递增至n,每次更新f[i] = f[i-1] + f[i-2],直至完成所有项的计算。
题目详情
7 判断题 偏易 GESP编程能力等级认证 ·GESP-C++四级 · 5.1 递推思想

递推是在给定初始条件下,已知前一项(或前几项)求后一项的过程。

A
对
B
错
答案与解析
正确答案:对
这道题暂未补解析。
题目详情
8 判断题 偏易 GESP编程能力等级认证 ·GESP-C++四级 · 5.1 递推思想

递推是—种通过已知的初始值和递推公式,逐步求解目标值的算法。

A
对
B
错
答案与解析
正确答案:对
这道题暂未补解析。
题目详情
9 判断题 偏易 GESP编程能力等级认证 ·GESP-C++四级 · 5.1 递推思想

递推是一种通过已知的初始值和递推公式,逐步求解目标值的算法。

A
对
B
错
答案与解析
正确答案:对
这道题暂未补解析。
题目详情
10 判断题 偏易 GESP编程能力等级认证 ·GESP-C++四级 · 5.1 递推思想

某算法的递推关系式为 T(n)=T(n−1)+n(n 为正整数)及 T(0)=1,则该算法的时间复杂度为 O(n2)。

A
对
B
错
答案与解析
正确答案:对
这道题暂未补解析。
题目详情
11 判断题 偏易 GESP编程能力等级认证 ·GESP-C++四级 · 5.1 递推思想

递推算法通过逐步求解当前状态和前一个或几个状态之间的关系来解决问题。

A
对
B
错
答案与解析
正确答案:对

递推算法通过利用已知的前一个或多个状态来逐步计算当前状态,从而解决问题。这种方法常用于动态规划和分治策略中,通过构建状态转移方程来有效地求解复杂问题。

题目详情
12 判断题 偏易 GESP编程能力等级认证 ·GESP-C++四级 · 5.1 递推思想

以下代码用递推法求斐波那契数列的第n 项,时间复杂度为指数级。

int fibonacci(int n) {
	if (n == 0) return 0;
	if (n == 1) return 1;
	
	int f0 = 0; // F(0)
	int f1 = 1; // F(1)
	int current;
	
	for (int i = 2; i <= n; i++) {
		current = f0+ f1; // F(n) = F(n-1) + F(n-2)
		f0 = f1;
		f1 = current;
	}
	
	return current;
}
A
对
B
错
答案与解析
正确答案:错

迭代的方式计算斐波那契数列,时间复杂度为线性O(n),而不是指数级O(2^n)

题目详情
13 判断题 偏易 GESP编程能力等级认证 ·GESP-C++四级 · 5.1 递推思想

数列 1, 1, 2, 3, 5, 8 ... 是以意大利数学家列昂纳多·斐波那契命名的数列,从第三个数开始,每个数是前面两项之和。如果计算该数列的第 n 项(其中 n>3)fib(n),我们采用如下方法:① 令 fib(1)=fib(2)=1 ②用循环 for i=3to n 分别计算 f(i) ③输出 fib(n)。这体现了递推的编程思想。

A
对
B
错
答案与解析
正确答案:对
这道题暂未补解析。
题目详情