首页 › 题库 › GESP编程能力等级认证 › 1 初等数论

GESP-C++五级 题库

共 130 道题 ,第 3 / 7 页 · 按题型筛选,点「查看答案」核对解析
章节 1 初等数论 清除
41 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 综合练习

对下面两个函数,说法错误的是( )。

int sumA(int n) {
	int res = 0;
	for (int i = 1; i <= n; i++) {
		res += i;
	}
	return res;
}

int sumB(int n) {
	if (n == 1)
		return 1;
	int res = n + sumB(n - 1);
	return res;
}


A
sumA体现了迭代的思想。
B
SumB采用的是递归方式。
C
SumB函数比SumA的时间效率更高。
D
两个函数的实现的功能相同。
答案与解析
正确答案:C

sumA函数是递推,sumB函数是递归,两个函数都是求的1~n的和,两个函数的时间复杂度基本一致,都是O(n)。

题目详情
42 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 1.3 同余与模运算

有如下函数 fun ,则 fun(20, 12) 的返回值为( )。

int fun(int a, int b) {
	if (a % b == 0)
		return b;
	else
		return fun(b, a % b);
}


A
20
B
12
C
4
D
2
答案与解析
正确答案:C

函数为辗转相除求两数的最大公约数,结果为4,如果没有看出函数作用,也可以手动模拟递归过程。

题目详情
43 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 1.1 素数与合数

下述代码实现素数表的埃拉托斯特尼筛法,筛选出所有小于等于 n 的素数,则横线上应填的最佳代码是( )。

void sieve_Eratosthenes(int n) {
	vector<bool> is_prime(n + 1, true);
	vector<int> primes;
	
	for (int i = 2; i * i <= n; i++) {
		if (is_prime[i]) {
			primes.push_back(i);
			________________________________ { // 在此处填入代码
				is_prime[j] = false;
			}
		}
	}
	
	for (int i = sqrt(n) + 1; i <= n; i++) {
		if (is_prime[i]) {
			primes.push_back(i);
		}
	}
	
	return primes;
}


A
for (int j = i; j <= n; j++)
B
for (int j = i * i; j <= n; j++)
C
for (int j = i * i; j <= n; j += i)
D
for (int j = i; j <= n; j += i)
答案与解析
正确答案:C
这道题暂未补解析。
题目详情
44 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 1.1 素数与合数

下述代码实现素数表的线性筛法,筛选出所有小于等于 n 的素数,则横线上应填的代码是( )。

vector<int> sieve_linear(int n) {
	vector<bool> is_prime(n + 1, true);
	vector<int> primes;
	
	for (int i = 2; i <= n / 2; i++) {
		if (is_prime[i])
			primes.push_back(i);
		________________________________ { // 在此处填入代码
			is_prime[i * primes[j]] = 0;
			if (i % primes[j] == 0)
				break;
		}
	}
	
	for (int i = n / 2 + 1; i <= n; i++) {
		if (is_prime[i])
			primes.push_back(i);
	}
	
	return primes;
}


A
for (int j = 0; j < primes.size() && i * primes[j] <= n; j++)
B
for (int j = 1; j < primes.size() && i * j <= n; j++)
C
for (int j = 2; j < primes.size() && i * primes[j] <= n; j++)
D
以上都不对
答案与解析
正确答案:A

这个地方是要枚举质数表,然后把质数的i倍数都筛掉,所以应该是选A。

题目详情
45 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 1.3 同余与模运算

现在有 n 个人要过河,每只船最多载2人,船的承重为100kg。下列代码中,数组 weight 中保存有 n 个人的体重(单位为kg),已经按从小到大排好序,代码输出过河所需要的船的数目,采用的思想为( )。

int i, j;
int count = 0;
for (i = 0, j = n - 1; i < j; j--) {
	if (weight[i] + weight[j] <= 100) {
		i++;
	}
	count++;
}
printf("过河的船数:%d\n", count);


