下面关于链表和数组的描述,错误的是( )。
2024年12月CCF-GESP编程能力等级认证C++编程五级真题 VIP
一、单选题
在循环单链表中,节点的 next 指针指向下一个节点,最后一个节点的 next 指针指向( )。
查看答案与解析
为了方便链表的增删操作,一些算法生成一个虚拟头节点,方便统一删除头节点和其他节点。下面代码实现了删除链表中值为 val 的节点,横线上应填的最佳代码是( )。
查看答案与解析
对下面两个函数,说法错误的是( )。
查看答案与解析
两块长方形土地的长宽分别为 24 和 36 米,要将它们分成正方形的小块,使得正方形的尺寸尽可能大。小杨采用如下的辗转相除函数 gcd(24, 36) 来求正方形分块的边长,则函数 gcd 调用顺序为( )。
查看答案与解析
唯一分解定理表明,每个大于1的自然数可以唯一地写成若干个质数的乘积。下面函数将自然数 n 的所有质因素找出来,横线上能填写的最佳代码是( )。
查看答案与解析
下述代码实现素数表的埃拉托色尼(埃氏)筛法,筛选出所有小于等于 n 的素数。
下面说法,正确的是( )。
查看答案与解析
下述代码实现素数表的线性筛法,筛选出所有小于等于 n 的素数。下面说法正确的是( )。
查看答案与解析
考虑以下C++代码实现的快速排序算法:
以下关于快速排序的说法,正确的是( )。
查看答案与解析
下面关于归并排序,描述正确的是( )。
查看答案与解析
给定一个长度为 n 的有序数组 nums ,其中所有元素都是唯一的。下面的函数返回数组中元素 target 的索引。
关于上述函数,描述不正确的是( )。
查看答案与解析
给定一个长度为 的有序数组 nums ,其中可能包含重复元素。下面的函数返回数组中某个元素 target 的左边界,若数组中不包含该元素,则返回 −1 。例如在数组 nums = [5,7,7,8,8,10] 中查找 target=8 ,函数返回 8 88 在数组中的左边界的索引为 3 33。则横线上应填写的代码为( )。
查看答案与解析
假设有多个孩子,数组 g 保存所有孩子的胃口值。有多块饼干,数组 s 保存所有饼干的尺寸。小杨给孩子们发饼干,每个孩子最多只能给一块饼干。饼干的尺寸大于等于孩子的胃口时,孩子才能得到满足。小杨的目标是尽可能满足越多数量的孩子,因此打算采用贪心算法来找出能满足的孩子的数目,则横线上应填写的代码为( )。
查看答案与解析
关于分治算法,以下说法中不正确的是( )。
查看答案与解析
小杨编写了一个如下的高精度减法函数:
下面说法,正确的是( )。
查看答案与解析
二、判断题
单链表只支持在表头进行插入和删除操作。
查看答案与解析
线性筛相对于埃拉托斯特尼筛法,每个合数只会被它的最小质因数筛去一次,因此效率更高。
查看答案与解析
任何一个大于1的自然数都可以分解成若干个不同的质数的乘积,且分解方式是唯一的。(2024.12-5)
查看答案与解析
贪心算法通过每一步选择当前最优解,从而一定能获得全局最优解。
查看答案与解析
递归算法必须有一个明确的结束条件,否则会导致无限递归并可能引发栈溢出。
查看答案与解析
快速排序和归并排序的平均时间复杂度均为 O(nlogn),且都是稳定排序。(2024.12-5)
查看答案与解析
快速排序的时间复杂度总比插入排序的时间复杂度低。
查看答案与解析
二分查找仅适用于数组而不适合链表,因为二分查找需要跳跃式访问元素,链表中执行跳跃式访问的效率低。
查看答案与解析
对有序数组 {5,13,19,21,37,56,64,75,88,92,100} 进行二分查找,成功查找元素 19 的比较次数是2。
查看答案与解析
递归函数每次调用自身时,系统都会为新开启的函数分配内存,以存储局部变量、调用地址和其他信息等,导致递归通常比迭代更加耗费内存空间。
查看答案与解析
三、简答题
奇妙数字
时间限制:1.0 s
内存限制:512.0 MB
题面描述
小杨认为一个数字 x 是奇妙数字当且仅当 x=pa,其中 p 为任意质数且 a 为正整数。例如, 8=23,所以 8 是奇妙数字,而 6 不是。
对于一个正整数 n ,小杨想要构建一个包含 m 个奇妙数字的集合{x1,x2,...,xm},使其满足以下条件:
集合中不包含相同的数字。
x1∗x2∗...∗xm是 n 的因子(即x1,x2,...,xm这 m 个数字的乘积是 n 的因子)。
小杨希望集合包含的奇妙数字尽可能多,请你帮他计算出满足条件的集合最多包含多少个奇妙数字。
输入格式
第一行包含一个正整数 n ,含义如题面所示。
输出格式
输出一个正整数,代表满足条件的集合最多包含的奇妙数字个数。
输入样例
输出样例
样例解释
关于本样例,符合题意的一个包含 3 个奇妙数字的集合是 2,4,8。首先,因为2=21,4=22,8=23, 所以 2,4,8 均为奇妙数字。同时,2∗4∗8=64 是 128 的因子。
由于无法找到符合题意且同时包含 4 个奇妙数字的集合,因此本样例的答案为 3 。

对于全部数据,保证有 2≤n≤1012。
查看答案与解析
武器强化
时间限制:1.0 s
内存限制:512.0 MB
题面描述
小杨有 n 种武器和 m 种强化材料。第 i 种强化材料会适配第 pi 种武器,小杨可以花费 ci 金币将该材料对应的适配武器修改为任意武器。
小杨最喜欢第 1 种武器,因此他希望适配该武器的强化材料种类数严格大于其他的武器,请你帮小杨计算为了满足该条件最少需要花费多少金币。
输入格式
第一行包含两个正整数 n,m,含义如题面所示。
之后 m 行,每行包含两个正整数 pi,ci,代表第 i 种强化材料的适配武器和修改花费。
输出格式
输出一个整数,代表能够使适配第 1 种武器的强化材料种类数严格大于其他的武器最少需要花费的金币。
输入样例
4 4
1 1
2 1
3 1
3 2
输出样例
1
样例解释
花费 1,将第三种强化材料的适配武器由 3 改为 1。此时,武器 1 有 2 种强化材料适配,武器 2 和武器 3 都各有 1 种强化材料适配。满足适配第 1 种武器的强化材料种类数严格大于其他的武器。

对于全部数据,保证有 1≤n,m≤1000,1≤pi≤n,1≤ci≤109。