2022 CCF 非专业级别软件能力认证第一轮 (CSP-J1)入门级 C++语言试题及答案

CSP-JS 2022第一轮认证已于9月18日结束,考完当天下午老师整理试卷并分享了估分链接,结果不算理想,当然官方的成绩还没正式公布,最终结果还未知。

考生注意事项:

  • 试题纸共有12页,答题纸共有1页,满分10日分。请在答题纸上作答,写在试题纸上的一律无效。
  • 不得使用任何电子设备《如计算器、手机、电子词典等)或查阅任何书籍资料。

单项选择

一、单项选择题(共 15 题,每题 2 分,共计 30 分;每题有且仅有一个正确选项)
1.以下哪种功能没有涉及C++语言的面向对象特性支持:( )。
A. C++中调用 printf 函数
B. C++中调用用户定义的类成员函数
C. C++中构造一个 class 或 struct
D. C++中构造来源于同一基类的多个派生类

答案:A
解析:printf 是格式化输出,是C语言中的输出方式,不涉及到面向对象。

2. 有 6 个元素,按照 6、5、4、3、2、1 的顺序进入栈 S,请问下列哪个出栈序列是非法的 ( )。
A. 5 4 3 6 1 2
B. 4 5 3 1 2 6
C. 3 4 6 5 2 1
D. 2 3 4 1 5 6

答案:C
解析:3出4出,然后栈顶是5,不能6出

3.运行以下代码片段的行为是( )。

cpp
  
int x = 101;
int y = 201;
int *p = &x;
int *q = &y;
p = q;

A. 将x的值赋为201
B. 将y的值赋为101
C. 将q指向x的地址
D. 将p指向y的地址

答案:D
解析:将q赋值给p以后,表示指针变量p和指针变量q中都存储的是变量y的地址。所以p和a都指向了y的地址。

4.链表和数组的区别包括( )。
A. 数组不能排序,链表可以
B. 链表比数组能存储更多的信息
C. 数组大小固定,链表大小可动态调整
D. 以上均正确

答案:C
解析:数组一经定义后,在内存中就会分配出固定的空间存放内存中的数据,链表的大小取决于链表中结点的个数,可以动态调整。所以选C

5. 对假设栈S和队列Q的初始状态为空。存在 e1~e6 六个互不相同的数据,每个数据按照 进栈S、出栈S、进队列Q、出队列Q的顺序操作,不同数据间的操作可能会交错。已知栈S中依次有数据 e1、e2、e3、e4、e5和e6进栈,队列Q依次有数据e2、e4、e3、e6、e5和e1出队列。则栈S的容量至少是( )个数据。
A. 2
B. 3
C. 4
D. 6

答案:B
解析:首先栈的顺序是先进后出
然后队列的顺序是先进先出
核心点:每一个结点的操作都是进栈,出栈,进队列,出队列。
根据队列来看,e2是第一个出队的,表明此时e2是第一个入队,也就是说在e2入队之前栈中存储的数据为el,e2。然后e2出栈,栈中保存元素为cl,然后队列第二个出队数据是e4,e4入队之前栈中数据有el,e3,e4。然后e4,e3依次出栈进入队列出队,然后队列下一个出队的元素e6,e6入队前栈中数据有el,e5,e6。 所以根据分析来看,栈的容量至少为3。

6.对表达式a+(b-c)*d的前缀表达式为( ),其中+、-、*是运算符。
A. *+a-bcd
B. +a*-bcd
C. abc-d*+
D. abc-+d

答案:B
解析:前缀表达式
方法一:按照运算顺序,符号前移,操作数后移。
方法二:按照表达式画出树后可以求出前序遍历,即为前缀表达式。

7. 假设字母表 {a, b, c, d, e} 在字符串出现的频率分别为 10%, 15%, 30%, 16%, 29%。若使用哈夫曼编码方式对字母进行不定长的二进制编码,字母d的编码长度为 ( )位。
A. 1
B. 2
C. 2或3
D. 3

