2023年 CSP-J 第一轮（入门级）

满分 100 分

时长 120 分钟

共 42 题

答题卡已答 0/42

已答正确错误编程题

选单项选择题（共 15 题，共 0 分）

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

static

mutable

unsigned

const

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

$21111111_8$

$22111111_8$

$22222221_8$

$22222211_8$

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

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

value.data = 3.14;

data->value = 3.14;

value->data = 3.14;

data.value = 3.14;

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

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

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

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;

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

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

$7$

$9$

$6$

$8$

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

以下关于高精度运算的说法错误的是（）

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

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

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

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

后缀表达式 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$ 的和为（）

$236_8$

$158_{10}$

$10110000_2$

$A0_{16}$

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

1010, 1001, 1000, 011, 010, 00

000, 001, 010, 011, 10, 11

1010, 1011, 110, 111, 00, 01

1111, 1110, 101, 100, 110, 0

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

EDGBFCA

DEBGFCA

DBEGFCA

EDBGFCA

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

[图片]

$1, 2, 4, 3$

$2,1,3,4$

$4,2,3,1$

$1, 2, 3, 4$

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

字（word）

千字节（kilobyte）

字节（byte）

比特（bit）

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

$1770$

$1540$

$2200$

$1420$

以下哪个不是操作系统?

Windows

Android

Linux

HTML

阅阅读程序（共 17 题，共 0 分）

程序代码请先阅读以下程序

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

程序代码请先阅读以下程序

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

程序代码请先阅读以下程序

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

完完善程序（共 10 题，共 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;
}

程序代码请先阅读以下程序

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

选 单项选择题（共 15 题，共 0 分）

阅 阅读程序（共 17 题，共 0 分）

完 完善程序（共 10 题，共 0 分）

考试完成

选单项选择题（共 15 题，共 0 分）

阅阅读程序（共 17 题，共 0 分）

完完善程序（共 10 题，共 0 分）