首页 › 试卷 › GESP编程能力等级认证 › GESP-C++五级 › 2024年9月CCF-GESP编程能力等级认证C++编程五级真题

2024年9月CCF-GESP编程能力等级认证C++编程五级真题 VIP

GESP-C++五级 共 27 题 2024 年 含标准答案与解析
返回试卷列表
本页为整卷浏览:先自己做一遍,再展开「查看答案与解析」核对。

一、单选题

1. 单选题

下面关于链表和数组的描述,错误的是( )。

  • A 数组大小固定,链表大小可动态调整。
  • B 数组支持随机访问,链表只能顺序访问。
  • C 存储相同数目的整数,数组比链表所需的内存多。
  • D

    数组插入和删除元素效率低,链表插入和删除元素效率高。

查看答案与解析
答案:C
解析:

存储相同数目的整数的时候,数组用的内存应该是更少的,因为数组不需要记录下一个值的地址。

2. 单选题

通过( )操作,能完成在双向循环链表结点 p 之后插入结点 s 的功能(其中 next 域为结点的直接后继,prev 域为结点的直接前驱)。

  • A p->next->prev = s; s->prev = p; p->next = s; s->next = p->next;
  • B p->next->prev = s; p->next = s; s->prev = p; s->next = p->next;
  • C s->prev = p; s->next = p->next; p->next = s; p->next->prev = s;
  • D s->next = p->next; p->next->prev = s; s->prev = p; p->next = s;
查看答案与解析
答案:D
解析:

A选项最后一句,此时p->next已经变成了s,所以错了

B选项最后一句,此时p->next已经变成了s,所以错了

C选项最后一句,应该是s->next->prev = s;

3. 单选题

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

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)。

4. 单选题

有如下函数 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,如果没有看出函数作用,也可以手动模拟递归过程。

5. 单选题

下述代码实现素数表的埃拉托斯特尼筛法,筛选出所有小于等于 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
这道题暂未补解析。
6. 单选题

下述代码实现素数表的线性筛法,筛选出所有小于等于 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。

7. 单选题

下面函数可以将 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
这道题暂未补解析。
8. 单选题

现在用如下代码来计算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
这道题暂未补解析。
9. 单选题

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

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

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

10. 单选题

考虑以下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)

11. 单选题

现在有 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
解析:

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

12. 单选题

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

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

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

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

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

13. 单选题

根据下述二分查找法,在排好序的数组 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,找到要查找的值,结束。

14. 单选题

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

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

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

15. 单选题

当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
这道题暂未补解析。

二、判断题

16. 判断题

在操作系统中,需要对一组进程进行循环。每个进程被赋予一个时间片,当时间片用完时,CPU将切换到下一个进程。这种循环操作可以通过环形链表来实现。

  • A对
  • B错
查看答案与解析
答案:对
解析:

进行是循环的,一个进程的时间片用完之后,进行下一个进程,所以进程可以用循环链表实现。

17. 判断题

找出自然数 n 以内的所有质数,常用算法有埃拉托斯特尼(埃氏)筛法和线性筛法,其中线性筛法效率更高。

  • A对
  • B错
查看答案与解析
答案:对
解析:

常见的质数筛有埃氏筛和欧拉筛(线性筛法),其中埃氏筛的时间复杂度为O(nlogn),经过一定的优化,可以到O(nloglogn),欧拉筛的时间复杂度为O(n),大部分情况下,欧拉筛的效率更高。

18. 判断题

唯一分解定理表明任何一个大于 1 的整数都可以唯一地分解为素数之和。

  • A对
  • B错
查看答案与解析
答案:错
解析:

任何一个大于等于2的整数,都可以唯一的分解为若干个质数的幂次方的乘积的形式

19. 判断题

贪心算法通过每一步选择局部最优解,从而一定能获得最优解。

  • A对
  • B错
查看答案与解析
答案:错
解析:

贪心算法的使用条件是:局部最优能够得到全局最优,不是所有的问题都可以通过贪心实现,因为局部最优不一定能得到全局最优

20. 判断题

快速排序和归并排序的平均时间复杂度均为 O(nlogn),且都是稳定排序。

  • A对
  • B错
查看答案与解析
答案:错
解析:

快速排序的均摊时间复杂度为O(nlogn),归并排序的时间复杂度是稳定的O(nlogn),所以对于时间复杂度的描述是正确的,但是快速排序不是稳定排序。

21. 判断题

插入排序的时间复杂度总是比快速排序低。

  • A对
  • B错
查看答案与解析
答案:错
解析:

插入排序的时间复杂度为O(n2),快速排序的均摊时间复杂度为O(nlogn),但是快速排序的最坏情况下,时间复杂度也是O(n2)

22. 判断题

引入分治策略往往可以提升算法效率。一方面,分治策略减少了操作数量;另一方面,分治后有利于系统的并行优化。

  • A对
  • B错
查看答案与解析
答案:对
解析:

分治算法的思想就是把问题划分成子问题,然后继续划分,知道子问题可以直接解决,然后合并子问题得到的结果,推得原问题的答案,分治提高了算法的效率,减少了操作数量。

23. 判断题

二分查找要求被搜索的序列是有序的,否则无法保证正确性。

  • A对
  • B错
查看答案与解析
答案:对
解析:

二分查找的前提条件是,序列有序。

