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

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

• C++中调用 printf 函数
• C++中调用用户定义的类成员函数
• C++中构造一个 class 或 struct
• C++中构造来源于同一基类的多个派生类

2. 有 6 个元素，按照 6、5、4、3、2、1 的顺序进入栈 S，请问下列哪个出栈序列是非法的 （ ）。 {{ select(2) }}

• 5 4 3 6 1 2
• 4 5 3 1 2 6
• 3 4 6 5 2 1
• 2 3 4 1 5 6

3. 运行以下代码片段的行为是（ ）。 int x = 101; int y = 201; int *p = &x; int *q = &y; p = q; {{ select(3) }}

• 将 x 的值赋为 201
• 将 y 的值赋为 102
• 将 q 指向 x 的地址
• 将 p 指向 y 的地址

4. 链表和数组的区别包括（ ）。 {{ select(4) }}

• 数组不能排序，链表可以
• 链表比数组能存储更多的信息
• 数组大小固定，链表大小可动态调整
• 以上均正确

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

   {{ select(5) }}

• 2
• 3
• 4
• 6

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

• *+a-bcd
• +a*-bcd
• abc-d*+
• abc-+d

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

• 1
• 2
• 2 或 3
• 3

8. 一棵有 n 个结点的完全二叉树用数组进行存储与表示，已知根结点存储在数组的第 1 个位 置。若存储在数组第 9 个位置的结点存在兄弟结点和两个子结点，则它的兄弟结点和右子 结点的位置分别是（ ）。 {{ select(8) }}

• 8、18
• 10、18
• 8、19
• 10、19

9. 考虑由 N 个顶点构成的有向连通图，采用邻接矩阵的数据结构表示时，该矩阵中至少存在 （ ）个非零元素。{{ select(9) }}

• N-1
• N
• N+1
• N 2

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

• 图的深度优先遍历算法常使用的数据结构为栈。
• 栈的访问原则为后进先出，队列的访问原则是先进先出。
• 队列常常被用于广度优先搜索算法。
• 栈与队列存在本质不同，无法用栈实现队列。

11. 以下哪组操作能完成在双向循环链表结点 p 之后插入结点 s 的效果（其中，next 域为结 点的直接后继，prev 域为结点的直接前驱）：（ ）。 {{ select(11) }}

• p->next->prev=s; s->prev=p; p->next=s; s->next=p->next;
• p->next->prev=s; p->next=s; s->prev=p; s->next=p->next;
• s->prev=p; s->next=p->next; p->next=s; p->next->prev=s;
• s->next=p->next; p->next->prev=s; s->prev=p; p->next=s;

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

• 冒泡排序算法是稳定的
• 简单选择排序是稳定的
• 简单插入排序是稳定的
• 归并排序算法是稳定的

13. 八进制数 32.1 对应的十进制数是（ ）。 {{ select(13) }}

• 24.125
• 24.250
• 26.125
• 26.250

14. 一个字符串中任意个连续的字符组成的子序列称为该字符串的子串，则字符串 abcab 有 （ ）个内容互不相同的子串。{{ select(14) }}

• 12
• 13
• 14
• 15

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

• 递归是允许使用多组参数调用函数的编程技术
• 递归是通过调用自身来求解问题的编程技术
• 递归是面向对象和数据而不是功能和逻辑的编程语言模型
• 递归是将用某种高级语言转换为机器代码的编程技术 二、阅读程序（程序输入不超过数组或字符串定义的范围；判断题正确填√ ，错误填× ；除特 殊说明外，判断题 1.5 分，选择题 3 分，共计 40 分） (1) 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) & 0x33; 10 x = (x | x<<1) & 0x55; 11 y = (y | y<<2) & 0x33; 12 y = (y | y<<1) & 0x55; 13 unsigned short z = x | y << 1; 14 cout<<z<<endl; 15 return 0; 16 } 假设输入的 x 、y 均 是不超过 15 的 自然数 ，完成下面的判断题和单选题 ：  判断题

