珅泽教育CSP-J第一轮模拟考第二十一套

本卷共 43 题，限时 120 分钟，满分 100 分。判断题请选择“正确”或“错误”；其余题目均为单项选择题。

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

1. C++ 是一种面向对象的程序设计语言。在 C++ 中，下面哪个关键字用于声明一个类，其缺省继承方式为 private 继承？（ ）

{{ select(1) }}

• union
• struct
• class
• enum

2. 下述代码实现的数据结构是（ ）。

int data[100], f = 1, r;
void insert(int value) {
    data[++r] = value;
}
void pop() {
    f++;
}

{{ select(2) }}

• 链表
• 栈
• 队列
• 平衡树

3. C++ 语言中，以 0b 开头的数为（ ）进制数。

{{ select(3) }}

• 二进制
• 八进制
• 十进制
• 十六进制

4. 根结点的高度为 1，高度为 5 的完全二叉树至少有（ ）个结点。

{{ select(4) }}

• 15
• 16
• 31
• 32

5. 下图所示二叉树的后序遍历结果是（ ）。

{{ select(5) }}

• acedgbf
• fbacdge
• edgcabf
• egdcfba

6. 考虑下图所示的数字电路，逻辑门的含义已在图中标出。高电平表示 true，低电平表示 false。当 $x,y,z$ 的输入依次为低电平、高电平、高电平时，输出为（ ）。

{{ select(6) }}

• 高电平
• 低电平
• 电路故障
• 高阻

7. 十进制数 $10.375$ 转换为八进制数的结果为（ ）。

{{ select(7) }}

• $10.5$
• $10.3$
• $12.5$
• $12.3$

8. 假设有一组字符 ${g,h,i,j,k,l}$，它们对应的频率分别为 8%、14%、17%、20%、23%、18%。以下哪个选项是字符 $g,h,i,j,k,l$ 分别对应的一组哈夫曼编码？（ ）

{{ select(8) }}

• g:1100, h:1101, i:111, l:10, k:00, j:01
• g:0000, h:001, i:010, l:011, k:10, j:11
• g:111, h:110, i:101, l:100, k:01, j:00
• g:110, h:111, i:101, l:100, k:0, j:01

9. 中缀表达式 ((6 - 3) * 2 + 7) / (5 ^ (3 * 4 + 2)) 对应的后缀表达式为（ ）。

{{ select(9) }}

• / + * - 6 3 2 7 ^ 5 + * 3 4 2
• 6 3 2 - * 7 + 5 3 4 * 2 + ^ /
• 6 3 - 2 * 7 + 5 3 4 * 2 + ^ /
• 6 3 - 2 * 7 + 3 4 * 2 + 5 ^ /

10. 将 3 个相同的红球和 3 个相同的黑球装入三个不同的袋中，每袋均装 2 个球，则不同的装法总数为（ ）。

{{ select(10) }}

• 7
• 8
• 9
• 10

11. 从 2 至 8 的 7 个整数中随机取 2 个不同的数，这两个数互质的概率为（ ）。

{{ select(11) }}

• $1/6$
• $1/3$
• $1/2$
• $2/3$

12. 以下哪一种算法典型地使用了分治法的思想来解决问题？（ ）

{{ select(12) }}

• 线性搜索
• 快速排序
• 冒泡排序
• 插入排序

13. 奇偶校验编码在原二进制编码最后增加一位校验位 $G$。奇校验保证 $A_n \operatorname{xor} \cdots \operatorname{xor} A_1 \operatorname{xor} G=1$，偶校验保证其结果为 $0$。下列编码与校验位对应正确的是（ ）。

{{ select(13) }}

• 编码 11100111，奇校验位为 0
• 编码 01100010，偶校验位为 0
• 编码 00010010，奇校验位为 1
• 编码 11100010，偶校验位为 1

14. 下列关于 NOI 系列活动的说法中，错误的是（ ）。

{{ select(14) }}

• NOI 考试对 C++ 语言的使用没有限制
• 选手不可以携带草稿纸、手机、U 盘等进入考场
• 主办单位 CCF 的全称为中国计算机学会
• 在 CSP 第一轮考试中舞弊，可能会被给予取消考试资格、禁赛等处罚

15. 考虑下图所示的无向图，度最大的结点为（ ）号结点。

{{ select(15) }}

• 3
• 4
• 5
• 6

二、阅读程序（判断题正确填 T，错误填 F；除特殊说明外，判断题 1.5 分，选择题 3 分，共计 40 分）

程序（1）

#include <bits/stdc++.h>
using namespace std;
int x, y;
unsigned int n;
int main() {
    cin >> n >> x >> y;
    unsigned int mask = 0xff;
    int x8 = x << 3;
    int y8 = y << 3;
    unsigned int nx = (n >> x8) & mask, ny = (n >> y8) & mask;
    n &= (~(mask << x8));
    n &= (~(mask << y8));
    n |= (nx << y8);
    n |= (ny << x8);
    cout << "0x";
    cout << std::hex << n << endl;
    return 0;
}

