与数组相比,链表在( )操作上通常具有更高的效率?
2025年6月CCF-GESP编程能力等级认证C++编程五级真题 VIP
一、单选题
下面C++代码实现双向链表。函数 is_empty() 判断链表是否为空,如链表为空返回 true ,否则返回false 。横线处不能填写?( )
查看答案与解析
基于上题代码正确的前提下,填入相应代码完善 append() ,用于在双向链表尾部增加新节点,横线上应填写?( )
查看答案与解析
下列C++代码用循环链表解决约瑟夫问题,即假设 n 个人围成一圈,从第一个人开始数,每次数到第 k 个的人就出圈,输出最后留下的那个人的编号。横线上应填写?( )
查看答案与解析
下列C++代码判断一个正整数是否是质数,说法正确的是?( )
查看答案与解析
下列C++代码用两种方式求解两个正整数的最大公约数,说法【错误】的是?( )
查看答案与解析
下面的代码用于判断整数 n 是否是质数,错误的说法是?( )
查看答案与解析
唯一分解定理描述了关于正整数的什么性质?( )
查看答案与解析
下面的C++代码,用于求一系列数据中的最大值。有关其算法说法【错误】的是?( )
查看答案与解析
下面的C++代码,用于求一系列数据中的最大值。有关其算法说法【错误】的是?( )
查看答案与解析
下面的 C++ 代码用于在升序数组 lst 中查找目标值 target 最后一次出现的位置。相关说法,正确的是?( )
查看答案与解析
有关下面C++代码的说法,【错误】的是?( )
查看答案与解析
硬币找零问题中要求找给客户最少的硬币。 coins 存储可用硬币规格,单位为角,假设规格都小于10角,且一定有1角规格。
amount 为要找零的金额,约定必须为1角的整数倍。输出为每种规格及其数量,按规格从大到小输出,如果某种规格不必要,则输出为0。
下面是其实现代码,相关说法正确的是?( )
查看答案与解析
关于下述C++代码的快速排序算法,说法【错误】的是?( )
查看答案与解析
小杨编写了一个如下的高精度除法函数,则横线上应填写的代码为?( )
查看答案与解析
二、判断题
下面C++代码是用欧几里得算法(辗转相除法)求两个正整数的最大公约数, a 大于 b 还是小于 b 都适用。( )
查看答案与解析
假设函数 gcd() 函数能正确求两个正整数的最大公约数,则下面的 lcm() 函数能求相应两数的最小公倍数。( )
查看答案与解析
下面的C++代码用于输出每个数对应的质因数列表,输出形如: {5: [5], 6: [2, 3], 7: [7], 8: [2, 2, 2]} 。( )
查看答案与解析
下面的C++代码实现归并排序。代码在执行时,将输出一次 HERE 字符串,因为merge()函数仅被调用一次。( )
查看答案与解析
归并排序的最好、最坏和平均时间复杂度均为 O(n log n)。( )
查看答案与解析
查字典这个小学生必备技能,可以把字典视为一个已排序的数组。
假设小杨要查找一个音首字母为 g 的单词,他首先翻到字典约一半的页数,发现该页的首字母是 m ,由于字母表中 g 位于 m 之前,所以排除字典后半部分,查找范围缩小到前半部分;不断重复上述步骤,直至找到首字母为 g 的页码。
这种查字典的一系列操作可看作二分查找。( )
查看答案与解析
求解下图中A点到D点最短路径,其中A到B之间的12可以理解为距离。求解这样的问题常用Dijkstra算法,其思路是通过逐步选择当前距离起点最近的节点来求解非负权重图(如距离不能为负值)单源最短路径的算法。

从该算法的描述可以看出,Dijkstra算法是贪心算法。( )
查看答案与解析
分治算法将原问题可以分解成规模更小的子问题,使得求解问题的难度降低。
但由于分治算法需要将问题进行分解,并且需要将多个子问题的解合并为原问题的解,所以分治算法的效率通常比直接求解原问题的效率低。( )
查看答案与解析
函数 puzzle 定义如下,则调用 puzzle(7) 程序会无限递归。( )
查看答案与解析
如下为线性筛法,用于高效生成素数表,其核心思想是每个合数只被它的最小质因数筛掉一次,时间复杂度为 O(n)。( )
查看答案与解析
三、简答题
奖品兑换
时间限制:1 s,内存限制:512 MB
【问题描述】
班主任给上课专心听讲、认真完成作业的同学们分别发放了若干张课堂优秀券和作业优秀券。同学们可以使用这两种券找班主任兑换奖品。
具体来说,可以使用 a 张课堂优秀券和 b 张作业优秀券兑换一份奖品,或者使用 b 张课堂优秀券和 a 张作业优秀券兑换一份奖品。
现在小 A 有 n 张课堂优秀券和 m 张作业优秀券,他最多能兑换多少份奖品呢?
【输入描述】
第一行,两个正整数 n、m,分别表示小 A 持有的课堂优秀券和作业优秀券的数量。
第二行,两个正整数 a、b,表示兑换一份奖品所需的两种券的数量。
【输出描述】
输出共一行,一个整数,表示最多能兑换的奖品份数。
【样例输入1】
【样例输出1】
【样例输入2】
【样例输出2】
【数据范围】
对于60%测试点,保证 1 <= a、b <= 100,1 <= n、m <= 500。
对于所有测试点,保证 1 <= a、b <= 10^4,1 <= n、m <= 10^9。
查看答案与解析
最大公因数
时间限制:1 s,内存限制:512 MB
【问题描述】
对于两个正整数 a、b,它们的最大公因数记为 gcd(a, b)。对于 k >=3 个正整数 c1、c2、……、ck,它们的最大公因数为:
gcd(c1, c2, ……, ck) = gcd(gcd(c1, c2, ……, c(k-1), ck)
给定 n 个正整数 a1、a2、……、an 以及 q 组询问。对于第 i(1<=i<=q)组询问,请求出 a1+i、a2+i、……、an+i 的最大公因数,也即 gcd(a1+i, a2+i, …… , an+i)。
【输入描述】
第一行,两个正整数 n、q,分别表示给定正整数的数量,以及询问组数。
第二行, n 个正整数 a1、a2、……、an。
【输出描述】
输出共 q 行,第 i 行包含一个正整数,表示 a1+i、a2+i、……、an+i 的最大公因数。
【样例输入1】
【样例输出1】
【样例输入2】
【样例输出2】
【数据范围】
对于60%的测试点,保证 1 <= n <= 1000,1 <= q <= 10。
对于所有测试点,保证 1 <= n、q <= 10^5,1 <= ai <= 1000。