这份卷子是 《信息学奥赛CSP通关之路——CSP-J/S第一轮原创全真模拟试卷集2026》 这本书中的一套模拟题卷3接下来我将非常非常非常详细的为你们讲解这张初赛卷的每一道题。单选题1. 答案 B考点Linux 基本命令常识ls -l长格式列表可显示文件权限、硬链接数、所有者、大小、修改时间等完整属性。-a仅用于显示隐藏文件.和..不包含详细属性-s仅显示分配块数。2. 答案 C考点IP 地址分类常识A类1.0.0.0 ~ 126.255.255.255B类128.0.0.0 ~ 191.255.255.255C类192.0.0.0 ~ 223.255.255.255192.168.1.1首段为 192明确属于 C 类地址。3. 答案 B考点C 逻辑运算与短路求值计算过程原式 !(53) (44) || (2!2)53为true取反得false44为truefalse true得false2!2为falsefalse || false最终得false4. 答案 D考点单向链表特性A 错链表结点离散存储只能顺序遍历不支持随机访问数组才支持。B 错插入/删除本身修改指针为 O(1)但若未知插入位置的前驱则需 O(n) 查找不能笼统称“都是 O(1)”。C 错链表不要求连续存储空间。D 对单向链表每个结点由数据域和指向后继结点的指针域组成。5. 答案 B考点二叉树最小高度判断逻辑A 错(\lfloor \log_2 n \rfloor) 常用于计算完全二叉树高度但未加 1 调整n2 时结果 1 虽对但 n3 时结果仍为 1实际最小高度为 2故不通用。B 对满/完全二叉树形态下高度为 (\lceil \log_2(n1)\rceil - 1)设根高度为 0。C 错(n-1) 是单支树链表的最大高度。D 错高度为 1 最多只能容纳 2 个结点。6. 答案 C考点十进制小数转二进制计算过程整数部分100 ÷ 2 50 余 050 ÷ 2 25 余 025 ÷ 2 12 余 112 ÷ 2 6 余 06 ÷ 2 3 余 03 ÷ 2 1 余 11 ÷ 2 0 余 1 → 逆序得1100100小数部分0.25 × 2 0.5取整 00.5 × 2 1.0取整 1→ 得.01合并为1100100.01。7. 答案 C考点排序算法的稳定性A 快排/ B 堆排 / D 选择排序均为不稳定排序交换或移动元素时可能改变相等元素的原始相对次序。C 归并排序合并时通过控制顺序保证相等元素相对位置不变是稳定的最适合“同分保序”场景。8. 答案 C考点存储设备易失性常识内存、缓存、寄存器均属半导体 RAM断电即失固态硬盘SSD基于闪存属非易失性存储。9. 答案 C考点DFS 栈空间需求路径最长结点数计算过程从左上角(1,1)到右下角(n,m)每次仅向右或向下。路径由(n-1)次向下和(m-1)次向右组成路径上结点总数为(n−1)(m−1)1nm−1 (n-1) (m-1) 1 n m - 1(n−1)(m−1)1nm−1栈需记录整条路径的结点故至少为(nm−1)(nm-1)(nm−1)。10. 答案 C考点循环时间复杂度分析计算过程变量i从 1 开始每次乘 3循环执行至i n。设执行次数为ttt则3t≥n3^t \ge n3t≥n解得t≈log⁡3nt \approx \log_3 nt≈log3​n故复杂度为O(log⁡n)O(\log n)O(logn)。11. 答案 A考点完全图边数公式计算过程8 个顶点的完全图每对顶点间有一条边边数C828×7228 C_8^2 \frac{8 \times 7}{2} 28C82​28×7​2812. 答案 B考点组合计数分类加法计算过程枚举并求和C51C31C51C32C51C33C52C31C52C32C53C3115155303030125 \begin{aligned} C_5^1C_3^1 C_5^1C_3^2 C_5^1C_3^3 \\ C_5^2C_3^1 C_5^2C_3^2 \\ C_5^3C_3^1 \\ 15 15 5 30 30 30 125 \end{aligned}​C51​C31​C51​C32​C51​C33​C52​C31​C52​C32​C53​C31​15155303030125​13. 答案 B考点二叉搜索树BST遍历性质A 前序根-左-右不保证升序。B 中序左-根-右BST 中序遍历恰好输出升序序列。C 后序左-右-根无升序特性。D 层次按层输出同样不保证升序。14. 答案 C考点时间复杂度规模估算计算过程T(n)∝n3T(n) \propto n^3T(n)∝n3当nnn从 100 增至 200变为 2 倍时T(200)T(100)≈(200100)38 \frac{T(200)}{T(100)} \approx \left(\frac{200}{100}\right)^3 8T(100)T(200)​≈(100200​)3815. 答案 B考点多媒体文件大小计算单位换算计算过程总帧数 10×60×301800010 \times 60 \times 30 1800010×60×3018000帧每帧像素 1920×10802,073,6001920 \times 1080 2,073,6001920×10802,073,60024 位色 3 字节/像素 → 每帧字节 2,073,600×36,220,800B2,073,600 \times 3 6,220,800 B2,073,600×36,220,800B未压缩总大小 18000×6,220,800111,974,400,000B18000 \times 6,220,800 111,974,400,000 B18000×6,220,800111,974,400,000B除以压缩比 50 →2,239,488,000B2,239,488,000 B2,239,488,000B转换为 GB按102431024^310243)2,239,488,000÷10243≈2.086 GB 2,239,488,000 \div 1024^3 \approx 2.086 \text{ GB}2,239,488,000÷10243≈2.086GB约2.1 GB。阅读程序题第一题程序如下判断题16.答案√解析函数solve采用更相减损术递归当y0返回x否则交换确保大数减小数递归调用solve(y, x-y)。该算法正确计算最大公约数。17.答案×解析若去掉第5行if(xy) swap(x,y);当输入xy时递归调用solve(y, x-y)中的x-y为负数后续无法满足y0终止条件会导致死循环或栈溢出程序不能正常结束并非“正常输出但结果不对”。18.答案×解析输入160, 115求最大公约数160-11545115-457070-452545-252025-20520-51515-51010-555-50得gcd5。输出应为160/532115/523即32/23。题干写23/32分子分母颠倒错误。选择题19.答案D79/13解析输入1817, 299用辗转相除法1817299×6231817 299 \times 6 231817299×62329923×130299 23 \times 13 029923×130得gcd23。输出分数1817/2379,299/23131817/2379,\quad 299/23131817/2379,299/2313故为79/13。A 错在未约分B 错为错误计算C 错在分母误写为最大公约数D 正确。20.答案B(O(\log n))解析更相减损术最坏情况为 (O(n))但题目限定输入为110000 随机数平均迭代次数与对数成正比故平均时间复杂度为 (O(\log n))。A 过小C/D 过高。第二题程序如下判断题21.答案√解析输入[5,3,8,2]5大于它的只有 8cnt1→ 累加 53大于它的有 5,8cnt2→ 不累加8大于它的无cnt0→ 不累加2大于它的有 5,3,8cnt3→ 不累加。输出为 5正确。22.答案√解析程序会累加所有满足“恰好一个元素大于它”的元素。例如[5,5,8]中两个 5 都满足都只有 8 大于它们均被累加故存在多个元素满足条件时会被全部累加。23.答案×解析输出为 0 不一定所有元素相等。反例[1,2,4,4]1大于它的有 2,4,4cnt32大于它的有 4,4cnt24大于它的有 0cnt0。没有任何元素 cnt1输出为 0但元素不全相等。选择题24.答案C8解析数组[9,8,7,6,5,4,3,2,1,0,-1,-2]为严格降序。9cnt08大于它的只有 9cnt1→ 累加 8其余元素大于它们的至少 2 个不累加。输出为 8。25.答案C解析程序统计所有满足“恰好有一个元素比它大”的元素之和。若第二大值有重复则累加所有重复值。A 错在“第二大元素的值”通常指单个值B、D 与平均值、最值无关。第三题程序如下判断题26.答案×解析程序按位置枚举组合相同数值但不同位置视为不同方案。例nums[1,1,2]k2选择两个 1位置0,1和为偶数计 1 次若去掉一个 1方案数改变因此重复数字数量会影响结果。27.答案×解析去掉nums.resize(n)和used.resize(n,false)后nums和used大小均为 0后续输入和访问used[pos]会下标越界程序崩溃不能正常运行。28.答案×解析110 中奇数 5 个偶数 5 个。选 2 个数和为偶数需同奇或同偶C52C521010202C52C_5^2 C_5^2 10 10 20 2C_5^2C52​C52​1010202C52​题干写 (2C_6^230)与实际不符故错误。选择题29.答案B1解析k0时dfs(0,0,0)立即判断countk成立sum0为偶数ans后返回输出 1。空集和为偶数算一种方案。A 错在误以为无方案C 错在认为依赖数组值实则不依赖D 错。30.答案C(O(2^n))解析DFS 对每个位置做选/不选分支虽用countk剪枝但最坏情况如k≈n/2仍需遍历指数级组合时间复杂度上界为 (O(2^n))。A/B/D 均不符合递归枚举特征。程序填空1归并排序程序原题程序作用这是标准的归并排序实现。程序先将数组一分为二mSort函数递归排序左右两半然后通过merge函数将两个有序子数组合并成一个完整有序数组。变量L和R分别暂存左半部分和右半部分的元素。31.答案Dm 1 j解析这一步是在将原数组a的右半部分元素复制到临时数组R中。右半部分的起始下标是m 1随着j从 0 递增应依次取a[m1]、a[m2]……因此表达式为m 1 j。A 只取了a[0]B 多加了 1 但未加mC 从m开始包含了左半部分的最后一个元素均错误。32.答案Ci n1 j n2解析这一步是合并两个有序数组L和R的循环条件。只要左半部分L还有剩余i n1且右半部分R还有剩余j n2就需要不断比较并取较小者放入a。一旦某一部分取完循环结束然后由后面的while语句处理剩余元素。A/B 中n是原数组总长度不是子数组长度D 使用会导致数组越界访问。33.答案Cleft, mid, right解析这一步是在mSort函数中对左右两半排序完成后调用merge函数将二者合并。merge函数的形参顺序是(int l, int m, int r)因此实参必须按照左边界、中间位置、右边界的顺序传入即merge(left, mid, right)。A/B/D 的顺序均不符合函数定义。34.答案A0, n - 1解析这一步是在main函数中调用mSort对整个数组进行排序。因为数组a的下标范围是0到n-1所以左边界传0右边界传n-1。B 的右边界n越界C 和 D 从1开始会漏掉下标为 0 的元素。35.答案Ba[n - 1]解析这一步是输出排序后的数组。前面的for循环已经输出了从a[0]到a[n-2]并且每个后面跟了空格U是空格或分隔符的 OCR 识别。最后一个元素不应再跟多余空格应单独输出a[n-1]。A 会在最后一个元素前多输出一个空格破坏了输出格式的规范性C 和 D 访问了a[n]属于越界访问2最长波动子序列程序原题程序作用这是使用动态规划求解最长波动子序列的长度。dp[i][0]表示以nums[i]结尾且最后一段是上升即从上一个元素到nums[i]是上升趋势的最长子序列长度dp[i][1]表示以nums[i]结尾且最后一段是下降的最长子序列长度。程序遍历每个元素并在其前面所有元素中寻找能形成波动的转移。36.答案Dfill(dp[0], dp[0] n * 2, 1);解析这一步是对 DP 数组进行初始化。对于序列中的每一个单独元素它自身就可以构成长度为 1 的波动子序列无论处于上升还是下降状态因此需要将所有dp[i][0]和dp[i][1]都初始化为 1。dp是一个二维数组但在内存中连续排列dp[0]指向首元素dp[0] n * 2正好指向数组末尾。A 的memset(dp,1,sizeof(dp));按字节填充1 会变成0x01010101十进制 16843009不是预期的数值 1B 赋的是极大值C 中dp ^ n*2语法错误异或且fill的第一个参数也写错了。37.答案Cj i解析这一步是内层循环的遍历范围。题目要求找前面的元素来构成子序列i是当前考察元素的下标j用于遍历i之前的所有元素所以循环条件是j i。A/B 包含了自身及后面的元素会导致重复计算或状态未定义D 使用会将自身也算进去转移逻辑错误。38.答案Anums[i] nums[j]解析这一步是判断当前元素nums[i]与前面的nums[j]是否构成上升趋势。只有当nums[i] nums[j]时才能考虑从状态dp[j][1]前面以nums[j]结尾且最后一段是下降转移过来形成上升趋势从而更新dp[i][0]。B 的忽略严格升降的波动要求相等不算波动C/D 将大小关系颠倒了不符合上升的判断条件。39.答案Cdp[j][0] 1解析这一步是在nums[i] nums[j]构成下降趋势时计算新的临时长度。既然要形成下降前一个状态必须是以nums[j]结尾且最后一段是上升的状态即dp[j][0]。在其基础上加上当前元素nums[i]长度加 1因此应填dp[j][0] 1。A 和 B 错误地使用了当前i的状态还未计算完毕D 使用了下降状态无法形成下降趋势的连续转移。40.答案Cmax(dp[i][0], dp[i][1])解析这一步是更新最终答案max_Len它需要记录整个数组中所有位置、两种状态下能达到的最大长度。对于每个i以nums[i]结尾的波动子序列长度无论是处于上升还是下降状态都应参与比较因此取二者中的较大值max(dp[i][0], dp[i][1])。A 或 B 只取单个状态会遗漏另一种可能性D 取最小值完全错误。以上是这张卷子的完整解析祝各位复习愉快P