# 2023 CCF 非专业级别软件能力认证第一轮（CSP-J）试题
*信奥赛*
2023 CCF 非专业级别软件能力认证第一轮（CSP-J）试题
## 目录
[TOC]
### 一、选择题（共15题，每题2分，共计30分：每题有且有一个正确选项）
#### 1. 在C++中，下面关键字中（ ）用于声明一个变量，其值不能被修改。
A. unsigned
B. const
C. static
D. mutable
#### 2. 八进制数（12345670）8和（07654321）8的和为（ ）。
A. （22222221）8
B. （21111111）8
C. （22111111）8
D. （22222211）8
#### 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
#### 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;
#### 5. 根节点的高度为 1，一棵拥有 2023 个节点的三叉树高度至少为（ ）。
A. 6
B. 7
C. 8
D. 9
#### 6. 小明在某一天中依次有 7 个空闲时间段，他想要选出至少一个空闲时间段来练习唱歌，但他希望任意两个练习的时间段之间都有至少两个空闲的时间段让他休息，则小明一共有（ ）种选择时间段的方案。
A. 31
B. 18
C. 21
D. 33
#### 7. 以下关于高精度运算的说法错误的是（ ）。
A. 高精度计算主要是用来处理大整数或需要保留多位小数的运算
B. 大整数除以小整数的处理的步骤可以是，将被除数和除数对齐，从左到右逐位尝试将除数乘以某个数，通过减法得到新的被除数，并累加商
C. 高精度乘法的运算时间只与参与运算的两个整数中长度较长者的位数有关
D. 高精度加法运算的关键在于逐位相加并处理进位
#### 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
#### 9. 数 101010₂ 和 166₈ 的和为（ ）。
A. 10110000₂
B. 236₈
C. 158₁₀
D. A0₁₆
#### 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. 1010, 1001, 1000, 011, 010, 00
C. 000, 001, 010, 011, 10, 11
D. 1010, 1011, 110, 111, 00, 01
#### 11. 给定一棵二叉树，其前序遍历结果为 ABDECFG，中序遍历结果为 DEBACFG。这棵树的正确后序遍历结果是（ ）。
A. EDBGFCA
B. EDGBFCA
C. DEBGFCA
D. DBEGFCA
#### 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
#### 13. 在计算机中，以下选项中描述的数据存储容量最小的是（ ）。
A. 字节（byte）
B. 比特（bit）
C. 字（word）
D. 千字节（kilobyte）
#### 14. 一个班级有 10 个男生和 12 个女生。如果要选出一个 3 人的小组，并且小组中必须至少包含 1 个女生，那么有（ ）种可能的组合。
A. 1420
B. 1770
C. 1540
D. 2200
#### 15. 以下选项中不是操作系统的是（ ）。
A. Linux
B. Windows
C. Android
D. HTML
### 二、阅读程序（程序输入不超过数组或字符串定义的范围，判断题正确填√，错误填×；除特殊说明外，判断题每题 1.5 分，选择题每题 3 分，共计 40 分）
（一）阅读以下程序，完成相关题目。
```
#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 的正整数，完成下面的判断题和选择题。
#### 判断题
16，（2 分）当输入为“2 2 2”时，输出为“1.7321”。（ √ ）
17，（2 分）将第 7 行中的“(s - b) * (s - c)”改为“(s - c) * (s - b)”不会影响程序运行的结果。（ √ ）
18，（2 分）程序总是输出 4 位小数。（ √ ）
#### 选择题
19，当输入为 “3 4 5” 时，输出为（ ）。
A. “6.0000”
B. “12.0000”
C. “24.0000”
D. “30.0000”
20，当输入为 “5 12 13” 时，输出为（ ）。
A. “24.0000”
B. “30.0000”
C. “60.0000”
D. “120.0000”
### (二) 阅读以下程序，完成相关题目。
```
#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;
}
```
#### 判断题
21， f 函数的返回值小于或等于 min(n,m)。（√）
22， f 函数的返回值等于两个输入字符串的最长公共子串的长度。（x）
23， 当输入两个完全相同的字符串时，g 函数的返回值总是 true。（x）
#### 选择题
24， 将第 19 行中的 “v[m][n]” 替换为 “v[n][m]”，那么该程序（）。
A. 行为不变 B. 只会改变输出 C. 一定非正常退出 D. 可能非正常退出
25， 当输入为 “csp-j p-jcs” 时，输出为（）。
A. “0” B. “1” C. “T” D. “F”
26， 当输入为 “csppsc spsccp” 时，输出为（）。
A. “T” B. “F” C. “0” D. “1”
### (三) 阅读以下程序，完成相关题目。
```
#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 的整数，完成下面的判断题和选择题。
#### 判断题
27，如果输入的 n 为正整数，solve2 函数的作用是计算 n 所有的因子的平方和。
28，第 13 ~ 14 行的作用是避免 n 的平方根因子（或 n/1）进入第 16 行而被计算两次。
29，如果输入的 n 为质数，solve2(n) 的返回值为 n²+1。
#### 选择题
30，(4 分) 如果输入的 n 为质数 p 的平方，那么 solve2(n) 的返回值为（ ）。
A. p² + p + 1
B. n² + n + 1
C. n² + 1
D. p⁴ + 2p² + 1
31，当输入为正整数时，第一项减去第二项的差值一定（ ）。
A. 大于或等于 0
B. 大于或等于 0 且不一定大于 0
C. 小于 0
D. 小于或等于 0 且不一定小于 0
32，当输入为 "5" 时，输出为（ ）。
A. "651 625"
B. "650 729"
C. "651 676"
D. "652 625"
### 三、完善程序（单选题，每小题3分，共30分）
#### (一) 寻找被移除的元素问题
原有长度为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 + (①)) {
②
} else {
③
}
}
return ④
}
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 == ⑤) {
cout << "Sequence is consecutive" << endl;
} else {
cout << "Missing number is " << missing_number << endl;
}
return 0;
}
```
33, ①处应该填（）。
A. 1
B. nums[0]
C. right
D. left
34, ②处应该填（）。
A. left = mid + 1
B. right = mid - 1
C. right = mid
D. left = mid
35, ③处应该填（）。
A. left = mid + 1
B. right = mid - 1
C. right = mid
D. left = mid
36, ④处应该填（）。
A. left + nums[0]
B. right + nums[0]
C. mid + nums[0]
D. right + 1
37, ⑤处应该填（）。
A. nums[0] + n
B. nums[0] + n - 1
C. nums[0] + n + 1
D. nums[n - 1]
#### （二）（编辑距离）给定两个字符串，每次操作可以选择删除（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] = __①__;
else if (j == 0)
dp[i][j] = __②__;
else if (__③__)
dp[i][j] = __④__;
else
dp[i][j] = 1 + min(dp[i][j - 1], dp[i - 1][j], __⑤__);
}
}
return dp[m][n];
}
int main() {
string str1, str2;
cin >> str1 >> str2;
cout << "Minimum number of operations:"
<< edit_dist_dp(str1, str2) << endl;
return 0;
}
```
38. ①处应该填（ ）。
A. j
B. i
C. =
D. ≠
39. ②处应该填（ ）。
A. j
B. i
C. =
D. ≠
40. ③处应该填（ ）。
A. str1[i-1]==str2[j-1]
B. str1[i]==str2[j]
C. str1[i-1]!=str2[j-1]
D. str1[i]!=str2[j]
41. ④处应该填（ ）。
A. dp[i-1][j-1]+1
B. dp[i-1][j-1]
C. dp[i-1][j]
D. dp[i][j-1]
42. ⑤处应该填（ ）。
A. dp[i][j]+1
B. dp[i-1][j-1]+1
C. dp[i-1][j-1]
D. dp[i][j]
------
***操作记录***
作者：[zhao](https://www.lingyuzhao.top//index.html?search=4 "zhao")
操作时间：2025-08-09 13:10:34 星期六 【时区：UTC 8】
事件描述备注：保存/发布
中国 天津市 天津
[](如果不需要此记录可以手动删除，每次保存都会自动的追加记录)