A
枚举算法
B
贪心算法
C
迭代算法
D
递归算法
答案与解析
正确答案:B

重量已经按照从小到大排序了,然后双指针处理,双指针的过程为最轻的人和最重的人尝试能否在同一个船上,如果可以,那么他们在同一个船上,否则,当前最重的人不能和其他人在一个船上,得单独一条船。采用的是贪心的思想。

题目详情
46 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 综合练习

当n=7 时,下面函数的返回值为( )。

int fun(int n) {
	if (n == 1) return 1;
	else if (n >= 5) return n * fun(n - 2);
	else return n * fun(n - 1);
}


A
105
B
840
C
210
D
420
答案与解析
正确答案:C
这道题暂未补解析。
题目详情
47 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 1.3 同余与模运算

下面C++代码用于将输入金额换成最少币种组合方案,其实现算法是( )。

#include <iostream>
using namespace std;

#define N_COINS 7
int coins[N_COINS] = {100, 50, 20, 10, 5, 2, 1}; //货币面值,单位相同
int coins_used[N_COINS];

void find_coins(int money) {
	for (int i = 0; i < N_COINS; i++) {
		coins_used[i] = money / coins[i];
		money = money % coins[i];
	}
	return;
}
int main() {
	int money;
	cin >> money; //输入要换算的金额
	
	find_coins(money);
	for (int i = 0; i < N_COINS; i++)
		cout << coins_used[i] << endl;
		
	return 0;
}
A
枚举算法
B
贪心算法
C
迭代算法
D
递归算法
答案与解析
正确答案:B

贪心算法:贪心算法是一种在每一步选择中都采取当前状态下最优(最有利)的选择,以期望最终能够达到全局最优解。在这段代码中,每次循环都选择当前面值最大的硬币进行尽可能多的使用,从而达到最少硬币数量的组合方案。

算法实现分析:

数组coins 存储了面值从大到小的硬币面额{100, 50, 20, 10, 5, 2, 1}。

函数find_coins() 中使用了一个循环遍历所有硬币面额。在每次循环中,计算当前金额money 可以使用的当前面额硬币数量,并更新剩余金额money。

循环结束后,coins_used 数组存储了每种面额硬币的使用数量,以达到组合最少硬币数量的目的。

选择最优:由于每次都选择当前最大面额的硬币,贪心算法能够在保证每次选择最优的情况下,快速得到全局最优解,即使用最少数量的硬币来组合金额。

根据代码实现方式和贪心算法的特性,这段C++代码确实属于贪心算法。

题目详情

下面是根据欧几里得算法编写的函数,它计算的是 与 的( )。

int gcd(int a, int b) {
	while (b != 0) {
		int temp = b;
		b = a % b;
		a = temp;
	}
	return a;
}
A
最小公倍数
B
最大公共质因子
C
最大公约数
D
最小公共质因子
答案与解析
正确答案:C

欧几里得算法,也称为辗转相除法,用于计算两个非负整数的最大公约数。

在函数中,通过循环不断将b 更新为a 除以b 的余数,直到b 变为0。此时a 的值就是最大公约数。

函数最终返回的是变量a 的值,即为输入的两个整数a 和b 的最大公约数。

因此,根据给出的函数实现和算法特性,函数gcd(int a, int b) 计算的是两个整数的最大公约数。

所以,答案是C.最大公约数。

题目详情

欧几里得算法还可以写成如下形式:

int gcd(int a, int b) {
	return b == 0 ? a : gcd(b, a % b);
}

下面有关说法,错误的是( )。

A
本题的 gcd() 实现为递归方式。
B
本题的 gcd() 代码量少,更容易理解其辗转相除的思想。
C
当a较大时,本题的 gcd() 实现会多次调用自身,需要较多额外的辅助空间。
D
当a较大时,相比上题中的 gcd() 的实现,本题的 gcd() 执行效率更高。
答案与解析
正确答案:D

