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

本卷为 CSP-J 部分，共 45 题，满分 100 分。判断题选择“正确/错误”。不含原卷 S 组附加题。

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

第 1 题

若在八进制下有等式 $47_8+X=100_8$，则 $X$ 的十进制值为（ ）。

{{ select(1) }}

• 21
• 25
• 31
• 33

第 2 题

执行下列代码后，z 的值等于（ ）。

int x = 0b1010;
int y = 0b1100;
int z = (x & y) + (x | y);

{{ select(2) }}

• x+y
• x^y
• x-y
• x*y

第 3 题

用两个栈 $S_1$、$S_2$ 模拟一个队列：入队时压入 $S_1$；出队时若 $S_2$ 非空则弹出 $S_2$，否则先把 $S_1$ 全部倒入 $S_2$ 再弹出。初始两栈为空，依次执行“入队 1,2,3,4；出队；入队 5；出队”后，栈 $S_2$ 中的元素从栈底到栈顶依次为（ ）。

{{ select(3) }}

• 3, 4
• 4, 3
• 2, 3, 4
• 4, 3, 2

第 4 题

下列关于哈夫曼编码的说法中，错误的是（ ）。

{{ select(4) }}

• 出现频率较高的字符，通常分配较短的编码（编码长度可以相同）
• 哈夫曼编码是前缀码，解码时无需额外分隔符
• 任意两个出现频率不同的字符，其编码长度一定不同
• 哈夫曼编码的带权路径长度是所有前缀码中最小的（之一）

第 5 题

有向图中存在一条从 $u$ 到 $v$ 的边，且该图无环。下列说法正确的是（ ）。

{{ select(5) }}

• 在任意拓扑排序中，$u$ 一定排在 $v$ 之前
• 存在一种拓扑排序使 $u$ 排在 $v$ 之前，也存在一种使 $v$ 排在 $u$ 之前
• 图中一定存在从 $v$ 回到 $u$ 的路径
• 无法确定 $u$ 与 $v$ 在拓扑排序中的先后

第 6 题

根结点深度为 1，深度为 $d$ 的完全二叉树，其结点数 $n$ 满足（ ）。

{{ select(6) }}

• $2^d-1\le n\le2^{d+1}-1$
• $2^{d-1}\le n\le2^d-1$
• $2^{d-1}\le n<2^d$
• $2^{d-1}-1<n\le2^d$

第 7 题

在 C++ 中，关于 const 与 static，下列说法正确的是（ ）。

{{ select(7) }}

• const 变量必须初始化，且初始化后不可修改
• static 局部变量在每次函数调用时都会重新初始化
• 用 const 修饰的变量一定存储在只读内存区域
• static 全局变量与普通全局变量的作用域完全相同

第 8 题

已知函数定义如下，则 $f(2026)-f(2025)$ 的值为（ ）。

int f(int n) {
    if (n < 10) return n;
    return f(n / 10) + n % 10;
}

{{ select(8) }}

• 1
• 2
• 9
• 10

第 9 题

一个整数数组中，除某个数外其余每个数都出现偶数次，现要找出这个出现奇数次的数。最高效的做法是（ ）。

{{ select(9) }}

• 排序后扫描
• 对所有数求异或
• 双重循环统计
• 用有序映射统计

第 10 题

一棵二叉树共有 100 个结点，其中度为 2 的结点有 45 个，则度为 1 的结点有（ ）个。

{{ select(10) }}

• 9
• 10
• 45
• 54

第 11 题

从 1 到 9 中选出 3 个不同的数，使它们的和为奇数，共有（ ）种选法。

{{ select(11) }}

• 40
• 50
• 60
• 84

第 12 题

函数 $f(0)=f(1)=1$，$f(n)=f(n-1)+2f(n-2)+1\ (n\ge2)$。若从 $f(0)$ 到 $f(n)$ 依次递推计算，则计算 $f(n)$ 的时间复杂度为（ ）。

{{ select(12) }}

• $O(n)$
• $O(n^2)$
• $O(2^n)$
• $O(\log n)$

第 13 题

二分图是指能将顶点划分成两个部分，每一部分内的顶点间没有边相连的简单无向图。那么，14 个顶点的二分图至多有（ ）条边。

{{ select(13) }}

• 42
• 48
• 49
• 56

第 14 题

字符串 xxxy 的互不相等的非空子串数量为（ ）。

{{ select(14) }}

• 7
• 8
• 10
• 15

第 15 题

给定一个含 $N$ 个不相同数字的数组，在最坏情况下，找出其中最大或最小的数至少需要 $N-1$ 次比较。同时找出最大与最小的数至少需要（ ）次比较。（$\lceil\ \rceil$ 表示向上取整，$\lfloor\ \rfloor$ 表示向下取整。）

{{ select(15) }}

