2023csp-j真题解析

2023 CCF 非专业级别软件能力认证第一轮
（认证时间：2023年9月16日 09:30~11:30）
一、 单项选择题（共15题，每题2分，共计30分：每题有且仅有一个正确选项）
1. 在C++中，下面哪个关键字用于声明一个变量，其值不能被修改？（ ）。
A. unsigned
B. const
C. static
D. mutable
答案: B
在C++中，关键字const用于声明一个变量，表示其值是常量，不能被修改。一旦用const声明一个变量后，它的值在声明之后就不能再被修改，任何试图修改该变量的操作都会被编译器报错。其中 A 选项为无符号性 B 为定义常亮 (不可修改)C 为静态变量 D 为可修改变量和 const
2. 八进制数123456708 和076543218的和为（ ）。
A. 222222218
B. 211111118
C. 221111118
D. 222222118
答案: D
首先将八进制数转换为十进制数，然后将两个十进制数相加，最后将结果转换回八进制数。
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
Union 为联合体，和 struct 类似，赋值应用.运算符，指针才能用->运算符
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
D 选项没有更新 head 的值，导致没法插入新的数据，BC 选项对 head 的 data 进行修改
5. 根节点的高度为1，一根拥有2023个节点的三叉树高度至少为（ ）。
A. 6
B. 7
C. 8
D. 9
答案: C
满三叉树的节点数为s=(3^n-1)/2,2023 个节点介于 7 层到 8 层之间，所以最少需要 8 层二叉树，所以至少八层
6. 小明在某一天中依次有七个空闲时间段，他想要选出至少一个空闲时间段来练习唱歌，但他希望任意两个练习的时间段之间都有至少两个空闲的时间段让他休息，则小明一共有（ ）种选择时间段的方案。
A. 31
B. 18
C. 21
D. 33
答案: B
只选一个练习时间段的有 7 种,选 2 个练习时间段的有 10 种,选 3 个联系时间段的有 1种,故总数为 18 种
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
根据后缀表达式到中缀表达式的转换规则，我们可以逆序遍历后缀表达式并使用栈来构建中缀表达式。遇到数字时，直接将其入栈；遇到运算符时，从栈中弹出相应数量的操作数，并按照运算符和操作数之间的优先级进行括号添加，然后将结果再次入栈。
对于给定的后缀表达式”6 2 3 + – 3 8 2 / + * 2 ^ 3 +”，我们可以通过上述方法得到中缀表达式为：
((6-(2+3))*(3+(8/2)))^2+3
因此，选项 A. ((6 – (2 + 3)) * (3 + 8 / 2)) ^ 2 + 3 是正确的答案。
9. 数101010(2)和166(8)的和为（ ）。
A. 10110000(2)
B. 236(8)
C. 158(10)
D. A0(16)
答案: D
将二进制数101010(2)转换为十进制得到42，将八进制数166(8)转换为十进制得到118。
将十进制数42和118相加得到160。
现在我们将160转换为十六进制，得到A0(16)。
因此，正确答案是选项 D. A0(16)。
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
答案: A
根据哈夫曼编码的生成过程，我们可以按照如下步骤得到字符a,b,c,d,e,f分别对应的哈夫曼编码：
将所有字符按照出现频率从小到大排序，得到字符序列{a,b,c,d,e,f}。
取出频率最小的两个字符a和b，构建一棵二叉树，并将其根节点的频率设置为a和b的频率之和（即5%+9%=14%）。
将原序列中的a和b删除，并将新生成的节点插入到序列中，得到新的字符序列{c,d,e,f,ab}。
重复步骤2和3，直到得到一棵包含所有字符的二叉树。
对于每条从根节点到叶子节点的路径，用0表示向左走，用1表示向右走，得到对应字符的哈夫曼编码。
按照上述算法，我们可以得到如下结果：
字符
频率
哈夫曼编码

a
5%
1111
b
9%
1110
c
12%
101
d
13%
100
e
16%
110
f
45%
0
因此，正确答案是选项 A. 1111，1110，101，100，110，0。
11. 给定一棵二叉树，其前序遍历结果为：ABDECFG，中序遍历结果为：DEBACFG。请问这棵树的正确后序遍历结果是什么？（ ）
A. EDBFGCA
B. EDBGCFA
C. DEBGFCA
D. DBEGFCA
答案: A
根据前序遍历结果和中序遍历结果重构二叉树的步骤如下：
前序遍历结果的第一个字符为根节点，即A。
在中序遍历结果中找到根节点A，将其左边的字符为左子树的中序遍历结果，右边的字符为右子树的中序遍历结果。根据此规则，我们可以得到左子树的中序遍历结果为DEB，右子树的中序遍历结果为CFG。
根据左子树的中序遍历结果DEB和左子树的前序遍历结果ABD，递归重构左子树。结果如下：
Copy Code
A
/ \
B F
/ \
D E
根据右子树的中序遍历结果CFG和右子树的前序遍历结果CFG，递归重构右子树。结果如下：
Copy Code
G
/ \
C G
将左子树和右子树连接到根节点上，得到整棵树的结构：
Copy Code
A
/ \
B F
/ \
D E
/ \
C G
根据后序遍历的性质，在后序遍历中，左子树先于右子树被访问，根节点最后被访问。因此，这棵树的正确后序遍历结果是EDBFGCA。
因此，正确答案是选项 A. EDBFGCA。
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