答案:B
解析:先构造哈夫曼树,然后可以发现d在哈夫曼树的第2层。编码长度为2。

8. 一棵有 n 个结点的完全二叉树用数组进行存储与表示,已知根结点存储在数组的第1个位 置。若存储在数组第9个位置的结点存在兄弟结点和两个子结点,则它的兄弟结点和右子 结点的位置分别是( )。
A. 8、18
B. 10、18
C. 8、19
D. 10、19

答案:C
解析:根据二叉树的顺序存储来看

9. 考虑由N个顶点构成的有向连通图,采用邻接矩阵的数据结构表示时,该矩阵中至少存在( )个非零元素。
A. N-1
B. N
C. N+1
D. N2

答案:B
解析:题目中说的是有向连通图,口个顶点最少存在n条边。所以存在n个非0元素。

10.以下对数据结构的表述不恰当的一项为:( )。
A. 图的深度优先遍历算法常使用的数据结构为栈。
B. 栈的访问原则为后进先出,队列的访问原则是先进先出。
C. 队列常常被用于广度优先搜索算法。
D. 栈与队列存在本质不同,无法用栈实现队列。

答案:D
解析:栈与队列存在本质相同,他们都是操作受限的线性表。

11.以下哪组操作能完成在双向循环链表结点 p 之后插入结点 s 的效果(其中,next 域为结 点的直接后继,prev域为结点的直接前驱):( )。
A. p->next->prev=s; s->prev=p; p->next=s; s->next=p->next;
B. p->next->prev=s; p->next=s; s->prev=p; s->next=p->next;
C. s->prev=p; s->next=p->next; p->next=s; p->next->prev=s;
D. s->next=p->next; p->next->prev=s; s->prev=p; p->next=s;

答案:D
解析:双向循环链表中,每个节点都存在一个pre指针域和nex!指针域。pre指针域存储前驱结点的地址,next指针域存储后继结点的地址。

12.以下排序算法的常见实现中,哪个选项的说法是错误的:( )。
A. 冒泡排序算法是稳定的
B. 简单选择排序是稳定的
C. 简单插入排序是稳定的
D. 归并排序算法是稳定的

答案:B
解析:不稳定排序有:选择,希尔,快速,堆排序

13.八进制数32.1对应的十进制数是( )。
A. 24.125
B. 24.250
C. 26.125
D. 26.250

答案:C
解析:3*8+2=26 / 1/8=0.125

14.一个字符串中任意个连续的字符组成的子序列称为该字符串的子串,则字符串abcab有( )个内容互不相同的子串。
A. 12
B. 13
C. 14
D. 15

答案:B
解析:长度为0的子串:空串
长度为1的子串:abc
长度为2的子串:ab bc ca
长度为3的子串:abc bca cab
长度为4的子串:abca bcab
长度为S的子串:abcab
一共是13个。

15.以下对递归方法的描述中,正确的是:( )
A. 递归是允许使用多组参数调用函数的编程技术
B. 递归是通过调用自身来求解问题的编程技术
C. 递归是面向对象和数据而不是功能和逻辑的编程语言模型
D. 递归是将用某种高级语言转换为机器代码的编程技术

答案:B
解析:递归就是西数自己调用自己

二、阅读程序(程序输入不超过数组或字符串定义的范围;判断题正确填√,错误填×;除特 殊说明外,判断题 1.5 分,选择题 3 分,共计 40 分)

阅读理解(1)

cpp

01  #include <iostream>
02
03  using namespace std;
04
05  int main()
06  {
07      unsigned short x, y;
08      cin>>x>>y;
09      x = (x | x << 2) &
10      x = (x | x << 1) &
11      y = (y | y << 2) &
12      y = (y | y << 1) &
13      unsigned short z =
14      cout << z << endl;
15      return 0;
16 }

假设输入的 x、y 均是不超过 15 的自然数,完成下面的判断题和单选题:

判断题

