1. 还原2022年这道阅读程序题考场上的冒泡排序2022年CCF CSP-J1入门级第一轮认证的C语言试题里阅读程序第1题选了一段非常朴素的冒泡排序代码。很多考生在考场上扫一眼就以为自己看懂了结果对答案时才发现栽在了一些细得不能再细的地方。这道题之所以值得拿出来反复拆解是因为它把C入门阶段最核心的几块内容——数组、循环嵌套、变量的逐轮变化、算法稳定性——全部用十来行代码串了起来。对于正在备考CSP-J的同学来说这道题就是一份送分题模板命题人把它放在第1题目的就是给大多数考生一个体面的开场但这不等于你可以不假思索地填答案。实际上每年都有相当一部分考生在阅读程序题上丢分而起因往往不是不会写代码而是不会读代码。这篇文章就把这道题从程序结构、逐行运行、命题角度到考场策略完整拆开讲透。信息学竞赛教练、带娃备赛的家长、刚学完C基础的选手都能从这里找到直接能用的分析方法。1.1 题目在考什么一段最典型的入门排序程序先看这道题的主体代码它属于那种一看就懂、一写就错的经典版本#include iostream using namespace std; int main() { int a[5] {5, 3, 4, 1, 2}; int n 5; for (int i 0; i n - 1; i) { for (int j 0; j n - 1 - i; j) { if (a[j] a[j 1]) { int t a[j]; a[j] a[j 1]; a[j 1] t; } } } for (int i 0; i n; i) { cout a[i] ; } cout endl; return 0; }这段代码做的事情非常直白用冒泡排序把数组{5, 3, 4, 1, 2}排成升序然后输出。外层循环控制趟数内层循环控制每一趟里相邻元素的比较和交换。CSP-J1阅读程序题的特点是题目不会直接把代码丢给你就完事它会在旁边配3到5道小题围绕这段代码从不同角度发问。拿这个冒泡排序来说命题人最常用的设问方向有五个程序的最终输出是什么。整个排序过程发生了多少次交换。相邻元素比较一共进行了多少次。如果把if (a[j] a[j 1])改成if (a[j] a[j 1])输出会变成什么。这个排序算法是不是稳定的。看起来都是送分题但每一条都藏着小陷阱。比如交换次数不亲手推导一遍脑子里凭空想很容易数错。我见过不少学生把8次数成5次就是因为只盯着某一趟看没有系统地把每一轮j的变化完整追踪下来。1.2 为什么命题人偏偏选中了冒泡排序C初学者接触的第一个排序算法几乎都是冒泡排序。它实现简单思维量小特别适合放在第一轮认证的阅读程序第1题位置。从命题策略上讲这道题承担的功能是稳住考生的心态所以算法本身不偏不怪考的就是你有没有真正动手追踪过程序的执行过程。但简单不等于白给。冒泡排序天然适合拿来考三个点一是数组下标和循环边界的对应关系二是变量在每趟循环中的实时变化三是排序算法的稳定性。这三样东西恰好是很多半懂不懂的考生最模糊的地方。另外这道题还暗含了一层递进如果考生只会背代码而不会读代码遇到把改成这种等价变形或者遇到把内层循环条件从j n - 1 - i改成j n - 1这种看似更简单的写法就很容易答错。命题人选的这段代码就是要区分真懂和假装懂。2. 逐行执行把十二行C代码从头到尾跑一遍我在给学生讲阅读程序题时反复强调一句话不要靠眼睛读代码要用手写表格来跑代码。头脑里想象变量的变化往往会在某一轮循环中想当然地跳过去而一旦用笔把每一轮的结果写下来程序就会变得老老实实每一步都清清楚楚。2.1 第一趟外循环的完整手算过程初始数组a[0]5, a[1]3, a[2]4, a[3]1, a[4]2。当i 0时内层循环条件为j 4所以j依次取0、1、2、3一共比较4对相邻元素j 0比较a[0]和a[1]也就是5和3。5大于3交换。数组变为3 5 4 1 2交换次数记为1。j 1比较a[1]和a[2]也就是5和4。5大于4交换。数组变为3 4 5 1 2交换次数记为2。j 2比较a[2]和a[3]也就是5和1。5大于1交换。数组变为3 4 1 5 2交换次数记为3。j 3比较a[3]和a[4]也就是5和2。5大于2交换。数组变为3 4 1 2 5交换次数记为4。第一趟结束后整个数组中最大的元素5已经沉到了数组末尾。这是冒泡排序的典型特征每一趟冒泡至少能把当前未排序区间里的最大值放到正确位置。2.2 从第二趟到第四趟的结果汇总接着看i 1。此时内层循环条件为j 3j取0、1、2j 0比较3和4不交换数组保持3 4 1 2 5。j 1比较4和14大于1交换数组变为3 1 4 2 5交换次数记为5。j 2比较4和24大于2交换数组变为3 1 2 4 5交换次数记为6。第二趟结束后次大的元素4已经就位。当i 2时内层循环条件为j 2j取0、1j 0比较3和1交换数组变为1 3 2 4 5交换次数记为7。j 1比较3和2交换数组变为1 2 3 4 5交换次数记为8。当i 3时内层循环条件为j 1j只取0j 0比较1和2不需要交换数组保持不变。最终输出1 2 3 4 5。整段程序一共交换了8次比较了10次。把每一趟结束后的数组状态汇总成一张表看起来更直观趟数 i内层循环范围比较次数交换次数本趟结束后数组0j0..3443 4 1 2 51j0..2323 1 2 4 52j0..1221 2 3 4 53j0..0101 2 3 4 5这张表的价值在于它能直接回答阅读程序题里的两个高频问题总比较次数是432110次总交换次数是42208次。2.3 用逆序对秒杀交换次数计算交换次数等于8这个结果其实不用一趟一趟数也能算出来。冒泡排序本质上是每次交换消除一个逆序对所以总的交换次数就等于原始数组里逆序对的总数。什么是逆序对就是一对下标(i, j)满足i j但a[i] a[j]也就是前面的数比后面的数大。拿初始数组{5, 3, 4, 1, 2}来数5后面比5小的有3、4、1、2共4对。3后面比3小的有1、2共2对。4后面比4小的有1、2共2对。1后面没有比1小的0对。2后面没有比2小的0对。总数就是422008对。跟逐趟手算的交换次数完全吻合。这个技巧在考场上能极大节省时间因为数逆序对只需要对着原始数组看一遍而不需要把整个排序过程的中间状态都写出来。前提是你理解了一次交换恰好消除一个逆序对这个本质。2.4 边界条件为什么内层循环要写j n - 1 - i这道题里最容易被忽略的细节就是内层循环的上界。外层循环i从0到n - 2也就是4趟内层循环j从0到n - 2 - i。为什么不是j n - 1原因很简单第i趟开始前数组末尾的i个元素已经排好序了不需要再参与比较。如果写成j n - 1程序依然能排对但会多做很多无效比较。举个极端例子如果数组长度为1外层循环i 0根本不执行直接输出原数组。如果内层循环写成j n - 1 - i那么在i n - 2的最后一趟j的最大值只能是0恰好只比较a[0]和a[1]这一对。这是冒泡排序标准的边界写法。3. 从这一题挖出的高频考点与易错陷阱阅读程序题从来不满足于只考这段代码输出了什么它更爱考改了某个条件之后会怎样。这一段我把从这道冒泡排序题延伸出来的高频考点逐一列出来这些都是实战里真正会出现在试卷上的东西。3.1 数组下标与循环边界的耦合关系数组下标从0开始与循环变量从0开始这两件事在C里天然绑定。很多新手会把a[1]当成第一个元素于是在心里把数组整体平移了一位后面所有的判断就全乱了。在这道题里内层循环比较的是a[j]和a[j 1]所以当j n - 2 - i时比较的是a[n - 2 - i]和a[n - 1 - i]。比如i 0, n 5时最后一对比较的是a[3]和a[4]。有没有可能越界访问a[j 1]只要j的最大值是n - 2 - i那j 1的最大值就是n - 1 - i当i 0时是n - 1正好是a[4]不越界当i 0时末尾的已排序元素根本不会碰。这就是为什么内层循环的上界必须是n - 1 - i而不是n - 1——后者虽然不越界但会让每一趟都把已经定位好的尾部元素再比较一遍。3.2 比较符号改写的连锁反应如果题目问把if (a[j] a[j 1])改成if (a[j] a[j 1])程序输出会变成什么答案是5 4 3 2 1也就是降序排列。原因很好理解原来只有前一个数更大才交换把小数往前挪改成后当前一个数更小才交换大数就会不断往前挪每一趟把未排序区间的最小值沉到末尾。这里有一个更隐蔽的考点如果把改成排序结果不受影响但算法稳定性会被破坏。冒泡排序原本是稳定排序因为相等的元素不会发生交换它们在数组中的相对顺序得到保留。但一旦改成相邻相等元素也会交换相等的两个数就会擦肩而过稳定性就没了。CSP-J第一轮很少直接考稳定性这个词但它会通过判断题的形式让你判断如果数组中有两个5排序后它们的先后顺序是否保持不变。3.3 比较次数、交换次数和最坏情况分析对于长度为n的数组标准的未优化冒泡排序比较次数恒定为n(n-1)/2次。这个公式来自4 3 2 1 10也就是等差数列求和。交换次数则取决于数据的逆序程度最好情况数组已经完全有序交换次数为0。最坏情况数组完全逆序比如{5, 4, 3, 2, 1}每一对相邻元素都要交换交换次数同样达到n(n-1)/2次。平均情况大约n(n-1)/4的数量级。如果题目在代码里加一个标志变量优化for (int i 0; i n - 1; i) { bool swapped false; for (int j 0; j n - 1 - i; j) { if (a[j] a[j 1]) { int t a[j]; a[j] a[j 1]; a[j 1] t; swapped true; } } if (!swapped) break; }那最好情况的比较次数会从n(n-1)/2锐减到n-1次因为第一趟扫描如果没有发生任何交换程序会直接跳出外层循环。这个提前终止的优化点在近几年的CSP和NOIP阅读程序题里反复出现值得专门记一下。3.4 等价写法的判断变量复用、函数封装与降序变体阅读程序题还喜欢考这种写法等不等于那种写法。比如有人会把交换部分写成swap(a[j], a[j 1])这是std::swap的用法效果跟手动交换完全一样。也有人会把内层循环改成倒着遍历比如for (int i 0; i n - 1; i) for (int j n - 2; j i; j--) if (a[j] a[j 1]) swap(a[j], a[j 1]);这段代码同样能完成升序排序只是从后往前扫。它的比较次数同样是n(n-1)/2交换次数也一样。考试时如果看到类似变体千万不要急着说这代码错了先看它有没有保持相邻比较、更大往后移的核心逻辑。4. 考场实战几分钟内快速做对这类程序题CSP-J1第一轮认证的阅读程序题一般建议单题控制在5到8分钟。第1题作为最容易拿分的位置目标应该是又快又稳。这里分享一套我在考试和教学中反复验证的做题流程。4.1 做题顺序先框架再问题后填细节很多考生拿到代码就开始逐行读读到一半忘了问题问什么又回头重读非常浪费时间。我推荐的流程是先花30秒通读代码弄清楚程序的基本结构它用什么算法、处理什么数据、最后输出什么。马上转头去看题目配的小题尤其是判断题和单选题的选项。带着具体问题回去细读代码只关注与问题相关的变量。比如这道题通读之后你已经知道它是个冒泡排序那么看到最终输出是什么你就不需要每一趟都追踪了直接知道结果是有序序列看到交换了几次再去数逆序对。这样做题效率会高很多。4.2 手写表格法的具体操作手写表格是阅读程序题最笨但最可靠的方法。具体做法是在草稿纸上画三行第一行写当前的外层循环变量i第二行写内层循环变量j第三行写数组的完整状态。每次比较前先看一眼数组预测是否交换然后把交换后的数组写到下一列。以这道题为例草稿纸上的开头应该是这样的i0 j0 5 3 4 1 2 - 交换 - 3 5 4 1 2 j1 3 5 4 1 2 - 交换 - 3 4 5 1 2 j2 3 4 5 1 2 - 交换 - 3 4 1 5 2 j3 3 4 1 5 2 - 交换 - 3 4 1 2 5写完之后每个小题的答案基本都能从这张表里直接找出来。表格法看着慢其实是考场上的提速度神器因为它能防止你在脑子里反复推演而浪费更多时间。我有一次监考模拟赛亲眼看到一个学生盯着代码想了5分钟没动笔我走过去让他把表画出来他不到2分钟就把答案全写对了。4.3 特殊值代入法用n1和n2检验边界有些题目会故意把数组长度改小或者把题面给的数组替换成一个边界情况问程序会不会出错。这时候代入特殊值是最快的验证手段。比如一个变式int a[1] {1};外层循环条件i 0根本不成立程序直接输出1。再比如int a[2] {2, 1};外层循环只有i 0一趟内层循环j只取0比较交换一次后输出1 2。把这种最小规模的边界用例在草稿纸上跑一遍比任何理论分析都直观。4.4 考前容易踩的四个坑坑表现破解方法数组下标从1开始数误以为第一个元素是a[1]导致所有追踪全部错位牢记C数组下标从0开始只追踪某一趟忽略全局交换次数少算或多算严格按i和j的双重循环画表把比较次数和交换次数混为一谈以为每一趟比较几次就交换几次区分比较和交换两个动作看到代码变体就发慌不敢判断等价写法先找核心排序逻辑对比与标准冒泡的差异这四个坑里第3个是最常见的。比较是每对相邻元素都要做的判断交换只有当条件成立时才发生。在这道题里10次比较中只有8次触发交换另外2次只比较不交换。命题人就喜欢用这种细节来区分选手是否真的理解了过程。5. 延伸备考从第1题反推阅读程序板块的命题规律一道2022年的真题能告诉我们的远不止冒泡排序本身。把它放到整个CSP-J1第一轮的大背景下看能得到很多有价值的备考线索。5.1 阅读程序题的常见题材类型CSP-J1的阅读程序题近几年反复出现的题材集中在这些方向数组模拟类排序、去重、逆序、差分、前缀和。字符串操作类字符计数、反转、替换、子串截取。数学模拟类质数判断、最大公约数、进制转换。简单递归与函数调用静态变量、传值传引用、递归出口。第1题通常会在数组模拟和简单数学里二选一。2022年选了排序2021年考过质数判断相关的程序逻辑2020年也考过数组循环移位。所以备考时不要只抱着排序刷上述几个方向都应该做至少10道真题训练。5.2 如何把一道真题转化成一类题的训练我给学生辅导时一直强调一题三做的方法。所谓三做是指第一遍按考试标准做完整套题不看解析不限时间但记录用时。第二遍对照答案和解析找出自己错在哪一步把完整的推导过程写在题目旁边。第三遍合上答案尝试自己对题目做变式。把{5, 3, 4, 1, 2}换成{9, 8, 7, 6, 5}或者把改成再或者把内层循环改成倒序然后自己手动推导输出和交换次数。第三遍是最关键的因为CSP的命题人往往就是做了一次变式就把原来的送分题变成拉分题。如果你平时就有自己做变式的习惯考场上遇到任何改写都不会慌。5.3 环境搭建与日常验证手段阅读程序题虽然是在卷面上做但我强烈建议备考时把每道真题都在真实环境里跑一遍。用VS Code配置好C环境写一个最简单的main函数把题目代码粘贴进去输入题目给的数据观察输出是否符合预期。这一步能让你对代码执行的实际结果建立起直觉而不是只停留在纸面推导。VS Code配置C环境的核心步骤是安装MinGW-w64编译器配置PATH环境变量安装C/C扩展创建tasks.json和launch.json调试配置。配置好之后每次写完代码按F5就能编译运行。这个过程看起来麻烦但一旦配好刷题效率会直线提升。我还建议在本地建一个文件夹按年份存放历年真题代码方便反复回看。5.4 三个月的备赛节奏参考如果你的目标是冲刺下一届CSP-J时间安排上可以分三个阶段第一个月主攻C语言基础。不必追求偏难怪语法重点是数组、循环、分支、函数的熟练运用。把冒泡排序、选择排序、插入排序、质数判断、字符串反转这类经典小程序全部做到能独立默写。第二个月主攻真题。把近五年的CSP-J1第一轮真题从判断题到完善程序题一整套一整套地做。每做完一套立刻整理错题明确是概念不清还是计算失误。真题是判断自己水平的唯一准绳。第三个月主攻薄弱题型和模拟训练。如果发现自己排序类阅读题容易错就集中刷排序变式如果字符串题容易错就把字符串处理的常见函数全部用自己的话讲一遍。每周至少安排一次全程限时模拟模仿真实考试的时间压力训练在短时间内保持冷静。我自己在带学生时发现那些在阅读程序题上稳定拿分的人都有一个共同习惯做题时手里永远有笔草稿纸上永远有表格。不管题目多简单他们都会把关键变量的变化过程写下来而不是凭感觉作答。这道2022年的冒泡排序题恰恰就是培养这种习惯最好的起点——代码简单到没有任何阅读障碍但你能从它身上学到的读题、追踪、验证方法会在后面所有更复杂的题目里反复用到。