2024 csp-j 初赛真题

2024/9/22

# 第1题

32 位 int 类型的存储范围是？

A. -2147483647 ~ +2147483647
B. -2147483647 ~ +2147483648
C. -2147483648 ~ +2147483647
D. -2147483648 ~ +2147483648

解析：32 位 int 类型，除最高位为符号位外，剩下 31 位均为数字。但 0 的二进制最高位也是 0，所以除了 0 以外，正整数部分只有 $2^{31} - 1 = 2147483647$ 个数，而负整数部分有 $2^{31} = 2147483648$ 个数字。

# 第2题

计算 $(14_{8} - 1010_{2}) {\times} D_{16} - 1101_{2}$ 的结果，并选择答案的十进制值：

A. 13
B. 14
C. 15
D. 16

解析： $14_{8} = 12_{10}$
$1010_{2} = 10_{10}$
$D_{16} = 13_{10}$
$1101_{2} = 13_{10}$
$(12 - 10) {\times} 13 - 13 = 13$

# 第3题

某公司有 10 名员工，分为 3 个部门：A 部门有 4 名员工，B 部门有 3 名员工、C 部门有 3 名员工。现需要从这 10 名员工中选出 4 名组成一个工作小组，且每个部门至少要有 1 人。问有多少种选择方式？

A. 120
B. 126
C. 132
D. 238

解析：分类讨论，三个部门选四个人，且每个部门至少要有 1 人：

A 部门选 2 人，B 部门和 C 部门各选 1 人，组合数为 $C(4,2) \times C(3,1) \times C(3,1) = 54$
B 部门选 2 人，A 和 C 部门各选 1 人，组合数为 $C(4,1) \times C(3,2) \times C(3,1) = 36$
C 部门选 2 人，A 和 B 部门各选 1 人，组合数为 $C(4,1) \times C(3,1) \times C(3,2) = 36$

总选择方式为 $54 + 36 + 36 = 126$ 。

# 第4题

以下哪个序列对应数字 0 至 7 的 3 位二进制格雷码（Gray code）？

A. 0000，0001，0011，0010，0110，0111，0101，1000
B. 0000，0001，0011，0010，0110，0111，0100，0101
C. 0000，0001，0011，0010，0100，0101，0111，0110
D. 0000，0001，0011，0010，0110，0111，0101，0100

解析：格雷码的性质为：

相邻两个编码只能有一位不同
首尾两个编码视作相邻，也只能有一位不同
同一编码不能重复出现明显只有 D 选项符合条件

# 第5题

记 1KB 为 1024 字节（byte）、1MB 为 1024KB，那么 1MB 是多少二进制位（bit）？

A. 1000000
B. 1048576
C. 8000000
D. 8388608

解析：
1 MB = 1024 KB = 1024 × 1024 B = 1024 × 1024 × 8 bit = 8388608 bit。

# 第6题

以下哪个不是 C++ 中的基本数据类型？

A. int
B. float
C. struct
D. char

解析：struct 结构体不算基本数据类型。

# 第7题

以下哪个不是 C++ 中的循环语句？

A. for
B. while
C. do-while
D. repeat-until

解析：C++ 中并没有 repeat-until 循环，其他三项为常见的循环语句。

# 第8题

在 C/C++ 中，(char)('a' + 13) 与下面哪个值相等？

A. 'm'
B. 'n'
C. 'z'
D. 'y'

解析：ASCII 码表中，小写字母按照字母表顺序连续出现。'a' + 13 就是从 'a' 开始往后数 13 个字母，即 'n'。

# 第9题

假设有序表中有 1000 个元素，则用二分法查找元素 X 最多需要比较多少次？

A. 25
B. 10
C. 7
D. 1

解析：二分法查找时间复杂度是以 2 为底数的对数，即 $\log_2 n$ 。当 $n = 1000$ 时，\log_2 1000 ≈ 10，或者可以模拟二分的过程，每次二分后要么直接找到对应数字，要么剩余数量变成原来的一半，观察做多少次可以剩 1 个数字即可

# 第10题

以下哪个不是操作系统的名字？

A. Notepad
B. Linux
C. Windows
D. macOS

解析：Notepad 是记事本软件，而不是操作系统。

# 第11题

在无向图中，所有顶点的度数之和等于什么？

A. 图的边数
B. 图的边数的两倍
C. 图的顶点数
D. 图的顶点数的两倍