24. 判断题

在C++语言中,递归的实现方式通常会占用更多的栈空间,可能导致栈溢出。

  • A对
  • B错
查看答案与解析
答案:对
解析:

递归用占用栈空间,而栈空间往往不是很大,递归层数过多的时候,可能会导致栈溢出。

25. 判断题

对于已经定义好的标准数学函数 sin(x) ,应用程序中的语句 y=sin(sin(x)); 是一种递归调用。

  • A对
  • B错
查看答案与解析
答案:错
解析:

递归是指的函数不断的调用自身,直到当前传参可以得到结果,并返回结果,递归应该是一个从大问题到小问题的分解,然后小问题有了结果并返回,解决大问题,而这个写法只能算是函数嵌套使用。

三、简答题

26. 简答题

小杨的武器

时间限制:1.0 s

内存限制:512.0 MB

题面描述

小杨有 n 种不同的武器,他对第 i ii 种武器的初始熟练度为ci。

小杨会依次参加 m 场战斗,每场战斗小杨只能且必须选择一种武器使用,假设小杨使用了第 i 种武器参加了第 j 场战斗,战斗前该武器的熟练度为ci′,则战斗后小杨对该武器的熟练度会变为 ci′+aj。需要注意的是,aj可能是正数,0 或负数,这意味着小杨参加战斗后对武器的熟练度可能会提高,也可能会不变,还有可能降低。

小杨想请你编写程序帮他计算出如何选择武器才能使得 m 场战斗后,自己对 n 种武器的熟练度的最大值尽可能大。

输入格式

第一行包含两个正整数 n,m,含义如题面所示。

第二行包含 n 个正整数 c1,c2,...,cn,代表小杨对武器的初始熟练度。

第三行包含 m 个正整数 a1,a2,...,am,代表每场战斗后武器熟练度的变化值。

输出格式

输出一个整数,代表 m 场战斗后小杨对 n 种武器的熟练度的最大值最大是多少。


输入样例

2 2
9 9
1 -1

输出样例

10

一种最优的选择方案为,第一场战斗小杨选择第一种武器,第二场战斗小杨选择第二种武器。

对于全部数据,保证有 1≤n,m≤105,−104≤ci,ai≤104。

查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">#include &lt;bits/stdc++.h&gt; using namespace std; const int N = 100010; int a[N], c[N]; int main(){ int n, m; cin&gt;&gt;n&gt;&gt;m; int mx = -10000; for (int i = 1; i &lt;= n; ++ i){ cin&gt;&gt;c[i]; mx = max(mx,c[i]); } for (int i = 1; i &lt;= m; ++ i){ cin&gt;&gt;a[i]; } for (int i = 1; i &lt;= m; ++ i){ if (n == 1 || a[i] &gt; 0){ mx += a[i]; } } cout&lt;&lt;mx&lt;&lt;"\n"; return 0; }</pre>
这道题暂未补解析。
27. 简答题

挑战怪物

时间限制:1.0 s

内存限制:512.0 MB

题面描述

小杨正在和一个怪物战斗,怪物的血量为 h ,只有当怪物的血量恰好为 0 时小杨才能够成功击败怪物。

小杨有两种攻击怪物的方式:

物理攻击。假设当前为小杨第 i 次使用物理攻击,则会对怪物造成 2i−1点伤害。

魔法攻击。小杨选择任意一个质数 x (x 不能超过怪物当前血量),对怪物造成 x 点伤害。由于小杨并不擅长魔法,他只能使用至多一次魔法攻击。

小杨想知道自己能否击败怪物,如果能,小杨想知道自己最少需要多少次攻击。

输入格式

第一行包含一个正整数 t ,代表测试用例组数。

接下来是 t 组测试用例。对于每组测试用例,第一行包含一个正整数 h ,代表怪物血量。

输出格式

对于每组测试用例,如果小杨能够击败怪物,输出一个整数,代表小杨需要的最少攻击次数,如果不能击败怪物,输出−1。


输入样例

3
6
188
9999

输出样例

2
4
-1

对于第一组测试用例,一种可能的最优方案为,小杨先对怪物使用魔法攻击,选择质数 5 造成 5 点伤害,之后对怪物使用第 1 次物理攻击,造成21−1=1 点伤害,怪物血量恰好为 0 ,小杨成功击败怪物。

对于全部数据,保证有 1≤t≤10,1≤h≤105。

查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">#include &lt;bits/stdc++.h&gt; using namespace std; vector&lt;int&gt; prime; bool is_prime[100010]; void Eratosthenes(int n) { is_prime[0] = is_prime[1] = false; for (int i = 2; i &lt;= n; ++i) is_prime[i] = true; for (int i = 2; i &lt;= n; ++i) { if (is_prime[i]) { prime.push_back(i); if ((long long)i * i &gt; n) continue; for (int j = i * i; j &lt;= n; j += i) is_prime[j] = false; } } } int main() { Eratosthenes(100000); int t; cin&gt;&gt;t; while(t--){ int tmp=1; int x; cin&gt;&gt;x; int ans=0; while(1){ if(is_prime[x]){ ans++; break; } x-=tmp; ans++; if(x&lt;=0){ if(x&lt;0)ans=-1; break; } tmp*=2; } cout&lt;&lt;ans&lt;&lt;"\n"; } }</pre>
这道题暂未补解析。