CCF GESP 2025年9月认证 C++ 5级

二 判断题
共 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;
}
正确
错误
第 2 题
假设函数 gcd() 能正确求两个正整数的最大公约数，则下面的 findMusicalPattern(4, 6) 函数返回 2。
void findMusicalPattern(int rhythm1, int rhythm2) {
    int commonDivisor = gcd(rhythm1, rhythm2);
    int patternLength = (rhythm1 * rhythm2) / commonDivisor;
    return patternLength;
}
正确
错误
第 3 题
下面递归实现的斐波那契数列的时间复杂度为 $O(2^n)$。
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;
}
正确
错误
第 4 题
链表通过更改指针实现高效的结点插入与删除，但结点访问效率低、占用内存较多，且对缓存利用不友好。
正确
错误
第 5 题
二分查找依赖数据的有序性，通过循环逐步缩减一半搜索区间来进行查找，且仅适用于数组或基于数组实现的数据结构。
正确
错误
第 6 题
线性筛关键是“每个合数只会被最小质因子筛到一次”，因此为 $O(n)$。
正确
错误
第 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);
}
正确
错误
第 9 题
所有递归算法都可以转换为迭代算法。
正确
错误
第 10 题
贪心算法总能得到全局最优解。
正确
错误
判断题部分已到底了。