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

一、单项选择题（共 15 题，每题 2 分，共 30 分）

1. NOI 是 CCF 主办的程序设计竞赛，其中 I 表示（ ）。

{{ select(1) }}

• Input，输入
• Informatics，信息学
• Information，信息
• Institution，机构

2. 把正整数分成三类，下面的分类标准中，不重不漏的是（ ）。

{{ select(2) }}

• 偶数、质数、平方数
• 奇数、合数、2
• 偶数、质数、奇合数
• 质数、合数、1

3. 下列关键字中，表示分支结构的是（ ）。

{{ select(3) }}

• switch
• const
• while
• continue

4. 下面四个整数中，最小的是（ ）。

{{ select(4) }}

• $-60_8$
• $-3F_{16}$
• $-1101_2$
• $+12_{10}$

5. 现代计算机遵循冯·诺依曼架构，由输入设备、输出设备、存储器、运算器和控制器组成。用自己的笔记本电脑浏览网站时，下列说法正确的是（ ）。

{{ select(5) }}

• 笔记本电脑的屏幕上显示输入的内容，屏幕是输入设备
• 网站服务器的交换机控制网络传输，在服务器中，交换机是控制器
• 无论是否有人访问网页，网站的代码一直都在运算器中
• 浏览网站时，笔记本电脑里的存储器也要参与

6. 12 和 22 的最小公倍数为（ ）。

{{ select(6) }}

• 2
• 22
• 132
• 264

7. 杨辉三角除第一列和最后一列均为 1 外，其余每个数字都等于左上角与右上角数字之和。下图是杨辉三角的一部分，$y$ 的值是（ ）。

⬚    1    ⬚    12    ⬚    ...
1    ⬚    x     ⬚     y    ...

{{ select(7) }}

• 13
• 25
• 66
• 78

8. 二进制数 $101100110_2$ 和 $110011_2$ 按位与的结果是（ ）。

{{ select(8) }}

• $101100010_2$
• $100010_2$
• $101110111_2$
• $10_2$

9. 前序遍历是 CAEDHFGBI、中序遍历是 AEDCFBGIH 的二叉树，其后序遍历为（ ）。

{{ select(9) }}

• DEABIGFHC
• CHFGIBAED
• EDABFIGHC
• DEABFIGHC

10. 阅读下面代码片段。要让程序正常运行结束并使 p->a 为 7，①处应填（ ）。

struct yumi {
    int a, b;
};

int main() {
    struct yumi *p = new yumi;
    *p = (yumi){2, 5};
    int *q = ①;
    *q = 7;
}

{{ select(10) }}

• &p.a
• &p->a
• p->a
• *p.a

11. 在 1、2、3、4、5 中选出三个互不相等的数字组成三位数，其中有（ ）个是 3 的倍数。

{{ select(11) }}

• 6
• 12
• 24
• 40

12. 小 A 在 1 至 50 中选一个整数让小 B 猜。小 B 有 6 次机会，每次猜后小 A 告知“大了”“小了”或“对了”。小 B 的猜测过程如下：

轮数	小 B 的猜测	小 A 的回答
1	26	大了
2	10	小了
3	18
4	20
5	23	大了
6	22	大了，机会用完

假设小 B 运气永远最差，在第（ ）轮后小 B 败局已定。

{{ select(12) }}

• 2
• 3
• 4
• 5

13. 有时线性数据结构之间可互相替代。下列说法错误的是（ ）。

{{ select(13) }}

• 可用单向链表实现栈，入栈、出栈时间复杂度均为 $O(1)$
• 可用单向链表实现队列，入队、出队时间复杂度均为 $O(1)$
• 可用两个栈实现队列，入队、出队时间复杂度均为 $O(1)$
• 可用数组实现栈，入栈、出栈时间复杂度均为 $O(1)$

14. 一棵二叉树有 2024 个结点，且只有一个孩子的结点多于叶子结点，则有两个孩子的结点至多有（ ）个。

{{ select(14) }}

• 673
• 674
• 1011
• 1012

15. 一份文件仅包含 1000 个英文小写字母。用哈夫曼编码进行不定长二进制编码，发现字母 e 的编码长度为 1，则 e 至少出现（ ）次。

{{ select(15) }}

• 39
• 334
• 500
• 501

二、阅读程序（共 40 分）

阅读程序（1）

#include <iostream>
using namespace std;

const double eps = 1e-9;

double f(double x) {
    return x * x - 2 * x + 1;
}

