首页 › 题库 › GESP编程能力等级认证 › GESP-C++五级

GESP-C++五级 题库

共 297 道题 ,第 5 / 15 页 · 按题型筛选,点「查看答案」核对解析
81 单选题 适中 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。

题目详情
82 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 2.1 多项式复杂度

下面函数可以将 n 的所有质因数找出来,其时间复杂度是( )。

#include <iostream>
#include <vector>

vector<int> get_prime_factors(int n) {
	vector<int> factors;
	
	while (n % 2 == 0) {
		factors.push_back(2);
		n /= 2;
	}
	
	for (int i = 3; i * i <= n; i += 2) {
		while (n % i == 0) {
			factors.push_back(i);
			n /= i;
		}
	}
	
	if (n > 2) {
		factors.push_back(n);
	}
	
	return factors;
}


A
O(n2)
B
O(nlogn)
C
D
O(n)
答案与解析
正确答案:C
这道题暂未补解析。
题目详情
83 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 2.1 多项式复杂度

现在用如下代码来计算xn(n个x相乘),其时间复杂度为( )。

double quick_power(double x, unsigned n) {
	if (n == 0) return 1;
	if (n == 1) return x;
	return quick_power(x, n / 2) * quick_power(x, n / 2) * ((n & 1) ? x : 1);
}


A
O(n)
B
O(n2)
C
O(logn)
D
O(nlogn)
答案与解析
正确答案:A
这道题暂未补解析。
题目详情
84 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 7.2 快速排序

假设快速排序算法的输入是一个长度为 n 的已排序数组,且该快速排序算法在分治过程总是选择第一个元素作为基准元素。下面选项( )描述的是在这种情况下的快速排序行为。

A
快速排序对于此类输入的表现最好,因为数组已经排序。
B
快速排序对于此类输入的时间复杂度是 O(nlogn)。
C
快速排序对于此类输入的时间复杂度是O(n2)。
D
快速排序无法对此类数组进行排序,因为数组已经排序。
答案与解析
正确答案:C

快速排序的过程是,每次选择一个基准值,比基准值大的放到它的右边 ,比基准值小的放到它的左边,但是这个序列是一个有序序列,且每次都是选择最小的元素作为基准值,所以每次所有的值都会放到基准值的右边,也就是说,每次都只是把基准值这个位置排序好。

题目详情
85 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 7.1 归并排序

考虑以下C++代码实现的归并排序算法:

void merge(int arr[], int left, int mid, int right) {
	int n1 = mid - left + 1;
	int n2 = right - mid;
	
	int L[n1], R[n2];
	
	for (int i = 0; i < n1; i++)
		L[i] = arr[left + i];
	for (int j = 0; j < n2; j++)
		R[j] = arr[mid + 1 + j];
		
	int i = 0, j = 0, k = left;
	while (i < n1 && j < n2) {
		if (L[i] <= R[j]) {
			arr[k] = L[i];
			i++;
		}
		else {
			arr[k] = R[j];
			j++;
		}
		k++;
	}
	
	while (i < n1) {
		arr[k] = L[i];
		i++;
		k++;
	}
	
	while (j < n2) {
		arr[k] = R[j];
		j++;
		k++;
	}
}

void merge_sort(int arr[], int left, int right) {
	if (left < right) {
		int mid = left + (right - left) / 2;
		
		merge_sort(arr, left, mid);
		merge_sort(arr, mid + 1, right);
		
		merge(arr, left, mid, right);
	}
}

对长度为 n 的数组 arr ,挑用函数 merge_sort(a, 0, n-1) ,在排序过程中 merge 函数的递归调用次数大约是( )。

A
O(1)
B
O(n)
C
O(logn)
D
O(nlogn)
答案与解析
正确答案:B

merge_sort函数的作用是递归进行分治的过程,每次把序列分成两半,然后分别处理,merge函数的作用是把两个有序序列,通过双指针操作,合并为一个有序序列。merge函数的调用次数,先是两个数的合并,执行次数为n/2,然后是4个数合并,执行次数为n/4……大约为O(n)

