普及组程序专项-递归
普及组递归算法专题训练（12题）
题目1：汉诺塔问题
1 #include <iostream>
2 using namespace std;
3
4 void hanoi(int n, char from, char to, char aux) {
5 if (n == 1) {
6 cout << "Move disk 1 from " << from << " to " << to << endl;
7 return;
8 }
9 hanoi(n - 1, from, aux, to);
10 cout << "Move disk " << n << " from " << from << " to " << to << endl;
11 hanoi(n - 1, aux, to, from);
12 }
13
14 int main() {
15 int n;
16 cin >> n;
17 hanoi(n, 'A', 'C', 'B');
18 return 0;
19 }
判断题
- 汉诺塔问题的时间复杂度是O(2^n)。 ( )
- 汉诺塔问题的递归方程是T(n) = 2T(n-1) + 1。 ( )
- 对于3个盘子，需要7次移动。 ( )
选择题
4. 对于4个盘子，需要多少次移动？ ( )
A. 15
B. 16
C. 31
D. 32
- 第9行的
hanoi(n - 1, from, aux, to)中，aux参数传递的是：( )
A. 源柱子
B. 目标柱子
C. 辅助柱子
D. 盘子编号
题目2：斐波那契数列（带行号）
1 #include <iostream>
2 using namespace std;
3
4 int fib(int n) {
5 if (n <= 1) return n;
6 return fib(n - 1) + fib(n - 2);
7 }
8
9 int main() {
10 int n;
11 cin >> n;
12 cout << fib(n) << endl;
13 return 0;
14 }
判断题
- 第5行的递归基包含n=0和n=1。 ( )
- 第6行的递归调用会产生大量重复计算。 ( )
- 计算fib(5)时，fib(3)会被计算2次。 ( )
选择题
4. 计算fib(6)时，fib(2)会被计算多少次？ ( )
A. 3次
B. 4次
C. 5次
D. 6次
- 如果将第5行改为
if (n == 0) return 0; if (n == 1) return 1;，会有什么影响？ ( )
A. 功能相同，但更明确
B. 效率提高
C. 可能栈溢出
D. 没有影响
题目3：阶乘计算（带行号）
1 #include <iostream>
2 using namespace std;
3
4 int factorial(int n) {
5 if (n == 0) return 1;
6 return n * factorial(n - 1);
7 }
8
9 int main() {
10 int n;
11 cin >> n;
12 cout << factorial(n) << endl;
13 return 0;
14 }
判断题
- 第5行是递归基，当n=0时返回1。 ( )
- 计算factorial(5)需要6次函数调用（包括第一次调用）。 ( )
- 如果将第6行改为
return n + factorial(n - 1)，会计算1+2+...+n的和。 ( )
选择题
4. 输入n=5时，函数调用的顺序是： ( )
A. factorial(5)→factorial(4)→factorial(3)→factorial(2)→factorial(1)→factorial(0)
B. factorial(0)→factorial(1)→factorial(2)→factorial(3)→factorial(4)→factorial(5)
C. factorial(5)→factorial(1)→factorial(2)→factorial(3)→factorial(4)
D. 以上都不对
- 如果输入n=-1，程序会： ( )
A. 返回1
B. 无限递归直到栈溢出
C. 编译错误
D. 返回0
题目4：字符串反转（带行号）
1 #include <iostream>
2 #include <string>
3 using namespace std;
4
5 string reverse(string s) {
6 if (s.length() <= 1) return s;
7 return reverse(s.substr(1)) + s[0];
8 }
9
10 int main() {
11 string s;
12 cin >> s;
13 cout << reverse(s) << endl;
14 return 0;
15 }
判断题
- 第6行的递归基处理空字符串和单字符字符串。 ( )
- 第7行的
s.substr(1)获取从索引1开始到结尾的子串。 ( ) - 这个算法在每次递归调用时都会创建新的字符串，效率不高。 ( )
选择题
4. 对于字符串"abc"，递归调用过程是： ( )
A. reverse("abc")→reverse("bc")→reverse("c")
B. reverse("abc")→reverse("ab")→reverse("a")
C. reverse("abc")→reverse("bca")→reverse("cab")
D. reverse("abc")→reverse("a")→reverse("b")→reverse("c")
- 如果将第7行改为
return s[s.length()-1] + reverse(s.substr(0, s.length()-1))，会： ( )
A. 功能相同，但递归方向不同
B. 结果错误
C. 效率更高
D. 栈溢出
题目5：数组求和（带行号）
1 #include <iostream>
2 using namespace std;
3
4 int sumArray(int arr[], int n) {
5 if (n <= 0) return 0;
6 return arr[n-1] + sumArray(arr, n-1);
7 }
8
9 int main() {
10 int n;
11 cin >> n;
12 int arr[n];
13 for (int i = 0; i < n; i++) {
14 cin >> arr[i];
15 }
16 cout << sumArray(arr, n) << endl;
17 return 0;
18 }
判断题
- 第5行处理n<=0的情况，包括数组为空的情况。 ( )
- 第6行的
arr[n-1]访问数组的最后一个元素。 ( ) - 这个算法会创建n个递归调用帧。 ( )
选择题
4. 对于数组[1,2,3,4,5]，递归调用的返回值顺序是： ( )
A. 0→1→3→6→10→15
B. 15→10→6→3→1→0
C. 5→9→12→14→15→0
D. 0→5→4→3→2→1
- 如果将第6行改为
return arr[0] + sumArray(arr+1, n-1)，会： ( )
A. 功能相同，但使用指针偏移
B. 结果错误
C. 效率更高
D. 需要修改函数签名
题目6：最大公约数（欧几里得算法）（带行号）
1 #include <iostream>
2 using namespace std;
3
4 int gcd(int a, int b) {
5 if (b == 0) return a;
6 return gcd(b, a % b);
7 }
8
9 int main() {
10 int a, b;
11 cin >> a >> b;
12 cout << gcd(a, b) << endl;
13 return 0;
14 }
判断题
- 第5行是递归基，当b=0时返回a。 ( )
- 第6行利用辗转相除法原理。 ( )
- 如果a<b，第一次递归调用会交换a和b的位置。 ( )
选择题
4. 计算gcd(48,18)的递归调用参数序列是： ( )
A. (48,18)→(18,12)→(12,6)→(6,0)
B. (48,18)→(18,48)→(48,18)→...
C. (18,48)→(48,18)→(18,12)→(12,6)→(6,0)
D. (48,18)→(30,18)→(18,12)→(12,6)→(6,0)
- 如果将第5行改为
if (b == 0 || a == b) return a;，会： ( )
A. 增加一个递归基，提高效率
B. 结果可能错误
C. 减少递归深度
D. A和C都正确
题目7：快速幂运算（带行号）
1 #include <iostream>
2 using namespace std;
3
4 double power(double x, int n) {
5 if (n == 0) return 1;
6 if (n % 2 == 0) {
7 double half = power(x, n/2);
8 return half * half;
9 } else {
10 return x * power(x, n-1);
11 }
12 }
13
14 int main() {
15 double x;
16 int n;
17 cin >> x >> n;
18 cout << power(x, n) << endl;
19 return 0;
20 }
判断题
- 第5行是递归基，任何数的0次方等于1。 ( )
- 第6-8行处理偶数次幂的情况，使用分治策略。 ( )
- 第10行处理奇数次幂的情况，转换为偶数次幂计算。 ( )
选择题
4. 计算power(2,10)的递归调用序列是： ( )
A. power(2,10)→power(2,5)→power(2,4)→power(2,2)→power(2,1)→power(2,0)
B. power(2,10)→power(2,5)→power(2,4)→power(2,2)→power(2,1)
C. power(2,10)→power(2,5)→power(2,2)→power(2,1)→power(2,0)
D. 以上都不对
- 如果将第6行改为
if (n % 2 == 0 || n == 0)，会： ( )
A. 增加不必要的判断
B. 提高效率
C. 结果错误
D. 没有影响
题目8：集合的所有子集（回溯法）（带行号）
1 #include <iostream>
2 #include <vector>
3 using namespace std;
4
5 void backtrack(vector<int>& nums, int start, vector<int>& path, vector<vector<int>>& result) {
6 result.push_back(path);
7
8 for (int i = start; i < nums.size(); i++) {
9 path.push_back(nums[i]);
10 backtrack(nums, i + 1, path, result);
11 path.pop_back();
12 }
13 }
14
15 vector<vector<int>> subsets(vector<int>& nums) {
16 vector<vector<int>> result;
17 vector<int> path;
18 backtrack(nums, 0, path, result);
19 return result;
20 }
21
22 int main() {
23 vector<int> nums = {1, 2, 3};
24 auto result = subsets(nums);
25
26 for (auto& subset : result) {
27 cout << "[";
28 for (int i = 0; i < subset.size(); i++) {
29 cout << subset[i];
30 if (i < subset.size() - 1) cout << ",";
31 }
32 cout << "] ";
33 }
34 return 0;
35 }
判断题
- 第6行的result.push_back(path)记录当前路径对应的子集。 ( )
- 第9-11行实现选择、递归、撤销选择的回溯过程。 ( )
- 第10行的backtrack调用中，i+1确保不会重复选择相同元素。 ( )
选择题
4. 对于nums={1,2,3}，递归树的第一层（start=0）会生成哪些子集？ ( )
A. {},{1},{2},{3}
B. {},{1},{1,2},{1,2,3}
C. {},{1},{1,2},{1,3},{2},{2,3},{3}
D. 以上都不对
- 如果将第6行移到第8行之后，会： ( )
A. 缺少空子集
B. 缺少所有子集
C. 结果相同
D. 程序错误
题目9：全排列（包含重复元素）（带行号）
1 #include <iostream>
2 #include <vector>
3 #include <algorithm>
4 using namespace std;
5
6 void permuteUnique(vector<int>& nums, int start, vector<vector<int>>& result) {
7 if (start == nums.size()) {
8 result.push_back(nums);
9 return;
10 }
11
12 for (int i = start; i < nums.size(); i++) {
13 if (i != start && nums[i] == nums[start]) continue;
14
15 swap(nums[start], nums[i]);
16 permuteUnique(nums, start + 1, result);
17 swap(nums[start], nums[i]);
18 }
19 }
20
21 vector<vector<int>> permuteUnique(vector<int>& nums) {
22 vector<vector<int>> result;
23 sort(nums.begin(), nums.end());
24 permuteUnique(nums, 0, result);
25 return result;
26 }
27
28 int main() {
29 vector<int> nums = {1, 1, 2};
30 auto result = permuteUnique(nums);
31
32 for (auto& perm : result) {
33 for (int num : perm) {
34 cout << num << " ";
35 }
36 cout << endl;
37 }
38 return 0;
39 }
判断题
- 第7-9行是递归基，当start等于数组大小时记录一个排列。 ( )
- 第13行跳过重复元素，避免生成重复排列。 ( )
- 第15-17行通过交换元素生成不同的排列顺序。 ( )
选择题
4. 对于nums={1,1,2}，start=0时，第12-18行的循环会执行几次？ ( )
A. 1次
B. 2次
C. 3次
D. 4次
- 如果删除第13行，对于nums={1,1,2}会： ( )
A. 产生重复排列
B. 结果正确但效率低
C. 缺少某些排列
D. 程序错误
题目10：数独求解器（带行号）
1 #include <iostream>
2 #include <vector>
3 using namespace std;
4
5 bool isValid(vector<vector<char>>& board, int row, int col, char c) {
6 for (int i = 0; i < 9; i++) {
7 if (board[i][col] == c) return false;
8 if (board[row][i] == c) return false;
9 if (board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] == c) return false;
10 }
11 return true;
12 }
13
14 bool solveSudoku(vector<vector<char>>& board) {
15 for (int i = 0; i < 9; i++) {
16 for (int j = 0; j < 9; j++) {
17 if (board[i][j] == '.') {
18 for (char c = '1'; c <= '9'; c++) {
19 if (isValid(board, i, j, c)) {
20 board[i][j] = c;
21 if (solveSudoku(board)) return true;
22 board[i][j] = '.';
23 }
24 }
25 return false;
26 }
27 }
28 }
29 return true;
30 }
31
32 int main() {
33 vector<vector<char>> board = {
34 {'5','3','.','.','7','.','.','.','.'},
35 {'6','.','.','1','9','5','.','.','.'},
36 {'.','9','8','.','.','.','.','6','.'},
37 {'8','.','.','.','6','.','.','.','3'},
38 {'4','.','.','8','.','3','.','.','1'},
39 {'7','.','.','.','2','.','.','.','6'},
40 {'.','6','.','.','.','.','2','8','.'},
41 {'.','.','.','4','1','9','.','.','5'},
42 {'.','.','.','.','8','.','.','7','9'}
43 };
44
45 solveSudoku(board);
46
47 for (auto& row : board) {
48 for (char c : row) {
49 cout << c << " ";
50 }
51 cout << endl;
52 }
53 return 0;
54 }
判断题
- 第6-10行的isValid函数检查行、列和3x3宫格是否合法。 ( )
- 第20-22行尝试放置数字，递归求解，失败时回溯。 ( )
- 第25行返回false表示当前分支无解，需要回溯。 ( )
选择题
4. 第9行检查3x3宫格的索引计算中，3 * (row / 3) + i / 3表示： ( )
A. 宫格内的行索引
B. 宫格内的列索引
C. 整个棋盘的行索引
D. 整个棋盘的列索引
- 如果将第22行删除，会： ( )
A. 无法回溯，可能导致死循环
B. 求解速度更快
C. 结果可能错误
D. 程序崩溃
题目11：表达式求值（带行号）
1 #include <iostream>
2 #include <string>
3 #include <stack>
4 #include <cctype>
5 using namespace std;
6
7 int calculate(string s) {
8 stack<int> nums;
9 stack<char> ops;
10 int num = 0;
11 char sign = '+';
12
13 for (int i = 0; i < s.length(); i++) {
14 char c = s[i];
15
16 if (isdigit(c)) {
17 num = num * 10 + (c - '0');
18 }
19
20 if (c == '(') {
21 int count = 1;
22 int j = i + 1;
23 while (j < s.length() && count > 0) {
24 if (s[j] == '(') count++;
25 if (s[j] == ')') count--;
26 j++;
27 }
28 num = calculate(s.substr(i + 1, j - i - 2));
29 i = j - 1;
30 }
31
32 if (!isdigit(c) && c != ' ' || i == s.length() - 1) {
33 if (sign == '+') {
34 nums.push(num);
35 } else if (sign == '-') {
36 nums.push(-num);
37 } else if (sign == '*') {
38 int top = nums.top();
39 nums.pop();
40 nums.push(top * num);
41 } else if (sign == '/') {
42 int top = nums.top();
43 nums.pop();
44 nums.push(top / num);
45 }
46
47 sign = c;
48 num = 0;
49 }
50 }
51
52 int result = 0;
53 while (!nums.empty()) {
54 result += nums.top();
55 nums.pop();
56 }
57 return result;
58 }
59
60 int main() {
61 string expr = "3*(4+5)-6/2";
62 cout << calculate(expr) << endl;
63 return 0;
64 }
判断题
- 第20-30行处理括号，递归计算括号内的表达式。 ( )
- 第32-49行遇到运算符或字符串结尾时处理前一个运算符。 ( )
- 第47行更新sign为当前字符c，用于下一次运算。 ( )
选择题
4. 对于表达式"2+34"，当遇到''时，sign的值是： ( )
A. '+'
B. '*'
C. ' '
D. 不确定
- 如果将第28行改为
num = calculate(s.substr(i, j - i));，会： ( )
A. 包含外层括号，导致无限递归
B. 结果正确
C. 缺少括号内的内容
D. 数组越界
题目12：N皇后问题（带行号）
1 #include <iostream>
2 #include <vector>
3 using namespace std;
4
5 bool isValid(vector<string>& board, int row, int col) {
6 for (int i = 0; i < row; i++) {
7 if (board[i][col] == 'Q') return false;
8 }
9
10 for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
11 if (board[i][j] == 'Q') return false;
12 }
13
14 for (int i = row - 1, j = col + 1; i >= 0 && j < board.size(); i--, j++) {
15 if (board[i][j] == 'Q') return false;
16 }
17
18 return true;
19 }
20
21 void backtrack(vector<string>& board, int row, vector<vector<string>>& result) {
22 if (row == board.size()) {
23 result.push_back(board);
24 return;
25 }
26
27 for (int col = 0; col < board.size(); col++) {
28 if (!isValid(board, row, col)) continue;
29
30 board[row][col] = 'Q';
31 backtrack(board, row + 1, result);
32 board[row][col] = '.';
33 }
34 }
35
36 vector<vector<string>> solveNQueens(int n) {
37 vector<vector<string>> result;
38 vector<string> board(n, string(n, '.'));
39 backtrack(board, 0, result);
40 return result;
41 }
42
43 int main() {
44 int n = 4;
45 auto solutions = solveNQueens(n);
46
47 for (int i = 0; i < solutions.size(); i++) {
48 cout << "Solution " << i + 1 << ":" << endl;
49 for (string row : solutions[i]) {
50 cout << row << endl;
51 }
52 cout << endl;
53 }
54 return 0;
55 }
判断题
- 第6-8行检查同一列是否有皇后冲突。 ( )
- 第10-12行检查左上对角线是否有皇后冲突。 ( )
- 第14-16行检查右上对角线是否有皇后冲突。 ( )
选择题
4. 第30-32行实现的选择、递归、撤销操作中，第32行的作用是： ( )
A. 放置皇后
B. 移除皇后，回溯
C. 检查合法性
D. 记录解
- 如果将第28行改为
if (isValid(board, row, col))，删除continue，会： ( )
A. 功能相同，但效率低
B. 结果错误
C. 缺少解
D. 程序错误