假设输入的 $n$ 是 32 位无符号整数范围内的整数，$x,y$ 是不超过 3 的自然数。

16. 代码中 mask 变量的值转化为二进制后的低 16 位为 0000 0000 1111 1111。（ ）

{{ select(16) }}

• 正确
• 错误

17. 当输入 $x=0$ 时，nx 表示 $n$ 中最低八位对应字节的数据。（ ）

{{ select(17) }}

• 正确
• 错误

18. 去掉程序第 11、12 行 (~(mask << x8)) 和 (~(mask << y8)) 两处最内层括号，不会改变程序结果。（ ）

{{ select(18) }}

• 正确
• 错误

19. 当输入为 15078 0 1 时，变量 nx,ny 的值分别是多少？（提示：十进制数 15078 与十六进制数 3AE6 相同）

{{ select(19) }}

• 0xE6, 0x3A
• 0x6, 0xE0
• 0x6, 0xE
• 0x6, 0xA

20. 当输入为 23270 0 1 时，输出为（ ）。（提示：十进制数 23270 与十六进制数 5AE6 相同）

{{ select(20) }}

• 0x5A6E
• 0x5E6A
• 0xA56E
• 0xE65A

21. 以下哪一个变量的类型修改可能影响程序输出？（ ）

{{ select(21) }}

• 将 x,y 修改为 unsigned int 类型
• 将 x8,y8 修改为 short 类型
• 将 mask 修改为 int 类型
• 将 nx,ny 修改为 unsigned long long 类型

二、阅读程序（判断题正确填 T，错误填 F；除特殊说明外，判断题 1.5 分，选择题 3 分，共计 40 分）

程序（2）

#include <bits/stdc++.h>
using namespace std;

int n, k;

int func(vector<int> &nums) {
    int ret = 0;
    for (int i = n; i > k; i--) {
        if (nums[i] > nums[i - k]) {
            swap(nums[i], nums[i - k]);
            ret++;
        }
    }
    return ret;
}

int main() {
    cin >> n >> k;
    vector<int> a(n + 1, 0);
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    int counter = 0, previous = -1;
    while (counter != previous) {
        previous = counter;
        counter += func(a);
    }
    for (int i = 1; i <= n; i++)
        cout << a[i] << ",";
    cout << endl << counter << endl;
    return 0;
}

假设输入的 $n,k$ 是不超过 100000 的正整数，输入的 $a[i]$ 是不超过 $10^9$ 的整数，且 $k \le n$。

22. 当输入的 $k$ 为 1 时，程序将 $a$ 从小到大排序。（ ）

{{ select(22) }}

• 正确
• 错误

23. 在题目限制的输入规模下，counter 可能会溢出。（ ）

{{ select(23) }}

• 正确
• 错误

24. （1 分）当输入为 8 1 1 9 2 3 4 6 8 7 时，输出共有 18 个可见字符。（ ）

{{ select(24) }}

• 正确
• 错误

25. 当输入的 $k$ 为 1 时，该程序的排序方法最接近（ ）。

{{ select(25) }}

• 冒泡排序
• 选择排序
• 计数排序
• 插入排序

26. 该程序的时间复杂度为（ ）。

{{ select(26) }}

• $O(n+k^2)$
• $O(n^2)$
• $O(nk)$
• $O(n^2/k)$

27. 当输入为 8 3 1 5 2 6 3 7 4 8 时，输出第一行的第三个数字为（ ）。

{{ select(27) }}

• 2
• 6
• 7
• 8

二、阅读程序（判断题正确填 T，错误填 F；除特殊说明外，判断题 1.5 分，选择题 3 分，共计 40 分）

程序（3）

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int MAXN = 200001;
int main() {
    int n, m, l, r, w;
    cin >> n >> m;
    vector<int> dist(MAXN, -1);
    vector<bool> vis(MAXN, false);
    vector<vector<pair<int, int>>> go(MAXN);
    for (int i = 1; i <= m; i++) {
        cin >> l >> r >> w;
        go[l].push_back(make_pair(r + 1, w));
        go[r + 1].push_back(make_pair(l, -w));
    }
    queue<int> q;
    dist[1] = 0, vis[1] = true;
    q.push(1);
    while (!q.empty()) {
        int x = q.front(); q.pop();
        for (auto i : go[x]) {
            if (!vis[i.first]) {
                vis[i.first] = true;
                dist[i.first] = dist[x] + i.second;
                q.push(i.first);
            }
        }
    }
    if (dist[n + 1] == -1) cout << "sorry" << endl;
    else cout << dist[n + 1] << endl;
    return 0;
}

假设输入的 $n,m$ 是不超过 200000 的正整数，程序每次输入的 $l,r$ 保证 $l \le r$。

28. 交换程序第 14 行与第 15 行，不影响程序运行结果。（ ）

{{ select(28) }}

• 正确
• 错误

