递归、递推与 DP¶

题目

int f(int n) { if (n == 1) return 1; return n * f(n - 1); } 则 f(4) =（ ）

• A. \(10\)
• B. \(24\)
• C. \(4\)
• D. \(16\)

题目

int g(int n) { if (n <= 2) return 1; return g(n-1) + g(n-2); } 则 g(6) =（ ）

• A. \(5\)
• B. \(6\)
• C. \(13\)
• D. \(8\)

题目

int h(int n) { if (n == 0) return 2; return h(n/2) + 1; } 则 h(8) =（ ）

• A. \(5\)
• B. \(4\)
• C. \(6\)
• D. \(3\)

题目

递归层数过多引发错误，是因为（ ）

• A. 堆空间溢出
• B. 队列空间溢出
• C. 系统分配的栈空间溢出
• D. CPU 过热

题目

递归 n 层、每层只开 O(1) 局部变量，空间复杂度（ ）

• A. \(O(n)\)（栈深 n 层）
• B. \(O(1)\)
• C. \(O(\log n)\)
• D. \(O(n^2)\)

题目

朴素递归计算 \(F(n)\)（斐波那契）的时间复杂度是（ ）

• A. \(O(n)\)
• B. \(O(n \log n)\)
• C. \(O(2^n)\)
• D. \(O(n^2)\)

题目

朴素递归斐波那契 \(O(2^n)\)、DP 迭代 \(O(n)\)，巨大差异的根本原因是（ ）

• A. 递归调用栈开销过大
• B. 操作系统限制递归深度
• C. DP 用了更少内存
• D. 朴素递归存在大量重叠子问题被重复计算

题目

给递归加上“算过的存起来、再要直接取”的缓存后，斐波那契的复杂度变为（ ）

• A. \(O(\log n)\)
• B. \(O(2^n)\)
• C. \(O(n^2)\)
• D. \(O(n)\)

题目

\(a_1 = 2\)，\(a_n = 2a_{n-1} + 1\)，则 $a_4 = $（ ）

• A. \(23\)
• B. \(31\)
• C. \(15\)
• D. \(7\)

题目

第 \(k\) 到 \(k+1\) 层消耗 \(10k\) 卡，从 1 层爬起消耗满 1000 卡，至少爬到（ ）层。

• A. \(13\)
• B. \(14\)
• C. \(16\)
• D. \(15\)

题目

\(T(n) = 2T(n/2) + O(n^2)\) 的解是（ ）

• A. \(O(n\log n)\)
• B. \(O(n^2)\)
• C. \(O(n^2 \log n)\)
• D. \(O(n^3)\)

题目

\(T(n) = 2T(n/2) + O(n)\) 的解是（ ）

• A. \(O(n)\)
• B. \(O(n \log n)\)
• C. \(O(n^2)\)
• D. \(O(\log n)\)

题目

\(T(n) = T(n/2) + O(1)\) 的解是（ ）

• A. \(O(1)\)
• B. \(O(\log n)\)
• C. \(O(n)\)
• D. \(O(\sqrt n)\)

题目

朴素的 pow(x, n) = x * pow(x, n-1) 的时间复杂度是（ ）

• A. \(O(n \log n)\)
• B. \(O(\log n)\)
• C. \(O(1)\)
• D. \(O(n)\)

题目

汉诺塔 \(T(n) = 2T(n-1) + 1\)，\(T(1) = 1\)，则 $T(6) = $（ ）

• A. \(63\)
• B. \(64\)
• C. \(31\)
• D. \(127\)

题目

容量 8、物品 \((w,v) = (3,4), (5,6), (4,5)\) 的 0-1 背包最优价值是（ ）

• A. \(11\)
• B. \(9\)
• C. \(10\)
• D. \(8\)

题目

0-1 背包不能按“价值/重量比”贪心求解的原因（ ）

• A. 物品不能拆分，高性价比物品可能挤占空间使整体不是最优
• B. 计算太慢
• C. 数据会溢出
• D. 没有原因，可以贪心

题目

LCS 中 \(x_i = y_j\) 时 $dp[i][j] = $（ ）

• A. \(\max(dp[i-1][j], dp[i][j-1])\)
• B. \(dp[i][j-1] + 1\)
• C. \(dp[i-1][j-1]\)
• D. \(dp[i-1][j-1] + 1\)

题目

ABCAAAABA 与 ABABCBABA 的 LCS 长度是（ ）

• A. \(4\)
• B. \(5\)
• C. \(6\)
• D. \(7\)

题目

朴素递归斐波那契计算 \(F(6)\)（\(F(1)=F(2)=1\)）共发生（ ）次函数调用。

• A. \(15\)
• B. \(5\)
• C. \(31\)
• D. \(8\)

题目

给上一题的递归加上记忆化后，计算 \(F(n)\) 的函数调用次数是（ ）

• A. \(O(n)\)（每个 \(F(i)\) 只算一次）
• B. \(O(2^n)\)
• C. \(O(n^2)\)
• D. \(O(1)\)

题目

$5^{22} \bmod 23 = $（ ）

• A. \(22\)
• B. \(1\)
• C. \(5\)
• D. \(0\)

题目

\(f(1) = 1\)，\(f(n) = 3f(n-1) \bmod 7\)，则 $f(4) = $（ ）

• A. \(2\)
• B. \(3\)
• C. \(6\)
• D. \(5\)

题目

4 根柱子，相邻圆环编号和必须是完全平方数，从 1 号开始依次放，最多放（ ）个。