double fabs(double x) {
    return x < 0 ? -x : x;
}

int main() {
    double l, r;
    cin >> l >> r;
    while (fabs(r - l) > eps) {
        double m = (l + r) / 2;
        if (f(m) < f(m + 1e-6))
            r = m;
        else
            l = m;
    }
    cout << l << endl;
    return 0;
}

16. 当输入为 0 3 时，程序的输出会大于 1.2。（ ）

{{ select(16) }}

• 正确
• 错误

17. 当输入为 -10000 0 时，第 15 至第 21 行的 while 循环执行次数少于 500 次。（ ）

{{ select(17) }}

• 正确
• 错误

18. fabs(-5) 的值为（ ）。

{{ select(18) }}

• 0
• -5
• 5
• 810

19. f(1) 的值为（ ）。

{{ select(19) }}

• 0
• 1
• 2
• 3

20. 将第 6 行改为 return x * x - 4 * x + 4;，对任意符合限制的输入，程序输出和（ ）最接近。

{{ select(20) }}

• 0
• 1
• 2
• 3

阅读程序（2）

#include <iostream>
#include <string>
using namespace std;

int main() {
    int T;
    cin >> T;
    while (T--) {
        string s1, s2;
        cin >> s1 >> s2;
        if (s1.length() == s2.length()) {
            int flag = 0;
            for (int i = 0; i < s1.length(); i++) {
                if (s1[i] != s2[i]) ++flag;
            }
            if (flag <= 1) cout << "similar" << endl;
            else cout << "not similar" << endl;
        } else {
            if (s1.length() > s2.length())
                swap(s1, s2);
            if (s1.length() < s2.length() - 1) {
                cout << "not similar" << endl;
                continue;
            }
            int succ = 0;
            for (int i = 0; i < s2.length(); i++) {
                string s = s2.substr(0, i) + s2.substr(i + 1);
                if (s == s1) succ = 1;
            }
            if (succ) cout << "similar" << endl;
            else cout << "not similar" << endl;
        }
    }
    return 0;
}

21. 第 11 行的 s1.length() 可以改为 s1.size()。（ ）

{{ select(21) }}

• 正确
• 错误

22. 第 14 行的 flag++ 可以改为 flag = 1。（ ）

{{ select(22) }}

• 正确
• 错误

23. 第 29 行的 succ = 1 可以改为 succ++。（ ）

{{ select(23) }}

• 正确
• 错误

24. 删除程序的第 22 至第 25 行，程序运行结果不会改变。（ ）

{{ select(24) }}

• 正确
• 错误

25. 输入为 2 apple bpple pink pink（不考虑换行）时，输出结果为（ ）。

{{ select(25) }}

• similar similar
• similar not similar
• not similar similar
• not similar not similar

26. 若输出为 not similar，则输入可能是（ ）。

{{ select(26) }}

• 1 similar similar
• 1 similar timilar
• 1 similarr similar
• 1 similarr similer

阅读程序（3）

#include <iostream>
using namespace std;

int A, B, C;
int a[25][25][25];

int main() {
    cin >> A >> B >> C;
    for (int i = 1; i <= A; i++)
        for (int j = 1; j <= B; j++)
            for (int k = 1; k <= C; k++)
                cin >> a[i][j][k];

    for (int i = 1; i <= A; i++)
        for (int j = 1; j <= B; j++)
            for (int k = 1; k <= C; k++)
                a[i][j][k] += a[i - 1][j][k];

    for (int i = 1; i <= A; i++)
        for (int j = 1; j <= B; j++)
            for (int k = 1; k <= C; k++)
                a[i][j][k] += a[i][j - 1][k];

    for (int i = 1; i <= A; i++)
        for (int j = 1; j <= B; j++)
            for (int k = 1; k <= C; k++)
                a[i][j][k] += a[i][j][k - 1];

    cout << a[A][B][C] << endl;
    return 0;
}

27. 如果输入的 $A$ 为 0，则程序会出现死循环。（ ）

{{ select(27) }}

• 正确
• 错误

28. 当输入数据均为小于 10 的正整数时，在执行至第 30 行前，a[1][2][2] 一定大于 a[1][2][1]。（ ）

{{ select(28) }}

• 正确
• 错误

29. 在任何输入下，交换 $A$ 和 $C$ 的值，程序输出不变。（ ）

{{ select(29) }}

• 正确
• 错误

30. 输入为 2 2 2 1 2 3 4 5 6 7 8 时，程序输出为（ ）。

