2023年CSP-J1答案与解析（全站首发(￣_,￣ )）

分数：100

考试时间：120分钟

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

1. 在 C++ 中，下面哪个关键字用于声明一个变量，其值不能被修改？
   A.unsigned
   B.const
   C.static
   D.mutable
   答案：B

2. 八进制数12345670₈和07654321₈的和为（ ）。
   A.22222221₈
   B.21111111₈
   C.22111111₈
   D.22222211₈
   答案：A
   解析：八进制逐位相加，结果为22222221₈。

3. 读下述代码，请问修改data的value成员以存储3.14，正确的方式是（ ）。

   union Data{ int num; float value; char symbol; }; union Data data;

   A.data.value = 3.14;
   B.value.data = 3.14;
   C.data->value = 3.14;
   D.value->data = 3.14;
   答案：A

4. 假设有一个链表的节点定义如下：

   struct Node{ int data; Node* next; };

   现在有一个指向链表头部的指针：Node* head，如果想要在表中插入一个新节点，其成员data的值为42，并使新节点成为链表的第一个节点，下面哪个操作是正确的？
   A.Node* newNode = new Node; newNode->data = 42; newNode->next = head; head = newNode;
   B.Node* newNode = new Node; head->data = 42; newNode->next = head; head = newNode;
   C.Node* newNode = new Node; newNode->data = 42; head->next = newNode;
   D.Node* newNode = new Node; newNode->data = 42; newNode->next = head;
   答案：A

5. 根节点的高度为 1，一棵拥有 2023 个节点的三叉树高度至少为（ ）。
   A.6
   B.7
   C.8
   D.9
   答案：C
   解析：高度为 h 的三叉树最多有 (3^h - 1) / 2 个节点，h=7 时最多 1093 个，不够，所以至少 8。

6. 小明在某一天中依次有七个空闲时间段，他想要选出至少一个空闲时间段来练习唱歌，但他希望任意两个练习的时间段之间都有至少两个空闲时间段让他休息，则小明一共有（ ）种选择时间段的方案。
   A.31
   B.18
   C.21
   D.33
   答案：B

7. 以下关于高精度运算的说法错误的是（ ）。
   A.高精度计算主要是用来处理大整数或需要保留多位小数的运算
   B.大整数除以小整数的处理的步骤可以是，将被除数和除数对齐，从左到右逐位尝试将除数乘以某个数，通过减法得到新的被除数，并累加商
   C.高精度乘法的运算时间只与参与运算的两个整数中长度较长者的位数有关
   D.高精度加法运算的关键在于逐位相加并处理进位
   答案：C

8. 后缀表达式6 2 3 + - 3 8 2 / + * 2 ^ 3 +对应的中缀表达式是（ ）。
   A.((6 - (2 + 3)) * (3 + 8 / 2)) ^ 2 + 3
   B.6 - 2 + 3 * 3 + 8 / 2 ^ 2 + 3
   C.(6 - (2 + 3)) * ((3 + 8 / 2) ^ 2) + 3
   D.6 - ((2 + 3) * (3 + 8 / 2)) ^ 2 + 3
   答案：A

9. 数101010₂和166₈的和为（ ）。
   A.10110000₂
   B.236₈
   C.158₁₀
   D.A0₁₆
   答案：D

10. 假设有一组字符{a, b, c, d, e, f}，对应的频率分别为5%, 9%, 12%, 13%, 16%, 45%。请问以下哪个选项是字符a, b, c, d, e, f分别对应的一组哈夫曼编码？
    A.1111, 1110, 101, 100, 110, 0
    B.1011, 1001, 1000, 011, 010, 100
    C.000, 001, 010, 011, 10, 11
    D.1010, 1011, 110, 111, 00, 01
    答案：A

11. 给定一棵二叉树，其前序遍历结果为：ABCDEFG，中序遍历结果为：DEBACFG。请问这棵树的后序遍历结果是什么？
    A.EDBFGCA
    B.EDBGCFA
    C.DEBGFCA
    D.DBEGFCA
    答案：C

12. 考虑一个有向无环图，该图包含 4 条有向边：(1, 2), (1, 3), (2, 4), (3, 4)。以下哪个选项是这个有向无环图的一个有效的拓扑排序？
    A.4, 2, 3, 1
    B.1, 2, 3, 4
    C.1, 2, 4, 3
    D.2, 1, 3, 4
    答案：B

