当前位置：首页 > news >正文

sh-2025模拟赛

news 2025/9/14 8:19:21

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，正确。

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(n^{2)\)次比较和交换，时间复杂度为\(\Theta(n}2)\)。

第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^k vs 10^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)\)。