时间紧任务重，可能有误，烦请指正 QwQ
第1题 (2分)
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题 (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题 (2分)
某公司有 10 名员工，分为 3 个部门：A 部门有 4 名员工，B 部门有 3 名员工、C 部门有 3 名员工。现需要从这 10 名员工中选出 4 名组成一个工作小组，且每个部门至少要有 1 人。问有多少种选择方式？
A. 120
B. 126
C. 132
D. 238
分类讨论，三个部门选四个人，且每个部门至少要有一人
① A部门选两人，其他部门选一人，\(C_4^2\times C_3^1 \times C_3^1 = 54\)
② B部门选两人，其他部门选一人，\(C_4^1\times C_3^2 \times C_3^1 = 36\)
① C部门选两人，其他部门选一人，\(C_4^1\times C_3^1 \times C_3^2 = 36\)
\(54+36+36=126\)
第4题 (2分)
以下哪个序列对应数字 0 至 7 的 4 位二进制格雷码（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题 (2分)
记 1KB 为 1024 字节（byte）、1MB 为 1024KB，那么 1MB 是多少二进制位（bit）？
A. 1000000
B. 1048576
C. 8000000
D. 8388608
\(1\text{ MB} = 1024\text{ KB} = 1024\times 1024 \text{ B} = 1024 \times 1024 \times 8 \text{ bit} = 8388608\text{ bit}\)
第6题 (2分)
以下哪个不是 C++中的基本数据类型？
A. int
B. float
C. struct
D. char
struct 结构体不算基本类型
第7题 (2分)
以下哪个不是 C++ 中的循环语句？
A. for
B. while
C. do-while
D. repeat-until
可以用排除法做
do-while 是先做一次循环内的代码，再根据条件循环执行的语句，也是 C++ 的语句
第8题 (2分)
在 C/C++ 中，(char)('a'+13) 与下面的哪一个值相等？
A. 'm'
B. 'n'
C. 'z'
D. '3'
ASCII 码表中，小写英文字母是按照字母表顺序连续出现的
'a' + 13 就是从 'a' 开始往后数 13 个字母，即 'n'
第9题 (2分)
假设有序表中有 1000 个元素，则用二分法查找元素 X 最多需要比较（ ）次。
A. 25
B. 10
C. 7
D. 1
二分法查找 时间复杂度是以 2 为底数的对数，即 \(\log_2 n\)
当 \(n = 1000\) 时，\(\log_2 1000 \approx 10\)
或者可以模拟二分的过程，每次二分后要么直接找到对应数字，要么剩余数量变成原来的一半，观察做多少次可以剩 \(1\) 个数字即可
第10题 (2分)
下面哪一个不是操作系统名字？
A. Notepad
B. Linux
C. Windows
D. macOS
Notepad 是记事本
第11题 (2分)
在无向图中，所有顶点的度数之和等于（ ）。
A. 图的边数
B. 图的边数的两倍
C. 图的顶点数
D. 图的顶点数的两倍
无向图中，每条边连接两个点
根据度数的定义，无向图中点的度数就是有多少条边连接着当前点
那么每条边对于总度数的贡献就是 \(2\)
即无向图的总度数一定等于边数 \(\times 2\)
第12题 (2分)
已知二叉树的前序遍历为 [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]
画图可得，这是一棵 7 个结点的满二叉树
第13题 (2分)
给定一个空栈，支持入栈和出栈操作。若入栈操作的元素依次是 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
第14题 (2分)
有 5 个男生和 3 个女生站成一排，规定 3 个女生必须相邻，问有多少种不同的排列方式？
A. 4320 种
B. 5040 种
C. 3600 种
D. 2880 种
三个女生必须相邻，不妨假设三个女生为一个整体，与其余五个男生之间的站位方案数为 \(A_6^6 = 6! = 720\) 种
三个女生内部也存在 \(A_3^3 = 3! = 6\) 种站位
因此总方案数为 \(720 \times 6 = 4320\) 种
第15题 (2分)
编译器的主要作用是什么？
A. 直接执行源代码
B. 将源代码转换为机器代码
C. 进行代码调试
D. 管理程序运行时的内存
A 源代码没法直接执行
C 调试功能是编辑器提供的
D 管理计算机运行过程中的资源是操作系统干的活
第 16 题 (10.5 分)
观察程序可知
isPrime(n)函数在判断整数 n 是否是一个素数
countPrimes(n)函数在求 \(2 \sim n\) 之间的素数数量
sumPrimes(n)函数在求 \(2 \sim n\) 之间的素数总和程序输入一个整数 \(x\)，输出两个整数：\(2\sim x\) 的素数数量以及 \(2 \sim x\) 的素数和
第16 - 1题(1.5 分)
当输入为 "10" 时，程序的第一个输出为 "4"，第二个输出为 "17"。
A. 对
B. 错
\(10\) 以内的素数有 \(2, 3, 5, 7\)
数量为 \(4\)，总和为 \(17\)
第16 - 2题(1.5 分)
若将 isPrime(i) 函数中的条件改为 i <= n / 2，输入"20" 时，countPrimes(20) 的输出将变为 "6"。
A. 对
B. 错
首先观察代码第 6 到 9 行，发现小于 \(2\) 的情况都已经被排除了，接下来循环过程一定满足 \(n \ge 2\)
原本的代码是
i * i <= n，就是说 \(i\) 不会超过 \(\lfloor \sqrt n \rfloor\)而改后的代码
i <= n / 2表示 \(i\) 不超过 \(\lfloor \dfrac n 2\rfloor\)发现在 \(n \ge 2\) 时，\(\lfloor \sqrt n \rfloor \le \lfloor \dfrac n 2\rfloor\) 一定成立
所以改后无非就是时间复杂度从 \(O(\sqrt n)\) 变成了 \(O(n)\)，对答案无影响
输入 \(20\) 时，\(20\) 以内的素数有 \(2,3,5,7,11,13,17,19\)，共 \(8\) 个
第16 - 3题(1.5 分)
sumPrimes 函数计算的是从 2 到 n 之间的所有素数之和。
A. 对
B. 错
易得
第16 - 4题(3 分)
当输入为 "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\)
总和为 \(328\)
第16 - 5题(3 分)
如果将 for (int i = 2; i * i <= n; i++) 改为 for (int i = 2; i <= n; i++)，输入 "10" 时，程序的输出（ ）。
A.将不能正确计算 10 以内素数个数及其和
B.仍然输出 "4" 和 "17"
C.输出 "3" 和 "10"
D.输出结果不变，但运行时间更短
改后
if(n % i == 0)这一句判断一定会在i == n时成立因此
return false一定会执行此时无法判断素数
第 17 题 (15 分)
虽然是一道线性动态规划，但很明显简单递推一下也能做题
如果想要充分理解代码的意思，可以给这道题定一个题目背景：
小明现在想要上楼梯，共有 \(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 作为答案了
第17 - 1题(1.5 分)
当输入的 cost 数组为 {10, 15, 20} 时，程序的输出为 15。
A.对
B.错
模拟即可
第17 - 2题(1.5 分)
如果将 dp[i - 1] 改为 dp[i - 3]，程序可能会产生编译错误。
A.对
B.错
数组越界出现的是运行时错误，不是编译错误
第17 - 3题(2 分)
程序总是输出 cost 数组中最小的元素。
A.对
B.错
明显不是取最小值输出
第17 - 4题(3 分)
当输入的 cost 数组为 {1, 100, 1, 1, 1, 100, 1, 1, 100, 1} 时，程序的输出为（ ）。
A.6
B.7
C.8
D.9
模拟即可，加到答案里的数字对应的下标可以是 \((1, 3, 5, 7, 8, 10)\)
第17 - 5题(4 分)
如果输入的 cost 数组为 {10, 15, 30, 5, 5, 10, 20}，程序的输出为（ ）。
A.25
B.30
C.35
D.40
模拟即可，加到答案里的数字对应的下标可以是 \((2, 4, 6)\)
第17 - 6题(3 分)
若将代码中的 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] = 0dp[1] = cost[0] = 5dp[2] = dp[1] + cost[0] = 5 + 5 = 10dp[3] = dp[2] + cost[1] = 10 + 10 = 20最后的答案是
min(dp[2], dp[3]) = 10
第18 题 (14.5 分)
分析
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\)
第18 - 1题(1.5 分)
当输入为 "2 3" 时，customFunction(2, 3) 的返回值为 "64"。
A.对
B.错
注意问的是函数返回值，而不是输出是什么！
返回值是 \(2 \times 4 = 8\)
第18 - 2题(1.5 分)
当 b 为负数时，customFunction (a, b) 会陷入无限递归。
A.对
B.错
边界条件是
b == 0，递归过程中b每次会减少，因此在b为负数时会无限递归下去但有的同学可能会认为，int 类型减到负整数最小值之后，再 \(-1\) 会变成正整数最大值，最终执行 \(2^{32}\) 层递归之后确实还是会出现
b == 0的情况。但这里要注意，递归函数执行调用的是栈空间，栈空间能够支持的递归层数远小于 \(2^{32}\) 这一级别的数字。（即使支持，这也肯定会超出题目的空间限制）（即使题目空间限制给得很宽，目前家用电脑的内存容量也不支持）
第18 - 3题(1.5 分)
当 b 的值越大，程序的运行时间越长。
A.对
B.错
如果
b是正整数，递归的时间复杂度是 \(O(b)\)，运行时间确实会随着b的变大而变长但上一题又问了负数的情况，所以有些小歧义，但负数时到后面会出现运行时错误，不算正常执行完程序，应该也可以不考虑
第18 - 4题(3 分)
当输入为 "5 4" 时，customFunction(5, 4) 的返回值为（ ）。
A.5
B.25
C.250
D.625
问的是返回值
即 \(5 \times (4 + 1) = 25\)
第18 - 5题(3 分)
如果输入 x = 3 和 y = 3，则程序的最终输出为（ ）。
A."27"
B. "81"
C."144"
D."256"
\(\text{result} = 3 \times (3 + 1) = 12\)
\(12 ^ 2 = 144\)
第18 - 6题(4 分)
若将 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\)
第19 题 (15 分)
（判断平方数）
问题：给定一个正整数 n，希望判断这个数是否为完全平方数，即存在一个正整数 x 使得 x 的平方为 n。
试补全程序。
（实际上从原理上讲，这题函数里也可以直接
return bound * bound == num;，没必要用到循环，但题目就这样考了，那就 for 一遍找答案吧）根据题目意思，如果我们找到一个正整数 \(x\)，满足 \(x^2 = n\)，那么 \(n\) 就是一个完全平方数
所以这里采用循环来找这个正整数 \(x\)
发现 \(x^2 = n\) 可以看作 \(x = \sqrt n\)，所以要找的数字一定不会超过 \(\sqrt n\)
所以只需要把 \(1 \sim \sqrt n\) 内的每一个整数看一遍，观察是否存在某个整数的平方等于 \(n\) 即可
第19 - 1题(3 分)
①处应填（ ）
A.1
B.2
C.3
D.4
题干中提到，我们要找的 \(x\) 是一个正整数，所以循环 \(i\) 要从 \(1\) 开始
第19 - 2题(3 分)
②处应填（ ）
A.(int)floor(sqrt(num))-1
B.(int)floor(sqrt(num))
C.floor(sqrt(num/2))-1
D.floor(sqrt(num/2))
这里的
sqrt表示取平方根，floor表示向下取整根据第 8 行循环条件可以判断出
bound变量表示的就是最大边界，所以bound应该等于 \(\sqrt{\text{num}}\)因为
bound是整数，所以可以把 \(\lfloor \sqrt{\text{num}} \rfloor\) 交给它四个选项中，只有 B 选项等于 \(\lfloor \sqrt{\text{num}} \rfloor\)
第19 - 3题(3 分)
③处应填（ ）
A.num = 2 * i
B.num == 2 * i
C.num = i * i
D.num == i * i
现在是假设循环变量 \(i\) 就是我们要找的 \(x\)
所以要判断的是 \(i^2 = \text{num}\) 是否成立
第19 - 4题(3 分)
④处应填（ ）
A.num = 2 * i
B.num == 2 * i
C.true
D.false
选完第三个空之后，发现只要第三个空的条件成立，就说明
num是一个完全平方数根据题意，这里直接
return true即可
第19 - 5题(3 分)
⑤处应填（ ）
A.num = i * i
B.num != i * i
C.true
D.false
填完第四个空后，根据题意，如果循环结束后都没有执行任何一次
return true，就说明 \(1 \sim \sqrt{\text{num}}\) 中找不到任何一个数字的平方等于 \(\text{num}\)，此时直接return false即可
第20 题 (15 分)
（汉诺塔问题）
给定三根柱子，分别标记为 A、B 和 C。初始状态下，柱子 A 上有若干个圆盘，这些圆盘从上到下按从小到大的顺序排列。任务是将这些圆盘全部移到柱子 C 上，且必须保持原有顺序不变。在移动过程中，需要遵守以下规则：
- 只能从一根柱子的顶部取出圆盘，并将其放入另一根柱子的顶部。
- 每次只能移动一个圆盘。
- 小圆盘必须始终在大圆盘之上。
试补全程序。
一道非常经典的汉诺塔题目
以及
一份非常经典的汉诺塔代码
为了能把
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
第20 - 1题(3 分)
①处应填（ ）
A.0
B.1
C.2
D.3
明显仅当只剩一个盘子的时候，可以执行一次第 10 行的
move，然后结束递归（如果条件里面没有
move直接return了，应当对应无盘子的情况，要选i == 0）
第20 - 2题(3 分)
②处应填（ ）
A.src, tmp
B.src, tgt
C.tmp, tgt
D.tgt, tmp
只剩一个盘子时，直接从
src移动到tgt即可，不用管tmp
第20 - 3题(3 分)
③处应填（ ）
A.src, tmp, tgt
B.src, tgt, tmp
C.tgt, tmp, src
D.tgt, src, tmp
三步走中的第一步，先把 \(i-1\) 个盘子从
src开始，借助tgt移动到tmp上
第20 - 4题(3 分)
④处应填（ ）
A.src, tmp, tgt
B.tmp, src, tgt
C.src, tgt, tmp
D.tgt, src, tmp
三步走中的第三步，要把第一步移动到
tmp上的 \(i-1\) 个盘子，再从tmp开始，借助src移动到tgt上
第20 - 5题(3 分)
⑤处应填（ ）
A.0
B.1
C.i - 1
D.i
同上