拓扑排序是有向无环图中对顶点进行排序的一种方法，使得所有的有向边从排在前面的顶点指向排在后面的顶点。根据提供的有向边 (1,2)，(1,3)，(2,4)，和(3,4)，我们可以确定拓扑排序的正确选项。

根据题目给出的有向边，可以得出以下关系：

– 1 -> 2

– 1 -> 3

– 2 -> 4

– 3 -> 4

根据拓扑排序的定义，我们需要先排列没有前置依赖的顶点。根据上述关系，只有顶点 1 没有前置依赖，所以它必须是拓扑排序的第一个顶点。

接下来，根据关系 (1,2) 和 (1,3)，顶点 2 和 3 是直接依赖于顶点 1 的，它们应该在 1 后面。

最后，根据关系 (2,4) 和 (3,4)，顶点 4 是直接依赖于顶点 2 和 3 的，所以它们也应该在 2 和 3 后面。

综上所述，有效的拓扑排序应该是 B. 1，2，3，4。

13. 在计算机中，以下哪个选项描述的数据存储容量最小？（ ）
A. 字节（byte）
B. 比特（bit）
C. 字（word）
D. 千字节（kilobyte）
答案: B
在计算机中，以下选项描述的数据存储容量最小是B. 比特（bit）。
比特（bit）是计算机中最基本的单位，用来表示二进制数据的单个位，可以取0或1两个值。比特是计算机中最小的存储单位。
字节（byte）是计算机中常用的数据存储单位，它由8个比特组成，可以用来表示一个字符或8个二进制位。字节是相对于比特来说更常用的单位。
字（word）通常指计算机中一个机器字的大小，表示计算机一次能够处理的二进制位数，其大小由机器的架构决定。
千字节（kilobyte）是计算机中常用的数据存储容量单位，等于1024字节，用来表示较小的数据量。
因此，在计算机中，比特是描述数据存储容量最小的单位。
正确答案是B. 比特（bit）。

14. 一个班级有10个男生和12个女生。如果要选出一个3人的小组，并且小组中必须至少包含1个女生，那么有多少种可能的组合？（ ）
A. 1420
B. 1770
C. 1540
D. 2200
答案: A
要选出一个3人的小组，并且小组中必须至少包含1个女生。
我们可以按照以下几种情况进行计算：
情况一：选取1个女生和2个男生。
选择女生的方式有 12 种，选择男生的方式有 C(10,2) = 45 种。
总共的组合方式为 12 * 45 = 540 种。
情况二：选取2个女生和1个男生。
选择女生的方式有 C(12,2) = 66 种，选择男生的方式有 10 种。
总共的组合方式为 66 * 10 = 660 种。
情况三：选取3个女生。
选择女生的方式有 C(12,3) = 220 种。
总共的组合方式为 220 种。
综上所述，总共的可能的组合方式为 540 + 660 + 220 = 1420 种。
因此，正确答案是 A. 1420。
15. 以下哪个不是操作系统？（ ）
A. Linux
B. Windows
C. Android
D. HTML
答案: D
HTML（超文本标记语言）是一种用于创建网页的标记语言，它并不是操作系统。HTML主要用于描述网页的结构和内容，而不是提供操作系统所需的核心功能，如管理资源、调度任务和控制硬件等。

Linux、Windows和Android都是常见的操作系统。Linux是一种开源的操作系统，被广泛应用于服务器和嵌入式设备等领域。Windows是由微软公司开发的操作系统，用于个人电脑和服务器等。Android是由谷歌开发的移动设备操作系统，用于智能手机、平板电脑等移动设备。

因此，D. HTML不是一个操作系统。

