GESP 2025年6月认证 C++ 5级试题

一、选择题

第 1 题 与数组相比，链表在（ ）操作上通常具有更高的效率。 {{ select(1) }}

• 随机访问元素
• 查找指定元素
• 在已知位置插入或删除节点
• 遍历所有元素

---

第 2 题 下面C++代码实现双向链表。函数 is_empty() 判断链表是否为空，如链表为空返回 true，否则返回 false。横线处不能填写（ ）。 {{ select(2) }}

• return head == nullptr;
• return tail == nullptr;
• return head.data == 0;
• return size == 0;

---

第 3 题 基于上题代码正确的前提下，填入相应代码完善 append()，用于在双向链表尾部增加新节点，横线上应填写（ ）。 {{ select(3) }}

• tail->next = newNode;
• newNode->prev = tail; tail = newNode;
• tail = newNode; newNode->prev = tail; tail->next = newNode;
• tail->next = newNode; newNode->prev = tail; tail = newNode;

---

第 4 题 下列C++代码用循环链表解决约瑟夫问题，即假设 $n$ 个人围成一圈，从第一个人开始数，每次数到第 $k$ 个的人就出圈，输出最后留下的那个人的编号。横线上应填写（ ）。 {{ select(4) }}

• prev->next = p->next; delete p; p = prev->next;
• delete p; prev->next = p->next; p = prev->next;
• delete p; p = prev->next; prev->next = p->next;
• prev->next = p->next; p = prev->next; delete p;

---

第 5 题 下列C++代码判断一个正整数是否是质数，说法正确的是（ ）。 {{ select(5) }}

• 代码存在错误，比如5是质数，但因为 5 % 5 余数是0返回了 false
• finish_number 的值应该是 n / 2，当前写法将导致错误
• 当前 while 循环正确的前提是：所有大于3的质数都符合 $6k±1$ 形式
• while 循环修改如下，其执行效果和执行时间相同

---

第 6 题 下列C++代码用两种方式求解两个正整数的最大公约数，说法错误的是（ ）。 {{ select(6) }}

• gcd0() 函数的时间复杂度为 $O(\log n)$
• gcd1() 函数的时间复杂度为 $O(n)$
• 一般说来，gcd0() 的效率高于 gcd1()
• gcd1() 中的代码 for (int i = small; i >= 1; --i) 应该修改为 for (int i = small; i > 1; --i)

---

第 7 题 下面的代码用于判断整数是否是质数，错误的说法是（ ）。 {{ select(7) }}

• 埃氏筛算法相对于上面的代码效率更高
• 线性筛算法相对于上面的代码效率更高
• 上面的代码有很多重复计算，因为不是判断单个数是否为质数，故而导致筛选出连续数中质数的效率不高
• 相对而言，埃氏筛算法比上面代码以及线性筛算法效率都高

---

第 8 题 唯一分解定理描述了关于正整数的什么性质？ {{ select(8) }}

• 任何正整数都可以表示为两个素数的和
• 任何大于1的合数都可以唯一分解为有限个质数的乘积
• 两个正整数的最大公约数总是等于它们的最小公倍数除以它们的乘积
• 所有素数都是奇数

---

第 9 题 下面的C++代码，用于求一系列数据中的最大值。有关其算法说法错误的是（ ）。 {{ select(9) }}

• 该算法采用分治算法
• 该算法是递归实现
• 该算法采用贪心算法
• 该算法不是递推算法

---

第 10 题 下面的C++代码，用于求一系列数据中的最大值。有关其算法说法错误的是（ ）。 {{ select(10) }}

• 本题 find_max() 函数采用的是迭代算法
• 本题 find_max() 函数的时间复杂度为 $O(n)$
• 和上一题的 find_max() 相比，因为没有递归，所以没有栈的创建和销毁开销
• 本题 find_max() 函数和上一题的 find_max() 时间复杂度相同

---

第 11 题 下面的 C++ 代码用于在升序数组 lst 中查找目标值 target 最后一次出现的位置。相关说法，正确的是（ ）。 {{ select(11) }}

• 当 lst 中存在重复的 target 时，该函数总能返回最后一个 target 的位置，即便 lst 全由相同元素组成
• 当 target 小于 lst 中所有元素时，该函数会返回 0
• 循环条件改为 while (low <= high) 程序执行效果相同，且能提高准确性
• 将代码中 (low + high + 1) / 2 修改为 (low + high) / 2 效果相同

---

第 12 题 有关下面C++代码的说法，错误的是（ ）。 {{ select(12) }}

• "阶段1"的目标是寻找正整数 $n$ 可能的正完全平方根
• "阶段2"的目标是如果正整数 $n$ 没有正完全平方根，则在可能产生完全平方根附近寻找带小数点的平方根
• 代码 check_int = (long long)(result + 0.5) 是检查因浮点误差是否为正完全平方根
• 阶段2的二分法中 high_d - low_d >= epsilon 不能用于浮点数比较，会进入死循环

---

第 13 题 硬币找零问题中要求找给客户最少的硬币。coins 存储可用硬币规格，单位为角，假设规格都小于10角，且一定有1角规格。amount 为要找零的金额，约定必须为1角的整数倍。输出为每种规格及其数量，按规格从大到小输出，如果某种规格不必要，则输出为0。下面是其实现代码，相关说法正确的是（ ）。 {{ select(13) }}

• 上述代码采用贪心算法实现
• 针对本题具体要求，上述代码总能找到最优解
• 上述代码采用枚举算法
• 上述代码采用分治算法

---

第 14 题 关于下述C++代码的快速排序算法，说法错误的是（ ）。 {{ select(14) }}

• 在 randomPartition 函数中，变量 $i$ 的作用是记录大于基准值的元素的边界
• randomPartition 函数随机选择基准值，可以避免输入数据特定模式导致的最坏情况下时间复杂度 $O(n^2)$
• 快速排序平均时间复杂度是 $O(n\log n)$
• 快速排序是稳定排序算法

---

第 15 题 小杨编写了一个如下的高精度除法函数，则横线上应填写的代码为（ ）。 {{ select(15) }}

• r.d[0] = a.d[i]; r.len++;
• r.d[i] = a.d[i]; r.len++;
• r.d[i] = a.d[i]; r.len = 1;
• r.d[0] = a.d[i]; r.len = 1;

---