2022年CSP-J第一轮认证试题解析

2022年CSP-J第一轮认证圆满结束

2022年9月18日上午11:30，CSP-J 2022第一轮认证圆满结束；今年的单项选择题少了数学上排列组合的考查，整体上知识点与去年接近; 阅读程序部分需要考生有较好的耐心和计算能力，三段程序算法难度相比去年有所下降; 完善程序的难度也比去年的题目更容易一些。整体来说，试卷的难度要弱于去年的难度，在参赛人数有大幅提升的情况下，分数线预计会比去年更高。

2022 CCF非专业级别软件能力认证第一轮

(CSP-J1) 入门级 C++语言试题

认证时间：2022年9月18日09:30~11:30

一、单项选择题(每题2分，共计30分)

【答案】A

【解析】printf函数是C语言中的函数，C语言是面向过程的语言，因此选A。

【答案】C

【解析】模拟入栈出栈，C选项中"6 5"不可能实现。

【答案】D

【解析】初始时p指向x的地址，q指向y的地址，执行第5行程序后，将p指向y的地址。

【答案】C

【解析】A选项，数组可以排序；B选项，链表不能存储比数组更多的信息；C选项正确。

【答案】B

【解析】栈的特点是后进先出，队列的特点是先进先出。依题意模拟过程，括号中表示栈中数据的个数：e1入栈(1)，e2入栈(2)，e2出栈(1)，e3入栈(2)，e4入栈(3)，e4出栈(2)，e3出栈(1)，e5入栈(2)，e6入栈(3)，e6出栈(2)，e5出栈(1)，e1出栈(0)。栈的容量至少为3。

【答案】B

【解析】中缀表达式转换为前缀表达式的方法：

①将所有运算按照优先级加上小括号，(a+((b-c)*d))

②将运算符移到对应小括号前，+(a*(-(b c) d)

③去掉小括号，+a*-bcd

【答案】B

【解析】按照哈夫曼编码规则画出哈夫曼树，如下图结点d到根节点的边数即编码长度为2。

【答案】C

【解析】9的父结点是4，兄弟结点是8，左儿子结点是18，右儿子结点是19

【答案】B

【解析】n个点有向连通图，至少有n条边，连成一圈，邻接矩阵中非零元素即为边数最少为n。

【答案】D

【解析】使用两个栈，一个栈存放入队的操作，另一个栈用来出队，即可用栈实现队列。

【答案】D

【解析】画图模拟，选项D正确。

【答案】B

【解析】选择排序是不稳定排序。

【答案】C

【解析】按权展开，3×8 + 2×1 + 1×1/8 = 26.125

【答案】B

【解析】所有子串共有 16个，刨去重复的子串"a", "b", "ab"，余下 13个不重复的子串。

【答案】B

【解析】递归是通过调用自身来求解问题的编程技术，B选项正确。

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

01

程序（1）

【解析】本程序考查位运算的知识点。unsigned short表示无符号短整型，数据范围为 0 ~ 65535，占 2个字节。| 为按位或运算，& 为按位与运算，<< 为左移运算。需要注意的是 << 运算优先级高于 |。0x33 表示 十六进制的33，即十进制的51; 0x55 表示 十六机制的55，即十进制的85。

【答案】 √

【解析】short为16位，删除unsigned，相当于少了一位最高位。0x55 = 01010101B，少一位不影响运算结果。

【答案】 ×

【解析】输入为不超过15的自然数，改为char以后，当输入为两位数时，x，y分别读入的是第一个数的十位和个位，改变了程序的行为和结果。

【答案】 ×

【解析】代入"2 2"，输出结果为"12"。

【答案】×

【解析】代入"2 2"，输出结果为"12"。

【答案】×

【解析】代入"2 2"，输出结果为"12"。

【答案】B

【解析】代入"13 8"，输出结果为"209"。

02

程序（2）

【解析】本程序中f函数和g函数的计算结果是一样的，f函数通过递归实现，g函数通过循环实现。因此，在计算结果时，可以代入任意函数列表进行计算得到结果。

【答案】×

【解析】代入模拟计算，共执行了448次。亦可通过递推式根据奇偶性快速判断。

【答案】√

【解析】两个函数的计算结果是一样的。

【答案】√

【解析】代入f函数，当m == 1时，计算结果为n。

【答案】C

【解析】i = 1 时，内层两重循环重复 (m-1)次;

i = 2时，内层两重循环重复 2(m-1)次；

i = n时，内层两重循环重复 n(m-1)次；

累加求和，可得∑i(m-1) = n(n+1)(m+1)/2，时间复杂度为O()。

【答案】C

【解析】代入模拟，可以发现m=2时，列举出n为1~20的计算结果为1个1，2个2，3个3，4个4，5个5，5个6，因此结果为6。

【答案】B

【解析】代入模拟，先计算出m=1，m=2，m=3的情况，找出规律，可以发现当m = 100的时候，列举出n从1~100的结果，为1个1，2个2，4个3，8个4，16个5，32个6，37个7，因此结果为7。

032

程序（3）

【解析】本程序考查二分法及牛顿迭代法求算术平方根。solve1函数用二分法求出近似的算术平方根，然后用solve2函数进行牛顿迭代法，求出n的算术平方根。k为迭代的次数。

【答案】√

【解析】solve1函数是二分O(logn)，solve2函数是O(k)，都只执行一次，是O(logn + k)。

【答案】√

【解析】9801 = 99 × 99，算术平方根为99。

【答案】×

【解析】如果算术平方根是无理数，则第二个数输出为0。

【答案】×

【解析】n <= 47000, mid <= n/2 <= 23500, mid * mid <= 552,250,000，不会溢出。

【答案】C

【解析】代入计算，solve1函数的计算结果为1，solve2函数的计算结果为1.5。

【答案】B

【解析】√3 = 1.732…，k=10，迭代次数越多精度越高，因此接近B。

【答案】A

【解析】256 = 16 × 16，输出的第一个数等于16。

三、完善程序(每题3分，共计30分)

01

程序（1）

【解析】本程序先从小到大输出小于算术平方根的因数，再特判算术平方根，最后输出大于算术平方根的因数。

【答案】A

【解析】判断 i 是 n 的一个因数，则加入数组fac中，因此判断条件为 A。

【答案】B

【解析】当前数组fac存储的是小于平方根的所有因数，按顺序输出即可。

【答案】C

【解析】特判，如果是完全平方数 i * i == n，则输出算术平方根 i。

【答案】D

【解析】如果是完全平方数 i * i == n，则输出算术平方根 i。

【答案】A

【解析】从小到大输出大于算术平方根的因数，因此需要倒序枚举小于算术平方根的因数fac[k]，输出对应的另一个因数 n / fac[k]。

021

程序（2）

【解析】用 bfs 实现洪水填充算法。flood_fill函数的参数依次为图像二维数组image，起始位置cur，给定的颜色new_color。

【答案】A

【解析】判断image[r][c]为旧颜色prev_color时，需要更新颜色，因此选A。

【答案】B

【解析】将起点位置image[cur.r][cur.c]更新颜色，选B。

【答案】C

【解析】上下左右四个相邻点，可以发现少了点(pt.r+1, pt.c)。

【答案】D

【解析】将当前位置image[p.r][p.c]更新颜色，选D。

【答案】A

【解析】如果p点符合要求，则将p点加入队列，选A。