CSP-J 模拟（九）题目解答
一、单项选择题（每题2分，共30分）
1. 进制转换计算
答案：C
解析：
- 先将八进制数\((2025)_8\)转换为十进制：
\(2\times8^3 + 0\times8^2 + 2\times8^1 + 5\times8^0 = 2\times512 + 0 + 16 + 5 = 1024 + 21 = 1045\)。 - 将十六进制数\((2025)_{16}\)转换为十进制：
\(2\times16^3 + 0\times16^2 + 2\times16^1 + 5\times16^0 = 2\times4096 + 0 + 32 + 5 = 8192 + 37 = 8229\)。 - 求和：\(1045 + 8229 = 9274\)。
- 验证选项：
- 选项C\((1001000111010)_2\)转换为十进制：\(2^{13} + 2^{10} + 2^6 + 2^5 + 2^4 + 2^2 = 8192 + 1024 + 64 + 32 + 16 + 4 = 9274\)，与结果一致。
2. 函数声明合法性
答案：C
解析：
二维数组作为函数参数时，第二维大小必须显式指定（第一维可省略）。
- A：未指定第二维大小，非法；
- B：第一维指定大小、第二维省略，非法；
- C：第二维指定大小（20），合法；
- D：语法错误（C++中二维数组参数格式为
a[][n]，而非[,]）。
3. 语法合规性判断
答案：B、D（题目中B和D均不符合语法）
解析：
- A：
&n是取地址，地址本质是整数，可与8相加，语法合法； - B：
n++9缺少运算符（如+），语法错误； - C：
15+n是合法的加法表达式； - D：
n--7缺少运算符，语法错误。
4. 循环队列元素个数
答案：D
解析：
循环队列中，头尾指针r（尾）、f（头），元素个数公式为\((r - f + n) % n\)：
- 若
r > f，则\((r - f + n) % n = r - f\)（正确）； - 若
r < f（队列绕圈），则\((r - f + n) % n = r - f + n\)（正确）； - A、B未考虑绕圈情况，C多加1（队列空时
r=f，结果为1，错误）。
5. 后缀表达式转中缀
答案：C
解析：
后缀表达式（逆波兰式）按“操作数1 操作数2 运算符”计算，步骤如下：
- 后缀表达式
1 2 + 3 * 14 7 / -：1 2 +→ \(1+2=3\)；3 3 *→ \(3\times3=9\)；14 7 /→ \(14\div7=2\)；9 2 -→ \(9-2\)。
- 对应的中缀表达式结构为
- * + 1 2 3 / 14 7，即选项C。
6. 二叉树遍历（题目缺失数据，无法作答）
说明：题目中“前序遍历结果”和“中序遍历结果”未给出，无法确定后序遍历结果。
7. 二叉树性质判断
答案：A
解析：
- A：完全二叉树是“除最后一层外全满，最后一层从左到右连续”，满二叉树是“所有层全满”，完全二叉树不一定是满二叉树（如最后一层少一个右节点），错误；
- B：满二叉树满足完全二叉树定义，正确；
- C：二叉树性质“叶节点数\(N_0 = N_2 + 1\)”（\(N_2\)是度为2的节点数），正确；
- D：二叉树第\(i\)层最多有\(2^{i-1}\)个节点（第1层1个，第2层2个，以此类推），正确。
8. 递归函数计算（题目缺失选项，逻辑如下）
解析：
函数f(n,m)递归公式：
- 边界：
n==1返回1，m==1返回n； - 递归：
f(n-1,m) + f(n,m-1)（类似组合数\(C(n+m-2, n-1)\)）。
计算f(5,6)：
\(f(5,6)=f(4,6)+f(5,5)=[f(3,6)+f(4,5)]+[f(4,5)+f(5,4)]=...=46\)（需结合选项选择结果）。
9. 最大公约数与最小公倍数（题目缺失数据，无法作答）
说明：题目中“最大公约数”和“最小公倍数”的具体数值未给出，无法计算正整数组个数。
10. 数据结构概念判断
答案：B
解析：
- A：数据结构是“带有结构的数据元素集合”，正确；
- B：线性存储（数组）和链式存储（链表）各有优劣：数组随机访问快但插入删除慢，链表反之，无“优劣”之分，错误；
- C、D：队列是“先进先出（FIFO）、一端插入（队尾）、一端删除（队头）”的线性表，正确。
11. 无向图顶点度数（题目缺失数据，无法作答）
说明：题目中选项A~D的“度数列表”未给出，无法判断合理性（无向图度数和必为偶数）。
12. 纸牌计数问题
答案：B
解析：
编号1~13的纸牌顺时针计数，从1开始数到n：
- 若
n%13==0，对应编号13（如n=13，13%13=0，实际编号13）； - 公式
(n-1)%13 + 1可覆盖所有情况：- n=13：
(12)%13 +1=13； - n=14：
(13)%13 +1=1，正确。
- n=13：
13. 无向图顶点个数（题目缺失数据，无法作答）
说明：题目中“边数”“度为k的顶点个数”等数据未给出，无法计算最少顶点数。
14. 删除数字求最小数（题目缺失选项，逻辑如下）
解析：
给定\(N=8934632178\)，每次删除后保留最小数，步骤：
- 第1次：删除8（序列变为934632178→34632178，实际更优为834632178？需逐位比较）；
- 第2~3次：继续删除较大数字；
- 第4次删除的数字需结合前三次结果判断（需选项匹配）。
15. 指针概念判断
答案：A（假设题目中“位计算机”为“64位”，64位系统指针占8字节）
解析：
- A：64位计算机中，指针变量占8字节（存储内存地址），正确；
- B：指针可进行加减运算（如
p++移动到下一个元素），错误； - C：数组名是“常量指针”，不可修改（如
a++错误），并非“指针变量”，错误； - D：指针可动态申请内存（如
new/malloc），错误。
二、阅读程序（判断题+选择题）
第1题：冒泡排序变形
判断题
-
答案：F
解析：found标记是否发生交换，若某轮无交换（数组已有序），则break退出循环，不会死循环。 -
答案：F
解析：数组[1,2,3,4,5]初始有序，第一轮found=false，循环仅运行0次（直接break）。 -
答案：F
解析：数组[5,4,3,2,1]是逆序，需4轮排序（每轮将最大数“沉底”），循环运行4次。 -
答案：F
解析：程序是冒泡排序，最终数组为升序（每次交换相邻逆序对）。
选择题
- 答案：C
解析：数组[3,1,4,1,5]排序过程：
- 第1轮：3与1交换→[1,3,4,1,5]，4与1交换→[1,3,1,4,5]；
- 第2轮：3与1交换→[1,1,3,4,5]；
- 最终结果为
[1,1,3,4,5]。
-
答案：B
解析：冒泡排序中，每次交换消除1个逆序对，总交换次数等于初始逆序对数量。 -
答案：D
解析：最坏情况（逆序数组）需\(O(n2)\)次比较和交换，时间复杂度为\(\Theta(n2)\)。
第2题：数字统计函数（代码存在语法错误，假设c += (n-1) p为c += (n-1)*p）
判断题
-
答案：F
解析：n每次除以10（逐渐减小到0），t = t + d*p（d是n的个位，p是位权），c和t最终会停止增长（n=0时循环结束）。 -
答案：T
解析：将10改为8（八进制），p增长变慢（p=8^kvs10^k），c的计算结果不会变大（如n=10，十进制计算c更大）。
选择题
- 答案：（需计算，假设n=99）
解析：
- 第1轮：n=99，d=9，n=9，p=1，t=9，c=9*1 + 9+1=19；
- 第2轮：n=9，d=9，n=0，p=10，t=9+910=99，c=19 + 010 + 99+1=119；
- 输出119（需匹配选项）。
-
答案：A
解析：p初始为1（个位），每次乘10（十位→百位→...），记录当前处理位的位权。 -
答案：B
解析：循环次数等于n的位数（如n=99为2位），时间复杂度为\(\Theta(log n)\)（log以10为底）。
第3题：数组操作（solve1 vs solve2）
判断题
- 答案：T
解析：
- solve1：正序处理，
+直接加d[i]，*对所有元素乘d[i]； - solve2：逆序处理，
*记录乘积f，+加d[i]*f（等效于后续的*操作），最终结果相同。
-
答案：T
解析：初始a[i]=0，*操作对0乘任何数仍为0，数组a恒为0。 -
答案：T
解析：op[i]全为+时，solve2中f=1，a[p[i]] += d[i]*1，a数组不为0。 -
答案：F
解析：solve1的时间复杂度为\(O(qn)\)（*操作遍历n个元素），solve2为\(O(q)\)；但当q很小或无*操作时，solve1可能比solve2快。
选择题
-
答案：A（假设操作序列正确）
解析：solve1和solve2最终结果一致，需按操作步骤计算（如+1 5→*2→a[1]=10，后续继续叠加）。 -
答案：（假设op全为
*，d[i]=2）
解析：solve2逆序处理，f初始为1，每次乘2，共q次，最终f=2^q（需匹配选项，可能题目选项为2^q）。 -
答案：D
解析：solve1中*操作遍历n个元素，最坏情况（q次*）时间复杂度为\(O(nq)\)。 -
答案：B
解析：solve2无遍历数组操作，仅遍历q次操作，时间复杂度为\(O(q)\)。
三、完善程序
第1题：合金炼制（动态规划）
-
答案：A
解析：i（黄金）和j（白银）均满足要求（≥a和≥b），无需继续选材料，返回0。 -
答案：C
解析：k==n表示已遍历所有材料（无材料可选），若未满足要求，返回无穷大（不可行）。 -
答案：D
解析：选第k块材料后，黄金为i+x[k]（不超过a，用min限制），白银同理，即min(i+x[k],a)和min(j+y[k],b)。 -
答案：C
解析：
giveup：不选第k块材料，递归dfs(k+1,i,j)；pickup：选第k块材料，递归dfs(k+1,ni,nj)并加杂质w[k]。
- 答案：B
解析：初始状态为k=0（未选材料）、i=0（黄金0）、j=0（白银0），调用dfs(0,0,0)。
第2题：子区间中位数的中位数（二分+归并排序）
-
答案：D
解析：归并排序中，s[i] <= s[j]时，s[j..end-1]均大于s[i]，贡献end - j个逆序对。 -
答案：B
解析：
length <=1：子数组长度为0或1，无需排序，返回0；- 总逆序对=前半段+后半段+跨段，即
front + back + cross。
- 答案：D
解析：
b[i]=1表示a[i] > key（用于转换子区间和的正负）；merge_sort(0, n+1)：s数组长度为n+1（s[0]~s[n]），需排序整个s数组。
-
答案：D
解析：二分查找中，若num >= (total+1)/2（total是子区间总数），说明key是候选中位数，调整左边界。 -
答案：A
解析：
length = end - begin：当前二分区间长度；mid = (end + begin)/2：中间值；- 循环结束后，
begin即为最终答案（子区间中位数的中位数）。