29. 输入的 $r$ 的最大值为 $n$ 时，程序可以正常运行。（ ）

{{ select(29) }}

• 正确
• 错误

30. 在程序第 17 行至第 29 行，相同的数可能重复进入队列。（ ）

{{ select(30) }}

• 正确
• 错误

31. 当输入的 $l$ 最小值为 $x$，输入的 $r$ 最大值为 $y$ 时，最多有（ ）个元素进入过队列。

{{ select(31) }}

• 1
• $y-x$
• $y-x+1$
• $y-x+2$

32. 当输入的 $n$ 为偶数，且 $r=l+1$ 时，$m$ 至少为（ ）时输出不为 sorry。

{{ select(32) }}

• $n/2$
• $n/2+1$
• $n/2-1$
• $n$

33. 当输入为 5 3 1 3 4 3 4 2 4 5 3 时，输出为（ ）。

{{ select(33) }}

• 4
• 5
• 6
• 7

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

程序（1）

（优美的进制）给出整数 $n$。当且仅当 $n$ 在 $k$ 进制下至少有两位，且每一位的数值都不同，我们称 $k$ 进制是优美的。求对于给定的 $n$，有哪些进制是优美的；不存在则输出 -1。试补全程序。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100000;
int n;
int vis[MAXN], a[MAXN];
vector<int> ans;
int check(int k) {
    int x = n, top = 0;
    for (int i = 0; i <= k; i++) vis[i] = 0;
    while (①) {
        a[++top] = ②;
        x = ③;
    }
    if (top < 2)
        return 0;
    for (int i = 1; i <= top; i++) {
        if (④)
            return 0;
        vis[a[i]] = 1;
    }
    return 1;
}
int main() {
    cin >> n;
    for (int i = ⑤; i <= n; i++) {
        if (check(i))
            ans.push_back(i);
    }
    if (ans.empty()) {
        cout << -1;
    }
    for (int i = 0; i < ans.size(); i++)
        cout << ans[i] << " ";
    return 0;
}

34. ①处应填（ ）。

{{ select(34) }}

• x > 0
• x > 1
• x / k > 0
• x / k > 1

35. ②处应填（ ）。

{{ select(35) }}

• x / k
• x % k
• (x - 1) / k + 1
• (x - 1) % k + 1

36. ③处应填（ ）。

{{ select(36) }}

• x / k
• x % k
• (x - 1) / k + 1
• (x - 1) % k + 1

37. ④处应填（ ）。

{{ select(37) }}

• vis[i] == 1
• vis[a[i]] == 0
• vis[i] == 0
• vis[a[i]] == 1

38. ⑤处应填（ ）。

{{ select(38) }}

• 1
• n - 1
• 2
• 0

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

程序（2）

（好运的日期）一个日期可以用 $x$ 年 $y$ 月 $z$ 日来表示。当且仅当 $xy(w-z+1)$ 为质数时，我们称这个日期是好运的，其中 $w$ 为 $x$ 年 $y$ 月的总天数。输入 $x,y,z$，判断对应日期是否好运。保证 $x \le 2024$、$y \le 12$，且 $x,y,z$ 可以构成合法日期。试补全线性筛程序，空间限制 512 MiB。

#include <bits/stdc++.h>
using namespace std;

const int MAXW = ①;
const int days[13] = {0, 31, 0, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
int prime[MAXW], cnt;
bool not_prime[MAXW];

void linear_prime(int n) {
    --n;
    not_prime[0] = not_prime[1] = true;
    for (int i = 2; i <= n; i++) {
        if (not_prime[i] == false)
            prime[++cnt] = i;
        for (int j = 1; ②; j++) {
            not_prime[i * prime[j]] = 1;
            if (i % prime[j] == 0)
                ③;
        }
    }
}
bool check(int n) {
    return ④;
}

int main() {
    linear_prime(MAXW);
    int x, y, z, w;
    cin >> x >> y >> z;
    if (y == ⑤)
        w = check(x) ? 29 : 28;
    else
        w = days[y];
    if (not_prime[x * y * (w - z + 1)])
        cout << "unlucky" << endl;
    else
        cout << "lucky" << endl;
    return 0;
}

39. ①处可以填（ ）。

{{ select(39) }}

• 753005
• 10000000000
• 725041
• 2024

40. ②处应填（ ）。

{{ select(40) }}

• j <= cnt
• i * prime[j] <= n
• (j <= cnt) && (i * prime[j] <= n)
• (i <= cnt) && (prime[i] * prime[j] <= n)

41. ③处应填（ ）。

{{ select(41) }}

• not_prime[i] = true
• return
• continue
• break

42. ④处应填（ ）。

{{ select(42) }}

• n % 4 == 0
• n % 400 == 0 || (n % 4 == 0 && n % 100 != 0)
• n % 4 == 0 && n % 100 != 0
• n % 100 == 0 || (n % 4 == 0 && n % 100 != 0)

43. ⑤处应填（ ）。

{{ select(43) }}

• 1
• 7
• 8
• 2