题目详情
86 单选题 适中 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

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

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

关于分治算法,以下哪个说法正确?

A
分治算法将问题分成子问题,然后分别解决子问题,最后合并结果。(2024.9-5)
B
归并排序不是分治算法的应用。
C
分治算法通常用于解决小规模问题。
D
分治算法的时间复杂度总是优于 O(nlog(n))。
答案与解析
正确答案:A

分治算法的思想就是把问题划分成子问题,然后继续划分,知道子问题可以直接解决,然后合并子问题得到的结果,推到原问题的答案。

B选项:归并排序的思想就是分治。

D选项:分治算法划分子问题的时间一般为logn,总的时间复杂度常为O(nlogn),如归并排序。

题目详情
88 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 5.1 二分查找

根据下述二分查找法,在排好序的数组 1,3,6,9,17,31,39,52,61,79 中查找数值 31 ,循环while (left <= right) 执行的次数为( )。

int binary_search(vector<int>& nums, int target) {
	int left = 0;
	int right = nums.size() - 1;
	
	while (left <= right) {
		int mid = left + (right - left) / 2;
		
		if (nums[mid] == target) {
			return mid;
		}
		else if (nums[mid] < target) {
			left = mid + 1;
		}
		else {
			right = mid - 1;
		}
	}
	
	return -1; // 如果找不到目标元素,返回-1
}


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

模拟即可,

第一次:mid=5,nums[5]=17,此时小于要查找的31,所以left=6。

第二次:mid=8,nums[8]=52,此时大于要查找的31,所以right=7。

第三次:mid=6,nums[6]=31,找到要查找的值,结束。

题目详情
89 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 3.1 高精度加法

以下关于高精度运算的说法错误的是( )。

A
高精度计算主要是用来处理大整数或需要保留多位小数的运算。
B
大整数除以小整数的处理的步骤可以是,将被除数和除数对齐,从左到右逐位尝试将除数乘以某个数,通过减法得到新的被除数,并累加商。
C
高精度乘法的运算时间只与参与运算的两个整数中长度较长者的位数有关。
D
高精度加法运算的关键在于逐位相加并处理进位。
答案与解析
正确答案:C

C选项,高精度的乘法,运算时间和两个整数的长度之和有关,两个长度分别为len1和len2的整数相乘,结果的长度至少为len1+len2。

题目详情
90 单选题 适中 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
这道题暂未补解析。
题目详情
91 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 4.1 单链表

下面C++代码用于求斐波那契数列,该数列第1、2项为1,以后各项均是前两项之和。函数fibo()属于( )。

int fibo(int n) {
	if (n <= 0)
		return 0;
	if (n == 1 || n == 2)
		return 1;
		
	int a = 1,b = 1, next;
	for (int i = 3; i <= n; i++) {
		next = a + b;
		a = b;
		b = next;
	}
	return next;
}
A
枚举算法
B
贪心算法
C
迭代算法
D
递归算法
答案与解析
正确答案:C

迭代算法:迭代算法是通过循环实现的,每次迭代利用前面计算的结果来推导出下一个结果。在给定的C++代码中,使用了一个循环for (int i = 3; i <= n; i++) 来计算斐波那契数列第n 项的值,通过迭代更新a 和b的值,直到计算出第n 项的值并返回。

题目详情
92 单选题 适中 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++代码确实属于贪心算法。

题目详情
93 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 2.1 多项式复杂度

小杨采用如下双链表结构保存他喜欢的歌曲列表:

struct dl_node {
	string song;
	dl_node* next;
	dl_node* prev;
};

小杨想在头指针为 head 的双链表中查找他喜欢的某首歌曲,采用如下查询函数,该操作的时间复杂度为( )。

dl_node* search(dl_node* head, string my_song) {
	dl_node* temp = head;
	while (temp != nullptr) {
		if (temp->song == my_song)
			return temp;
		temp = temp->next;
	}
	return nullptr;
}
A
O(1)
B
O(n)
C
O(logn)
D
O(n2)
答案与解析
正确答案:B

该查询函数的时间复杂度为O(n),其中n是双链表中节点的数量。