16. 删去第7行与第13行的unsigned,程序行为不变。( )

答案:V
解析:因为输入的x和y都是不超过15 的自然数,15表示为二进制是 1111, short类型的变量是2个字节,16位,其中最高位是符号位,剩下15位存放数据,足够放的下运算的结果。所以加不加unsigned(无符号)没有影响。所以本题正确。

17. 将第7行与第13行的short均改为char,程序行为不变。( )

答案:x
解析:如果改成char类型,因为y在整个程序中左移了4位,那么最高位的值有可能是1,导致最后的结果存不到char类型的变量中,最后结果就会出错,所以本题错误。

18. 程序总是输出一个整数“0”。( )

答案:x
解析:第4题和第s题带入模拟后能够判断输出不是0,所以本题错误。

19. 当输入为“2 2”时,输出为“10”。( )

答案:x
解析:输入是22之后,模拟带入运算答案是12,所以本题错误。

20. 当输入为“2 2”时,输出为“59”。( )

答案:x
解析:输入是22之后,模拟带入运算答案是12,所以本题错误。

单选题

21. 当输入为“13 8”时,输出为( )。
A. “0” B. “209” C. “197” D. “226”

答案:B
解析:经过模拟运算,计算出答案是209。

阅读理解(2)

cpp

01  #include <algorithm> 
02  #include <iostream>
03  #include <limits>
04
05  using namespace std; 
06
07  const int MAXN = 105;
08  const int MAXK = 105;
09
10  int h[MAXN][MAXK];
11
12  int f(int n, int m)
13  {
14      if (m == 1) return n;
15      if (n == 0) return 0;
16
17      int ret = numeric_limits::max();
18      for (int i = 1; i <= n; i++)
19          ret = min(ret, max(f(n - i, m), f(i - 1, m - 1)) + 1);
20      return ret;
21 }
22
23 int g(int n, int m)
24 {
25      for (int i = 1; i <=n; i++)
26          h[i][1] = i;
27      for (int j = 1; j <= m; j++)
28          h[0][j] = 0;
29
30      for (int i = 1; i <= n; i++)
31          for ( j = 2; j <= m; j++) {
32              h[i][j] = numeric_limits<int>::max();
33              for (int k = 1; k <= i; k++)
34              h[i][j] = min(
35                  h[i][j],
36                  max(h[i -k][j], h[k - 1][j - 1] + 1);
37          }
38      }
39
40      return h[n][m];
41 }
42
43 int main()
44 {
45 int n, m;
46 cin >> n >> m;
47 cout << f(n, m) << endl << g(n, m) << endl;
48 return 0;
49 }

假设输入的 n、m 均是不超过 100 的正整数,完成下面的判断题和单选题:

判断题

22.当输入为“7 3”时,第 19 行用来取最小值的 min 函数执行了 449 次。( )

