GESP C++ 五 级 2025年9月真题（180 分钟，总分 100 分）

判断题（共 10 题，每题 2 分，共 20 分）

1. 基于下面定义的函数，通过判断 isDivisibleBy9(n) == isDigitSumDivisibleBy9(n) 代码可验算如果一个数能被9整除，则它的各位数字之和能被9整除。

bool isDivisibleBy9(int n) {
   return n % 9 == 0;
}
bool isDigitSumDivisibleBy9(int n) {
   int sum = 0;
   string numStr = to_string(n);
   for (char c : numStr) {
       sum += (c - '0');
  }
   return sum % 9 == 0;
}

{{ select(1) }}

• 正确
• 错误

2. 假设函数gcd()能正确求两个正整数的最大公约数，则下面的 findMusicalPattern(4，6) 函数返回2。

void findMusicalPattern(int rhythm1, int rhythm2) {
   int commonDivisor = gcd(rhythm1, rhythm2);
   int patternLength = (rhythm1 * rhythm2) / commonDivisor;
   return patternLength；
}

{{ select(2) }}

• 正确
• 错误

3. 下面递归实现的斐波那契数列的时间复杂度为 O(2ⁿ)。

long long fib_memo(int n, long long memo[]) {
   if (n <= 1) return n;
   if (memo[n] != -1) return memo[n];
   memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo);
   return memo[n];
}
int main() {
   int n = 40;
   long long memo[100];
   fill_n(memo, 100, -1);
   long long result2 = fib_memo(n, memo);
   return 0;
}

{{ select(3) }}

• 正确
• 错误

4. 链表通过更改指针实现高效的结点插入与删除，但结点访问效率低、占用内存较多，且对缓存利用不友好。

{{ select(4) }}

• 正确
• 错误

5. 二分查找依赖数据的有序性，通过循环逐步缩减一半搜索区间来进行查找，且仅适用于数组或基于数组实现的数据结构。

{{ select(5) }}

• 正确
• 错误

6. 线性筛关键是“每个合数只会被最小质因子筛到一次”，因此为 O(n)。

{{ select(6) }}

• 正确
• 错误

7. 快速排序和归并排序都是稳定的排序算法。

{{ select(7) }}

• 正确
• 错误

8. 下面代码采用分治算法求解标准 3 柱汉诺塔问题，时间复杂度为 O( n log n)。

void move(vector<int> &src, vector<int> &tar) {
   int pan = src.back();
   src.pop_back();
   tar.push_back(pan);
}
void dfs(int n, vector<int> &src, vector<int> &buf, vector<int> &tar) {
   if (n == 1) {
       move(src, tar);
       return;
  }
   dfs(n - 1, src, tar, buf);
   move(src, tar);
   dfs(n - 1, buf, src, tar);
}
void solveHanota(vector<int> &A, vector<int> &B, vector<int> &C) {
   int n = A.size();
   dfs(n, A, B, C);
}

{{ select(8) }}

• 正确
• 错误

9. 所有递归算法都可以转换为迭代算法。

{{ select(9) }}

• 正确
• 错误

10. 贪心算法总能得到全局最优解。

{{ select(10) }}

• 正确
• 错误