13. 在计算机中，以下哪个选项描述的数据存储容量最小？
    A.字节（byte）
    B.比特（bit）
    C.字（word）
    D.千字节（kilobyte）
    答案：B

14. 一个班级有 10 个男生和 12 个女生。如果要选出一个 3 人的小组，并且小组中必须至少包含 1 个女生，那么有多少种可能的组合？
    A.1420
    B.1770
    C.1540
    D.2200
    答案：A

15. 以下哪个不是操作系统？
    A.Linux
    B.Windows
    C.Android
    D.HTML
    答案：D

    二、阅读程序

    程序一

    #include<iostream> #include<cmath> using namespace std; double f(double a, double b, double c) { double s = (a + b + c) / 2; return sqrt(s * (s - a) * (s - b) * (s - c)); } int main() { cout.flags(ios::fixed); cout.precision(4); int a, b, c; cin >> a >> b >> c; cout << f(a, b, c) << endl; return 0; }

假设输入的所有数都为不超过 1000 的正整数，完成下面的判断题和单选题。

判断题

1. 当输入为2 2 2时，输出为1.7321。
   答案：√

2. 将第 7 行中的(s-b)*(s-c)改为(s-c)*(s-b)不会影响程序运行的结果。
   答案：√
   解析：乘法交换律，结果不变。

3. 程序总是输出四位小数。
   答案：√
   解析：ios::fixed配合precision(4)固定输出 4 位小数。

单选题

1. 当输入为3 4 5时，输出为（ ）。
   A.6.0000
   B.12.0000
   C.24.0000
   D.30.0000
   答案：A

2. 当输入为5 12 13时，输出为（ ）。
   A.24.0000
   B.30.0000
   C.60.0000
   D.120.0000
   答案：B

程序二

cpp

#include<iostream> #include<vector> #include<algorithm> using namespace std; int f(string x, string y) { int m = x.size(); int n = y.size(); vector<vector<int>> v(m + 1, vector<int>(n + 1, 0)); for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { if (x[i - 1] == y[j - 1]) { v[i][j] = v[i - 1][j - 1] + 1; } else { v[i][j] = max(v[i - 1][j], v[i][j - 1]); } } } return v[m][n]; } bool g(string x, string y) { if (x.size() != y.size()) { return false; } return f(x + x, y) == y.size(); } int main() { string x, y; cin >> x >> y; cout << g(x, y) << endl; return 0; }

判断题

1. f函数的返回值小于等于min(n, m)。
   答案：√

2. f函数的返回值等于两个输入字符串的最长公共子串的长度。
   答案：×
   解析：返回的是最长公共子序列的长度，不是子串。

3. 当输入两个完全相同的字符串时，g函数的返回值总是true。
   答案：√

单选题

1. 将第 19 行中的v[m][n]替换为v[n][m]，那么该程序（ ）。
   A.行为不变
   B.只会改变输出
   C.一定非正常退出
   D.可能非正常退出
   答案：D
   解析：若m != n，访问v[n][m]可能越界，程序可能崩溃。

2. 当输入为csppsc spsccp时，输出为（ ）。
   A."0"
   B."1"
   C."T"
   D."F"
   答案：B

3. 当输入为csppsc spsccp时，输出为（ ）。
   A."T"
   B."F"
   C."0"
   D."1"
   答案：D

程序三

cpp

#include <iostream> #include <cmath> using namespace std; int solve1(int n) { return n * n; } int solve2(int n) { int sum = 0; for (int i = 1; i <= sqrt(n); i++) { if (n % i == 0) { if (n / i == i) { sum += i * i; } else { sum += i * i + (n / i) * (n / i); } } } return sum; } int main() { int n; cin >> n; cout << solve2(solve1(n)) << " " << solve1(solve2(n)) << endl; return 0; }

假设输入的n是绝对值不超过 1000 的整数，完成下面的判断题和单选题。

判断题

1. 如果输入的n为正整数，solve2函数的作用是计算n所有的因子的平方和。
   答案：√

2. 第 13~14 行的作用是避免n的平方根因子i（或n/i）进入第 16 行而被计算两次。
   答案：√

3. 如果输入的n为质数，solve2(n)的返回值为n² + 1。
   答案：√

