2021CSP-J初赛真题解析（适合复习、巩固、备考）

【第一部分 选择题】

1.以下不属于面向对象程序设计语言的是（ ）。
A. C++
B. Python
C. Java
D. C
【解析】D。
C语言是一种面向过程的结构化程序设计语言。
2.以下奖项与计算机领域最相关的是（ ）。
A. 奥斯卡奖
B. 图灵奖
C. 诺贝尔奖
D. 普利策奖
【解析】B。
3.目前主流的计算机储存数据最终都是转换成（ ）数据进行储存。
A. 二进制
B. 十进制
C. 八进制
D. 十六进制
【解析】A。
B选项：十进制 是人类习惯使用的计数方式。
C和D选项：八进制 和 十六进制 主要是为了方便人类阅读和书写二进制代码而引入的缩写形式（例如在编程中常用来表示颜色或内存地址），但它们在计算机硬件底层依然是以二进制的形式存在的。
4.以比较作为基本运算，在 N 个数中找出最大数，最坏情况下所需要的最少的比较次数为 （ ）。
A.N2N^{2}N2
B. N
C. N−1
D. N+1
【解析】C。
让第1个数作为默认最大数，与后面的N-1个数进行N-1次比较。
5.对于入栈顺序为 a,b,c,d,e 的序列，下列（ ）不是合法的出栈序列。
A. a,b,c,d,e
B. e,d,c,b,a
C. b,a,c,d,e
D. c,d,a,e,b
【解析】D。
d出栈后，不可能是a出栈。

6.对于有 n 个顶点、m 条边的无向连通图 (m>n)，需要删掉（ ）条边才能使其成为一棵树。
A. n−1
B. m−n
C. m−n−1
D. m−n+1
【解析】D。
树核心特点：
（1）没有环（无回路）：树中的结点之间不能形成闭环。
（2）连通：树中任意两个结点之间都有且仅有一条路径相连。
（3）边与结点的关系： n 个结点的树，有且仅有 n−1 条边。
（4）层次结构：树具有明显的层级关系，包含根结点、双亲结点等。
所以要成为一个棵树，需要保留n-1条边，删掉m-(n-1)=m-n+1。
7. 二进制数 101.11 对应的十进制数是（ ）。
A. 6.5
B. 5.5
C. 5.75
D. 5.25
【解析】C。
整数部分和小数部分按位权展开求和。
101.11₂= 1*222^{2}22+0*212^{1}21+1*202^{0}20+1*2−12^{-1}2−1+1*2−22^{-2}2−2=4+0+1+0.5+0.25=5.75。
8.如果一棵二叉树只有根结点，那么这棵二叉树高度为 1。请问高度为 5 的完全二叉树有 （ ）种不同的形态？
A. 16
B. 15
C. 17
D. 32
【解析】A。
第1层有1个结点，第2层有2个结点，第3层有4个结点，第4层有8个结点，第5层最多有16个结点，最少保证有1个结点，第5层从左右依次不间断的情况下增加结点，构成不同的完全二叉树。

9.表达式 a*(b+c)*d 的后缀表达式为( )，其中 * 和 + 是运算符。
A. **a+bcd
B. abc+*d*
C. abc+d**
D. *a*+bcd
【解析】B。
按照运算优先级依次加上括号:((a*(b+c))*d),然后按照运算优先级依次将对应括号中的运算符挪到对应括号后面((a(bc)+)*d)*，去掉括号，得到后缀表达式abc+*d*。
10.6 个人，两个人组一队，总共组成三队，不区分队伍的编号。不同的组队情况有（ ）种。
A. 10
B. 15
C. 30
D. 20
【解析】B。
区分队伍的编号（即队伍的先后顺序），第1支队伍C(6,2)，第2支队伍C(4,2),第3支队伍就是剩余2人，所以共有C(6,2)* C(4,2)*1 = 90。
如果6个人依次是1～6，考虑队伍编号的情况，以下6种情况属于一种组队方式。
[12 34 56]、[12 56 34]、[34 12 56]、[34 56 12]、[56 12 34]、[56 34 12]
所以考虑队伍编号的情况下总共的组队方式是90/A(3,3) = 90/6 = 15。
11. 在数据压缩编码中的哈夫曼编码方法，在本质上是一种（ ）的策略。
A. 枚举
B. 贪心
C. 递归
D. 动态规划
【解析】B。
哈夫曼树构造规则：每次选两个频率最小的结点合并，新结点频率为两结点之和，根据构造出的哈夫曼树进行哈夫曼编码，是一种贪心的策略。
12.由 1,1,2,2,3 这五个数字组成不同的三位数有（ ）种。
A. 18
B. 15
C. 12
D. 24
【解析】A。
假设三位数为abc，分情况讨论：
三个数位都不相同，从{1,2,3}中构成，有A(3,3) = 6种。
有两个数位相同：
（1）有两个数位是相同的1{ab,ac,bc}，剩下一位可以是{2,3}，共有3*2 = 6种。
（2）有两个数位是相同的2{ab,ac,bc}，剩下一位可以是{1,3}，共有3*2 = 6种。
共有18种。
13.考虑如下递归算法