答案:x
解析:执行了448次。两个参数,可以画一个表进行模拟。额外标记每一次运算需要的次数。
2022 CCF 非专业级别软件能力认证第一轮  (CSP-J1)入门级 C++语言试题
每个表格里面存放了当前的值,(里面表示运行min的次数。发现n–7,m-=3的时候min运行了448次。

23.输出的两行整数总是相同的。( )

答案:V
解析:模拟过后发现两个西数的目的相同,做的是同样的运算。所以本题正确。

24.当m为1时,输出的第一行总为n。( )

答案:V
解析:当m的值是1的时候,递归出口在第14行 if(m == 1) return n;所以本题正确

单选题

25.算法g(n,m)最为准确的时间复杂度分析结果为( )。
A. 0(n3/2m)
B. 0(nm)
C. 0(n2m)
D. 0(nm2)

答案:C
解析:关注第30行、第31行、第33行,这3行循环的次数分别是n,m,n,所以时间复杂度可以估计为0(m*n2)。所以答案选C。

26.当输入为“20 2”时,输出的第一行为( )。
A. “4” B. “5” C. “6” D. “20”

答案:C
解析:因为两个函数结果相同,带入到,或者g西数中模拟可得6,所以选择C选项。

27.(4 分)当输入为“100 100”时,输出的第一行为()
A. “6” B. “7” C. “8” D. “9”

答案:B
解析:因为两个函数结果相同,带入到f或者g西数中模拟可得了,所以选择B选项

阅读理解(3)

cpp

01 #include <iostream>
02
03 using namespace std;
04
05 int n, k;
06
07 int solve1()
08 {
09      int l = 0, r = n;
10      while (l <= r) {
11          int mid = (l + r) / 2;
12          if (mid * mid <= n) l = mid + 1;
13          else r = mid - 1;
14      }
15      return l - 1;
16 }
17
18 double solve2(double x) 19 {
20 if (x == 0) return x;
21 for (int i = 0; i < k; i++)
22 x = (x + n / x) / 2;
23 return x;
24 }
25
26 int main()
27 {
28      cin >> n >> k;
29      double ans = solve2(solve1());
30      cout << ans << ' ' << (ans * ans == n) << endl;
31      return 0;
32 }

假设int为32位有符号整数类型,输入的n是不超过47000的自然数、k是不超过int表示范围的自然数,完成下面的判断题和单选题:

经过模拟,我们可以发现本题主要运算的就是n的平方根,当k在增大的时候,运算出的答案就越接近n的平方根。

判断题

28.该算法最准确的时间复杂度分析结果为𝑂𝑂(log𝑛𝑛+𝑘𝑘)。( )

答案:V
解析:sovlel西数是一个二分的西数,时间复杂度是O(logn)
solve2西数是一个循环k次的西数,时间复杂度是O(k)
因为solve1函数和solve2函数都仅仅调用了一次,所以整个算法的时间复杂度是0(k十logr)。所以本题正确。

29.当输入为“9801 1”时,输出的第一个数为“99”。( )

答案:V
解析:输入的是9801,1
相当于计算的是sqrt(9801)=99,所以输出的ans是99。,所以本题正确。

30.对于任意输入的n,随着所输入k的增大,输出的第二个数会变成“1”。( )

答案:×
解析:只要不能开平方根,就是0,所以本题错误。

31.该程序有存在缺陷。当输入的 n 过大时,第 12 行的乘法有可能溢出,因此应当将 mid强制转换为64位整数再计算。( )

答案:x
解析:n是不超过47000的自然数,mid是二分后的值,mid*mid是不会超过in范围的,所以本题错误。

单选题

32.当输入为“2 1”时,输出的第一个数最接近( )。
A. 1 B. 1.414 C. 1.5

答案:C
解析:带入模拟,可得1.5

33.当输入为“3 10”时,输出的第一个数最接近( )。
A. 1.7 B. 1.732 C. 1.75

答案:B
解析:输入的3和10,发现经过了多次运算后,会逐步接近于3的平方根,也就是1.732

34.当输入为“256 11”时,输出的第一个数( )。
A. 等于16
B. 接近但小于16
C. 接近但大于 16
D. 前三种情况都有可能

答案:A
解析:因为256的平方根就是16,无论k是多少,答案都是16.

三、完善程序(单选题,每小题 3 分,共计 30 分)

完善程序1

(1)(枚举因数)从小到大打印正整数 n 的所有正因数。 试补全枚举程序。

2022 CCF 非专业级别软件能力认证第一轮  (CSP-J1)入门级 C++语言试题
35. (1)处应填( )
A. n%i == 0
B. n%i == 1
C. n%(i-1) == 0
D. n%(i-1) == 1

答案:A
解析:需要将所有口的因子放入vector中。所以判断i是不是因数的方式为if(n%i==0)

36. (2)处应填( )
A. n / fac[k]
B. fac[k]
C. fac[k]-1
D. n / (fac[k]-1)

答案:B
解析:输出了所有小于sqrt(n)的因子

37. (3)处应填( )
A. (i-1)*(i-1)==n
B. (i-1)*i==n
C. i*i==n
D. i*(i-1)==n

答案:C
解析:如果口是一个完全平方数,则会出现i*i==n的情况,此时i只需要输出一个即可。

38. (4)处应填( )
A. n-i
B. n-i+1
C. i-1
D. I

答案:D
解析:当i*i==n时,输出一个i(这里原题面为大写I)

39. (5)处应填( )
A. n / fac[k]
B. fac[k]
C. fac[k]-1
D. n / (fac[k]-1)

答案:A
解析:输出所有大于sort(n)的因子,因为因数成对出现,所以可以直接用口除以其中一个约数等于另外一个约数。也就是n/fac[k]

完善程序2

(2)(洪水填充)现有用字符标记像素颜色的8×8图像。颜色填充的操作描述如下:给定起始像素的位置和待填充的颜色,将起始像素和所有可达的像素(可达的定义:经过一次或多次的向上、下、左、右四个方向移动所能到达且终点和路径上所有像素的颜色 都与起始像素颜色相同),替换为给定的颜色。
试补全程序。
2022 CCF 非专业级别软件能力认证第一轮  (CSP-J1)入门级 C++语言试题

40. (1)处应填( )
A. image[r][c] == prev_color
B. image[r][c] != prev_color
C. image[r][c] == new_color
D. image[r][c] != new_color

答案:A
解析:判断(0)是否不越界且合法。坐标在范围内,颜色等于起点坐标颜色,颜色还没被巷换过条件2的表达为image[r][c]==pre_color

41. (2)处应填( )
A. image[cur.r+1][cur.c] = new_color
B. image[cur.r][cur.c] = new_color
C. image[cur.r][cur.c+1] = new_color
D. image[cur.r][cur.c] = prev_color

答案:B
解析:将起点的颜色替换为新颜色
image[cur.c][cur.c]=new color

42. (3)处应填( )
A. Point(pt.r, pt.c)
B. Point(pt.r, pt.c+1)
C. Point(pt.r+1, pt.c)
D. Point(pt.r+1, pt.c+1)

答案:C
解析:经过方向为上、下、左、右
(r-1,c)、 (r+1,c)、 (r, c-1)、 (r,c+1)
缺了往下方向的。即Point(pt.r+1,pt.c)

43. (4)处应填( )
A. prev_color = image[p.r][p.c]
B. new_color = image[p.r][p.c]
C. image[p.r][p.c] = prev_color
D. image[p.r][p.c] = new_color

答案:D
解析:将符合条件的邻接位置的颜色替换为新颜色
image[p.r][p.c]=new_color

44. (5)处应填( )
A. queue.push(p)
B. queue.push(pt)
C. queue.push(cur)
D. queue.push(Point(ROWS,COLS))

答案:A
解析:下一个位置入队

那年 • 今日
写于2022年9月20日
酸甜苦辣咸,五味调和,共存相生,百味纷呈。

赞助 点赞 0

独元殇, Sirit, UI柒, XI等人对本文发表了9条热情洋溢的评论。
  • 独元殇说道: 2
    这些是报了培训班学的吗?
    1. 老王说道:
      回复 独元殇: 嗯,有老师教,然后在网上看视频。。。
  • Sirit说道: 0
    好多题啊~
    1. 老王说道:
      回复 Sirit: 嗯,12页,不过还好都是选择题和判断题!
  • UI柒说道: 0
    应该问题不大
    1. 老王说道:
      回复 UI柒: 结果出来了,拿了个二等奖,在好多省都可以晋级,不过在广东不行。。。 ::wb:wl::
  • XI说道: 2
    曾经也是学过、考过的,现在居然快不认识了
    1. 老王说道:
      回复 XI: 这么牛叉 👍👍👍
      1. XI说道: 2
        回复 老王: N年前的事了
  • 发表回复

    您的电子邮箱地址不会被公开。 必填项已用*标注