csp-j 初赛真题（S第一轮认证分析）

一、2022CSP-J真题分析及解析：

总体试卷难度相比于去年要低不少，考查内容更细节、更“信息化”。

一、单项选择部分：

今年单选变化很大，J组中没有出现排列组合等数学题，考查的内容全部都是编程方面，包括：c 语言特性、语法代码、数据结构和算法等。难度其实是降低了，因为没有“数学题”可以节约很多时间和精力。考点更倾向于基础和概念性知识，对于数学好的学生在考试中的优势没有去年那么大。

二、阅读程序部分：

阅读程序题的题型和前两年很相近，代码量和得分难度比21年要小。考查的内容包括：位运算、进制、递归、二分、时间复杂度等。得分仍然依赖计算的准度和速度，通过要求考生对数据的“敏感度”很高，例如

三、完善程序部分：

完善程序题型相比于往年没有变化，但是两道题难度均比21年要低，不仅题意理解起来简单，而且代码阅读难度也不高。一道题是基础的因数问题，一道是基础的广搜算法，均是普及组级别难度的题目。

CSPJ-2022真题答案解析——答案——一、单项选择(共15题，每题2分，共计30分)

二、阅读程序（除特殊说明外判断题每题1.5分，选择题每题3分，共计40分）

三、完善程序（共10题，每题3分，共计30分）

——解析——一、单项选择

1.C语言也能调用printf，但是C语言是面向过程。

2.4的下面是5，6不能先出。

3.指针指向问题，p=q,将p指向y，最后p,q都会指向y。

4.都能排序，都能存很多数据，但数组定义后大小固定，而链表不会。

5.栈先进后去，对于队列先进先出，本题本质就是队列的出顺序，也就是栈的出顺序，故最大空间为3。

6.根据前序遍历可以画出如下二叉树：

7. 将百分制转为整数，采取哈夫曼编码，访问到16需要经过2根线（画完图，之后数连接线根数）

8.画树 8，19

9.注意是‘有向图’’连通’图，边数最少时是一个环（圆圈）。

10. 两个栈就可以模拟队列了。

11.从最后往前做，注意一点P->next不能先修改，不然S指向不了后继。

12.

13.按位权展开3*8 2 8-1 = 26.125。

14.

去重 a,b,ab

5*6/2 1–3=13

15.递归和编译无关。

二、阅读程序

阅读1

16、

对。unsigned short 表示无符号，所以范围在 0-65535，short的数值范围在-32767 - 32768 之间。unsigned删除相当于少一位，最大的数字是0x55 = 01010101B ，在short的数值范围以内，所以删除不会有影响。

17、

错。char 是字符类型，每次只会读取一个字符，而输入的数字可能为两位数，这会导致输入数据不能正常读取。

18、

错

结合19，20题考虑输入为2 2的情况

x=(x|x<<2)&0x33=（10|1000）&00110011=1010&00110011=10=2

x=(x|x<<1)&0x55=（10|100）&01010101=110&01010101=100=4

y=(y|y<<2)&0x33=（10|1000）&00110011=1010&00110011=10=2

y=(y|y<<1)&0x55=（10|100）&01010101=110&01010101=100=4

z=(x|y<<1)=100|1000=1100=12

故可以输出12不是只能输出0

19、

错 输入2 2结果为12

20、

错 输入2 2结果为12

21、B。

x=(x|x<<2)&0x33=（1101|110100）&00110011=111101&00110011=110001=49

x=(x|x<<1)&0x55=（110001|1100010）&01010101=1110011&01010101=11010001=209

y=(y|y<<2)&0x33=（1000|100000）&00110011=101000&00110011=100000=32

y=(y|y<<1)&0x55=（100000|1000000）&01010101=1100000&01010101=1000000=64

z=(x|y<<1)= 11010001|10000000=11010001=209

故应该输出209

阅读2

22. 错 执行了448次。

23. 对 2个函数功能相同。

24. 对 14行if（m==1）return n。

25. C 较为简单，30行的n乘以31行的m再乘以33行的n，0（m*n^2）。

26. C 用f函数计算更简单

27. B 用g函数计算更简单

阅读3：

28、对。solve1()是二分法，时间复杂度为logn，solve2()for循环是k次，两个函数各调用一次，时间复杂度做加法。

29、对。对于sqrt（n），k表示保留小数的位数，99*99=9801

30、错。只有n是平方数时才满足，比如：输入4，第二个数输出1。输入5，第二个数输出0，第二个数表示是否完全相等。

31、错。不会溢出，mid最大值为23500，mid*mid<=2e9，且mid只会往小变。

32、C sqrt（2）=1.414....，k=1，保留一位小数，所以第一个数为1.5

33、B sqrt（3）=1.732..

34、A sqrt（256）=16

三、完善程序

完善1：

题意：先求小于

的因数，在求大于

的因数。

35.A. 这个循环的目的是求出n的质因数，所以如果n%==0那么便进入循环。

36.B. 依次输出现在已经求出的质因数的值，直接输出fac[k]即可。

37.C. 由于上一个求质因数的循环跳出条件是i*i<n，所以如果n刚好是一个平方数那么根号n就被遗漏掉了，这里特殊判断这种情况，所以进入循环的条件应该是i*i==n。

38.D. 输出特殊情况i。

39.A. 再反向遍历质因数数组，通过除法依次求出较大的那个正因数。即输出大于sqrt（n）的因子。

完善2：

题意：通过广搜实现

40、A.前四个判断条件保证了这个点的范围在图像范围内不会越界，最后的判断image[r][c]!=new_color保证了不会进入已经被填充新颜色的像素，还需要的判断条件是题意的路径上所有像素的颜色都与起始像素颜色相同，所以需要image[r][c]==prev_color。