则调用 solve(7) 得到的返回结果为（ ）。
A. 105
B. 840
C. 210
D. 420
【解析】C。
1*2*3*5*7 = 210。

14.以 a 为起点，对下边的无向图进行深度优先遍历，则 b,c,d,e 四个点中有可能作为最后一个遍历到的点的个数为（ ）。

A. 1
B. 2
C. 3
D. 4
【解析】B。
起点固定为a的情况下，深搜过程可能是：abdce、acedb、acdbe，最后一个遍历的点可能是e或b两种情况。
15.有四个人要从 A 点坐一条船过河到 B 点，船一开始在 A 点。该船一次最多可坐两个人。 已知这四个人中每个人独自坐船的过河时间分别为 1,2,4,8，且两个人坐船的过河时间为两人独自过河时间的较大者。则最短（ ）时间可以让四个人都过河到 B 点（包括从 B 点把船开回 A 点的时间）。
A. 14
B. 15
C. 16
D. 17
【解析】B。
（1）先让1和2一起过河到B，然后1自己开回A点，共耗时2+1=3。
（2）再让4和8一起过河到B，然后2自己开回A点，共耗时8+2=10。
（3）最后让1和2一起过河到B，耗时2。
最少耗时15。
核心点是第（2）步，让大的和大的一起，否则可能会出现8+4的情况。

【第二部分 阅读程序题】

阅读程序（程序输入不超过数组或字符串定义的范围）

（1）输入的 n 等于 1001 时，程序不会发生下标越界。
A.对
B.错
【解析】B。
数组a长度为1000，最大下标999，n为1001，第22行会用到下标1000，会发生下标越界。
（2）输入的 a[i] 必须全为正整数，否则程序将陷入死循环。
A.对
B.错
【解析】B。
可以参考（3）的解析，f函数和g函数是对x的二进制进行的操作，x是负数情况下不受影响。
（3）当输入为 5 2 11 9 16 10 时，输出为 3 4 3 17 5。
A.对
B.错
【解析】B。
n为5，依次2、11、9、16、10这五个数的二进制形式进行操作，输出的为3 4 3 17 4。

（4）当输入为 1 511998 时，输出为 18。
A.对
B.错
【解析】A。
将511998转换为二进制111 1100 1111 1111 1110，共16个1，f函数返回16，g函数取最低位有效1，返回2，程序输出18。
（5）将源代码中 g 函数的定义（14∼17 行）移到 main 函数的后面，程序可以正常编译运行。
A.对
B.错
【解析】B。
g函数没有在main函数之前声明，会报编译错误。
（6）当输入为 2 -65536 2147483647 时，输出为（ ）。
A. 65532 33
B. 65552 32
C. 65535 34
D. 65554 33
【解析】B。
2147483647 0111 1111 1111 1111 1111 1111 1111 1111，共31个1，f返回31，g函数返回1。选B。
-65536涉及负数的补码，可以理解为f函数和g函数的二进制表示都是补码形式，正数的原码和补码相同，所以不用可以刻意转换。
在32位系统中，-65536的原码是
0000 0000 0000 0001 0000 0000 0000 0000
取反
1111 1111 1111 1110 1111 1111 1111 1111
加1
1111 1111 1111 1111 0000 0000 0000 000，所以f函数返回16，g函数返回2^16 = 65536，输出65552。

【阅读程序-2】

base64编码是通过算法，将任意的字节数组数据，对照编码表，生成只有大小写英文字母、数字字符、+、-的字符串形式。
原理：base64编码是把3个字节（原数据）变成4个字符（编码后的数据）。
编码过程：
原数据3字节24位，编码成4字节，具体过程如图所示：

