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 解析：下一个位置入队