16. 删去第 7 行与第 13 行的 unsigned，程序行为不变。（ ）{{ select(16) }}
17. 将第 7 行与第 13 行的 short 均改为 char，程序行为不变。（ ）{{ select(17) }}
18. 程序总是输出一个整数“0”。（ ）{{ select(18) }}
19. 当输入为“2 2”时，输出为“10”。（ ）{{ select(19) }}
20. 当输入为“2 2”时，输出为“59”。（ ）{{ select(20) }}  单选题
21. 当输入为“13 8”时，输出为（ ）。 {{ select(21) }}

• “ 0 ” - “ 209 ” - “ 197 ” - “ 226 ” （2） 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<int>::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 (int 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 次。（ ）{{ select(22) }}
23. 输出的两行整数总是相同的。（ ）{{ select(23) }}
24. 当 m 为 1 时，输出的第一行总为 n。（ ）{{ select(24) }}  单选题
25. 算法 g(n,m)最为准确的时间复杂度分析结果为（ ）。 {{ select(25) }}

• 𝑂𝑂(𝑛𝑛 3/2 𝑚𝑚)
• 𝑂𝑂(𝑛𝑛𝑚𝑚) - 𝑂𝑂(𝑛𝑛 2 𝑚𝑚)
• 𝑂𝑂(𝑛𝑛𝑚𝑚 2 )

26. 当输入为“20 2”时，输出的第一行为（ ）。 {{ select(26) }}

• “4” - “5”
• “6” - “20”

27. （4 分）当输入为“100 100”时，输出的第一行为（ ）。 {{ select(27) }}

• “6”
• “7”
• “8”
• “9” （3） 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() CCF CSP-J 2022 第一轮 C++语言试题 第8页，共12页 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 表示范围的自然数 ，完成下面的判断题和单选题 ：  判断题

28. 该算法最准确的时间复杂度分析结果为𝑂𝑂(log𝑛𝑛 + 𝑘𝑘)。（ ）{{ select(28) }}
29. 当输入为“9801 1”时，输出的第一个数为“99”。（ ）{{ select(29) }}
30. 对于任意输入的 n，随着所输入 k 的增大，输出的第二个数会变成“1”。（ ）{{ select(30) }}
31. 该程序有存在缺陷。当输入的 n 过大时，第 12 行的乘法有可能溢出，因此应当将 mid 强制转换为 64 位整数再计算。（ ）{{ select(31) }}  单选题
32. 当输入为“2 1”时，输出的第一个数最接近（ ）。 {{ select(32) }}

• 1 - 1.414 - 1.5 - 2

33. 当输入为“3 10”时，输出的第一个数最接近（ ）。 {{ select(33) }}

• 1.7 - 1.732 - 1.75 - 2

34. 当输入为“256 11”时，输出的第一个数（ ）。 {{ select(34) }}

• 等于 16 - 接近但小于 16
• 接近但大于 16 - 前三种情况都有可能 三、完善程序（ 单选题，每小题 3 分，共计 30 分 ） （1 ） （枚举因数）从小到大打印正整数 n 的所有正因数。 试补全枚举程序。 01 #include <bits/stdc++.h> 02 using namespace std; 03 04 int main() { 05 int n; 06 cin >> n; CCF CSP-J 2022 第一轮 C++语言试题 第9页，共12页 07 08 vector<int> fac; 09 fac.reserve((int)ceil(sqrt(n))); 10 11 int i; 12 for (i = 1; i * i < n; ++i) { 13 if (①) { 14 fac.push_back(i); 15 } 16 } 17 18 for (int k = 0; k < fac.size(); ++k) { 19 cout << ② << " "; 20 } 21 if (③) { 22 cout << ④ << " "; 23 } 24 for (int k = fac.size() - 1; k >= 0; --k) { 25 cout << ⑤ << " "; 26 } 27 }

35. ①处应填（ ）{{ select(35) }}

• n % i == 0
• n % i == 1
• n % (i-1) == 0
• n % (i-1) == 1

36. ②处应填（ ）{{ select(36) }}

• n / fac[k]
• fac[k]
• fac[k]-1
• n / (fac[k]-1)

37. ③处应填（ ）{{ select(37) }}

• (i-1) * (i-1) == n
• (i-1) * i == n
• i * i == n
• i * (i-1) == n

38. ④处应填（ ）{{ select(38) }}

• n-i
• n-i+1
• i-1
• I

39. ⑤处应填（ ）{{ select(39) }}

• n / fac[k]
• fac[k]
• fac[k]-1
• n / (fac[k]-1) （2 ） （洪 水 填充）现有用字符标记像素颜色的 8x8 图像。颜色填充的操作描述如下：给 定起始像素的位置和待填充的颜色，将起始像素和所有可达的像素（可达的定义：经过 一次或多次的向上、下、左、右四个方向移动所能到达且终点和路径上所有像素的颜色 都与起始像素颜色相同），替换为给定的颜色。 试补全程序。 01 #include <bits/stdc++.h> 02 using namespace std; 03 04 const int ROWS = 8; 05 const int COLS = 8; 06 07 struct Point { 08 int r, c; 09 Point(int r, int c) : r(r), c(c) {} 10 }; 11 12 bool is_valid(char image[ROWS][COLS], Point pt, 13 int prev_color, int new_color) { 14 int r = pt.r; 15 int c = pt.c; 16 return (0 <= r && r < ROWS && 0 <= c && c < COLS && 17 ① && image[r][c] != new_color); 18 } 19 20 void flood_fill(char image[ROWS][COLS], Point cur, int new_color) { 21 queue<Point> queue; 22 queue.push(cur); 23 24 int prev_color = image[cur.r][cur.c]; 25 ②; 26 27 while (!queue.empty()) { 28 Point pt = queue.front(); 29 queue.pop(); 30 31 Point points[4] = {③, Point(pt.r - 1, pt.c), 32 Point(pt.r, pt.c + 1), Point(pt.r, pt.c - 1)}; 33 for (auto p : points) { 34 if (is_valid(image, p, prev_color, new_color)) { 35 ④; 36 ⑤; 37 } 38 } 39 } 40 } 41 42 int main() { 43 char image[ROWS][COLS] = {{'g', 'g', 'g', 'g', 'g', 'g', 'g', 'g'}, 44 {'g', 'g', 'g', 'g', 'g', 'g', 'r', 'r'}, 45 {'g', 'r', 'r', 'g', 'g', 'r', 'g', 'g'}, 46 {'g', 'b', 'b', 'b', 'b', 'r', 'g', 'r'}, 47 {'g', 'g', 'g', 'b', 'b', 'r', 'g', 'r'}, 48 {'g', 'g', 'g', 'b', 'b', 'b', 'b', 'r'}, 49 {'g', 'g', 'g', 'g', 'g', 'b', 'g', 'g'}, 50 {'g', 'g', 'g', 'g', 'g', 'b', 'b', 'g'}}; 51 52 Point cur(4, 4); 53 char new_color = 'y'; 54 55 flood_fill(image, cur, new_color); 56 57 for (int r = 0; r < ROWS; r++) { 58 for (int c = 0; c < COLS; c++) { 59 cout << image[r][c] << " "; 60 } 61 cout << endl; 62 } 63 // 输出： 64 // g g g g g g g g 65 // g g g g g g r r 66 // g r r g g r g g 67 // g y y y y r g r 68 // g g g y y r g r 69 // g g g y y y y r 70 // g g g g g y g g 71 // g g g g g y y g 72 73 return 0; 74 }

40. ①处应填（ ）{{ select(40) }}

• image[r][c] == prev_color
• image[r][c] != prev_color
• image[r][c] == new_color
• image[r][c] != new_color

41. ②处应填（ ）{{ select(41) }}

• image[cur.r+1][cur.c] = new_color
• image[cur.r][cur.c] = new_color
• image[cur.r][cur.c+1] = new_color
• image[cur.r][cur.c] = prev_color

42. ③处应填（ ）{{ select(42) }}

• Point(pt.r, pt.c) - Point(pt.r, pt.c+1)
• Point(pt.r+1, pt.c) - Point(pt.r+1, pt.c+1)

43. ④处应填（ ）{{ select(43) }}

• prev_color = image[p.r][p.c] - new_color = image[p.r][p.c]
• image[p.r][p.c] = prev_color - image[p.r][p.c] = new_color

44. ⑤处应填（ ）{{ select(44) }}

• queue.push(p)
• queue.push(pt)
• queue.push(cur)
• queue.push(Point(ROWS,COLS))