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

二、判断题

第 16 题 下面C++代码是用欧几里得算法（辗转相除法）求两个正整数的最大公约数，$a$ 大于 $b$ 还是小于 $b$ 都适用。（ ） {{ select(16) }}

• 对
• 错

第 17 题 假设函数 gcd() 函数能正确求两个正整数的最大公约数，则下面的 lcm() 函数能求相应两数的最小公倍数。（ ） {{ select(17) }}

• 对
• 错

第 18 题 下面的C++代码用于输出每个数对应的质因数列表，输出形如：{5: [5], 6: [2, 3], 7: [7], 8: [2, 2, 2]}。（ ） {{ select(18) }}

• 对
• 错

第 19 题 下面的C++代码实现归并排序。代码在执行时，将输出一次 HERE 字符串，因为 merge() 函数仅被调用一次。（ ） {{ select(19) }}

• 对
• 错

第 20 题 归并排序的最好、最坏和平均时间复杂度均为 $O(n\log n)$。（ ） {{ select(20) }}

• 对
• 错

第 21 题 查字典这个小学生必备技能，可以把字典视为一个已排序的数组。假设小杨要查找一个音首字母为 g 的单词，他首先翻到字典约一半的页数，发现该页的首字母是 m，由于字母表中 g 位于 m 之前，所以排除字典后半部分，查找范围缩小到前半部分；不断重复上述步骤，直至找到首字母为 g 的页码。这种查字典的一系列操作可看作二分查找。（ ） {{ select(21) }}

• 对
• 错

第 22 题 求解图中A点到D点最短路径，其中A到B之间的12可以理解为距离。求解这样的问题常用Dijkstra算法，其思路是通过逐步选择当前距离起点最近的节点来求解非负权重图（如距离不能为负值）单源最短路径的算法。从该算法的描述可以看出，Dijkstra算法是贪心算法。（ ） {{ select(22) }}

• 对
• 错

第 23 题 分治算法将原问题可以分解成规模更小的子问题，使得求解问题的难度降低。但由于分治算法需要将问题进行分解，并且需要将多个子问题的解合并为原问题的解，所以分治算法的效率通常比直接求解原问题的效率低。（ ） {{ select(23) }}

• 对
• 错

第 24 题 函数 puzzle 定义如下，则调用 puzzle(7) 程序会无限递归。（ ） {{ select(24) }}

• 对
• 错

第 25 题 如下为线性筛法，用于高效生成素数表，其核心思想是每个合数只被它的最小质因数筛掉一次，时间复杂度为 $O(n)$。（ ） {{ select(25) }}

• 对
• 错