解析：无向图中，每条边连接两个点
根据度数的定义，无向图中点的度数就是有多少条边连接着当前点
那么每条边对于总度数的贡献就是 2
即无向图的总度数一定等于边数 × 2

# 第12题

已知二叉树的前序遍历为 [A, B, D, E, C, F, G]，中序遍历为 [D, B, E, A, F, C, G]，请问该二叉树的后序遍历结果是：

A. [D, E, B, F, G, C, A]
B. [D, E, B, F, G, A, C]
C. [D, B, E, F, G, C, A]
D. [D, B, E, F, G, A, C]

解析：

       A
      / \
     B   C
    / \  / \
   D   E F  G

画出对应的二叉树后可知，这是一个包含 7 个节点的满二叉树，后序遍历的结果是 [D, B, E, F, G, C, A]。

# 第13题

给定一个空栈，支持入栈和出栈操作。若入栈操作的元素依次是 1 2 3 4 5 6，其中 1 最先入栈，6 最后入栈，下面哪种出栈顺序是不可能的？

A. 6 5 4 3 2 1
B. 1 6 5 4 3 2
C. 2 4 6 5 3 1
D. 1 3 5 2 4 6

解析：通过模拟栈操作可以发现，D 选项的出栈顺序在 1 3 5 出栈后，栈顶元素不可能是 2，因此 D 是不可能的。

# 第14题

有 5 个男生和 3 个女生站成一排，规定 3 个女生必须相邻，问有多少种不同的排列方式？

A. 4320 种
B. 5040 种
C. 3600 种
D. 2880 种

解析：将 3 个女生视为一个整体，这样与剩下的 5 个男生组成 6 个单位，这 6 个单位的排列方式有 $6! = 720$ 种。然后，3 个女生内部还有 $3! = 6$ 种排列方式。因此，总的排列方式是 $6! \times 3! = 720 \times 6 = 4320$ 。

# 第15题

编译器的主要作用是什么？

A. 直接执行源代码
B. 将源代码转换为机器代码
C. 进行代码调试
D. 管理程序运行时的内存

解析：编译器的作用是将源代码转换为机器代码。A 选项是解释器的功能，C 选项是调试器的功能，D 选项是操作系统的功能。

#include <iostream> // 包含输入输出库
using namespace std; // 使用标准命名空间

// 检查一个整数 n 是否为素数
bool isPrime(int n)
{
    // 如果 n 小于等于 1，则不是素数
    if(n <= 1)
    {
        return false; // 返回 false
    }
    // 从 2 开始检查到 n 的平方根
    for(int i = 2; i * i <= n; i++)
    {
        // 如果 n 能被 i 整除，则不是素数
        if(n % i == 0)
        {
            return false; // 返回 false
        }
    }
    // 如果没有找到因数，则 n 是素数
    return true; // 返回 true
}

// 统计小于等于 n 的素数数量
int countPrimes(int n)
{
    int count = 0; // 初始化计数器为 0
    // 从 2 开始遍历到 n
    for(int i = 2; i <= n; i++)
    {
        // 如果 i 是素数，计数器加一
        if(isPrime(i))
        {
            count++; // 计数器加一
        }
    }
    // 返回素数的总数量
    return count; // 返回计数器的值
}

// 计算小于等于 n 的素数和
int sumPrimes(int n)
{
    int sum = 0; // 初始化和为 0
    // 从 2 开始遍历到 n
    for(int i = 2; i <= n; i++)
    {
        // 如果 i 是素数，将 i 加到和中
        if(isPrime(i))
        {
            sum += i; // 累加素数
        }
    }
    // 返回素数的总和
    return sum; // 返回和的值
}

int main()
{
    int x; // 定义变量 x
    cin >> x; // 从标准输入读取整数 x
    // 输出小于等于 x 的素数数量和素数的总和
    cout << countPrimes(x) << " " << sumPrimes(x) << endl; 
    return 0; // 返回 0，表示程序正常结束
}

观察程序可知
isPrime(n)函数在判断整数n是否是一个素数
countPrimes(n)函数在求 2~n 之间的素数数量
sumPrimes(n)函数在求 2~n 之间的素数总和
程序输入一个整数x，输出两个整数:2~x的素数数量以及2~x的素数和

# 第16题

当输入为 "10" 时，程序的第一个输出为 "4"，第二个输出为 "17"。

A. 对
B. 错

