二、判断题（每题 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^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;
}

{{ 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) }}

• 正确
• 错误