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

（CSP-J1）入门级 C++语言试题

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

考生注意事项：

 试题纸共有 12页，答题纸共有 1页，满分 100分。请在答题纸上作答，写在试题纸上的

一律无效。

 不得使用任何电子设备（如计算器、手机、电子词典等）或查阅任何书籍资料。

一、单项选择题（共 15题，每题 2分，共计 30分；每题有且仅有一个正确选项）

1. 以下哪种功能没有涉及 C++语言的面向对象特性支持：（）。

A. C++中调用 printf函数（printf 为C语言的输出语句）

B. C++中调用用户定义的类成员函数

C. C++中构造一个 class或 struct

D. 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 ： 进栈：6 5 4 3；出栈 3 4；错误5没有出栈，6不能出栈

D. 2 3 4 1 5 6

3. 运行以下代码片段的行为是（ ）。

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的地址：p和q都存储了y的地址，都指向y

4. 链表和数组的区别包括（ ）。

A. 数组不能排序，链表可以

B. 链表比数组能存储更多的信息

C. 数组大小固定，链表大小可动态调整：链表和数组都能排序，都能存储很多数据

D. 以上均正确

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：模拟一下：e1进栈(1)、e2进栈(2)、e2出栈(1)、e3进栈(2)、e4进栈(3)、e4出栈(2)、e3出栈(1)、e5进栈(2)、e6进栈(3)、e6出栈(2)、e5出栈(1)、e1出栈(0)，因此栈S的容量至少为3

C. 4

D. 6

6. 对表达式 a+(b-c)*d的前缀表达式为（ ），其中+、-、*是运算符。

A. *+a-bcd

B. +a*-bcd：加括号法：(a+( (b-c)*d) )  -bc;  *-bcd;  +a*-bcd

C. abc-d*+

D. abc-+d

7. 假设字母表 {a, b, c, d, e} 在字符串出现的频率分别为 10%, 15%, 30%, 16%,

29%。若使用哈夫曼编码方式对字母进行不定长的二进制编码，字母 d的编码长度为

（ ）位。

A. 1

B. 2 ：按"哈夫曼编码"规则模拟,每次都选两个最小的合并,最后构建了一颗二叉树(哈夫曼树、最优二叉树),节点到根的边数就是编码位数

C. 2或 3

D. 3

8. 一棵有 n个结点的完全二叉树用数组进行存储与表示，已知根结点存储在数组的第 1个位

置。若存储在数组第 9个位置的结点存在兄弟结点和两个子结点，则它的兄弟结点和右子

结点的位置分别是（ ）。

A. 8、18

B. 10、18

C. 8、19：9 的父节点是4,兄弟是8,右儿子是19

D. 10、19

9. 考虑由 N个顶点构成的有向连通图，采用邻接矩阵的数据结构表示时，该矩阵中至少存在

（ ）个非零元素。

A. N-1

B. N 考察选手对连通图的理解，连通图需要保证所有节点被链接，无向连通图n个节点至少需要n-1条边，因为题目说的是有向图，无反向边，所以邻接矩阵中至少有n个节点不是0。n个点有向连通图，至少有n条边，连成一圈，邻接矩阵中非零元素即为边数最少为n。

C. N+1

D. N2

10.以下对数据结构的表述不恰当的一项为：（ ）。

A. 图的深度优先遍历算法常使用的数据结构为栈。

B. 栈的访问原则为后进先出，队列的访问原则是先进先出。

C. 队列常常被用于广度优先搜索算法。

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;

画图模拟就行

12.以下排序算法的常见实现中，哪个选项的说法是错误的：（ ）。

A. 冒泡排序算法是稳定的

B. 简单选择排序是稳定的：常见排序中，稳定排序有冒泡排序、插入排序、归并排序、堆排序，不稳定排序有：快速排序、选择排序

C. 简单插入排序是稳定的

D. 归并排序算法是稳定的

13.八进制数 32.1对应的十进制数是（ ）。

A. 24.125

B. 24.250

C. 26.125  按权展开，3×8 + 2×1 + 1×1/8 = 26.125

D. 26.250