• A. \(9\)
• B. \(11\)
• C. \(7\)
• D. \(13\)

题目

任何递归算法（ ）改成迭代。

• A. 都可以（用显式栈模拟递归栈）
• B. 只有树递归可以
• C. 不可以
• D. 只有简单递归可以

题目

下列递归中没有重叠子问题的是（ ）

• A. 斐波那契 \(F(n) = F(n-1) + F(n-2)\)
• B. \(g(n) = g(n-1) + n\)
• C. 组合数 \(C(n,k) = C(n-1,k-1) + C(n-1,k)\)
• D. 朴素递归 LCS

题目

小明想通过走楼梯来锻炼身体，假设从第 \(1\) 层走到第 \(2\) 层消耗 \(10\) 卡热量，接着从第 \(2\) 层走到第 \(3\) 层消耗 \(20\) 卡热量，从第 \(3\) 层走到第 \(4\) 层消耗 \(30\) 卡热量，依此类推，从第 \(k\) 层走到第 \(k+1\) 层消耗 \(10k\) 卡热量（\(k>1\)）。如果小明想从 \(1\) 层开始，通过连续向上爬楼梯消耗 \(1000\) 卡热量，至少要爬到第几层楼？（ ）

• A. \(14\)
• B. \(16\)
• C. \(15\)
• D. \(13\)

题目

在程序运行过程中，如果递归调用的层数过多，可能会由于（ ）引发错误。

• A. 系统分配的栈空间溢出
• B. 系统分配的队列空间溢出
• C. 系统分配的链表空间溢出
• D. 系统分配的堆空间溢出

题目

有如下递归代码：

1
2
3

solve(t, n):
    if t=1 return 1
    else return 5*solve(t-1,n) mod n

则 solve(23,23) 的结果为（ ）。

• A. \(1\)
• B. \(7\)
• C. \(12\)
• D. \(22\)

题目

斐波那契数列的定义为：\(F_1=1\)，\(F_2=1\)，\(F_n=F_{n-1}+F_{n-2}\)（\(n\ge3\)）。现在用如下程序来计算斐波那契数列的第 \(n\) 项，其时间复杂度为（ ）。

1
2
3

F(n):
    if n<=2 return 1
    else return F(n-1) + F(n-2)

• A. \(O(n)\)
• B. \(O(n^2)\)
• C. \(O(2^n)\)
• D. \(O(n\log n)\)

题目

ack 函数在输入参数 (2,2) 时的返回值为（ ）。

1
2
3
4
5

unsigned ack(unsigned m, unsigned n) {
    if (m == 0) return n + 1;
    if (n == 0) return ack(m - 1, 1);
    return ack(m - 1, ack(m, n - 1));
}

• A. \(5\)
• B. \(7\)
• C. \(9\)
• D. \(13\)

题目

假设有 \(n\) 根柱子，需要按照以下规则依次放置编号为 \(1,2,3,\ldots\) 的圆环：每根柱子的底部固定，顶部可以放入圆环；每次从柱子顶部放入圆环时，需要保证任何两个相邻圆环的编号之和是一个完全平方数。请计算当有 \(4\) 根柱子时，最多可以放置（ ）个圆环。

• A. \(7\)
• B. \(9\)
• C. \(11\)
• D. \(5\)

题目

最长公共子序列长度常常用来衡量两个序列的相似度。给定两个序列 \(X=\{x_1,x_2,x_3,\ldots,x_m\}\) 和 \(Y=\{y_1,y_2,y_3,\ldots,y_n\}\)，最长公共子序列（LCS）问题的目标是找到一个最长的新序列 \(Z\)，使得 \(Z\) 既是 \(X\) 的子序列，又是 \(Y\) 的子序列，且长度最大。（序列 \(A\) 是 \(B\) 的子序列，当且仅当保持 \(B\) 的元素顺序删除若干元素后可构成 \(A\)。）

序列 ABCAAAABA 和 ABABCBABA 的最长公共子序列长度为（ ）。

• A. \(4\)
• B. \(5\)
• C. \(6\)
• D. \(7\)

题目

在 C++ 中，以下哪个函数调用会造成栈溢出？（ ）

• A. int foo() { return 0; }
• B. int bar() { int x = 1; return x; }
• C. void baz() { int a[1000]; baz(); }
• D. void qux() { return; }

题目

已知 \(f(1) = 1\)，且对于 \(n \ge 2\) 有 \(f(n) = f(n - 1) + f(\lfloor n/2 \rfloor)\)，则 \(f(4)\) 的值为（ ）。

• A. \(4\)
• B. \(5\)
• C. \(6\)
• D. \(7\)

题目

一个 \(0\)-\(1\) 背包问题，背包容量为 \(20\)。现有 \(5\) 个物品，其重量和价值分别为 \(7, 5, 4, 3, 6\) 和 \(15, 12, 9, 7, 13\)。装入背包的物品能获得的最大总价值是多少？

• A. \(43\)
• B. \(41\)
• C. \(45\)
• D. \(44\)

题目

斐波那契数列的定义为 \(F(0)=0\)，\(F(1)=1\)，\(F(n) = F(n-1) + F(n-2)\)。使用朴素递归方法计算 \(F(n)\) 的时间复杂度是指数级的。而使用动态规划（或迭代）方法的时间复杂度是线性的。造成这种巨大差异的根本原因是？

• A. 递归函数调用栈开销过大
• B. 操作系统对递归深度有限制
• C. 朴素递归中存在大量的重叠子问题未被重复利用
• D. 动态规划使用了更少的数据存储空间