解析：10 以内的素数有 2, 3, 5, 7，数量为 4，总和为 17。因此答案是对的。

# 第17题

若将 isPrime(i) 函数中的条件改为 i <= n / 2，输入 "20" 时，countPrimes(20) 的输出将变为 "6"。

A. 对
B. 错

解析：首先观察代码第 6 到 9 行，发现小于 2 的情况都已经被排除了，接下来循环过程一定满足 $n \geq 2$
原本的代码判断条件是 $i^2 \leq n$ ，表示 i 不会超过 $\sqrt{n}$
而改后的代码 $i \leq \frac{n}{2}$ 表示 $i$ 不超过 $\lfloor \frac{n}{2} \rfloor$ 。在 $n \geq 2$ 时， $\lfloor \sqrt{n} \rfloor \leq \lfloor \frac{n}{2} \rfloor$ 一定成立。所以改后无非就是时间复杂度从 $O(\sqrt{n})$ 变成了 $O(n)$ ，对答案无影响。输入 $20$ 时， $20$ 以内的素数有 $2, 3, 5, 7, 11, 13, 17, 19$ ，共 $8$ 个。

# 第18题

sumPrimes 函数计算的是从 2 到 n 之间的所有素数之和。

A. 对
B. 错

解析：sumPrimes 函数计算的是从 2 到 n 之间的所有素数之和，因此答案是对的。

# 第19题

当输入为 50 时，sumPrimes(50) 的输出为（）。

A. 1060
B. 328 C. 381 D. 275

解析：50 以内的素数有 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47，总和为 $2 + 3 + 5 + 7 + 11 + 13 + 17 + 19 + 23 + 29 + 31 + 37 + 41 + 43 + 47 = 328$ 。因此答案是 B。

# 第20题

若将 for (int i = 2; i * i <= n; i++) 改为 for (int i = 2; i <= n; i++)，输入 "10" 时，程序的输出（）。

A. 将不能正确计算 10 以内素数个数及其和
B. 仍然输出 "4" 和 "17"
C. 输出 "4" 和 "17"
D. 输出结果不变，但运行时间更短

解析：更改后的代码在 i 大于 $\sqrt{n}$ 时会继续进行判断，不能正确判断素数。因此答案为 A。

#include <iostream> // 包含输入输出库
#include <vector>   // 包含向量库
using namespace std; // 使用标准命名空间

// 计算最小花费
int compute(vector<int>& cost)
{
    int n = cost.size(); // 获取成本数组的大小
    vector<int> dp(n + 1, 0); // 创建动态规划数组 dp，大小为 n + 1，初始值为 0
    dp[1] = cost[0]; // dp[1] 赋值为成本数组的第一个元素

    // 从第 2 个楼梯开始计算最小花费
    for(int i = 2; i <= n; i++)
    {
        // 计算到达第 i 个楼梯的最小花费
        dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i - 1]; 
        // 取到达前一个楼梯和前两个楼梯的最小花费，并加上当前楼梯的成本
    }

    // 返回到达最后一个或倒数第二个楼梯的最小花费
    return min(dp[n], dp[n - 1]); 
}

int main()
{
    int n; // 定义变量 n
    cin >> n; // 从标准输入读取楼梯的数量
    vector<int> cost(n); // 创建一个大小为 n 的向量，用于存储每个楼梯的成本
    for(int i = 0; i < n; i++)
    {
        cin >> cost[i]; // 从标准输入读取每个楼梯的成本
    }
    cout << compute(cost) << endl; // 输出最小花费
    return 0; // 返回 0，表示程序正常结束
}

