EXY-TF-0850
第 151 题
如下为线性筛法，用于高效生成素数表，其核心思想是每个合数只被它的最小质因数筛掉一次，时间复杂度为 $O(n)$。
vector<int> linearSieve(int n) {
vector<bool> is_prime(n + 1, true);
vector<int> primes;
for (int i = 2; i <= n; ++i) {
if (is_prime[i]) {
primes.push_back(i);
}
for (int j = 0; j < primes.size() && i * primes[j] <= n; ++j) {
is_prime[i * primes[j]] = false;
if (i % primes[j] == 0) {
break;
}
}
}
return primes;
}
语言：
C++
GESP真题
五级
2025.6
判断题号：
10
EXY-TF-0849
第 152 题
函数 puzzle 定义如下，则调用 puzzle(7) 程序会无限递归。
int puzzle(int n) {
if (n == 1) return 1;
if (n % 2 == 0) return puzzle(n / 2);
return puzzle(3 * n + 1);
}
语言：
C++
GESP真题
五级
2025.6
判断题号：
9
EXY-TF-0848
第 153 题
分治算法将原问题可以分解成规模更小的子问题，使得求解问题的难度降低。但由于分治算法需要将问题进行分解，并且需要将多个子问题的解合并为原问题的解，所以分治算法的效率通常比直接求解原问题的效率低。
语言：
C++
GESP真题
五级
2025.6
判断题号：
8
EXY-TF-0847
第 154 题
求解下图中 A 点到 D 点最短路径，其中 A 到 B 之间的 12 可以理解为距离。求解这样的问题常用 Dijkstra 算法，其思路是通过逐步选择当前距离起点最近的节点来求解非负权重图（如距离不能为负值）单源最短路径的算法。从该算法的描述可以看出，Dijkstra 算法是贪心算法。
语言：
C++
GESP真题
五级
2025.6
判断题号：
7
EXY-TF-0846
第 155 题
查字典这个小学生必备技能，可以把字典视为一个已排序的数组。假设小杨要查找一个音首字母为 $g$ 的单词，他首先翻到字典约一半的页数，发现该页的首字母是 $m$，由于字母表中 $g$ 位于 $m$ 之前，所以排除字典后半部分，查找范围缩小到前半部分；不断重复上述步骤，直到找到首字母为 $g$ 的页码。这种查字典的一系列操作可看作二分查找。
语言：
C++
GESP真题
五级
2025.6
判断题号：
6
当前页显示 151 - 155
，共 840 道判断题