• $\lceil3N/2\rceil-2$
• $\lfloor3N/2\rfloor-2$
• $2N-2$
• $2N-4$

二、阅读程序（判断题每题 1 分，选择题每题 3 分，共 40 分）

程序阅读（1）：对角线枚举

阅读程序，回答第 16—23 题。输入 a、b 均为正整数。

int solve(int a, int b)
{
    int x = 1;
    int y = 1;
    int rank = 1;
    int dx = -1;
    int dy = 1;
    while (x != a || y != b) {
        if (x + dx < 1) {
            y++;
            dx = -dx;
            dy = -dy;
        } else if (y + dy < 1) {
            x++;
            dx = -dx;
            dy = -dy;
        } else {
            x = x + dx;
            y = y + dy;
        }
        rank++;
    }
    return rank;
}

第 16 题

当输入为 2 1 与输入为 1 2 时，程序的输出相同。（ ）

{{ select(16) }}

• 正确
• 错误

第 17 题

函数的时间复杂度为 $\Theta(a+b)$。（ ）

{{ select(17) }}

• 正确
• 错误

第 18 题

交换输入 a 与 b 后，当 $a+b$ 为偶数时输出一定改变。（ ）

{{ select(18) }}

• 正确
• 错误

第 19 题

当输入为 5 1 时，程序的输出为 11。（ ）

{{ select(19) }}

• 正确
• 错误

第 20 题

当 $a+b$ 为奇数时，程序的输出等于 $(a+b-1)(a+b)/2+a$。（ ）

{{ select(20) }}

• 正确
• 错误

第 21 题

若 $a,b$ 均为正整数且 $a+b=4$，则 rank 的最小可能值为（ ）。

{{ select(21) }}

• 3
• 4
• 6
• 7

第 22 题

当输入为 20 26 时，函数的返回值为（ ）。

{{ select(22) }}

• 972
• 1010
• 1016
• 1026

第 23 题

下列关于输出 rank 的奇偶性，正确的是（ ）。

{{ select(23) }}

• rank 一定为偶数
• rank 一定为奇数
• rank 的奇偶性与 $a+b$ 的奇偶性始终相同
• rank 的奇偶性不能仅由 $a+b$ 的奇偶性确定

程序阅读（2）：统计三元组

阅读程序，回答第 24—28 题。

int solve(int n, int a[])
{
    int cnt = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            for (int k = 0; k < n; ++k) {
                if (a[i] == a[j] && a[i] != a[k]) {
                    cnt++;
                }
            }
        }
    }
    return cnt;
}

第 24 题

当数组 a 中所有元素互不相同时，函数的返回值为 0。（ ）

{{ select(24) }}

• 正确
• 错误

第 25 题

若某个值在数组 a 中重复出现了 $k$ 次，则它对该函数返回值的贡献为 $\frac{k(k-1)(n-k)}2$。（ ）

{{ select(25) }}

• 正确
• 错误

第 26 题

该函数的功能是（ ）。

{{ select(26) }}

• 统计三个元素全相等的三元组个数
• 统计恰好两个元素相等、第三个元素与之不同的三元组个数
• 统计三个元素两两不同的三元组个数
• 统计数组 a 中不同元素的个数

第 27 题

若 n=100，a=[1,2,3,...,99,100]，函数返回（ ）。

{{ select(27) }}

• 0
• 1
• 100
• 4950

第 28 题

下列关于该函数返回值的说法，正确的是（ ）。

{{ select(28) }}

• 返回值一定为偶数
• 返回值一定为 3 的倍数
• 返回值的上界为 $O(n^3)$
• 返回值与数组 a 中元素的具体顺序有关

程序阅读（3）：等差数列与二分查找

阅读程序，回答第 29—35 题。设 n 为正整数，计算过程中不发生整数溢出。

int solve(int x, int a, int d, int n)
{
    if (d < 0) {
        return solve(x, a + d * (n - 1), -d, n);
    }
    int begin = 0;
    int end = n;
    while (begin < end) {
        int mid = begin + (end - begin) / 2;
        if (a + d * mid < x) {
            begin = mid + 1;
        } else {
            end = mid;
        }
    }
    if (end == 0) {
        return a - x;
    } else if (end == n) {
        return x - (a + d * (n - 1));
    } else {
        int upper = a + d * end;
        int lower = upper - d;
        return std::min(x - lower, upper - x);
    }
}

第 29 题

若把 if (d < 0) 改为 if (d <= 0)，当 $d=0$ 时程序会陷入无限递归。（ ）

{{ select(29) }}

• 正确
• 错误

第 30 题

函数的时间复杂度为 $\Theta(\log n)$。（ ）

{{ select(30) }}

• 正确
• 错误

第 31 题

当 $n=1$ 时，对任意 $x$，函数都返回 $x-a$。（ ）

{{ select(31) }}

