题目 1

【读代码找输出】

下面是一段计算前缀和并查询区间和的代码，请问输出结果是什么？

#include <iostream>
using namespace std;

int main() {
    int arr[5] = {2, 1, 3, 4, 2};
    int prefix[5];
    
    prefix[0] = arr[0];
    for(int i = 1; i < 5; i++){
        prefix[i] = prefix[i-1] + arr[i];
    }
    
    // 查询区间 [1, 3] 的和
    int L = 1, R = 3;
    int sumLR = prefix[R] - prefix[L-1];
    
    cout << sumLR << endl;
    return 0;
}

{{ select(1) }}

• 6
• 8
• 9
• 10

题目 2

【区间更新应用】 利用差分数组进行区间更新时，如果我们想对原数组中区间 [L, R] 的每一个元素都加上一个值 v，我们应该怎么操作 diff 数组？ {{ select(2) }}

• diff[L] += v，并且 diff[R] += v

• diff[L] -= v，并且 diff[R+1] += v

• diff[L] += v，并且 diff[R+1] -= v

• diff[R] -= v，并且 diff[R+1] += v

题目 3

【时间复杂度】

常规埃拉托斯特尼筛法在筛选 1 ~ n 的质数时，时间复杂度大约是多少？ {{ select(3) }}

• O(n)
• O(n * log n)
• O(n * log log n)
• O(n^2)

题目 4

以下是一个递归函数的调用过程：

int factorial(int n) {
    if(n == 0) return 1;
    return n * factorial(n - 2);
}

对于输入 n = 5，以下哪个选项正确描述了递归函数的行为？
{{ select(4) }}

• 递归函数会进行5次调用，最后返回1
• 递归函数会进行5次调用，然后返回结果120
• 递归函数会进行10次调用
• 递归函数在栈上会发生溢出

题目 5

以下代码使用递归计算斐波那契数列，时间复杂度是多少？

int fib(int n) {
    if(n <= 1) return n;
    return fib(n - 1) + fib(n - 2);
}

{{ select(5) }}

• O(n)
• O(log n)
• O(2^n)
• O(n^2)