2022-CSP-J入门级第一轮试题答案与解析

2022CCF非专业级别软件能力认证第一轮(CSP-J1)入门级C++语言试题认证时间：2022年9月18日09:30~11:30一、单项选择题(每题2分，共计30分)【答案】A【解析】printf函数是C语言中的函数，C语言是面向过程的语言，因此选A。【答案】C【解析】模拟入栈出栈，C选项中"65"不可能实现。【答案】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*(-(bc)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）【解析】本程序考查位运算的知识点。unsignedshort表示无符号短整型，数据范围为0~65535，占2个字节。|为按位或运算，&为按位与运算，<<为左移运算。需要注意的是<<运算优先级高于|。0x33表示十六进制的33，即十进制的51;0x55表示十六机制的55，即十进制的85。【答案】√【解析】short为16位，删除unsigned，相当于少了一位最高位。0x55=01010101B，少一位不影响运算结果。【答案】×【解析】输入为不超过15的自然数，改为char以后，当输入为两位数时，x，y分别读入的是第一个数的十位和个位，改变了程序的行为和结果。【答案】×【解析】代入"22"，输出结果为"12"。【答案】×【解析】代入"22"，输出结果为"12"。【答案】×【解析】代入"22"，输出结果为"12"。【答案】B【解析】代入"138"，输出结果为"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【解析】