14.一个字符串中任意个连续的字符组成的子序列称为该字符串的子串，则字符串 abcab有

（ ）个内容互不相同的子串。

A. 12

B. 13：手动模拟各个长度下的子串数量,注意空串 和自己也是子串。子串有：空串a ab abe abca abcab b be bca bcab c ca   cab 共12个

C. 14

D. 15

15.以下对递归方法的描述中，正确的是：（ ）

A. 递归是允许使用多组参数调用函数的编程技术

B. 递归是通过调用自身来求解问题的编程技术：递归参数数量随意;调用自身;面向功能和 逻辑;不是编译;

C. 递归是面向对象和数据而不是功能和逻辑的编程语言模型

D. 递归是将用某种高级语言转换为机器代码的编程技术

二、阅读程序（程序输入不超过数组或字符串定义的范围；判断题正确填√，错误填×；除特

殊说明外，判断题 1.5分，选择题 3分，共计 40分）

(1)

#include <iostream>

using namespace std;

int main()
{
    unsigned short x, y;
    cin >> x >> y;
    x = (x | x << 2) &   0x33;
    x = (x | x << 1) &   0x55;
    y = (y | y << 2) &   0x33;
    y = (y | y << 1) &   0x55;
    unsigned short z = x | y <<   1;
    cout   << z << endl;
    return   0;
}

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

 判断题

16. 删去第 7行与第 13行的 unsigned，程序行为不变。（对）unsigned删除相当于少一位,最大的数字是 0x55=01010101B,不需要最高位。

17. 将第 7行与第 13行的 short均改为 char，程序行为不变。（错）输入2位数就错了,字符只能存一位

18. 程序总是输出一个整数“0”。（错 ）输入2 2结果12

19. 当输入为“2 2”时，输出为“10”。 （错 ）

20. 当输入为“2 2”时，输出为“59”。 （错 ）

 单选题

位运算模拟自己代入计算：先计算<运算符，然后计算|运算，最后在和后面的16进制数相&

21. 当输入为“13 8”时，输出为（ ）。

A. “0”

B. “209”

C. “197”

D. “226”

（2）

#include <algorithm>
#include <iostream>
#include <limits>

using namespace std;

const int MAXN = 105;
const int MAXK = 105;

int h[MAXN][MAXK];

int f(int n, int m)
{
  if (m == 1) return n;
  if (n == 0) return 0;
  
  int ret = numeric_limits<int>::max();
  for (int i = 1; i <= n; i++)
  	ret = min(ret, max(f(n - i, m), f(i - 1, m - 1)) + 1);
  return ret;
}

 int g(int n, int m)
 {
  for (int i = 1; i <= n; i++)
  	h[i][1] = i;
  for (int j = 1; j <= m; j++)
  	h[0][j] = 0;
   
  for (int i = 1; i <= n; i++) {
  	for (int j = 2; j <= m; j++) {
  		h[i][j] = numeric_limits<int>::max();
  		for (int k = 1; k <= i; k++)
  			h[i][j] = min(
  			h[i][j],
  			max(h[i - k][j], h[k - 1][j - 1]) + 1);
  	}
  }
   
  return h[n][m];
}

int main()
{
  int n, m;
  cin >> n >> m;
  cout << f(n, m) << endl << g(n, m) << endl;
  return 0;
}

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

 判断题

22.当输入为“7 3”时，第 19行用来取最小值的 min函数执行了 449次。（错）执行448次,递归模拟

23.输出的两行整数总是相同的（ 对）2 个函数在做一道题，f函数和g函数本质其实是一样的，只是一个通过递归实现，另一个通过循环实现。

24.当 m为 1时，输出的第一行总为 n。（ 对）14 行f(m == 1) return n;

 单选题

25.算法 g(n,m)最为准确的时间复杂度分析结果为（ C）。

30和33行的循环在排序中常见就是n^2, 加上31行m的循环就是0(m*n^2)

26.当输入为“20 2”时，输出的第一行为（ C）。代入f函数模拟

A. “4”

B. “5”

C. “6”

D. “20”

27.（4分）当输入为“100 100”时，输出的第一行为（ B）。代入g函数模拟