经典的动态规划问题，每次可以选择走一步或者走两步，求最小花费。
我们做过相似的题目，例如：
小明现在想要上楼梯，共有 $n+1$ 级台阶，其中第 $1$ 到 $n$ 级的每一级台阶上都有一个整数，第 $i$ 级台阶上的整数是 $cost[i - 1]$ 。
小明现在正站在第 $0$ 级台阶上，每一步他可以向上走 $1$ 级或者跨 $2$ 级，并且每一步走完之后，他都要把当前位置台阶上的数字加到答案里去，直到他走到第 $n+1$ 级台阶上为止。
问答案的最小值
现在有概念了，我们可以开始分析代码了
首先输入的 cost 数组下标是从 0 开始的，而动态规划过程中的 dp 数组下标是从 1 开始的，不要搞混。
小明一开始就站在第 0 级台阶上，所以初始状态为 $dp[0] = 0$ ，但代码中没写出来，也没关系。
如果想走到第 1 级台阶上，那么就只能从第 0 级台阶走上来，所以 $dp[1] = dp[0] + cost[1 - 1]$ ，也就是 $dp[1] = cost[0]$ 。
从第 2 级台阶开始，第 $i$ 级台阶的上一步只有第 $i-1$ 级和第 $i-2$ 级两种情况，两种情况取个最小值转移过来即可，所以这一部分的状态转移方程为 $dp[i] = \min(dp[i-1], dp[i-2]) + cost[i-1]$ 。
最后目标是走到第 $n+1$ 级台阶上，但由于第 $n+1$ 级台阶没有数字，所以不能用 cost 数组，又由于 $dp[n+1] = \min(dp[n], dp[n-1])$ ，所以直接 return 作为答案了。

# 第21题

当输入的 cost 数组为 {10, 15, 20} 时，程序的输出为 15。

A. 对
B. 错

解析：根据动态规划的思想，计算到达每一级楼梯的最小花费，最终输出最后一级楼梯的最小花费。对于输入 {10, 15, 20}，最小花费为 15，因此答案是对的。

# 第22题

如果将 dp[i - 1] 改为 dp[i - 3]，程序可能会产生编译错误。

A. 对
B. 错

解析：将 dp[i - 1] 改为 dp[i - 3]，数组越界出现的是运行时错误，不是编译错误。

# 第23题

程序总是输出 cost 数组中最小的元素。

A. 对
B. 错

解析：程序计算的是到达每一级楼梯的最小花费，最终输出最后一级楼梯的最小花费，而不是输出 cost 数组中最小的元素。

# 第24题

当输入的 cost 数组为 {1, 100, 1, 1, 1, 100, 1, 1, 100, 1} 时，程序的输出为（）。

A. 6 B. 7 C. 8 D. 9

解析：根据动态规划的思想，计算到达每一级楼梯的最小花费，最终输出最后一级楼梯的最小花费。对于输入 {1, 100, 1, 1, 1, 100, 1, 1, 100, 1}，最小花费为 6，因此答案是 A。也可以模拟执行过程，模拟即可，加到答案里的数字对应的下标可以是 (1,3,5,7,8,10)

# 第25题

如果输入的 cost 数组为 {10, 15, 30, 5, 5, 10, 20}，程序的输出为（）。

A. 25 B. 30 C. 35 D. 40

解析：同上，加到答案里的数字对应的下标可以是 (2,4,6)

# 第26题

若将代码中的 min(dp[i - 1], dp[i - 2]) + cost[i - 1] 修改为 dp[i - 1] + cost[i - 2]，输入 cost 数组为 {5, 10, 15} 时，程序的输出为（）。

A. 10 B. 15 C. 20 D. 25

解析：相当于完全变成了一个递推

dp[0] = 0
dp[1] = cost[0] = 5
dp[2] = dp[1] + cost[0] = 5 + 5 = 10
dp[3] = dp[2] + cost[1] = 10 + 10 = 20 最后的答案是 min(dp[2], dp[3]) = 10

#include <iostream> // 包含输入输出库
#include <cmath>    // 包含数学库，用于使用 pow 函数
using namespace std; // 使用标准命名空间

// 自定义递归函数，计算 a + b
int customFunction(int a, int b)
{
    // 基础情况：如果 b 等于 0，返回 a
    if(b == 0)
    {
        return a; // 返回 a
    }
    // 递归调用：计算 a + (a + (a + ...))，共 b 次
    return a + customFunction(a, b - 1); 
}

int main()
{
    int x, y; // 定义变量 x 和 y
    cin >> x >> y; // 从标准输入读取 x 和 y
    int result = customFunction(x, y); // 调用自定义函数计算结果
    cout << pow(result, 2) << endl; // 输出结果的平方
    return 0; // 返回 0，表示程序正常结束
}

分析 customFunction 这个函数，发现每次只有参数 $b$ 会变成 $b-1$ ，并且过程中每次递归会把下一层答案 $+a$ 后返回给上一层。
观察到 $b == 0$ 时遇到边界结束，所以总共递归 $b$ 层，过程中共有 $b$ 个 $a$ 相加。
但在 $b == 0$ 时执行了 return $a$ ，所以最终答案里是有 $b+1$ 个 $a$ 相加。
综上，customFunction( $a, b$ ) 的功能就是计算 $a \times (b+1)$ 。
最后输出的是 $pow(result, 2)$ ，也就是说程序输入了两个整数 $x, y$ ，然后输出 $(x \times (y+1))^2$ 。

