CSP-J 2023 第一轮试题

场次：2023年CSP-J第1轮
考试时长：120 分钟
满分：100 分
题目来源：第三方来源（社区转写，非官方，仅供参考）

单项选择题

本分区标题为平台补的结构性占位，原卷（来源件）未收录。

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

在 C++ 中，下面哪个关键字用于声明一个变量，其值不能被修改?

unsigned

const

static

mutable

八进制数 $12345670_8$ 和 $07654321_8$ 的和为

$22222221_8$

$21111111_8$

$22111111_8$

$22222211_8$

阅读下述代码，请问修改 data 的 value 成员以存储 $3.14$ ，正确的方式是

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

data.value = 3.14;

value.data = 3.14;

data -> value = 3.14;

value->data = 3.14;

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

struct Node { int data; Node* next; }

现在有一个指向链表头部的指针：Node* head。如果想要在链表中插入一个新节点，其成员 data 的值为 $42$ ，并使新节点成为链表的第一个节点，下面哪个操作是正确的？

Node* newNode = new Node; newNode->data = 42; newNode->next = head; head = newNode;

Node* newNode = new Node; head->data = 42; newNode->next = head; head = newNode;

Node* newNode = new Node; newNode->data = 42; head->next = newNode;

Node* newNode = new Node; newNode->data = 42; newNode->next = head;

根节点的高度为 $1$ ，一棵拥有 $2023$ 个节点的三叉树高度至少为（）。

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

以下关于高精度运算的说法错误的是()

高精度计算主要是用来处理大整数或需要保留多位小数的运算

大整数除以小整数的处理的步骤可以是，将被除数和除数对齐，从左到右逐位尝试将除数乘以某个数，通过减法得到新的被除数，并累加商

高精度乘法的运算时间只与参与运算的两个整数中长度较长者的位数有关

高精度加法运算的关键在于逐位相加并处理进位

后缀表达式 6 2 3 + - 3 8 2 / + * 2 ^ 3 + 对应的中缀表达式是

((6-(2+3))*(3+8/2))^2+3

6-2+3*3+8/2^2+3

(6-(2+3))*((3+8/2)^2)+3

6-((2+3)*(3+8/2))^2+3

数 $101010_2$ 和 $166_8$ 的和为 ( )

$(10110000)_2$

$(236)_8$

$(158)_{10}$

$(A0)_{16}$

假设有一组字符 {a,b,c,d,e,f}, 对应的频率分别为 $5\%,9\%,12\%,13\%,16\%,45\%$ 。请问以下哪个选项是字符abcdef分别对应的一组哈夫曼编码?

1111,1110,101,100,110,0

1010,1001,1000,011,010,00

000,001,010,011,10,11

1010,1011,110,111,00,01

给定一棵二叉树，其前序遍历结果为：ABDECFG,中序遍历结果为：DEBACFG。请问这棵树的正确后序遍历结果是什么?

EDBGFCA

EDGBFCA

DEBGFCA

DBEGFCA

考虑一个有向无环图，该图包含 $4$ 条有向边： $(1,2),(1,3),(2,4)$ 和 $(3,4)$ 。以下哪个选项是这个有向无环图的一个有效的拓扑排序?

4,2,3,1

1,2,3,4

1,2,4,3

2,1,3,4

在计算机中，以下哪个选项描述的数据存储容量最小（）

字节 (byte)

比特 (bit)

字 (word)

千字节 (kilobyte）

一个班级有 $10$ 个男生和 $12$ 个女生。如果要选出一个 $3$ 人的小组，并且小组中必须至少包含 $1$ 个女生，那么有多少种可能的组合?()

$1420$

$1770$

$1540$

$2200$

以下哪个不是操作系统?()

Linux

Windows

Android

HTML

二、阅读程序（程序输入不超过数组或字符串定义的范围；判断题正确填 √，错误填 ⨉ ；除特殊说明外，判断题 1.5 分，选择题 3 分，共计 40 分）

判断题「√」表示正确，「×」表示错误

阅读程序共 12 分5 道小题

整组作答后提交批改，成绩计入掌握度 · 已答 0/5

程序

#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;}

16判断2 分
（2分）当输入为 2 2 2 时，输出为1.7321（）
17判断2 分
（2分）将第7行中的 (s-b)*(s-c) 改为 (s-c)*(s-b) 不会影响程序运行的结果（）
18判断2 分
（2分）程序总是输出四位小数（）
19单选3 分
单选题
1. 当输入为 3 4 5 时，输出为（）
A
6.0000

B
12.0000

C
24.0000

D
30.0000
20单选3 分
当输入为 5 12 13 时，输出为（）

A
24.0000

B
30.0000

C
60.0000

D
120.0000

三、完善程序（单选题，每小题 3 分，共计 30 分）

完善程序共 15 分5 道小题

整组作答后提交批改，成绩计入掌握度 · 已答 0/5

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

#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;
}

程序

#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（①）单选空位 ①3 分
①处应填（）

A
1

B
nums[0]

C
right

D
left
34（②）单选空位 ②3 分
②处应填（）

A
left=mid+1

B
right=mid-1

C
right=mid

D
left=mid
35（③）单选空位 ③3 分
③处应填（）

A
left=mid+1

B
right=mid-1

C
right=mid

D
left=mid
36（④）单选空位 ④3 分
④处应填（）

A
left+nums[0]

B
right+nums[0]

C
mid+nums[0]

D
right+1
37（⑤）单选空位 ⑤3 分
⑤处应填（）

A
nums[0]+n

B
nums[0]+n-1

C
nums[0]+n+1

D
nums[n-1]

完善程序共 15 分5 道小题

整组作答后提交批改，成绩计入掌握度 · 已答 0/5

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

#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;
}

程序

#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（①）单选空位 ①3 分
①处应填（）

A
j

B
i

C
m

D
n
39（②）单选空位 ②3 分
②处应填（）

A
j

B
i

C
m

D
n
40（③）单选空位 ③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]
41（④）单选空位 ④3 分
④处应填（）

A
dp[i-1][j-1]+1

B
dp[i-1][j-1]

C
dp[i-1][j]

D
dp[i][j-1]
42（⑤）单选空位 ⑤3 分
⑤处应填（）

A
dp[i][j] + 1

B
dp[i-1][j-1]+1

C
dp[i-1][j-1]

D
dp[i][j]