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分)
![](http://dingyue.ws.126.net/2022/0918/836b702fj00rietk8001ac000u0006mm.jpg)
【答案】A
【解析】printf函数是C语言中的函数,C语言是面向过程的语言,因此选A。
![](http://dingyue.ws.126.net/2022/0918/f2768bc0j00rietk9000uc000u0007zm.jpg)
【答案】C
【解析】模拟入栈出栈,C选项中"6 5"不可能实现。
![](http://dingyue.ws.126.net/2022/0918/ee41dbc3j00rietk6000mc000u000b7m.jpg)
![](http://dingyue.ws.126.net/2022/0918/9b8ef4a3p00rietk7000ec000u0002im.png)
【答案】D
【解析】初始时p指向x的地址,q指向y的地址,执行第5行程序后,将p指向y的地址。
![](http://dingyue.ws.126.net/2022/0918/2a86193aj00rietk80012c000u0006nm.jpg)
【答案】C
【解析】A选项,数组可以排序;B选项,链表不能存储比数组更多的信息;C选项正确。
![](http://dingyue.ws.126.net/2022/0918/8e556e4fj00rietk90023c000u000azm.jpg)
【答案】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。
![](http://dingyue.ws.126.net/2022/0918/d0f52839j00rietk9000oc000u0006mm.jpg)
【答案】B
【解析】中缀表达式转换为前缀表达式的方法:
①将所有运算按照优先级加上小括号,(a+((b-c)*d))
②将运算符移到对应小括号前,+(a*(-(b c) d)
③去掉小括号,+a*-bcd
![](http://dingyue.ws.126.net/2022/0918/a2250750j00rietk90014c000u0006tm.jpg)
![](http://dingyue.ws.126.net/2022/0918/ec2acb55p00rietk70002c000u0002dm.png)
【答案】B
【解析】按照哈夫曼编码规则画出哈夫曼树,如下图结点d到根节点的边数即编码长度为2。
![](http://dingyue.ws.126.net/2022/0918/201c56ddj00rietk8001nc000cy00cjm.jpg)
![](http://dingyue.ws.126.net/2022/0918/9245995aj00rietk9001hc000u0009cm.jpg)
【答案】C
【解析】9的父结点是4,兄弟结点是8,左儿子结点是18,右儿子结点是19
![](http://dingyue.ws.126.net/2022/0918/0a2cbbf3j00rietk9000vc000u0007wm.jpg)
【答案】B
【解析】n个点有向连通图,至少有n条边,连成一圈,邻接矩阵中非零元素即为边数最少为n。
![](http://dingyue.ws.126.net/2022/0918/1a97eb1ej00rietk9001nc000u0006om.jpg)
【答案】D
【解析】使用两个栈,一个栈存放入队的操作,另一个栈用来出队,即可用栈实现队列。
![](http://dingyue.ws.126.net/2022/0918/4f2fc70fj00rietk9001rc000u0006om.jpg)
![](http://dingyue.ws.126.net/2022/0918/27d5f56dp00rietk60006c000u00017m.png)
【答案】D
【解析】画图模拟,选项D正确。
![](http://dingyue.ws.126.net/2022/0918/8522a470j00rietk90017c000u0006nm.jpg)
【答案】B
【解析】选择排序是不稳定排序。
![](http://dingyue.ws.126.net/2022/0918/071845aej00rietk8000kc000u0006im.jpg)
【答案】C
【解析】按权展开,3×8 + 2×1 + 1×1/8 = 26.125
![](http://dingyue.ws.126.net/2022/0918/28ef9336j00rietk8000vc000u00082m.jpg)
【答案】B
【解析】所有子串共有 16个,刨去重复的子串"a", "b", "ab",余下 13个不重复的子串。
![](http://dingyue.ws.126.net/2022/0918/88cabf49j00rietk9001tc000u0006lm.jpg)
【答案】B
【解析】递归是通过调用自身来求解问题的编程技术,B选项正确。
二、阅读程序题(除特殊说明外,判断题每题1.5分,选择题每题3分,共计40分)
01
程序(1)
![](http://dingyue.ws.126.net/2022/0918/e8341480j00rietka0040c000si00kum.jpg)
【解析】本程序考查位运算的知识点。unsigned short表示无符号短整型,数据范围为 0 ~ 65535,占 2个字节。| 为按位或运算,& 为按位与运算,<< 为左移运算。需要注意的是 << 运算优先级高于 |。0x33 表示 十六进制的33,即十进制的51; 0x55 表示 十六机制的55,即十进制的85。
![](http://dingyue.ws.126.net/2022/0918/58c9e9b1p00rietk7000qc000t30029m.png)
【答案】 √
【解析】short为16位,删除unsigned,相当于少了一位最高位。0x55 = 01010101B,少一位不影响运算结果。
![](http://dingyue.ws.126.net/2022/0918/030597bdp00rietk7000lc000t2000zm.png)
【答案】 ×
【解析】输入为不超过15的自然数,改为char以后,当输入为两位数时,x,y分别读入的是第一个数的十位和个位,改变了程序的行为和结果。
![](http://dingyue.ws.126.net/2022/0918/dde0dd38p00rietk7000fc000sr0013m.png)
【答案】 ×
【解析】代入"2 2",输出结果为"12"。
![](http://dingyue.ws.126.net/2022/0918/56e7543bp00rietk7000ec000t70013m.png)
【答案】×
【解析】代入"2 2",输出结果为"12"。
![](http://dingyue.ws.126.net/2022/0918/58869ca7p00rietk7000ec000su0011m.png)
【答案】×
【解析】代入"2 2",输出结果为"12"。
![](http://dingyue.ws.126.net/2022/0918/b1fe8b49j00rietk8000wc000tt004im.jpg)
【答案】B
【解析】代入"13 8",输出结果为"209"。
02
程序(2)
![](http://dingyue.ws.126.net/2022/0918/44b9f6abj00rietk9002kc000u0007lm.jpg)
![](http://dingyue.ws.126.net/2022/0918/b97a114aj00rietka0088c000u000rom.jpg)
![](http://dingyue.ws.126.net/2022/0918/29955d98j00rietka0051c000u000l5m.jpg)
【解析】本程序中f函数和g函数的计算结果是一样的,f函数通过递归实现,g函数通过循环实现。因此,在计算结果时,可以代入任意函数列表进行计算得到结果。
![](http://dingyue.ws.126.net/2022/0918/802a8c73p00rietk70012c000u00023m.png)
【答案】×
【解析】代入模拟计算,共执行了448次。亦可通过递推式根据奇偶性快速判断。
![](http://dingyue.ws.126.net/2022/0918/ecc6aff0p00rietk7000ic000u00011m.png)
【答案】√
【解析】两个函数的计算结果是一样的。
![](http://dingyue.ws.126.net/2022/0918/e1a29755p00rietk7000gc000u00012m.png)
【答案】√
【解析】代入f函数,当m == 1时,计算结果为n。
![](http://dingyue.ws.126.net/2022/0918/4358241fp00rietk7001ec000u00031m.png)
【答案】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()。
![](http://dingyue.ws.126.net/2022/0918/ce9a8058p00rietk7000sc000u0001wm.png)
【答案】C
【解析】代入模拟,可以发现m=2时,列举出n为1~20的计算结果为1个1,2个2,3个3,4个4,5个5,5个6,因此结果为6。
![](http://dingyue.ws.126.net/2022/0918/fb43d02dp00rietk7000xc000u0001xm.png)
【答案】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)
![](http://dingyue.ws.126.net/2022/0918/d5ca9507j00rietka005ic000u000ozm.jpg)
![](http://dingyue.ws.126.net/2022/0918/95d8c211j00rietk90036c000u0009lm.jpg)
【解析】本程序考查二分法及牛顿迭代法求算术平方根。solve1函数用二分法求出近似的算术平方根,然后用solve2函数进行牛顿迭代法,求出n的算术平方根。k为迭代的次数。
![](http://dingyue.ws.126.net/2022/0918/f23b8c66p00rietk7000yc000u00022m.png)
【答案】√
【解析】solve1函数是二分O(logn),solve2函数是O(k),都只执行一次,是O(logn + k)。
![](http://dingyue.ws.126.net/2022/0918/7602f447p00rietk7000nc000u0000zm.png)
【答案】√
【解析】9801 = 99 × 99,算术平方根为99。
![](http://dingyue.ws.126.net/2022/0918/586bbad6p00rietk7000xc000u0000um.png)
【答案】×
【解析】如果算术平方根是无理数,则第二个数输出为0。
![](http://dingyue.ws.126.net/2022/0918/4115f5aap00rietk8001hc000u0001vm.png)
【答案】×
【解析】n <= 47000, mid <= n/2 <= 23500, mid * mid <= 552,250,000,不会溢出。
![](http://dingyue.ws.126.net/2022/0918/add5246ap00rietk8000wc000u0002pm.png)
【答案】C
【解析】代入计算,solve1函数的计算结果为1,solve2函数的计算结果为1.5。
![](http://dingyue.ws.126.net/2022/0918/bbe22378p00rietk8000tc000u0001um.png)
【答案】B
【解析】√3 = 1.732…,k=10,迭代次数越多精度越高,因此接近B。
![](http://dingyue.ws.126.net/2022/0918/5c265e1fp00rietk80016c000u0002um.png)
【答案】A
【解析】256 = 16 × 16,输出的第一个数等于16。
三、完善程序(每题3分,共计30分)
01
程序(1)
![](http://dingyue.ws.126.net/2022/0918/3470a05dj00rietk9002bc000nh00bgm.jpg)
![](http://dingyue.ws.126.net/2022/0918/908fb6d9j00rietka003mc000nl00oem.jpg)
【解析】本程序先从小到大输出小于算术平方根的因数,再特判算术平方根,最后输出大于算术平方根的因数。
![](http://dingyue.ws.126.net/2022/0918/c9de7258p00rietk8000ic000ps003bm.png)
【答案】A
【解析】判断 i 是 n 的一个因数,则加入数组fac中,因此判断条件为 A。
![](http://dingyue.ws.126.net/2022/0918/707ca587p00rietk8000jc000pn003hm.png)
【答案】B
【解析】当前数组fac存储的是小于平方根的所有因数,按顺序输出即可。
![](http://dingyue.ws.126.net/2022/0918/8c007a22p00rietk8000hc000pu003fm.png)
【答案】C
【解析】特判,如果是完全平方数 i * i == n,则输出算术平方根 i。
【答案】D
【解析】如果是完全平方数 i * i == n,则输出算术平方根 i。
![](http://dingyue.ws.126.net/2022/0918/03de6f43p00rietk9000hc000po003fm.png)
【答案】A
【解析】从小到大输出大于算术平方根的因数,因此需要倒序枚举小于算术平方根的因数fac[k],输出对应的另一个因数 n / fac[k]。
021
程序(2)
![](http://dingyue.ws.126.net/2022/0918/dbd605e4p00rietk9002fc000u00021m.png)
![](http://dingyue.ws.126.net/2022/0918/0ce136e6p00rietk9001xc000u00044m.png)
![](http://dingyue.ws.126.net/2022/0918/e59de024j00rietkb00a9c000u000rxm.jpg)
![](http://dingyue.ws.126.net/2022/0918/8dde6c31j00rietka003nc000u000b1m.jpg)
![](http://dingyue.ws.126.net/2022/0918/19e51adfj00rietkb008nc000u000o3m.jpg)
![](http://dingyue.ws.126.net/2022/0918/85994188j00rietka0039c000u000azm.jpg)
【解析】用 bfs 实现洪水填充算法。flood_fill函数的参数依次为图像二维数组image,起始位置cur,给定的颜色new_color。
![](http://dingyue.ws.126.net/2022/0918/3074ba95j00rietk90022c000u0005hm.jpg)
【答案】A
【解析】判断image[r][c]为旧颜色prev_color时,需要更新颜色,因此选A。
![](http://dingyue.ws.126.net/2022/0918/8880a068p00rietk9000lc000u00025m.png)
![](http://dingyue.ws.126.net/2022/0918/2a947bfep00rietk9000yc000u0003am.png)
【答案】B
【解析】将起点位置image[cur.r][cur.c]更新颜色,选B。
![](http://dingyue.ws.126.net/2022/0918/b08fa016p00rietk90014c000u00037m.png)
【答案】C
【解析】上下左右四个相邻点,可以发现少了点(pt.r+1, pt.c)。
![](http://dingyue.ws.126.net/2022/0918/1c47f5f2p00rietk9001ec000u00036m.png)
【答案】D
【解析】将当前位置image[p.r][p.c]更新颜色,选D。
【答案】A
【解析】如果p点符合要求,则将p点加入队列,选A。
热门跟贴