A. “6”

B. “7”

C. “8”

D. “9”

（3）

#include <iostream>

using namespace std;

int n, k;

int solve1()
{
  int l = 0, r = n;
  while (l <= r) {
    int mid = (l + r) / 2;
    if (mid * mid <= n) l = mid + 1;
    else r = mid - 1;
	}
	return l - 1;
}

double solve2(double x)
{
  if (x == 0) return x;
  for (int i = 0; i < k; i++)
  x = (x + n / x) / 2;
  return x;
}

int main()
{
  cin >> n >> k;
  double ans = solve2(solve1());
  cout << ans << ' ' << (ans * ans == n) << endl;
  return 0;
}

假设 int为 32位有符号整数类型，输入的 n是不超过 47000的自然数、k是不超过 int

表示范围的自然数，完成下面的判断题和单选题：

 判断题

28.该算法最准确的时间复杂度分析结果为 (log +  )。（对 ）solve是二分logn,solve循环是k,他们都 只调用一次所以是logn +k

29.当输入为“9801 1”时，输出的第一个数为“99”。 （对 ）本题求的是sqrt (n),k表示精确的位数, 所以sqrt (9801)=99

30.对于任意输入的 n，随着所输入 k的增大，输出的第二个数会变成“1”。（ 错）只要不能开除平方根就是0,sqrt(2),就是 无限小数 之 2

31.该程序有存在缺陷。当输入的 n过大时，第 12行的乘法有可能溢出，因此应当将

mid强制转换为 64位整数再计算。（ 错）不会溢出,47000*47000会溢出,但他乘的 是mid,mid只有n的一半并且只会往前找

 单选题

32.当输入为“2 1”时，输出的第一个数最接近（C）。sqrt(2)=1.414.. ,但k=1,所以1.5

A. 1

B. 1.414

C. 1.5

D. 2

33.当输入为“3 10”时，输出的第一个数最接近（B ）。sqrt(3)=1.732..

A. 1.7

B. 1.732

C. 1.75

D. 2

34.当输入为“256 11”时，输出的第一个数（ A）。sqrt(256)=16

A. 等于 16

B.接近但小于 16

C. 接近但大于 16

D.前三种情况都有可能

三、完善程序（单选题，每小题 3分，共计 30分）

（1）（枚举因数）从小到大打印正整数 n的所有正因数。

试补全枚举程序。

#include <bits/stdc++.h> 
using namespace std; 

int main() {   
  int n;   
  cin >> n;   
  
  vector<int> fac;   
  fac.reserve((int)ceil(sqrt(n)));   
  
  int i;   
  for (i = 1; i * i < n; ++i) {     
    if (①) {      
      fac.push_back(i);     
    }   
  } 
  
  for (int k = 0; k < fac.size(); ++k) {    
    cout << ② << " ";   
  }  
  if (③) {    
    cout << ④ << " ";   
  }   
  for (int k = fac.size() - 1; k >= 0; --k) {   
    cout   << ⑤ <<   " ";   
  } 
}

整体代码分析：从小到大输出n的所有约数，被分成了小于根号n的部分和大于根号n的两部分，对于完全平方数进行了一个特判。

35.①处应填（A ）求因子：当能够被i整除时候，表示i是一个约数，加入数组fac中

A. n % i == 0

B. n % i == 1

C. n % (i-1) == 0

D. n % (i-1) == 1

36.②处应填（ B）从1到根号n之内的约数先输出，输出小于sqrt(n)的因子,fac[k]

A. n / fac[k]

C. fac[k]-1

B. fac[k]

D. n / (fac[k]-1)

37.③处应填（C ）判断特殊情况i*i==n

A. (i-1) * (i-1) == n

C. i * i == n

B. (i-1) * i == n

D. i * (i-1) == n

38.④处应填（ D）输出特殊情况i，输出完全平方数的约数根号n,即i

A. n-i

B. n-i+1

D. i

C. i-1

39.⑤处应填（ A）从后往前得到之前的约数，用n/fac[k]获取对称的约数。因为约数都是成对出现的。输出大于sqrt(n)的因子,n/fac[k]