# 第27题

当输入为 2 3 时，调用 customFunction(a, b) 的返回值为 64。

A. 对
B. 错

解析：注意问的是函数返回值，而不是输出是什么，这是一个坑。
返回值是 $2 \times 4 = 8$ 。

# 第28题

当 b 为负数时，customFunction (a, b) 会陷入无限递归。

A. 对
B. 错

解析：边界条件是 $b == 0$ ，递归过程中 $b$ 每次会减少，因此在 $b$ 为负数时会无限递归下去。
但有的同学可能会认为，int 类型减到负整数最小值之后，再 $-1$ 会变成正整数最大值，最终执行 $2^{32}$ 层递归之后确实还是会出现 $b == 0$ 的情况。但这里要注意，递归函数执行调用的是栈空间，栈空间能够支持的递归层数远小于 $2^{32}$ 这一级别的数字。（即使支持，这也肯定会超出题目的空间限制）（即使题目空间限制给得很宽，目前家用电脑的内存容量也不支持）

# 第29题

当 b 的值越大，程序的运行时间越长。

A. 对
B. 错

解析：如果 $b$ 是正整数，递归的时间复杂度是 $O(b)$ ，运行时间确实会随着 $b$ 的变大而变长。但是对于负数的情况，可能会出现运行时错误，因此在考虑时间复杂度时可以不考虑负数的情况。

# 第30题

当输入为 5 4 时，customFunction(5, 4) 的返回值为（）。

A. 5
B. 25
C. 250
D. 625

解析：问的是返回值
$5 \times (4 + 1) = 25$

# 第31题

如果输入 x = 3 和 y = 3，则程序的最终输出为（）。

A. 27 B. 81 C. 144 D. 256

解析： $result = 3 \times (3 + 1) = 12$
$12^2 = 144$

# 第32题

若将 customFunction 函数改为 return a + customFunction(a-1, b-1) 并输入 3 3，则程序的最终输出为

A. 9
B. 16
C. 25
D. 36

解析：让我们来模拟一遍：

customFunction(3, 3)

= 3 + customFunction(2, 2)

= 3 + 2 + customFunction(1, 1)

= 3 + 2 + 1 + customFunction(0, 0)

= 3 + 2 + 1 + 0

= 6

$6^2 = 36$

所以 customFunction(3, 3) 的返回值为 36。

（判断平方数） 问题：给定一个正整数 n，希望判断这个数是否为完全平方数，即存在一个正整数 x 使得 x 的平方为 n。
试补全程序。

#include<iostream>
#include<vector>
using namespace std;

bool isSquare(int num) {
    int i = __①__;
    int bound = __②__;
    for (; i <= bound; ++i) {
        if (__③__) {
            return __④__;
        }
    }
    return __⑤__;
}

int main() {
    int n;
    cin >> n;
    if (isSquare(n)) {
        cout << n << " is a square number" << endl;
    } else {
        cout << n << " is not a square number" << endl;
    }
    return 0;
}

（实际上从原理上讲，这题函数里也可以直接 return bound * bound == num;，没必要用到循环，但题目就这样考了，那就 for 一遍找答案吧）
根据题目意思，如果我们找到一个正整数 $x$ ，满足 $x^2 = n$ ，那么 $n$ 就是一个完全平方数。
所以这里采用循环来找这个正整数 $x$ 。
发现 $x^2 = n$ 可以看作 $x = \sqrt{n}$ ，所以要找的数字一定不会超过 $\sqrt{n}$ 。
所以只需要把 $1 \sim \sqrt{n}$ 内的每一个整数看一遍，观察是否存在某个整数的平方等于 $n$ 即可。

# 第33题

①处应填（）。

A. 1 B. 2 C. 3 D. 4

解析：题干中提到，我们要找的 x 是一个正整数，所以循环 i 要从 1 开始。

# 第34题

②处应填（）。

A.(int)floor(sqrt(num))-1

B.(int)floor(sqrt(num))

C.floor(sqrt(num/2))-1

D.floor(sqrt(num/2))

解析：

这里的 sqrt 表示取平方根， $\text{floor}$ 表示向下取整。