{{ select(30) }}

• 0
• 36
• 32
• 72

31. 输入为 2 2 2 1 2 3 4 5 6 7 8 时，在执行至第 30 行前，a[1][2][1] 的值为（ ）。

{{ select(31) }}

• 1
• 2
• 3
• 4

32. 当 $A,B,C$ 均为 5，且后续输入为 125 个 7 时，在执行至第 30 行前，a[A][B][1] 的值为（ ）。

{{ select(32) }}

• 175
• 0
• 875
• 运行时错误

三、完善程序（共 10 题，每题 3 分，共 30 分）

完善程序（1）：区间和

给定长度为 $n$ 的正数数列 $a$，第 $i$ 个数为 $a_i$。有 $Q$ 次询问，每次给定 $l$，求最小的 $r$，满足 $a_l+a_{l+1}+cdots+a_r$ 不小于 $k$。保证有解。试补全倍增法程序。

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

const int MAXN = 200000 + 7;
int n, k, Q, l, a[MAXN], s[MAXN];

int main() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        s[i] = ①;
    }
    cin >> Q;
    int limit = ②;
    while (Q--) {
        cin >> l;
        int r = l;
        for (③) {
            int dist = ④;
            if (r + dist > n)
                continue;
            if (⑤)
                r += dist;
        }
        cout << r + 1 << endl;
    }
    return 0;
}

33. ①处应填（ ）。

{{ select(33) }}

• a[i]
• s[i - 1]
• s[i] + a[i]
• s[i - 1] + a[i]

34. ②处应填（ ）。

{{ select(34) }}

• log(n)
• sqrt(n)
• log(n) / log(2) + 1
• sqrt(n) / sqrt(2) + 1

35. ③处应填（ ）。

{{ select(35) }}

• int i = limit; i >= 0; i--
• int i = 0; i <= limit; i++
• int i = limit; i >= 0; i++
• int i = 0; i <= limit; i--

36. ④处应填（ ）。

{{ select(36) }}

• 2 ^ i
• 1 << i
• 2 * i
• i

37. ⑤处应填（ ）。

{{ select(37) }}

• s[r] - s[l] < k
• s[r] - s[l - 1] < k
• s[r + dist] - s[l] < k
• s[r + dist] - s[l - 1] < k

完善程序（2）：数字矩阵

给定一个 $N$ 行 $M$ 列的非负整数矩阵，需要从中取出若干个数字，使取出的任意两个数字不相邻。如果一个数字位于另一个数字周围相邻的 8 个格子之一，就认为这两个数字相邻。求所取数字之和的最大值。

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

bool vis[8][8];
int n, m, a[8][8], mx, sum;

void dfs(int x, int y) {
    if (①)
        return;
    if (②) {
        vis[x][y] = true;
        sum += a[x][y];
        mx = max(mx, sum);
        if (③)
            dfs(x, y + 1);
        else
            dfs(x + 1, 1);
        sum -= a[x][y];
        vis[x][y] = 0;
    }
    if (③)
        dfs(x, y + 1);
    else
        dfs(x + 1, 1);
}

int main() {
    int T;
    cin >> T;
    while (T--) {
        ④
        cin >> n >> m;
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
                cin >> a[i][j];
        ⑤
        cout << mx << endl;
    }
    return 0;
}

38. ①处应填（ ）。

{{ select(38) }}

• x == m
• x == m + 1
• x == n
• x == n + 1

39. ②处应填（ ）。

{{ select(39) }}

• !vis[x + 1][y + 1] && !vis[x + 1][y] && !vis[x + 1][y - 1] && !vis[x][y + 1]
• !vis[x - 1][y - 1] && !vis[x][y - 1] && !vis[x + 1][y - 1] && !vis[x - 1][y]
• !vis[x - 1][y - 1] && !vis[x - 1][y] && !vis[x - 1][y + 1] && !vis[x][y - 1]
• !vis[x - 1][y - 1] && !vis[x - 1][y] && !vis[x - 1][y + 1] && !vis[x][y]

40. ③处应填（ ）。

{{ select(40) }}

• y < m
• x < n
• y == m
• x == n

41. ④处应填（ ）。

{{ select(41) }}

• int n, m
• sum = 0
• memset(a, 0, sizeof(a))
• mx = 0

42. ⑤处应填（ ）。

{{ select(42) }}

• dfs(n, m)
• dfs(1, 1)
• dfs(0, 0)
• dfs(1, 0)