2022CCF非专业级别软件能力认证第一轮CSP-J初赛试题

2022 CCF非专业级别软件能力认证第 一轮 (CSP-Jl）入门级C＋＋语言试题 认证时间：2022年9月18日09:30～11:3θ 考生注意事项： • 试题纸共有12页， 答题纸共有1页， 满分100分。 请在答题纸上作答， 写在试题纸上的 一律无效。 • 不得使用任何电子设备（如计算器、 于机、 电子词典等）或查阅任何书籍资料。 一 、 单项选择题（共15题， 每题2分， 共计到分：每题有且仅有一个正确选项〉 1. 以下哪种功能没有涉及（＋＋语言的面向对象特性支持：（ ）。 A. C＋＋中调用printf函数 B. C＋＋中调用用户定义的类成员函数 (. （＋＋中构造一个class或struct D. C＋＋中构造来源于同 一基类的多个派生类 2. 有6个元素， 按照6、 5、 4、 3、 2、 1的顺序进入校5， 请问下列哪个出枝序列是非法的 （ ） 。 A. 5 4 3 6 1 2 B. 4 5 3 1 2 6 C. 346521 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 CCF CSP-J 2022 第一轮 C＋＋语言试题 第1页， 共 12页 C. 将q指向x的地址 D. 将p指向y的地址 4. 链表和数组的区别包括（ ）。 A. 数组不能排序， 链表可以 B. 链表比数组能存储更多的信息 C. 数组大小固定， 链表大小可动态调整 D. 以上均正确 5. 对假设枝5和队列Q的初始状态为墅。存在el～e6六个互不相同的数据，每个数据按照进 枝弘出校5、 进队列Q、 出队列Q的顺序操作， 不同数据间的操作可能会交错。 己知枝 s 中依次有数据el、 e2、 e3、 e4、 es和e6进枝， 队列Q依次有数据e2、 e4、 e3、 e6、 es 和el出队列。 则核5的容量至少是（ ）个数据。 A. 2 B. 3 C. 4 D. 6 6. 对表达式a+(b-c)*d的前缀表达式为（ ）， 其中＋、 － 、 ＊是运算符。 A. *+a-bed B. +a*-bcd C. abc-d*+ D. abc-+d 7. 假设字母表｛a, b, c, d, e｝在字符串出现的频率分别为1锁， 15%, 30%, 16%, 29%。 若使用哈夫曼编码方式对字母进行不定长的二进制编码， 字母d的编码长度为（ ）位。 A. 1 B. 2 c. 2或3 CCF CSP-J 2022第一轮C＋＋语言试题 第2页， 共12页 D. 3 8. 一棵有n个结点的完全二叉树用数组进行存储与表示， 己知根结点存储在数组的第1个位 置。 若存储在数组第9个位置的结点存在兄弟结点和两个子结点， 则它的兄弟结点和右子 结点的位置分别是（ 〉。 A. 8、 18 B. 10 、 18 C. 8、 19 D. 10、 19 9. 考虑、由N个顶点构成的有向连通图， 采用邻接矩阵的数据结构表示时， 该矩阵中至少存在 （ ）个非零元素。 A. N-1 B. N C. N+l D. N2 1θ．以下对数据结构的表述不恰当的一项为： （ ）。 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->p俨 ev=s; D. s->next=p->next; p->next->prev=s; s->prev=p; p->next=s; CCF CSP-J 2022第一轮C＋＋语言试题 第3页， 共12页 12.以下排序算法的常见实现中， 哪个选项的说法是错误的： （ ）。 A. 冒泡排序算法是稳定的 B. 简单选择排序是稳定的 C. 简单插入排序是稳定的 D. 归并排序算法是稳定的 13.八进制数32.1对应的十进制数是（ ）。 A. 24.125 B. 24.250 (. 26.125 D. 26.250 14.一个字符串中任意个连续的字符组成的子序列称为该字符串的子串， 则字符串abcab有 （ ）个内容互不相同的子串。 A. 12 B. 13 (. 14 D. 15 15.以下对递归方法的描述中， 正确的是： （ ） A. 递归是允许使用多组参数调用函数的编程技术 B. 递归是通过调用自身来求解问题的编程技术 C. 递归是面向对象和数据而不是功能和逻辑的编程语言模型 D. 递归是将用某种高级语言转换为机器代码的编程技术 二、 阅读程序（程序输入不超过数组或字符串定义的范围；判断题正确填d， 错误填×：除特 殊说明外， 判断题1.5分， 选择题3分， 共计40分） (1) 01 #include <iostream> CCF CSP-J 2022第一轮C＋＋语言试题 第4页， 共12页 02 03 using namespace std; 04 05 int main() 06 { 07 unsigned shor、t x, y; 08 Cln 》 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 shor、t z = X I y 《 1; 14 cout 《 Z 《 endl; 15 return 0; 16} 假设输入的x、 y均是不超过15的自然数， 完成下面的判断题和单选题z • 判断题 16. 删去第7行与第13行的unsigned， 程序行为不变。 （ ） 17. 将第7行与第13行的short均改为char， 程序行为不变。 （ ） 18. 程序总是输出一个整数 “ ＠ ” 。 （ ） 19. 当输入为 “ 2 2 ” 时， 输出为 “ 四 ” 。 （ ） 20. 当输入为 “ 2 2 ” 时， 输出为 “ 四 ” 。 （ ） • 单选题 21. 当输入为 “ 13 8 ” 时， 输出为（ ）。 A. “＠ ” B. “209 (2) 01 #include <algorithm> 02 #include <iostr、earn> 03 #include <limits> 04 05 using namespace std; 06 07 const int MAXN = 105; 08 const int MAXK = 105; 09 C. “197 CCF CSP-J 2022 第一轮 C＋＋语言试题 第5页， 共12页 D. “226 10 int h[MAXN］［问AXK]; 11 12 int f(int n, 13 { 14 int m) r、eturn n; r、eturn 0; (m == 1) (n == 0) if if + 1); 1)) m 1, f(i ret = numeric_limits< int＞：：『nax(); (int i= 1; i <= n; i++) ret = min(ret, max(f(n - i, return ret; ．，、，，，m int for for (int i= 1; h[i][l] = i; for (int j = 1; j h[0][j] = 0; i++) 1 <= n; int m) pn g(int 18 19 20 21} 22 23 int 24 { 25 26 FD FO 寸J 句4 句4 咱4 j++) <= m; 27 28 + 1); 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 - 1]) l][j LK FEE－－』」门k][j], endl; 《、、，，，m g(n, 《 endl 《 return h[n][m]; int n, m; cin 》 n 》 m; cout 《 f(n, m) return 0; 29 、】，，，，．‘、n ． la m＋L n 、bJ － 1· F4L ＠ 1 2 3 4 5 6 7 8 9 ＠ 1 2 3 4 5 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 46 47 48 49 假设输入的n 、 m均是不超过四＠的正整数， 完成下面的判断题和单选题z 判断题 22.当输入为 ＂ 7 3 ” 时， 第19行用来取最小值的min函数执行了449次。 ． CCF CSP-J 2022第一轮C＋＋语言试题 第6页， 共12页 23.输出的两行整数总是相同的。 （ ） 24.当m为1时， 输出的第一行总为n。 （ ） • 单选题 25.算法g(n,m）最为准确的时间复杂度分析结果为（ ）。 A. 0 （η3/Zm) B. 0 〔nm) C. O(n2m) D. O （ηmz ) 26.当输入为 “ 20 2 ” 时， 输出的第 一行为（ ）。 A. “4 ” B. “5 ” C. “6 ” D. “2θ ” 27. (4分）当输入为 “ 四0 100 ” 时， 输出的第 一行为（ ）。 A. “6 ” B. “7 ” (3) θ1 #include < iostream> 02 03 using namespace std; 04 05 int n, k; 06 07 int solvel() 08 { 09 10 11 int 1 = 0， 俨 ＝ n; while (1 ＜＝ 俨）｛ int mid= (1 ＋ 俨） I 2; C. “8 ” 12 if (mid* mid<= n) 1 = mid + 1; 13 else r = mid - 1; 14 15 return 1 - 1; 16} 17 18 double solve2(double x) 19 { 20 if (x == 0) r、eturn x; 21 手0 俨（ inti= 0; i < k; i++) 22 x = (x + n Ix) I 2; 23 return x; 24} 25 26 int main() 27 { 28 cin 》 n 》 k; CCF CSP-J 2022第一轮C＋＋语言试题 第7页， 共12页 D. “ 9 ” 29 double ans = solve2(solvel()); 30 cout 《 ans 《 E E 《（ans * ans == n ）《 endl; 31 return 0; 32} 假设int为32位有符号整数类型， 输入的n是不超过47000的自然数、 k是不超过int 表示范围的自然数， 完成下面的判断题和单选题： • 判断题 28.该算法最准确的时间复杂度分析结果为O(logn ＋的。 （ 〉 29.当输入为 “ 9801 1 ” 时，输出的第一个数为 “ 99 ” 。 （ ） 30.对于任意输入的n，随着所输入k的增大，输出的第二个数会变成 ＂ 1 ” 。 （ ） 31.该程序有存在缺陷。 当输入的n过大 时，第12行的乘法有可能溢出，因此应当将mid 强制转换为64位整数再计算。 （ ） • 单选题 32.当输入为 “ 2 1 ” 时，输出的第一个数最接近（ ）。 A. 1 B. 1.414 C. 1. 5 33.当输入为 ＂ 3四 ” 时，输出的第一个数最接近（ ）。 A. 1.7 B. 1. 732 C. 1. 75 34.当输入为 “256 11 ” 时， 输出的第一个数（ ）。 A. 等于16 B. 接近但小于16 C. 接近但大于 16 D. 前三种情况都有可能 三、 完善程序（单选题， 每小题3分， 共计到分） (1) 〈枚举因数）从小到大打印正整数n的所有正因数。 试补全枚举程序。 01 #include <bits/stdc++.h> 02 using namespace std; 03 04 int main() { 05 int n; 06 cin 》 n; 07 08 vector、＜int> fac; CCF CSP-J 2022第一轮C＋＋语言试题 第8页， 共12页 D. 2 D. 2 09 10 11 12 13 14 15 16 17 18 for (int k = 0; k < fac.size(); ++k) { 19 cout《②《 H II; 20 } 21 if （③）｛ 22 cout《④《 ’ ； 23 } 24 for (int k = fac.size() 25 cout《⑤《 ’ 3 26 } 27} fac.俨eserve((int)ceil(sqrt(n))); int i; for (i = 1; i * i < n; ++i) { if （①）｛ fac.push_back(i); ｝ ｝ --k) {k >= 0; - 1; n % i == 1 n % (i-1) == 1 B. 35.①处应填（） A. n % i == 0 C. n % ( i-1) == 0 fac[k] n I (fac[k]-1) D. B. 36.②处应填（ ） A. n I fac[k] C. fac[k]-1 (i-1) * i == n i * (i-1) == n D. B. 37.③处应填（ ） A. (i-1) * (i-1) == n C. i * i == n 44 ＋ － l nH － 14 D. B. 38.④处应填（ A. n-i (. i-1 fac[k] n I (fac[k]-1) D. B. 39.⑤处应填（ ） A. n I fac[k] C. fac[k]-1 D. (2) （洪水填充）现有用字符标记像素颜色的 8x8 图像。颜色填充的操作描述如下：给 定起始像素的位置和待填充的颜色，将起始像素和所有可达的像素（可达的定义：经过一 次或多次的向上、下、左、右四个方向移动所能到达且终点和路径上所有像素的颜色都与 起始像素颜色相同），替换为给定的颜色。 CCF CSP-J 2022第一轮C＋＋语言试题 第9页， 共12页 试补全程序。 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), c(c) {} 10 } ; 11 12 bool is_valid(char、image[ROWS][COLS], Point pt, 13 int p俨ev_color, int new_color、）｛ 14 int 俨 ＝ pt. r; 15 int C = pt. C j 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_c。lor) { 21 queue<Point> queue; 22 queue. push (cur); 23 24 int p俨ev_colo俨 ＝ image[cur.r][cur.c]; 25 ②； 26 27 while (!queue.empty()) { 28 Point pt = queue.俨ront(); 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 CCF CSP-J 2022 第一轮 C＋＋语言试题 第 10页， 共 12页 42 int main() { 43 char、image[ROWS][COLS] = {{ I g ’ ， ’ g ’ ， 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 ｛ ’ g ’ 3 ’ g ’ 3 ｛ ’ g ’ 3 'r ’ P ｛ ’ g ’ 3 I b I J ｛ ’ g ’ ， ’ g I J ｛ ’ g I J I g I J ｛ ’ g ’ 3 g ｛ ’ g I J g Point cur(4, 4); char new color ＝ ’y I; flood_fill(image, cur, new_color); for (int r ＝ θ；俨＜ ROWS；俨＋＋）｛ for、（int C ＝ θ ； c < COLS; c++) { cout《image［俨］［ c ］《 ” ” ； ｝ cout 《 endl; ／／输出： II g g g g g g g g II g g g g g g r r II g俨俨g g r g g II g y y y y俨g r II g g g y y俨g俨 II g g g y y y y r II g g g g g y g g II g g g g g y y g return 0; 74} 40.①处应填（ A. B. (. D. image［「］［c] prev_color image［俨］［c] != p俨ev_color image[r][c] new color image [ r] [ c] ! = new color 41.②处应填（ ） A. image[cur.r+l][cur.c] = new_color、 B. image[cur.r][cur.c] = new_color C. image[cur.r][cur.c+l] = new_color、 g , ’ g I J Ir I J I b I J I g' J ’ g I J g g CCF CSP-J 2022 第一轮 C＋＋语言试题 第11页， 共 12页 g , I g I J ’ g ’ ， ’ g ’ 3 ’ g I}, g , ’ g ’ 3 ’ g ’ 3 ’ r ’ ， ’ r'}, I g' J ’ g ’ 3 ’ I句 ’ 3 ’ g ’ 3 ’ g ’ ｝， I b I J ’ b ’ 3 ’ I鸣 ’ 3 ’ g ’ 3 ’ r'}, 'b ’ ， ’ b ’ 3 ’ I例 ’ 3 I g ’ ， 'r'}, 'b ’ ， ’ b ’ 3 ’ b ’ 3 I b ’ 3 ’ r ’ ｝， I g' J g ’ b ’ 3 g ’ g ’ ｝， g g ’ b ’ 3 ’ b I J ’ g ’ ｝｝； D. image[cur.r][cur.c] = prev_color 42.③处应填（ ） A. Point(pt.r, pt.c) C. Point(pt.r+l, pt.c) 43.④处应填（ ） A. prev_color = image[p.r][p.c] C. image[p.r][p.c] = prev_color 44.⑤处应填（ ） A. queue.push(p) B. queue.push(pt) C. queue.push(cur) D. queue.push(Point(ROWS,COLS)) B. Point(pt.r, pt.c+l) D. Point(pt.r+l, pt.c+l) B. new_color、 ＝ image[p.r][p.c] D. image[p.r][p.c] = new color CCF CSP-J 2022 第一轮 C＋＋语言试题 第 12页， 共 12页