根据第 8 行循环条件可以判断出 $bound$ 变量表示的就是最大边界，所以 $bound$ 应该等于 $\sqrt{num}$ 。

因为 $bound$ 是整数，所以可以把 $\lfloor \sqrt{num} \rfloor$ 交给它。

四个选项中，只有 B 选项等于 $\lfloor \sqrt{num} \rfloor$ 。

# 第35题

③处应填（）

A.num = 2 * i B.num == 2 * i C.num = i * i D.num == i * i

解析：现在假设循环变量 $i$ 就是我们要找的 $x$ 。
所以要判断的是 $i^2 = num$ 是否成立。

# 第36题

④处应填（）

A.num = 2 * i B.num == 2 * i C.true D.false

解析：选完第三个空之后，发现只要第三个空的条件成立，就说明 num 是一个完全平方数,根据题意，这里直接 return true 即可

# 第37题

⑤处应填（）

A.num = i * i B.num != i * i C.true D.false

解析：填完第四个空后，根据题意，如果循环结束后都没有执行任何一次 return true，就说明 $1 \sim \sqrt{num}$ 中找不到任何一个数字的平方等于 $num$ ，此时直接 return false 即可。

（汉诺塔问题）

给定三根柱子，分别标记为 A、B 和 C。初始状态下，柱子 A 上有若干个圆盘，这些圆盘从上到下按从小到大的顺序排列。任务是将这些圆盘全部移到柱子 C 上，且必须保持原有顺序不变。在移动过程中，需要遵守以下规则：

只能从一根柱子的顶部取出圆盘，并将其放入另一根柱子的顶部。
每次只能移动一个圆盘。
小圆盘必须始终在大圆盘之上。试补全程序。

#include <iostream>
#include <vector>
using namespace std;

void move(char src, char tgt){
    cout <<"从柱子”<< src <<“挪到柱子"<< tgt << endl;
}
void dfs(int i, char src, char tmp, char tgt){
    if(i == __①__){
        move(__②__);
        return;
    }
    dfs(i-1, __③__);
    move(src, tgt);
    dfs(__④__,__⑤__);
}
int main(){
    int n;
    cin >> n;
    dfs(n,'A','B','C');
    return 0;
}

一道非常经典的汉诺塔题目
以及
一份非常经典的汉诺塔代码

为了能把 src 上的 i 个盘子移动到 tgt 上，我们可以借助递归分三步走：

先把起始柱 src 上面的 i − 1 个盘子先借助 tgt 移动到中间柱 tmp 上
- 移动完成后，目标柱 tgt 为空
再把最大的这个盘子从 src 移动到 tgt 上
- 移动完成后，起始柱 src 为空
再把第一步中的 i − 1 个盘子借助 src 移动到目标柱 tgt 上

move(src, tgt) 函数就表示执行一次移动，从 src 移动到 tgt

dfs(i, src, tmp, tgt) 表示递归，将 i 个盘子从 src 移动到 tgt 上，中间柱是 tmp

# 第38题

①处应填（）

A. 0 B. 1 C. 2 D. 3

解析：明显仅当只剩一个盘子的时候，可以执行一次第 10 行的 move，然后结束递归（如果条件里面没有 move 直接 return 了，应当对应无盘子的情况，要选 i == 0）

# 第39题

②处应填（）

A. src, tmp B. src, tgt C. tmp, tgt D. tgt, tmp

解析：只剩一个盘子时，直接从 src 移动到 tgt 即可，不用管 tmp

# 第40题

③处应填（）

A.src, tmp, tgt B.src, tgt, tmp C.tgt, tmp, src D.tgt, src, tmp

解析：三步走中的第一步，先把 i−1 个盘子从 src 开始，借助 tgt 移动到 tmp 上

# 第41题

④处应填（）

A.src, tmp, tgt B.tmp, src, tgt C.src, tgt, tmp D.tgt, src, tmp

解析：三步走中的第三步，要把第一步移动到 tmp 上的 i−1 个盘子，再从 tmp 开始，借助 src 移动到 tgt 上

# 第42题

⑤处应填（）

A.0 B.1 C.i - 1 D.i

解析：第一步移动到 tmp 上的 i−1 个盘子，再从 tmp 开始，借助 src 移动到 tgt 上，所以递归的时候应该是 i−1

真题练习4 真题机试线上练习

讲义