GESP 2024年12月_C++五级试卷

第1题中级 2.0分单选

下面关于链表和数组的描述，错误的是（）。

A. 当数据数量不确定时，为了应对各种可能的情况，需要申请一个较大的数组，可能浪费空间；此时用链表比较合适，大小可动态调整。

B. 在链表中访问节点的效率较低，时间复杂度为O(n)。

C. 链表插入和删除元素效率较低，时间复杂度为O(n)。

D. 链表的节点在内存中是分散存储的，通过指针连在一起。

第2题中级 2.0分单选

在循环单链表中，节点的next指针指向下一个节点，最后一个节点的next指针指向（）。

A. 当前节点

B. nullptr

C. 第一个节点

D. 上一个节点

第3题中级 2.0分单选

为了方便链表的增删操作，一些算法生成一个虚拟头节点，方便统一删除头节点和其他节点。下面代码实现了删除链表中值为val的节点，横线上应填的最佳代码是( )。

A. dummyHead->next = head; cur = dummyHead;

B. dummyHead->next = head->next; cur = dummyHead;

C. dummyHead->next = head; cur = dummyHead->next;

D. dummyHead->next = head->next; cur = dummyHead->next;

第4题中级 2.0分单选

对下面两个函数，说法错误的是（）。

A. 两个函数的实现的功能相同。

B. fibA采用递推方式。

C. fibB采用的是递归方式。

D. fibA时间复杂度为O(n)，fibB的时间复杂度为O(n)。

第5题中级 2.0分单选

两块长方形土地的长宽分别为a和b米，要将它们分成正方形的小块，使得正方形的尺寸尽可能大。小杨采用如下的辗转相除函数gcd(24, 36)来求正方形分块的边长，则

A. gcd(24,36)、gcd(24,12)、gcd(12,0)

B. gcd(24,36)、gcd(12,24)、gcd(0,12)

C. gcd(24,36)、gcd(24,12)

D. gcd(24,36)、gcd(12,24)

第6题中级 2.0分单选

唯一分解定理表明，每个大于1的自然数可以唯一地写成若干个质数的乘积。下面函数将自然数的所有质因数找出来，横线上能填写的最佳代码是（）。

A. for (int i = 3; i <= n; i++)

B. for (int i = 3; i * i <= n; i++)

C. for (int i = 3; i <= n; i += 2)

D. for (int i = 3; i * i <= n; i += 2)

第7题中级 2.0分单选

下述代码实现素数表的埃拉托色尼筛法，筛选出所有小于等于n的素数。下面说法，正确的是（）。

A. 代码的时间复杂度是O(n)。

B. 在标记非素数时，代码从i²开始，可以减少重复标记。

C. 代码会输出所有小于等于n的奇数。

D. 调用函数sieve_Eratosthenes(10)，函数返回值的数组中包含的元素有：2,3,5,7,9。

第8题中级 2.0分单选

下述代码实现素数表的线性筛法，筛选出所有小于等于n的素数。下面说法正确的是( )。

A. 线性筛的时间复杂度是O(n log n)。

B. 每个合数会被其所有的质因子标记一次。

C. 线性筛和埃拉托色尼筛的实现思路完全相同。

D. 以上都不对

第9题中级 2.0分单选

考虑以下C++代码实现的快速排序算法。以下关于快速排序的说法，正确的是（）。

A. 快速排序通过递归对子问题进行求解。

B. 快速排序的最坏时间复杂度是O(n log n)。

C. 快速排序是一个稳定的排序算法。

D. 在最优情况下，快速排序的时间复杂度是O(n)。

第10题中级 2.0分单选

下面关于归并排序，描述正确的是（）。

A. 归并排序是一个不稳定的排序算法。

B. 归并排序的时间复杂度在最优、最差和平均情况下都是O(n log n)。

C. 归并排序需要额外的O(1)空间。

D. 对于输入数组{12,11,13,5,6,7}，代码输出结果为：7 6 5 13 12 11。

第11题中级 2.0分单选

给定一个长度为n的有序数组nums，其中所有元素都是唯一的。下面的函数返回数组中元素target的索引。关于上述函数，描述不正确的是（）。

A. 函数采用二分查找，每次计算搜索当前搜索区间的中点，然后根据中点的元素值排除一半搜索区间。

B. 函数采用递归求解，每次问题的规模减小一半。

C. 递归的终止条件是中间元素的值等于target，若数组中不包含该元素，递归不会终止。

D. 算法的复杂度为O(log n)。

第12题中级 2.0分单选

给定一个长度为n的有序数组nums，其中可能包含重复元素。下面的函数返回数组中某个元素target的左边界，若数组中不包含该元素，则返回-1。则横线上应填写的代

A. right = middle - 1;

B. right = middle;

C. right = middle + 1;

D. 以上都不对

第13题中级 2.0分单选

假设有多个孩子，数组g保存所有孩子的胃口值。有多块饼干，数组s保存所有饼干的尺寸。小杨给孩子们发饼干，每个孩子最多只能给一块饼干。饼干的尺寸大于等于孩子的胃口时

A. result++; index--;

B. result--; index--;

C. result--; index++;

D. result++; index++;

第14题中级 2.0分单选