41、B.因为起始的坐标点不会再在整个搜索过程中使用，所以读取初始颜色之后直接给起点填充上新颜色。

42、C.points数组存储的是当前像素的四个方向，上下左右，需要补充完整的是上方的像素坐标Point(pt.r 1,pt.c)。

43、D.根据if判断语句的条件，现在已经找到了需要填充的点，所以直接把当前的点填充上新颜色image[p.r][p.c]=new_color;

44、A.根据宽度优先搜索的思想，当找到一个新的点的时候需要把新的点加入队列，方便以后再通过这个点来搜索周围的点，直到队列中为空，所以应该加入的点是queue.push(p)

二、2022CSP-S真题分析及解析：

和J组类似，总体试卷难度相比于去年要低，整套题阅读起来比较轻松。

一、单项选择部分:

单选考的较偏，出现了多字节数据的存储和time命令等平时很难接触到的新题，数学题出现了2道，比去年要少。平时比较注重计算机基础理论学习的同学会相对占优。

二、阅读程序部分:

阅读程序题的题型没有变化，但根据输入推导输出的题特别多，即使读不懂题目也可以通过精准的计算得到分数。每道题的计算量相比于去年要少，因此阅读程序整体难度小幅降低。计算快和准的考生得分率会更高。

三、完善程序部分

完善第一题相比往年表现的中规中矩，但完善第二题并没有考查高阶数据结构或算法，题意也相对容易理解。学过DFS的同学都可以尝试，甚至利用对称技巧和函数命名可以快速得到满分答案，因此完善程序大幅下调了难度。

CSPS-2022真题答案解析——答案——一、单项选择(共15题，每题2分，共计30分)

二、阅读程序（除特殊说明外判断题每题1.5分，选择题每题3分，共计40分）

三、完善程序（共10题，每题3分，共计30分）

——解析——一、单项选择

1.Linux中用于切换目录的命令是cd

2.

real程序实际的执行时间

user用户态时间

sys内核态时间

秒表最接近的值应该是real值

3.D选项连续出栈了5次

4.归并排序在任何情况下都是O(nlogn)，快排最坏情况下是O(n2)

5.1个数错误不会影响整体

6.char类型是1个字节，强转为char后会取低地址的1个字节。

7.画图模拟。

8. 强连通图: 有向图中，若任意两个顶点 Vi 和 Vj，满足从 Vi 到 Vj 以及从 Vj 到 Vi 都连通，也就是都含有至少一条通路，则称此有向图为强连通图。如图 4 所示就是一个强连通图。不一定两个顶点之间都有边。

9.举例n=3，此时只有一种情况，四个选项里只有D是1。

10.8个人中选2个C(2,8)。

11. 每个ℒ符号有26种选法，这个符号有10种选法一共26*26*10*10*10=676000个。

12. 71存在1中，23存在3中，73由于3冲突存在4中，99存在9中

44由于4冲突存在5中79由于9冲突存在0中，89由于9冲突以

及0冲突以及1冲突存在2中。

13.外层循环复杂度O(n),内层循环为logn，复杂度O(nlogn)

14.取第一个为标准值，后面n-1数比较，比较n-1次

15. 递归转递推计算即可。

二、阅读程序

阅读1：

1、对。没有相等的子串，故为-1。

2、错。答案为3，“abab”在“abbababbbab”中第一次出现的下标。

3、对。“22”长度为2，匹配两次。

4、D。字符串匹配过程中，最坏情况下每次都最后才匹配失败，最坏情况O(nm)。

5、A。a.find(b)也是返回a中第一次找到b的位置。

6、B。模拟即可，10次。

阅读2：

1、错。类基数排序，稳定。

2、错。明显也与k相关。

3、对。外层m次，内层n k次，得到O(m(n k))

4、D。模拟即可

5、C。充分利用空间换时间，k越大，只要val[i]/k不超过空间上限，就效率越高。

6、C。通过第29行可知，计数排序

阅读3：

1、对。由第20行发现，n不断除以k，同时m ，因此17行和22行的循环次数都是

。

2、错。不强制转换会输出数字。

3、对。可

由

m=

推算，也可代入k=2，n为2的次方，进行模拟。

4、A。模拟即可，类似100转7进制得202。

5、B。模拟即可。

6、B。看着数据很大，实际5~6次计算即可得到结果。

三、完善程序

完善1：

1.C. 根据cnt的执行语句if(cnt<k)可知，cnt与k进行比较，cnt的含义为两个mid的左边的数字数量总和，也就是较小的数字的个数有没有达到k从而判断不到第k小或者超过里第k小。

2.B. 根据该if语句的执行内容以及与之相对的else的执行内容，if里移动left1而else里移动left2可知，当a1里的mid小于a2中的mid时才移动left1。

3.C. 根据该if语句的执行内容和else的执行内容，if里x=a1[left1-1]代表a1数组排序完成，即left1>right1时。

4.C. 第4和5空时挑选出第k小的的和第k-1小的两个进行比较，较大的数即是第k小。根据逗号前x的赋值可知，x前有left1-1个比他小的，则y为a2[k-left1-1]，有k-left1-1个比y小的，一共有k-left1-1 left1-1=k-2个比x和y小的，此时x和y分别为第k-1大和第k大。

5.A.同上

完善2：

1.A。由对称位置的45行可知是从容器2向容器1倒水，而且（1）和（4）是同一种情况。

2.C。由对称位置的50行可知是从容器1向容器2倒水，而且（2）和（5）是同一种情况。

3.A。go(0,0)是从（0,0）开始的，由对称位置的13行可以得到搜索结束的边界。

4.A。原因同1。

5.C。原因同2。

三、2022CSP-J/S真题

,