递归实现的gcd()函数并不比非递归实现的效率更高。两者的时间复杂度是相同的,选择使用哪种实现通常更依赖于个人或特定环境下的偏好或要求。

题目详情
50 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 1.1 素数与合数

下述代码实现素数表的线性筛法,筛选出所有小于等于 的素数,则横线上应填的代码是( )。

vector<int> linear_sieve(int n) {
	vector<bool> is_prime(n + 1, true);
	vector<int> primes;
	is_prime[0] = is_prime[1] = 0; //0和1两个数特殊处理
	for (int i = 2; i <= n; ++i) {
		if (is_prime[i]) {
			primes.push_back(i);
		}
		________________________________ { // 在此处填入代码
			is_prime[i * primes[j]] = 0;
			if (i % primes[j] == 0)
				break;
		}
	}
	return primes;
}
A
or (int j = 0; j < primes.size() && i * primes[j] <= n; j++)
B
for (int j = 0; j <= sqrt(n) && i * primes[j] <= n; j++)
C
for (int j = 0; j <= n; j++)
D
for (int j = 1; j <= sqrt(n); j++)
答案与解析
正确答案:A

使用for (int j = 0; j < primes.size() && i * primes[j] <= n; j++) 这个循环来遍历当前已知的素数列表primes,确保了我们使用当前素数i 来乘以已知素数primes[j],并且正确地筛选掉不超过n 的合数。

题目详情
51 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 综合练习

给定如下函数:

int fun(int n) {
	if (n == 1) return 1;
	if (n == 2) return 2;
	return fun(n - 2) - fun(n - 1);
}

则当 n = 7 n=7n=7 时,函数返回值为( )。

A
0
B
1
C
21
D
-11
答案与解析
正确答案:D

函数的计算过程:

fun(1) 的返回值是 1。

fun(2) 的返回值是 2。

对于其他 n >= 3 的情况,函数递归地计算 fun(n):

fun(3) = fun(1) - fun(2) = 1 - 2 = -1

fun(4) = fun(2) - fun(3) = 2 - (-1) = 3

fun(5) = fun(3) - fun(4) = (-1) - 3 = -4

fun(6) = fun(4) - fun(5) = 3 - (-4) = 7

fun(7) = fun(5) - fun(6) = -4 - 7 = -11

根据递归定义,我们可以看出 fun(n) 的计算是基于前两个值的递归差值。

现在来解决问题,当 n = 7 时,函数 fun(7) 返回的值是 -11。

因此,正确答案是 -11。

题目详情
52 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 综合练习

给定如下函数(函数功能同上题,增加输出打印):

int fun(int n) {
	cout << n << " ";
	if (n == 1) return 1;
	if (n == 2) return 2;
	return fun(n - 2) - fun(n - 1);
}

则当 n = 4 n=4n=4 时,屏幕上输出序列为( )。

A
4 3 2 1
B
1 2 3 4
C
4 2 3 1 2
D
4 2 3 2 1
答案与解析
正确答案:C

分析函数调用过程:

当n = 4 时,函数调用fun(4):

fun(4) 输出4,然后计算fun(2) - fun(3)。输出顺序为4。

fun(2) 输出2,然后返回2。输出顺序为4 2。

fun(3) 输出3,然后计算fun(1) - fun(2)。输出顺序为4 2 3.

fun(1) 输出1,然后返回1。输出顺序为4 2 3 1.

fun(2) 返回2,因为已经计算过,不再输出。输出顺序为4 2 3 1 2.

计算fun(3) = 1 - 2 = -1,返回-1。输出顺序为4 2 3 1 2.

计算fun(4) = 2 - (-1) = 3,返回3。输出顺序为4 2 3 1 2 4.

结论:

因此,当n = 4 时,屏幕上输出的序列是 4 2 3 1 2。