解码过程：
对照编码过程取出原3字节对应的二进制位，还原回来。
分析程序：
init函数：初始化编码表base和映射表table，假设编码后的字符‘F’，通过table[‘F’]就能快速得到‘F’在base数组中的下标5，所以table数组是用来提高查表速度的。
table的有效下标是‘A’～‘Z’、‘a’～‘z’、‘0’～‘9’、‘+’、‘-’、‘=’。

decode函数：每次取4字节还原为3字节，可以参考下图从下往上理解。

（1）输出的第二行一定是由小写字母、大写字母、数字和 +、 /、= 构成的字符串。
A.对
B.错
【答案】B。
decode函数是解码还原的过程，原先的字符串可能是任意值，例如第（6）题结果中就有空格。
base64编码过程会将原先的字符串聚焦到小写字母、大写字母、数字和 +、 /、=构成的字符串。
（2）可能存在输入不同，但输出的第二行相同的情形。
A.对
B.错
【解析】A。
（3）输出的第一行为 -1。
A.对
B.错
【解析】A。
base编码数组元素没有0，注意字符‘0’不是数值0，table[0]就是0xff，char是有符号类型，值对应-1。
（4）设输入字符串长度为 n，decode 函数的时间复杂度为（ ）。
A. O(√n)
B. O(n)
C. O(nlogn)
D. O(n2n^{2}n2)
【解析】A。
decode函数中只有一层for循环，时间负责度为O(n)。
（5）当输入为 Y3Nx 时，输出的第二行为（）。
A. csp
B. csq
C. CSP
D. Csp
【解析】B。
‘Y’- 24 – 00 011000
‘3’- 55 - 00 110111
‘N’- 13 – 00 001101
‘x’- 49 – 00 110001
还原后：
第1个字节：011000 11 – 99 – ‘c’
第2个字节：0111 0011 – 115 – ‘s’
第3个字节：01110001 – 113 – ‘p’
（6）当输入为 Y2NmIDIwMjE= 时，输出的第二行为（ ）。
A. ccf2021
B. ccf2022
C. ccf 2021
D. ccf 2022
【解析】C。
每4个字符为一组，解码后对应3个字符。但是最后一组有一个‘=’，所以最后一组解码后对应2个字符，所以会输出8个字符，排除A和B选项，C和D选项只在最有一个分组不同，解码最后一个分组。
第1组：Y2Nm
第2组：IDIw
第3组：MjE=
最后一个分组参考第（5）题的过程，需要超耐心的位运算与进制转换计算储备。
【阅读程序-3】

假设输入的 x 是不超过 1000 的自然数，完成下面的判断题和单选题：
题目是在经典欧拉筛的基础上增加了一些操作。

从第15和第16行可以猜出，a数组标记是否是质数，b数组是存储质数。筛选几次理解不同数组含义
f[i]表示i的约数个数，g[i]表示i的所有约数之和。
（1）若输入不为 1，把第 13 行删去不会影响输出的结果。
A.对
B.错
【解析】A。
除了第13行对f[1]和g[1]进行初始化，后面没有用到f[1]和g[1]，删掉不影响输出结果。
（2）第 25 行的 f[i] / c[i * k]可能存在无法整除而向下取整的情况。
A.对
B.错
【解析】B。
第24行，i*k是合数，k是i*k的最小质因数，每次c[i]+1，表示i*k的最小质因数的个数。例如：9 = 32，c[9] = 2。
结合约数个数定理，假设i的质因数分解为(p1)a1(p1)^{a1}(p1)a1*(p2)a2(p2)^{a2}(p2)a2*…
f[i] = (p1 + 1)*（p2+1）*…
所以f[i]是包含c[i]+1的，f[i] / c[i * k]不可能存在无法整除而向下取整的情况。

（3）在执行完 init() 后，f 数组不是单调递增的，但 g 数组是单调递增的。
A.对
B.错
【解析】B。
f数组表示约数个数，g数组表示约数之和，都不是单调递增的。
（4）init 函数的时间复杂度为（ ）。
A. O(n)
B. O(nlogn)
C. O(n√n)
D. O(n2n^{2}n2)
【解析】A。
欧拉筛也称为线性筛，应为每个合数仅会被筛掉一次。
（5）在执行完 init() 后，f[1],f[2],f[3]…f[100] 中有（）个等于 2。
A. 23
B. 24
C. 25
D. 26
【解析】C。
f数组存储约数个数，只有质数的约数个数是2个，1～100之间的质数有25个。
（6）当输入为 1000 时，输出为（）。
A. 15 1340
B. 15 2340
C. 16 2340
D. 16 1340
【解析】C。
1000的约数有16个，分别是1、2、4、5、8、10、20、25、40、50、100、125、200、250、500、1000，约数之和2340。

