CSP-S 2026提高组初赛真题详解与知识点剖析——阅读程序1

（说明：输入保证为一个长度恰为32的 '0'/'1' 字符串）

做题前分析

（1）第9~11行循环，将输入的01串转化为数字存储在a数组中，第12~14行循环，为a数组的32~43位补0；

（2）第15~20行，对于01串中每一个位置i，如果该位置的数字不为0，则从位置i开始，后续13位与gen做按位异或运算；

这里就可以解释为什么12~14行需要补0了，如果a[31]=1，那么就要将31~43下标的元素依次与gen[j]异或

（3）第21~23行，最终输出a数组中补位的32~43位的值。

我们发现，如果只是阅读代码，根本看不出来程序想做什么，只能看出可能与按位异或的计算相关。

1、这里就考察考生对按位异或运算特殊性的了解，对于二进制来说，按位异或有3种情况：

0^0=0

0^1=1^0=1

1^1=0

一般来说，我们会将异或看作是不进位的加法（参考1^1=0），但同时，按位异或也能看成是不借位的减法（参考0^1=1）因为在二进制中，不进位的加法与不借位的减法，表达式是一样的；

程序第17、18行代码，让a[i]~a[i+12]与gen[0]~gen[12]按位异或，可以看作是在做减法。这里有读者可能会疑问：为什么那么肯定是减法呢？

因为这涉及到第16行的特殊判断：如果a[i]=0，则跳过；

假设这里是加法运算，那遇到1的时候，才需要判断是否会出现1^1=0进位的情况；

但是这里要求高位必须是1才能进行，那就大概率是减法计算，即a[i~i+12]-gen[0~12]；

并且假设a[i]=1，循环中第一次异或为a[i]^gen[0]=1^1=0，两个数字进行一个运算后，高位变为0，并且没有判断是否进位，那就更可能是减法了。

2、根据上一步，我们分析出第17~20行在循环进行减法，并且不是每次都进行减法，每次减法完毕后，遍历到剩余数据的下一个1才进行下一次减法；

这里可以举例演示一下：假设输入为110000 000（后面3个位补0），与1101（假设的gen值）模拟相减过程：

（1）第一趟减法后，数字去掉最高位（对应循环i++），变为000100 000；

（2）第二趟看最高位是0，因此直接去掉最高位，不进行减法；

（3）第三趟看最高位仍然是0，因此直接去掉最高位，仍然不进行减法；

（4）第四趟看100 000高位是1，可以与1101相减，结果为010 100；

（5）第五趟看10 100最高位是1，可以与1101相减，结果为01 110；

（6）第六趟看1 110最高位是1，可以与1101相减，最终结果是0 011；

那这么相减有什么意义呢？我们来把数据都转换为十进制来看：

输入的数字a=384（算上补位），gen=13，最终计算结果=3，从十进制的角度来看，384÷13的商和余数都不是3，但是减法的过程，有没有觉得非常眼熟？

对，和小学数学学习的列竖式除法很相似，例如：

至此可以确定两数在进行除法运算，那么具体是做什么呢？

其实分析到这一步，我们再去看第20题，题干中其实给了我们答案：

答案就是选项B，将输入的二进制数s与gen做模2除法求余数，输出计算结果的12位余数。

3、再次深究一下，这个运算有什么用呢？其实这段代码复现了计算机科学中一种校验数据的方式——循环冗余校验，用于检测数据传输或保存过程中可能出现的错误。

数据的发送方，先将待发送的数据，除以gen，获得余数后接在发送的数据后面；

数据的接收方，收到数据后，用数据除以gen，如果算出来的余数为0，说明数据在传输过程中没有出现问题，如果不是，说明数据有损坏。

该算法由于容易进行数学分析并且善于检测传输信号干扰导致的数据错误，因此被广泛使用于压缩包文件验证、U盘,硬盘等数据检查、以及网络通信等领域。

16. （1分）当输入为32个'0'时，程序输出12个0。

答案：√

解析：如果输入的全部是0，那么会一直触发第16行的判断，不进行任何一次的按位异或运算，a数组中保持都是0的状态，最终输出a[32~43]补位的12个0。

17. 程序运行结束后，数组a中下标从0到31的元素一定全部为0。

答案：√

解析：在循环中，每遇到一个a[i]=1，就与gen[0]=1进行异或后变为0，而内层循环是从左往右依次计算的，因此当a[i]变为0后不会再变回1，也不会出现计算过程中回头把数据变为1的情况。

因此，当15~20行循环结束后，a[0~31]的值一定都为0。

18. 若将第12~14行（为a[32]到a[43]补0的循环）删除，会改变程序输出结果。

答案：×

解析：由于a数组被定义在全局变量中，因此如果不对元素进行初始化，默认数组元素的值就为0，即a[32~43]默认值就是0，因此不改变程序输出结果。

19. 关于第6行定义的数组gen，下列说法正确的是（    ）

A、gen共有12个元素，表示一个12位的除数

B、gen共有13个元素，表示一个13位的被除数

C、gen共有13个元素，其中gen[0]是除数的最高位

D、gen共有13个元素，其中ge[12]是除数的最高位

答案：C

解析：在完成这一题之前，我们已经能分析出第20题选B，从做题技巧来说，这里的a数组一定是除数；

而在a数组中，a[0]是高位，a[31]是低位，因此在计算中，相对应的gen[0]是除数的高位，gen[12]是除数的低位，对应正确描述为选项C。

20. 该程序实现的功能，最准确的说法是（    ）

A、将输入的32位串看成二进制数M，输出M与13位二进制数1100000001111按位异或的结果

B、将输入串视为32位二进制数M，在其后补12个0（即计算），再对它做模2除法求余数，并输出12位余数

C、对输入的32位串逐位取反并输出结果

D、统计输入串中1的个数，并把该个数用12位二进制表示后输出

答案：B

解析：参考前文的分析。

21. 若将第16行“if ( a[i] == 0 ) continue;”删除，说法正确的是（   ）

A、程序输出的结果不会改变

B、可能造成程序运行错误

C、程序能够正常输出一个12位 '0'/'1' 串，但是输出结果与输入的s无关

D、程序运行结束后，a[0]的值一定为0

答案：C

解析：

选项A：删除前，只对a[i]=1的时候进行异或，删除后不管是0还是1都会进行异或，一定会改变输出的结果；

选项B：删除后，只是改变了计算过程与输出结果，不会影响到程序的运行情况，这里的continue删除了更不会出现死循环，因此不会造成运行错误；

选项D：删除后，当a[0]=0时，由于会无条件进行异或计算，因此会有a[0]^gen[0]=0^1=1，从而使a[0]的值变为1；

因此，通过排除法，我们可以确定正确的描述为选项C。

这里，我们可以来推理一下，删除这行代码后，程序的输出会是什么呢？

对于a[32]来说，循环中影响它结果的计算有i=20时与gen[12]异或、i=21时与gen[11]异或、...、i=31时与gen[1]异或；

因此a[32]=gen[12]^gen[11]^gen[10]^...^gen[2]^gen[1]=1；

同理，影响a[33]的值有i=21时与gen[12]异或，i=22时与gen[11]异或，...，i=31时与gen[2]异或，因此a[33]=gen[12]^gen[11]^...^gen[2]=0；

接下来可以发现规律了：

a[34]=gen[12]^gen[11]^...^gen[3]=0

a[35]=gen[12]^gen[11]^...^gen[4]=0

……

最终，计算出的结果为a[32~43]=100000000101，是一个定值。