二、 阅读程序（程序输入不超过数组成字符串定义的范围：判断题正确填√，错误填×；除特殊说明外，判断题1.5分，选择题3分，共计40分）
(1）
01 #include
02 #include
03 using namespace std;
04
05 double f(double a,double b,double c){
06 double s=(a+b+c)/2;
07 return sqrt(s*(s-a)*(s-b)*(s-c));
08 }
09
10 int main(){
11 cout.flags(ios::fixed);
12 cout.precision(4);
13
14 int a,b,c;
15 cin>>a>>b>>c;
16 cout<
02 #include
03 #include
04 using namespace std;
05
06 int f(string x,string y){
07 int m=x.size();
08 int n=y.size();
09 vector>v(m+1,vector(n+1,0));
10 for(int i=1;i<=m;i++){ 11 for(int j=1;j<=n;j++){ 12 if(x[i-1]==y[j-1]){ 13 v[i][j]=v[i-1][j-1]+1; 14 }else{ 15 v[i][j]=max(v[i-1][j],v[i][j-1]); 16 } 17 } 18 } 19 return v[m][n]; 20 } 21 22 bool g(string x,string y){ 23 if(x.size() != y.size()){ 24 return false; 25 } 26 return f(x+x,y)==y.size(); 27 } 28 29 int main(){ 30 string x,y; 31 cin>>x>>y;
32 cout<
02 #include
03 using namespace std;
04
05 int solve1(int n){
06 return n*n;
07 }
08
09 int solve2(int n){
10 int sum=0;
11 for(int i=1;i<=sqrt(n);i++){ 12 if(n%i==0){ 13 if(n/i==i){ 14 sum+=i*i; 15 }else{ 16 sum+=i*i+(n/i)*(n/i); 17 } 18 } 19 } 20 return sum; 21 } 22 23 int main(){ 24 int n; 25 cin>>n;
26 cout<
03
04 using namespace std;
05
06 int find missing(vector& nums) (
07 int left = 0, right = nums.size() – 1;
08while (left < right){ 09 int mid = left + (right left) / 2; 10 if (nums[mid] - mid+ ①) ( 11 ②; 12 }else{ 13 ③ 14 } 15 } 16 return ④; 17 } 18 19 int main() ( 20 int n; 21 cin >> n;
22 vector nums(n);
23 for (int i= 0; i< n; i++) cin >> nums[i];
24 int missing_number = find_missing(nums);
25 if_(missing_number == ⑤) {
26 cout << "Sequence is consecutive" << endl; 27 }else{ 28 cout << "Missing number is " << ,missing numbeer << endl; 29 } 30 return 0; 31 } 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] 答案: BACBD 注意：第四个有可能选A。暂定B 这段代码实现了一个在连续的整数序列中查找缺失数字的功能。代码中定义了一个函数find_missing，以及一个主函数main。 函数find_missing接收一个整数数组nums作为参数，在while循环中对数组进行二分查找。首先，定义左右指针left和right分别指向数组的首尾元素。在每次循环中，计算中间位置mid，并判断nums[mid]是否等于mid+1，如果是，则说明缺失的数字在[mid+1, right]之间；否则说明缺失的数字在[left, mid]之间。根据这个判断，更新left和right的值，继续进入下一轮循环直到left=right时退出循环。最后返回结果left+1。 主函数main中，读取用户输入的整数n，并依次读取n个整数存储到数组nums中。然后调用find_missing函数查找缺失数字，并根据返回结果输出相应的信息。如果返回的结果是nums.size()，即没有找到缺失数字，就输出"Sequence is consecutive"；否则输出"Missing number is "和缺失的数字。最后程序返回0。 需要注意的是，在使用这段代码之前，需要确保输入的数组nums是连续的整数序列，且没有重复元素。 (2) （编辑距离）给定两个字符串，每次操作可以选择删除（Delete）、插入（Insert）、替换（Replace），一个字符，求将第一个字符串转换为第二个字符串所需要的最少操作次数。 1.#include
2.#include
3.#include
4.using namespace std;
5.
6.int min(int x,int y,int z){
7. return min(min(x,y),z);
8.}
9.
10.int edit_dist_dp(string str1,string str2){
11. int m=str1.length();
12. int n=str2.length();
13. vector> dp(m+1,vector(n+1));
14.
15. for(int i=0;i<=m;i++){ 16. for(int j=0;j<=n;j++){ 17. if(i==0) 18. dp[i][j]=(1); 19. else if(j==0) 20. dp[i][j]=(2); 21. else if((3)) 22. dp[i][j]=(4); 23. else 24. dp[i][j]=1+min(dp[i][j-1],dp[i-1][j],(5)); 25. } 26. } 27. return dp[m][n]; 28.} 29. 30.int main(){ 31. string str1,str2; 32. cin>>str1>>str2;
33. cout<<"Mininum number of operation:" 34. <