题目详情
53 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 1.4 质因数分解

唯一分解定理描述的内容是(   )?

A
任意整数都可以分解为素数的乘积
B
每个合数都可以唯一分解为一系列素数的乘积
C
两个不同的整数可以分解为相同的素数乘积
D
以上都不对
答案与解析
正确答案:B
这道题暂未补解析。
题目详情
54 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 综合练习

下面的 C++ 代码片段用于计算阶乘。请在横线处填入(   ),实现正确的阶乘计算。

int factorial(int n) {
	if (n == 0 || n == 1) {
		return 1;
	} else {
		_________________________________ // 在此处填入代码
	}
}
A
return n * factorial(n - 1);
B
return factorial(n - 1) / n;
C
return n * factorial(n);
D
return factorial(n / 2) * factorial(n / 2);
答案与解析
正确答案:A
这道题暂未补解析。
题目详情

辗转相除法也被称为(   )

A
高斯消元法
B
费马定理
C
欧几里德算法
D
牛顿迭代法
答案与解析
正确答案:C
这道题暂未补解析。
题目详情
56 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 1.1 素数与合数

下面的代码片段用于判断一个正整数是否为素数。请对以下代码进行修改,使其能正确实现相应功能。(   )

bool isPrime(int num) {
	if (num < 2) {
		return false;
	}
	for (int i = 2; i * i < num; ++i) {
		if (num % i == 0) {
			return false;
		}
	}
	return true;
}
A
num < 2 应该改为 num <= 2
B
循环条件 i * i < num 应该改为 i * i <= num
C
循环条件应该是 i <= num
D
循环体中应该是 if (num % i != 0)
答案与解析
正确答案:B
这道题暂未补解析。
题目详情
57 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 1.1 素数与合数

在埃拉托斯特尼筛法中,要筛选出不大于 n 的所有素数,最外层循环应该遍历什么范围(   )?

vector<int> sieveOfEratosthenes(int n) {
	std::vector<bool> isPrime(n + 1, true);
	std::vector<int> primes;
	_______________________ {
		if (isPrime[i]) {
			primes.push_back(i);
			for (int j = i * i; j <= n; j += i) {
				isPrime[j] = false;
			}
		}
	}
	for (int i = sqrt(n) + 1; i <= n; ++i) {
		if (isPrime[i]) {
			primes.push_back(i);
		}
	}
	return primes;
}
A
for (int i = 2; i <= n; ++i)
B
for (int i = 1; i < n; ++i)
C
for (int i = 2; i <= sqrt(n); ++i)
D
for (int i = 1; i <= sqrt(n); ++i)
答案与解析
正确答案:C
这道题暂未补解析。
题目详情
58 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 1.1 素数与合数

素数的线性筛法时间复杂度为(   )。

A
O(n)
B
O(nloglogn)
C
O(nlogn)
D
O(n2)
答案与解析
正确答案:A
这道题暂未补解析。
题目详情
59 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 综合练习

下面C++代码用于求斐波那契数列,该数列第1、2项为1,以后各项均是前两项之和。下面有关说法错误的是(   )。

A

fiboA( ) 用递归方式, fiboB() 循环方式

B

fiboA( ) 更加符合斐波那契数列的数学定义,直观易于理解,而 fiboB() 需要将数学定义转换为计算机程序实现

C

fiboA( ) 不仅仅更加符合数学定义,直观易于理解,且因代码量较少执行效率更高

D

fiboB( ) 虽然代码量有所增加,但其执行效率更高

答案与解析
正确答案:C
这道题暂未补解析。
题目详情
60 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 综合练习

阅读下面的C++代码,执行后其输出是(   )。

A

1->120<===>2->120

B

1->120<===>1->120

C

1->120<===>1->2->3->4->5->120

D

1->120<===>2->3->4->5->6->120

答案与解析
正确答案:D
这道题暂未补解析。
题目详情