• 正确
• 错误

第 32 题

执行 solve(1000000007, 1000000030, -100, 1000000) 的返回值为（ ）。

{{ select(32) }}

• 23
• 33
• 77
• 100

第 33 题

当 end == 0 时，说明（ ）。

{{ select(33) }}

• $x$ 比首项还小（或等于首项）
• $x$ 比末项还大
• $x$ 位于数列中某两项之间
• 数列为空

第 34 题

当 end == n 时，说明（ ）。

{{ select(34) }}

• $x$ 比首项还小
• $x$ 比末项还大
• $x$ 恰好等于某一项
• $x$ 位于数列中某两项之间

第 35 题

该函数的功能是（ ）。

{{ select(35) }}

• 求 $x$ 在等差数列中的下标
• 判断 $x$ 是否为等差数列中的一项
• 求 $x$ 与等差数列某一项的最小距离
• 求 $x$ 与等差数列首项的差

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

完善程序（1）：第 k 小子段和

给定一个长度为 $n$、由正整数组成的序列 $a_1,a_2,\ldots,a_n$，共有 $\frac{n(n+1)}2$ 个子段。程序中 s 为前缀和数组。请补全程序，使 solve 返回所有子段和中的第 $k$ 小值。回答第 36—39 题。

using i64 = long long;
i64 s[100005];

bool check(int n, int k, i64 mid)
{
    i64 cnt = 0;
    for (int l = 1, r = 1; r <= n; ++r) {
        while (l <= r && ____(1)____) l++;
        cnt += ____(2)____;
    }
    return ____(3)____;
}

i64 solve(int n, int k, int a[])
{
    for (int i = 1; i <= n; ++i)
        s[i] = s[i - 1] + a[i];
    i64 lbound = 0, rbound = 5000000000, mid;
    while (lbound < rbound) {
        mid = (lbound + rbound) >> 1;
        if (check(n, k, mid))
            rbound = ____(4)____;
        else
            lbound = ____(5)____;
    }
    return lbound;
}

第 36 题

（1）处应填（ ）。

{{ select(36) }}

• s[1] > mid
• s[r] > mid
• s[r] - s[l-1] > mid
• s[r] - s[l] > mid

第 37 题

（2）处应填（ ）。

{{ select(37) }}

• 1
• r
• r - 1
• r - l + 1

第 38 题

（3）处应填（ ）。

{{ select(38) }}

• cnt < k
• cnt <= k
• cnt > k
• cnt >= k

第 39 题

（4）和（5）处应填（ ）。

{{ select(39) }}

• mid、mid + 1
• mid - 1、mid
• mid - 1、mid + 1
• mid、mid

完善程序（2）：分数化简与排版

给定一个分数 a / b，若它是假分数，请将它化简成带分数形式输出。例如 91 / 30 输出：

  1
3--
 30

当输入是真分数时，请将它化简后输出，并忽略整数部分。例如 30 / 100 输出：

 3
--
10

当输入的分数可以变成整数时，忽略分数部分。所有输出分数都应为既约分数。回答第 40—45 题。

#include <iostream>
using i64 = long long;

i64 gcd(i64 n, i64 m)
{
    if (m == 0) return n;
    else return gcd(m, n % m);
}

void print(char c, int a) {
    while (a > 0) {
        std::cout << c;
        a--;
    }
}

int length(int a) {
    if (a == 0) return 0;
    else return length(a / 10) + 1;
}

int main()
{
    i64 n, m;
    char c;
    std::cin >> n >> c >> m;
    auto d = ______(1)______;
    n = n / d;
    m = ______(2)______;
    auto z = ______(3)______;
    n = n % m;
    if (______(4)______) std::cout << z << "\n";
    else {
        print(' ', ______(5)______);
        std::cout << n << "\n";
        if (z > 0) std::cout << z;
        print('-', ______(6)______);
        std::cout << "\n";
        print(' ', length(z));
        std::cout << m << "\n";
    }
}

第 40 题

（1）处应填（ ）。

{{ select(40) }}

• gcd(n, m)
• n / m
• n % m
• m % n

第 41 题

（2）处应填（ ）。

{{ select(41) }}

• m / d
• m % d
• n / d
• d / m

第 42 题

（3）处应填（ ）。

{{ select(42) }}

• m / n
• n % m
• m % n
• n / m

第 43 题

（4）处应填（ ）。

{{ select(43) }}

• m == 0
• z == 0
• n == 0
• d == 1

第 44 题

（5）处应填（ ）。

{{ select(44) }}

• length(z) + length(n) - length(m)
• length(z) + length(m) - length(n)
• length(m) - length(n)
• length(z) - length(m) + length(n)

第 45 题

（6）处应填（ ）。

{{ select(45) }}

• length(n)
• length(z)
• length(m)
• length(n) + length(m)