单选题

1. 如果输入的n为质数p的平方，那么solve2(n)的返回值为（ ）。
   A.p² + p + 1
   B.n² + n + 1
   C.n² + 1
   D.p⁴ + 2p² + 1
   答案：B

2. 当输入为正整数时，第一项减去第二项的差值一定（ ）。
   A.大于 0
   B.大于等于 0 且不一定大于 0
   C.小于 0
   D.小于等于 0 且不一定小于 0
   答案：D

3. 当输入为5时，输出为（ ）。
   A."651 625"
   B."650 729"
   C."651 676"
   D."652 625"
   答案：C

三、完善程序

（1）寻找被移除的元素

问题：原有长度为n+1、公差为 1 的等差升序数列，将数列输入到程序的数组时移除了一个元素，导致长度为n的升序数组可能不再连续，除非被移除的是第一个或最后一个元素。需要在数组不连续时，找出被移除的元素。试补全程序。

cpp

#include <iostream> #include <vector> using namespace std; int find_missing(vector<int>& nums) { int left = 0, right = nums.size() - 1; while (left < right) { int mid = left + (right - left) / 2; if (nums[mid] - mid == nums[0]) { left = mid + 1; } else { right = mid; } } return left + nums[0]; } int main() { int n; cin >> n; vector<int> nums(n); for (int i = 0; i < n; i++) cin >> nums[i]; int missing_number = find_missing(nums); if (missing_number == nums[n - 1]) { cout << "Sequence is consecutive" << endl; } else { cout << "Missing number is " << missing_number << endl; } return 0; }

1. ① 处应填（ ）。
   A.1
   B.nums[0]
   C.right
   D.left
   答案：B

2. ② 处应填（ ）。
   A.left = mid + 1
   B.right = mid - 1
   C.right = mid
   D.left = mid
   答案：A

3. ③ 处应填（ ）。
   A.left = mid + 1
   B.right = mid - 1
   C.right = mid
   D.left = mid
   答案：C

4. ④ 处应填（ ）。
   A.left + nums[0]
   B.right + nums[0]
   C.mid + nums[0]
   D.right + 1
   答案：A

5. ⑤ 处应填（ ）。
   A.nums[0] + n
   B.nums[0] + n - 1
   C.nums[0] + n + 1
   D.nums[n - 1]
   答案：D

（2）编辑距离

给定两个字符串，每次操作可以选择删除（Delete）、插入（Insert）、替换（Replace）一个字符，求将第一个字符串转换为第二个字符串所需要的最少操作次数。

cpp

#include <iostream> #include <string> #include <vector> using namespace std; int min(int x, int y, int z) { return min(min(x, y), z); } int edit_dist_dp(string str1, string str2) { int m = str1.length(); int n = str2.length(); vector<vector<int>> dp(m + 1, vector<int>(n + 1)); for (int i = 0; i <= m; i++) { for (int j = 0; j <= n; j++) { if (i == 0) dp[i][j] = j; else if (j == 0) dp[i][j] = i; else if (str1[i - 1] == str2[j - 1]) dp[i][j] = dp[i - 1][j - 1]; else dp[i][j] = 1 + min(dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1]); } } return dp[m][n]; } int main() { string str1, str2; cin >> str1 >> str2; cout << "Mininum number of operation:" << edit_dist_dp(str1, str2) << endl; return 0;

}

1. ① 处应填（ ）。
   A.j
   B.i
   C.m
   D.n
   答案：A

2. ② 处应填（ ）。
   A.j
   B.i
   C.m
   D.n
   答案：B

3. ③ 处应填（ ）。
   A.str1[i - 1] == str2[j - 1]
   B.str1[i] == str2[j]
   C.str1[i - 1] != str2[j - 1]
   D.str1[i] != str2[j]
   答案：A

4. ④ 处应填（ ）。
   A.dp[i - 1][j - 1] + 1
   B.dp[i - 1][j - 1]
   C.dp[i - 1][j]
   D.dp[i][j - 1]
   答案：B

5. ⑤ 处应填（ ）。
   A.dp[i][j] + 1
   B.dp[i - 1][j - 1] + 1
   C.dp[i - 1][j - 1]
   D.dp[i][j]
   答案：C

参考答案汇总

写完啦，bye！