关于分治算法，以下说法中不正确的是（）。

A. 分治算法将问题分成子问题，然后分别解决子问题，最后合并结果。

B. 归并排序采用了分治思想。

C. 快速排序采用了分治思想。

D. 冒泡排序采用了分治思想。

第15题中级 2.0分单选

小杨编写了一个如下的高精度减法函数。下面说法，正确的是（）。

A. 如果数组a表示的整数小于b表示的整数，代码会正确返回二者的差为负数。

B. 代码假设输入数字是以倒序存储的，例如500存储为{0,0,5}。

T. 正确

F. 错误

第26题中级 25.0分编程

奇妙数字

小杨认为一个数字x是奇妙数字当且仅当x=p^k，其中p为任意质数且k为正整数。例如，8=2^3，所以8是奇妙数字，而6不是。对于一个正整数N，小杨想要构建一个包含k个奇妙数字的集合S，使其满足以下条件： 1. 集合中不包含相同的数字。 2. S中所有数字的乘积是N的因子。小杨希望集合包含的奇妙数字尽可能多，请你帮他计算出满足条件的集合最多包含多少个奇妙数字。

【输入格式】

第一行包含一个正整数N，含义如题面所示。

【输出格式】

输出一个正整数，代表满足条件的集合最多包含多少个奇妙数字。

【样例输入】

128
【样例输出】

3
对于全部数据，保证有1<=N<=10^12。

第27题中级 25.0分编程

武器强化

小杨有n种武器和m种强化材料。第i种强化材料会适配第pi种武器，小杨可以花费ci金币将该材料对应的适配武器修改为任意武器。小杨最喜欢第1种武器，因此他希望适配该武器的强化材料种类数严格大于其他的武器，请你帮小杨计算为了满足该条件最少需要花费多少金币。

【输入格式】

第一行包含两个正整数n、m，含义如题面所示。
之后m行，每行包含两个正整数pi、ci，代表第i种强化材料的适配武器和修改花费。

【输出格式】

输出一个整数，代表能够使适配第1种武器的强化材料种类数严格大于其他的武器最少需要花费的金币。

【样例输入】

4 4
1 1
2 1
3 1
3 2
【样例输出】

1
对于全部数据，保证有2<=n,m<=1000，1<=pi<=n，1<=ci<=10^9。

GESP 2024年12月_C++五级试卷

试卷题目预览

下面关于链表和数组的描述，错误的是（ ）。

在循环单链表中，节点的next指针指向下一个节点，最后一个节点的next指针指向（ ）。

为了方便链表的增删操作，一些算法生成一个虚拟头节点，方便统一删除头节点和其他节点。下面代码实现了删除链表中值为val的节点，横线上应填的最佳代码是( )。

对下面两个函数，说法错误的是（ ）。

两块长方形土地的长宽分别为a和b米，要将它们分成正方形的小块，使得正方形的尺寸尽可能大。小杨采用如下的辗转相除函数gcd(24, 36)来求正方形分块的边长，则

唯一分解定理表明，每个大于1的自然数可以唯一地写成若干个质数的乘积。下面函数将自然数的所有质因数找出来，横线上能填写的最佳代码是（ ）。

下述代码实现素数表的埃拉托色尼筛法，筛选出所有小于等于n的素数。下面说法，正确的是（ ）。

下述代码实现素数表的线性筛法，筛选出所有小于等于n的素数。下面说法正确的是( )。

考虑以下C++代码实现的快速排序算法。以下关于快速排序的说法，正确的是（ ）。

下面关于归并排序，描述正确的是（ ）。

给定一个长度为n的有序数组nums，其中所有元素都是唯一的。下面的函数返回数组中元素target的索引。关于上述函数，描述不正确的是（ ）。

给定一个长度为n的有序数组nums，其中可能包含重复元素。下面的函数返回数组中某个元素target的左边界，若数组中不包含该元素，则返回-1。则横线上应填写的代

假设有多个孩子，数组g保存所有孩子的胃口值。有多块饼干，数组s保存所有饼干的尺寸。小杨给孩子们发饼干，每个孩子最多只能给一块饼干。饼干的尺寸大于等于孩子的胃口时

关于分治算法，以下说法中不正确的是（ ）。

小杨编写了一个如下的高精度减法函数。下面说法，正确的是（ ）。

单链表只支持在表头进行插入和删除操作。

线性筛相对于埃拉托斯特尼筛法，每个合数只会被它的最小质因数筛去一次，因此效率更高。

任何一个大于1的自然数都可以分解成若干个不同的质数的乘积，且分解方式是唯一的。

贪心算法通过每一步选择当前最优解，从而一定能获得全局最优解。

递归算法必须有一个明确的结束条件，否则会导致无限递归并可能引发栈溢出。

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

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

二分查找仅适用于数组而不适合链表，因为二分查找需要跳跃式访问元素，链表中执行跳跃式访问的效率低。

对有序数组{5,13,19,21,37,56,64,75,88,92,100}进行二分查找，成功查找元素19的比较次数是2。

递归函数每次调用自身时，系统都会为新开启的函数分配内存，以存储局部变量、调用地址和其他信息等，导致递归通常比迭代更加耗费内存空间。