A. n / fac[k]

C. fac[k]-1

B. fac[k]

D. n / (fac[k]-1)

（2）（洪水填充）现有用字符标记像素颜色的 8x8图像。颜色填充的操作描述如下：给

定起始像素的位置和待填充的颜色，将起始像素和所有可达的像素（可达的定义：经过

一次或多次的向上、下、左、右四个方向移动所能到达且终点和路径上所有像素的颜色

都与起始像素颜色相同），替换为给定的颜色。

试补全程序。

#include <bits/stdc++.h>
 using namespace std;

const int ROWS = 8;
const int COLS = 8;

struct Point {
int r, c;
Point(int r, int c) : r(r), c(c) {}
};

bool is_valid(char   image[ROWS][COLS], Point pt,
  int prev_color, int new_color) {
  int r = pt.r;
  int c = pt.c;
	return (0 <= r && r < ROWS && 0 <= c   && c < COLS &&
	① && image[r][c] !=   new_color);
}

void flood_fill(char   image[ROWS][COLS], Point cur, int new_color) {
  queue<Point> queue;
  queue.push(cur);
  
  int prev_color = image[cur.r][cur.c];
  ②;
  
  while (!queue.empty()) {
    Point pt = queue.front();
    queue.pop();
    
    Point points[4] = {③, Point(pt.r - 1, pt.c),
    					Point(pt.r, pt.c + 1), Point(pt.r, pt.c - 1)};
    for (auto p : points) {
      if (is_valid(image, p,   prev_color, new_color)) {
      ④;
      ⑤;
      }
    }
  }
}

int main() {
  char image[ROWS][COLS] = {{'g', 'g', 'g', 'g', 'g', 'g', 'g', 'g'},
  {'g', 'g', 'g', 'g', 'g', 'g', 'r', 'r'},
  {'g', 'r', 'r', 'g', 'g', 'r', 'g', 'g'},
  {'g', 'b', 'b', 'b', 'b', 'r', 'g', 'r'},
  {'g', 'g', 'g', 'b', 'b', 'r', 'g', 'r'},
  {'g', 'g', 'g', 'b', 'b', 'b', 'b', 'r'},
  {'g', 'g', 'g', 'g', 'g', 'b', 'g', 'g'},
  {'g', 'g', 'g', 'g', 'g', 'b', 'b', 'g'}};
  
  Point cur(4, 4);
  char new_color = 'y';
  
  flood_fill(image, cur, new_color);
  
  for (int r = 0; r < ROWS; r++) {
  	for (int c = 0; c < COLS; c++)   {
  		cout << image[r][c]   << " ";
	}
	cout << endl;
   }
  // 输出：
  // g g g g g g g g
  // g g g g g g r r
  // g r r g g r g g
  // g y y y y r g r
  // g g g y y r g r
  // g g g y y y y r
  // g g g g g y g g
  // g g g g g y y g
  
  return 0;
}

40.①处应填（ A）判断r c位置的颜色为需变更颜色才可以被替换

A. image[r][c] == prev_color

B. image[r][c] != prev_color

C. image[r][c] == new_color

D. image[r][c] != new_color

41.②处应填（B）广搜起点位置直接改为目标字符，此时需要将当前位置修改成新的颜色

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

42.③处应填（ C）四个方向,这里少了一个向"下&#​34;的方向

A. Point(pt.r, pt.c)

C. Point(pt.r+1, pt.c)

B. Point(pt.r, pt.c+1)

D. Point(pt.r+1, pt.c+1)

43.④处应填（ D）与41类似，找到了挨着的相同的字符,改为目标字符

A. prev_color = image[p.r][p.c]

C. image[p.r][p.c] = prev_color

B. new_color = image[p.r][p.c]

D. image[p.r][p.c] = new_color

44.⑤处应填（ A）广搜逻辑, 根据队列的类型，需要加入的是一个Point 类型，is_valid 判断这个点合法，那么当然需要加入队列，下一个位置入队。

A. queue.push(p)

B. queue.push(pt)

C. queue.push(cur)

D. queue.push(Point(ROWS,COLS))