【第三部分 完善程序题】

【完善程序-1】（Josephus 问题）
有 n 个人围成一个圈，依次标号 0 至 n～1。从 0 号开始，依次 0,1,0,1,… 交替报数，报到 1 的人会离开，直至圈中只剩下一个人。求最后剩下人的编号。

做题顺序：先（2）、（3）、（4）、（5）再（1）
（1）①处应填（ ）
A.i < n
B.c < n
C.i < n- 1
D.c < n-1
【解析】D。
环上离开n-1个人，剩余1个人，就不需要循环，c是记录离开的人数，排除A和C选项，分析B选项，当c是n-1时，c < n成立，仍进行标记，可能把最后一个人也标记掉，不符合题意，所以此处应该c < n-1。
（2）②处应填（ ）
A.i % 2 == 0
B.i % 2 == 1
C.p
D.!p
【解析】C。
p用来实现0、1、0、1、...交替报数，p初始值为0，当p为1时，i离开圈。
（3）③处应填（ ）
A.i++
B.i = (i + 1) % n
C.c++
D.p ^= 1
【解析】C。
F[i]=1表示i编号的人离开，c记录离开的人数，此处c++。
（4）④处应填（ ）
A.i++
B.i = (i + 1) % n
C.c++
D.p ^= 1
【解析】D。
p用来实现0、1、0、1、...交替报数，p ^= 1异或运算，能够实现0、1交替，例如：当p为0时，p ^= 1，p变为1；当p为1时，p ^= 1，p变为0。
（5）⑤处应填（ ）
A.i++
B.i = (i + 1) % n
C.c++
D.p ^= 1
【解析】B。
因为第13行会判断当前i是否被标记，所以此处就是下一个环上的编号，不管这个编号是否被标记，因为是在环上，环的大小是n，此处要取余i = (i + 1) % n。

【完善程序-2】矩形计数
平面上有 n 个关键点，求有多少个四条边都和 x 轴或者 y 轴平行的矩形，满足四个顶点都是关键点。给出的关键点可能有重复，但完全重合的矩形只计一次。

试补全枚举算法。
（1）①处应填（ ）
A. a.x != b.x ? a.x < b.x : a.id < b.id
B. a.x != b.x ? a.x < b.x : a.y < b.y
C. equals(a, b) ? a.id < b.id : a.x < b.x
D. equals(a, b) ? a.id < b.id : (a.x != b.x ? a.x < b.x : a.y < b.y)
【解析】B。
第61行和62行是先排序再去重，去重函数中unique中，只要保证x和y都相同的关键点连续在一起，不关心id的顺序。
（2）②处应填（ ）
A. i == 0 || cmp(A[i], A[i - 1])
B. t == 0 || equals(A[i], A[t - 1])
C. i == 0 || !cmp(A[i], A[i - 1])
D. t == 0 || !equals(A[i], A[t - 1])
【解析】D。
t用来记录去重后关键点的个数，当!equals(A[i], A[t - 1])
成立时，记录。
（3）③处应填（ ）
A. b - (b - a) / 2 + 1
B. (a + b + 1) >> 1
C. (a + b) >> 1
D. a + (b - a + 1) / 2
【解析】C。
取中间点。
（4）④处应填（ ）
A. !cmp(A[mid], p)
B. cmp(A[mid], p)
C. cmp(p, A[mid])
D. !cmp(p, A[mid])
【解析】B。
（4）和（5）结合结合起来理解，相当于构造了两个新的点p：（1）i点的x和j点的y构成一个新的点p，利用二分查找与p相同的点；（2）i点的y和j点的x构成一个新的点p，利用二分查找与p相同的点。如果能找到，就找到了如图所示的矩形。
因为关键点都按照x、y从小到大排序，所以mid点小于p点时，往右收敛。

（5）⑤处应填（ ）
A. A[i].x == A[j].x
B. A[i].id < A[j].id
C. A[i].x == A[j].x && A[i].id < A[j].id
D. A[i].x < A[j].x && A[i].y < A[j].y
【解析】D。
枚举i和j时，所有情况都包含，如果不保证i和j一个在左边，一个在右边，会有重复枚举的情况。参考（4）解析的图。