扫码填写或分享
登录后保存考试记录立即登录
0%
2022 CCF 非专业级别软件能力认证第一轮
（CSP-J1）入门级 C++语言试题
一、单项选择题(共15题，每题 2 分，共计 30 分；每题有且仅有一个正确选项)
*
您的姓名是？
*
1 以下哪种功能没有涉及 C++语言的面向对象特性支持：（ ）。
*
2 有 6 个元素，按照 6、5、4、3、2、1 的顺序进入栈 S，请问下列哪个出栈序列是非法的（ ）。
*
3运行以下代码片段的行为是（ ）。
int x = 101; int y = 201; int *p = &x; int *q = &y; p = q;
*
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 的容量至少是（ ）个数据。
*
6 对表达式 a+(b-c)*d 的前缀表达式为（ ），其中+、-、*是运算符。
*
7 假设字母表 {a, b, c, d, e} 在字符串出现的频率分别为 10%，15%，30%，16%，29%。若使用哈夫曼编码方式对字母进行不定长的二进制编码，字母 d 的编码长度为（ ）位。
*
8 一棵有 n 个结点的完全二叉树用数组进行存储与表示，已知根结点存储在数组的第 1 个位置。若存储在数组第 9 个位置的结点存在兄弟结点和两个子结点，则它的兄弟结点和右子结点的位置分别是（ ）。
*
9 考虑由 N 个顶点构成的有向连通图，采用邻接矩阵的数据结构表示时，该矩阵中至少存在（ ）个非零元素。
*
10 以下对数据结构的表述不恰当的一项为：（ ）。
*
11 以下哪组操作能完成在双向循环链表结点 p 之后插入结点 s 的效果（其中，next 域为结点的直接后继，prev 域为结点的直接前驱）：（ ）。
*
12 以下排序算法的常见实现中，哪个选项的说法是错误的：（ ）。
*
13 八进制数32.1对应的十进制数是（ ）。
*
14 一个字符串中任意个连续的字符组成的子序列称为该字符串的子串，则字符串abcab有（ ）个内容互不相同的子串。
*
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，程序行为不变。（ ）
*
17 将第 7 行与第 13 行的 short 均改为 char，程序行为不变。（ ）
*
18 程序总是输出一个整数 "0"。（ ）
*
19 当输入为 "2 2" 时，输出为 "10"。（ ）
*
20 当输入为 "2 2" 时，输出为 "59"。（ ）
*
21 当输入为 "13 8" 时，输出为 （ ）。
01. #include <iostream>
02. #include <algorithm>
03. #include <limits>
04.
05. using namespace std;
06.
07. const int MAXN = 105;
08. const int MANK = 105;
09.
10. int h[MAXN][MANK];
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. int main()
43. {
44. int n, m;
45. cin>>n>>m;
46. cout<<f(n, m)<<endl<<g(n, m)<<endl;
47. return 0;
48. }
*
22 当输入为"7 3"时，第19行用来取最小值的min函数执行了449次。（ ）
*
23 输出的两行整数总是相同的。（ ）
*
24 当m为1时，输出的第一行总为n。（ ）
*
25 算法g(n,m)最为准确的时间复杂度分析结果为（ ）。
*
26 当输入为"20 2"时，输出的第一行为（ ）。
*
27 （4分）当输入为"100 100"时，输出的第一行为（ ）。
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. }
*
28 该算法最准确的时间复杂度分析结果为 \( O(\log n + k) \)。（ ）
*
29 当输入为 "9801 1" 时，输出的第一个数为 "99"。（ ）
*
30 对于任意输入的 n，随着所输入 k 的增大，输出的第二个数会变成 "1"。（ ）
*
31 该程序存在缺陷。当输入的 n 过大时，第 12 行的乘法有可能溢出，因此应当将 mid 强制转换为 64 位整数再计算。（ ）
*
32 当输入为 "2 1" 时，输出的第一个数接近（ ）。
*
33 当输入为 "3 10" 时，输出的第一个数接近（ ）。
*
34 当输入为 "256 11" 时，输出的第一个数（ ）。
三、完善程序（单选题，每小题3分，共计30分）
（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;
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①处应填（ ）
*
36②处应填（ ）
*
37③处应填（ ）
*
38④处应填（ ）
*
39⑤处应填（ ）
（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] = {
44. {'g', 'g', 'g', 'g', 'g', 'g', 'g', 'g'},
45. {'g', 'g', 'g', 'g', 'g', 'g', 'r', 'r'},
46. {'g', 'r', 'r', 'g', 'g', 'r', 'g', 'g'},
47. {'g', 'b', 'b', 'b', 'b', 'r', 'g', 'r'},
48. {'g', 'g', 'g', 'b', 'b', 'r', 'g', 'r'},
49. {'g', 'g', 'g', 'b', 'b', 'b', 'b', 'r'},
50. {'g', 'g', 'g', 'g', 'g', 'b', 'g', 'g'},
51. {'g', 'g', 'g', 'g', 'g', 'b', 'b', 'g'}};
52.
53. Point cur(4, 4);
54. char new_color = 'y';
55.
56. flood_fill(image, cur, new_color);
57.
58. for (int r = 0; r < ROWS; r++) {
59. for (int c = 0; c < COLS; c++) {
60. cout << image[r][c] << " ";
61. }
62. cout << endl;
63. }
64. // 输出：
65. // g g g g g g g g
66. // g g g g g g r r
67. // g r r g g r g g
68. // g y y y y r g r
69. // g g g y y r g r
70. // g g g y y y y r
71. // g g g g g y g g
72. // g g g g g y y g
73.
74. return 0;
75. }
试补全程序。
*
40⑤处应填（ ）
*
41②处应填（ ）
*
42③处应填（ ）
*
43④处应填（ ）
*
44⑤处应填（ ）
隐私政策
龙艺秀提供技术支持举报
答题卡
已答0未答51
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44