发帖
雷达卡
2025年计算机考研408真题及答案解析
题目一：程序段的时间复杂度分析
int count = 0; i,j;
for(i=1; i*i <= n; i++)
for(j=1; j <= i; j++)
count++;
选项：
A. log n
B. n
C. n log n
D. n?
该程序段的时间复杂度为 B. O(n)。
详细解析：
- 外层循环的控制条件是 i*i <= n，因此 i 的取值范围是从 1 到 √n，共执行约 √n 次。
- 内层循环的执行次数依赖于当前的 i 值，每次从 j = 1 执行到 j = i，因此内层循环在第 i 次外层迭代中执行 i 次。
总的执行次数为：
当 i = 1 时，内层执行 1 次；
i = 2 时，执行 2 次；
……
i = √n 时，执行 √n 次。
总和为：1 + 2 + 3 + … + √n = (√n)(√n + 1)/2 ≈ (n + √n)/2。
在大 O 表示法中，忽略低阶项与常数因子后，最终时间复杂度为 O(n)。
因此，正确答案为 B。
题目二：括号匹配与栈容量限制问题
已知算法 A 使用一个初始为空的栈来判断字符串中括号是否匹配。若栈的最大容量为 3，则下列哪个表达式是算法 A 无法处理的？
选项：
A. (a+[b+(c+d))/e]+f)+g-h
B. [a*((b+c)/(d-e)+f/g)-h]
C. [a*(b-(c-d)*e/(f+g))-h]
D. [a-(b+[c*(d+e)-f]+g+h)]
本题考察的是括号嵌套深度与栈空间限制的关系。由于栈容量仅为 3，当未匹配的左括号数量超过 3 层时，将导致栈溢出，无法继续处理。
逐项分析：
选项 A：(a+[b+(c+d)e]+f)+g-h
1. 遇到 '(' → 栈：['(']（深度1）
2. 遇到 '[' → 栈：['(', '[']（深度2）
3. 遇到 '(' → 栈：['(', '[', '(']（深度3）
4. 遇到 ')' → 匹配，弹出 '(' → 栈：['(', '[']（深度2）
5. 遇到 ']' → 弹出 '[' → 栈：['(']（深度1）
6. 遇到 ')' → 弹出 '(' → 栈：[]（深度0）
[此处为图片1]
整个过程中最大嵌套深度为 3，未超出栈容量，可处理。
选项 B：[a*((b+c)/(d-e)+f/g)]-h
1. 遇到 '[' → 栈：['[']（深度1）
2. 遇到 '(' → 栈：['[', '(']（深度2）
3. 遇到 '(' → 栈：['[', '(', '(']（深度3）
4. 遇到 ')' → 弹出 '(' → 栈：['[', '(']（深度2）
5. 遇到 ')' → 弹出 '(' → 栈：['[']（深度1）
6. 遇到 ']' → 弹出 '[' → 栈：[]（深度0）
[此处为图片2]
最大深度为 3，未超限，可处理。
选项 C：[a*(b-(c-d)*e/(f+g))-h]
1. 遇到 '[' → 栈：['[']（深度1）
2. 遇到 '(' → 栈：['[', '(']（深度2）
3. 遇到 '(' → 栈：['[', '(', '(']（深度3）
4. 遇到 ')' → 弹出 '(' → 栈：['[', '(']（深度2）
5. 遇到 ')' → 弹出 '(' → 栈：['[']（深度1）
6. 遇到 ']' → 弹出 '[' → 栈：[]（深度0）
[此处为图片3]
最大深度仍为 3，未超限，可处理。
选项 D：[a-(b+[c*(d+e)-f]+g+h)]
1. 遇到 '[' → 栈：['[']（深度1）
2. 遇到 '(' → 栈：['[', '(']（深度2）
3. 遇到 '[' → 栈：['[', '(', '[']（深度3）
4. 遇到 '(' → 尝试压入，此时需进入第 4 层 → 栈深度变为 4
[此处为图片4]
但栈容量仅为 3，无法容纳第四个元素，发生溢出。
因此，算法 A 无法处理选项 D 中的表达式。
正确答案：D
京公网安备 11010802022788号
