六、递推与递归（共18题）

1. 用递归法求 n 的阶乘，时间复杂度是 O(n)。（判断题）

{{ select(1) }}

• 正确
• 错误

2. 下面C++代码采用递推算法来实现整数 n 的阶乘，则横线上应填写（ ）。

int factorial(int n) {
    int result = 1;
    for (int i = 2; i <= n; i++) {
        // 在此处填入代码
    }
    return result;
}

{{ select(2) }}

• result *= i;
• result += i;
• result *= result;
• result += result;

3. 下面代码采用递推算法来计算斐波那契数列 f(n)=f(n-1)+f(n-2)，则横线上应填写（ ）。

int fib(int n) {
    if (n == 0 || n == 1) return n;
    int f1 = 0, f2 = 1, result = 0;
    for (int i = 2; i <= n; i++) {
        // 在此处填入代码
    }
    return result;
}

{{ select(3) }}

• result = f1 + f2; f1 = f2; f2 = result;
• result = f1 + f2; f2 = result; f1 = f2;
• result = f1 + f2; f1 = result; f2 = f1;
• f1 = f2; f2 = f1 + f2; result = f2;

4. 给定如下代码，其时间复杂度为（ ）。

int cellRecur(int n) {
    if (n == 1) return 1;
    return cellRecur(n - 1) + cellRecur(n - 1) + 1;
}

{{ select(4) }}

• O(n²)
• O(2ⁿ)
• O(1)
• O(n)

5. 小杨正在爬楼梯，需要爬 n 阶才能到达楼顶。如果每次可以爬1个或2个台阶，下面代码采用递推算法来计算一共有多少种不同的方法可以爬到楼顶，则横线上应填写（ ）。

int f(int n) {
    if (n == 1 || n == 2) return n;
    int f1 = 1, f2 = 2, res = 0;
    for (int i = 3; i <= n; i++) {
        // 在此处填入代码
    }
    return res;
}

{{ select(5) }}

• res = f1 + f2; f1 = f2; f2 = res;
• res += f1 + f2; f1 = f2; f2 = res;
• res = f1 + f2; f2 = res; f1 = f2;
• res += f1 + f2; f2 = res; f1 = f2;

6. 给定如下算法，其时间复杂度为（ ）。

bool f(int arr[], int n, int target) {
    for (int i = 0; i < (1 << n); i++) {
        int sum = 0;
        for (int j = 0; j < n; j++) {
            if (i & (1 << j)) sum += arr[j];
        }
        if (sum == target) return true;
    }
    return false;
}

{{ select(6) }}

• O(n²)
• O(n × 2ⁿ)
• O(1)
• O(n³)

7. 下述斐波那契数列计算的时间复杂度是（ ）。

int fibonacci(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    return fibonacci(n - 1) + fibonacci(n - 2);
}

{{ select(7) }}

• O(n)
• O(n²)
• O(n³)
• O(2ⁿ)

8. 小杨正在爬楼梯，需要 n 阶才能到达楼顶，每次可以爬1阶或2阶，求小杨有多少种不同的方法可以爬到楼顶，横线上应填写（ ）。

int climbStairs(int n) {
    if (n <= 2) return n;
    int prev2 = 1, prev1 = 2, current = 0;
    for (int i = 3; i <= n; ++i) {
        // 在此处填入代码
    }
    return current;
}

{{ select(8) }}

• prev2 = prev1; prev1 = current; current = prev1 + prev2;
• current = prev1 + prev2; prev2 = prev1; prev1 = current;
• current = prev1 + prev2; prev1 = current; prev2 = prev1;
• prev1 = current; prev2 = prev1; current = prev1 + prev2;

9. 给定函数 climbStairs(int n) 的定义如下，则 climbStairs(5) 的返回的值是（ ）。

int climbStairs(int n) {
    if (n <= 2) return n;
    int a = 1, b = 2;
    for (int i = 3; i <= n; i++) {
        int temp = a + b;
        a = b;
        b = temp;
    }
    return b;
}

{{ select(9) }}

• 5
• 8
• 13
• 10

10. 阅读以下函数，若调用 climbStairs(4)，返回值为（ ）。

int climbStairs(int n) {
    if (n <= 2) return n;
    int a = 1, b = 2;
    for (int i = 3; i <= n; i++) {
        int temp = a + b;
        a = b;
        b = temp;
    }
    return b;
}

{{ select(10) }}

• 3
• 4
• 5
• 8

11. 给定如下算法，其时间复杂度为（ ）。

bool f(int arr[], int n, int target) {
    for (int i = 0; i < n; i++) {
        int sum = 0;
        for (int j = 0; j < n; j++) {
            if (i & (1 << j)) sum += arr[j];
        }
        if (sum == target) return true;
    }
    return false;
}

{{ select(11) }}

• O(n)
• O(n²)
• O(n³)
• O(2ⁿ)

12. 执行 climb(6) 的返回值为（ ）。

int climb(int n) {
    if (n <= 2) return n;
    int a = 1, b = 2, c = 0;
    for (int i = 3; i <= n; i++) {
        c = a + b;
        a = b;
        b = c;
    }
    return c;
}

{{ select(12) }}

• 8
• 13
• 5
• 10

13. 下列代码段的时间复杂度为（ ）。

int cnt = 0;
for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        if ((i + j) % 3 == 0) cnt++;
    }
}

{{ select(13) }}

• O(n)
• O(n log n)
• O(n²)
• O(2ⁿ)

14. 假设有一个班级的成绩单，存储在一个长度为 n 的数组 scores 中，每个元素是一个学生的分数。老师想要找出所有满足 scores[i] + scores[j] + scores[k] == 300 的三元组，其中 i<j<k。下面代码实现该功能，请问其时间复杂度是（ ）。

int cnt = 0;
for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
        for (int k = j + 1; k < n; k++) {
            if (scores[i] + scores[j] + scores[k] == 300) cnt++;
        }
    }
}

{{ select(14) }}

• O(n)
• O(n²)
• O(n³)
• O(2ⁿ)

15. 考虑用如下递推方式计算斐波那契数列，时间复杂度是 O(n)。（判断题）

int n = 10;
int f[20];
f[0] = 0; f[1] = 1;
for (int i = 2; i <= n; i++)
    f[i] = f[i - 1] + f[i - 2];

{{ select(15) }}

• 正确
• 错误

16. 以下程序中使用了递推方式计算阶乘（n! = 1×2×...×n），计算结果正确。（判断题）

int factorial(int n) {
    int res = 1;
    for (int i = 0; i < n; ++i) {
        res = i;
    }
    return res;
}

{{ select(16) }}

• 正确
• 错误

17. 下面用递推方式计算斐波那契数列第 n 项的程序，时间复杂度是 O(2ⁿ)。（判断题）

int fib(int n) {
    if (n <= 1) return n;
    int f0 = 0, f1 = 1, cur = 0;
    for (int i = 2; i <= n; i++) {
        cur = f0 + f1;
        f0 = f1;
        f1 = cur;
    }
    return cur;
}

{{ select(17) }}

• 正确
• 错误

18. 递推算法通过逐步求解当前状态和前一个或几个状态之间的关系来解决问题。（判断题）

{{ select(18) }}

• 正确
• 错误