函数使用一个指针temp从头指针head开始,沿着双链表向后遍历。

在每个节点处,它检查节点中的歌曲名称是否与目标歌曲my_song匹配。

最坏情况下,如果目标歌曲不在双链表中或者在最后一个节点才找到,那么需要遍历整个双链表,因此时间复杂度为O(n)

这是因为在最坏情况下,需要遍历所有n个节点才能确定目标歌曲是否存在。

题目详情
94 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 4.1 单链表

小杨想在如上题所述的双向链表中加入一首新歌曲。为了能快速找到该歌曲,他将其作为链表的第一首歌曲,则下面横线上应填入的代码为( )。

void insert(dl_node *head, string my_song) {
	p = new dl_node;
	p->song = my_song;
	p->prev = nullptr;
	p->next = head;
	
	if (head != nullptr) {
		________________________________ // 在此处填入代码
	}
	head = p;
}
A
head->next->prev = p;
B
head->next = p;
C
head->prev = p;
D
触发异常,不能对空指针进行操作。
答案与解析
正确答案:C

在将p 插入后,先前的头节点(head)必须更新其prev 指针,指向新的头节点p,以保持双向链表的结构:

p->next 指向先前的头节点head。head->prev 指向新的头节点p。

题目详情

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

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

题目详情
97 单选题 适中 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 的合数。

题目详情
98 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 2.1 多项式复杂度

上题代码的时间复杂度是( )。

A
O(n2)
B
O(nlogn)
C
O(nloglogn)
D
O(n)
答案与解析
正确答案:D

linear_sieve 函数的主要执行部分是主循环,(for (int i = 2; i <= n; ++i)):主循环从2到n进行遍历,因此有O(n)次迭代

题目详情
99 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 7.2 快速排序

为了正确实现快速排序,下面横线上的代码应为( )。

void qsort(vector<int>& arr, int left, int right) {
	int i, j, mid;
	int pivot;
	
	i = left;
	j = right;
	mid = (left + right) / 2; // 计算中间元素的索引
	pivot = arr[mid]; // 选择中间元素作为基准值
	
	do {
		while (arr[i] < pivot) i++;
		while (arr[j] > pivot) j--;
		if (i <= j) {
			swap(arr[i], arr[j]); // 交换两个元素
			i++; j--;
		}
	} ________________________________; // 在此处填入代码
	if (left < j) qsort(arr, left, j); // 对左子数组进行快速排序
	if (i < right) qsort(arr, i, right); // 对右子数组进行快速排序
}
A
while (i <= mid)
B
while (i < mid)
C
while (i < j)
D
while (i <= j)
答案与解析
正确答案:D

快速排序的分区过程中,我们使用两个指针i和j分别从左到右和从右到左遍历数组,将小于基准值的元素放到基准值的左边,大于基准值的元素放到右边。

具体的分区过程如下:

首先选择一个基准值pivot,通常选择中间元素arr[mid]。

使用两个指针i和j,分别从数组的左右两端开始向中间移动。

i从左向右移动,直到找到一个大于或等于pivot的元素。

j从右向左移动,直到找到一个小于或等于pivot的元素。

如果i <= j,则交换arr[i]和arr[j],然后i向后移动一位,j向前移动一位。

重复步骤2和3,直到i大于j,此时所有小于等于pivot的元素都在pivot的左边,所有大于等于pivot的元素都在pivot的右边。

在填写横线上的代码时,应该使用while (i <= j),因为分区过程应该持续进行直到i超过j,这样保证了整个分区过程的完成。

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

关于分治算法,以下哪个说法正确?

A
分治算法将问题分成子问题,然后分别解决子问题,最后合并结果。
B
归并排序不是分治算法的应用。
C
分治算法通常用于解决小规模问题。
D
分治算法的时间复杂度总是优于 O(nlog(n))。
答案与解析
正确答案:A

分治算法的基本思想是将原问题分解成若干个规模较小但结构与原问题相似的子问题,递归地求解这些子问题,然后再合并其结果,得到原问题的解。

题目详情