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

原卷为《CSP-J/S模拟（六）》。依据原卷说明，J 组不做附加题；本卷仅收录第 1—45 题，共 100 分。

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

1. 若 $A,B,C,D$ 均为布尔变量，$\oplus$ 是异或运算，表达式 $(A\oplus B)\land(\neg B\lor C)\lor(B\land\neg C)$ 可化简为（ ）。

{{ select(1) }}

• $A\oplus B$
• $A\land B\lor\neg C$
• $(A\lor B)\land\neg C$
• $(A\oplus B)\lor(B\land\neg C)$

2. 在带尾指针 clist 的循环单链表中（结点数 $\ge 3$），下面操作描述正确的是（ ）。

{{ select(2) }}

• 头部插入：p -> next = clist -> next -> next; clist -> next = p;
• 尾部插入：p -> next = clist -> next; clist -> next = p; clist = p;
• 头部删除：p = clist -> next; clist -> next = p -> next -> next; delete p;
• 尾部删除：p = clist; clist = clist -> next; delete p;

3. 不合法的前缀码的组合为（ ）。

{{ select(3) }}

• (11,01,001,0001)
• (0,10,110,111)
• (1,01,001,000)
• (0,10,110,01)

4. 能将变量 x 最低处的 1 改为 0 的代码是（ ）。

{{ select(4) }}

• x ^= (x & -x)
• x = x ^ (x - 1)
• x |= (x >> 1)
• x = x | (x - 1)

5. 如果根结点的深度记为 $1$，则一棵恰有 $2026$ 个叶子结点的二叉树的深度可能是（ ）。

{{ select(5) }}

• $9$
• $10$
• $11$
• $12$

6. 定义一种字符串操作，一次可以将其中一个元素移到任意位置。举例说明，对于字符串 BCA 可以将 A 移到 B 之前，变成字符串 ABC。如果要将字符串 DACHEBGIF 变成 ABCDEFGHI，最少需要（ ）次操作。

{{ select(6) }}

• $2$
• $3$
• $4$
• $5$

7. 如果平面上任取 $n$ 个整点（横纵坐标都是整数），其中一定存在两个点，它们连线的中点也是整点，那么 $n$ 至少是（ ）。

{{ select(7) }}

• $2$
• $3$
• $5$
• $7$

8. 计算机中的数值信息分为整数和实数（浮点数）。实数之所以能够表示很大或者很小的数，是由于使用了（ ）。

{{ select(8) }}

• 阶码
• 补码
• 反码
• 较长的尾数

9. 下面关于指针的说法正确的是（ ）。

{{ select(9) }}

• 在 $64$ 位编译环境下，一个指针变量占 $8$ 字节
• 指针运算实际上是地址操作，只能取地址和间接访问，不能进行加减运算
• 数组名是指向数组元素的指针变量
• 指针只可以静态申请内存空间

10. 设有一个 $10$ 个顶点的完全图，每两个顶点之间都有一条边。有多少个长度为 $5$ 的环（ ）。

{{ select(10) }}

• $252$
• $1260$
• $3024$
• $5040$

11. 在 $3\times3$ 的棋盘上，初始时所有格子均为白色。每次操作可以选择任意一个格子，将其自身以及与其四连通（上下左右相邻）的所有格子颜色翻转（白变黑，黑变白）。若想将整个棋盘全部变为黑色，至少需要操作（ ）次。

{{ select(11) }}

• $3$
• $4$
• $5$
• $6$

12. 下列关于排序算法的说法中，正确的是（ ）。

{{ select(12) }}

• 快速排序在任何情况下时间复杂度都不超过 $\Theta(n\log n)$
• 归并排序是稳定排序，且在任何情况下时间复杂度均为 $\Theta(n\log n)$
• 插入排序在任何情况下时间复杂度均为 $\Theta(n^2)$
• 冒泡排序是不稳定排序，且空间复杂度为 $\Theta(1)$

13. 已知在 $k$ 进制下，等式 $123_k\times45_k=5777_k$ 成立，则 $k$ 的值为（ ）。

{{ select(13) }}

• $6$
• $7$
• $8$
• $9$

14. 在一个无向图中，如果任意两点之间都存在路径相连，则称其为连通图。现有一个拥有 $5$ 个顶点的无向完全图，共有 $10$ 条边，它是一个连通图。若要使它不再是连通图，至少要删去其中的（ ）条边。

{{ select(14) }}

• $1$
• $2$
• $3$
• $4$

15. 每个顶点度数均为 $2$ 的无向图称为“$2$ 正规图”。由编号为从 $1$ 到 $n$ 的顶点构成的所有 $2$ 正规图，其中包含欧拉回路的不同 $2$ 正规图的数量为（ ）。

{{ select(15) }}

• $n!$
• $(n-1)!$
• $\dfrac{n!}{2}$
• $\dfrac{(n-1)!}{2}$

二、阅读程序（判断题每题1分，选择题每题3分，共计40分；判断题正确填 T，错误填 F）

第1题

void print(int n)
{
    int r;
    if (n % 2 == 0) {
        r = 0;
    }
    else {
        r = 1;
    }
    int q = (n - r) / (-2);
    if (q != 0) {
        print(q);
    }
    std::cout << r;
}

16. 在 C/C++ 中，(-5) % 2 的值必然为 1（ ）。

{{ select(16) }}

• 正确
• 错误

17. 无论 $n$ 是正数、负数还是零，程序只会输出数字 0 和 1（ ）。

{{ select(17) }}

• 正确
• 错误

18. 调用 print(-7)，输出结果是（ ）。

{{ select(18) }}

• 111
• 1101
• 1001
• 11001

19. 若某次调用的输出为 11011，则传入的 $n$ 是（ ）。

{{ select(19) }}

• $-7$
• $27$
• $7$
• $-11$

20. print(n) 的时间复杂度为（ ）。

{{ select(20) }}

• $\Theta(\log |n|)$
• $\Theta(|n|)$
• $\Theta(|n|^2)$
• $\Theta(2^{|n|})$

二、阅读程序（判断题每题1分，选择题每题3分，共计40分；判断题正确填 T，错误填 F）

第2题

int solve(int n, int d, int x[])
{
    std::sort(x, x + n);
    int pair = 0;
    int j = 0;
    for (int i = 0; i < n; ++i)
    {
        while (j < n and x[j] - x[i] <= d)
        {
            j++;
        }
        pair += j - i - 1;
    }
    return pair;
}

21. 如果输入数据中所有点的坐标互不相同且 $d=0$，则程序输出 $0$（ ）。

{{ select(21) }}

• 正确
• 错误

22. 对于输入 $n=5,d=2,x=[3,1,4,1,5]$，程序输出为 $7$（ ）。

{{ select(22) }}

• 正确
• 错误

23. 若 $d>0$ 且 $n>0$，内层 while 循环的迭代次数总和为 $\Theta(n)$（ ）。

{{ select(23) }}

• 正确
• 错误

24. 不考虑 std::sort() 的运行时间，剩余程序的时间复杂度为（ ）。

{{ select(24) }}

• $\Theta(n)$
• $\Theta(n\log n)$
• $\Theta(n^2)$
• $\Theta(n\log d)$

25. 该程序的功能是（ ）。

{{ select(25) }}

• 统计满足 $i<j$ 且 $x[j]-x[i]\le d$ 的点对个数
• 统计满足 $|x_i-x_j|\le d$ 的有序点对数（即 $(i,j)$ 与 $(j,i)$ 各计一次）
• 统计排序后差值恰好等于 $d$ 的点对个数
• 求排序后相邻元素之差不超过 $d$ 的最长连续段长度

26. 若 $d>0$ 且 $n>0$，则程序结束时，变量 $j$ 的值（ ）。

{{ select(26) }}

• 一定等于 $n$
• 一定小于 $n$
• 一定等于 $1$
• 以上三种说法都不对

27. 当 $n=10$ 时，程序返回值的最大可能值为（ ）。

{{ select(27) }}

• $10$
• $20$
• $45$
• $90$

二、阅读程序（判断题每题1分，选择题每题3分，共计40分；判断题正确填 T，错误填 F）

第3题

using u64 = unsigned long long;
u64 decode(std::string code)
{
    if (code == "")
    {
        return 0;
    }
    char head = code[0];
    std::string tail = code.substr(1);
    if (head == '0')
    {
        return decode(tail);
    }
    else
    {
        u64 length = 1ULL << tail.size();
        u64 rev = decode(tail);
        return (length - rev) + (length - 1);
    }
}

28. decode("0110") 的返回值为 $4$（ ）。

{{ select(28) }}

• 正确
• 错误

29. 对两个只含有 0 与 1 的字符串 $s$ 与 $t$，若两者长度相同，且 $s\ne t$，则 decode 的返回值一定不同（ ）。

{{ select(29) }}

• 正确
• 错误

30. decode("111") 的返回值为 $7$（ ）。

{{ select(30) }}

• 正确
• 错误

31. s.substr(1) 的语义是构造一个从 s[1] 开始直到最后一个字符结束的子串（ ）。

{{ select(31) }}

• 正确
• 错误

32. 将所有长度相等的 01 串按 decode 值从小到大排列，任意相邻两个串恰好只有 $1$ 位不同（ ）。

{{ select(32) }}

• 正确
• 错误

33. 以下哪个输入字符串所对应的返回值为 $31$，且该字符串长度最短（ ）。

{{ select(33) }}

• 10000
• 010000
• 1001
• 11111

34. 下列输入中，输出最大的数是（ ）。

{{ select(34) }}

• "01111"
• "10110"
• "10100"
• "11111"

35. 以下错误的判断是（ ）。

{{ select(35) }}

• decode(s) 的奇偶性，与 01 字符串 s 中字符 '1' 个数的奇偶性相同
• decode("1010101010") + decode("0101010101") == 1023
• decode("010101") == decode("10101")
• decode("1010101010") + decode("0010101010") == 1023

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

第1题

给定 $n$ 个整数 $a_1,a_2,ldots,a_n$，每个数字都是 $0,1,2$ 中的一个。可以不断交换这个序列中的任意两个数字，目标是让这个序列成为升序，请问最少需要几次交换？

#include<iostream>
int a[1000005], c[3] = {0}, q[3][3] = {0}, sum;
void cal(int u, int v)
{
    int pair = std::min(____(1)____);
    sum += pair;
    q[u][v] -= pair;
    q[v][u] -= pair;
}
int main()
{
    int n;
    std::cin >> n;
    for (int i = 0; i < n; ++i) {
        std::cin >> a[i];
        ____(2)____;
    }
    for (int i = 0; i < n; ++i) {
        int from = ____(3)____;
        int to = 0;
        if (i >= c[0]) to++;
        ____(4)____ to++;
        q[from][to]++;
    }
    cal(0, 1);
    cal(0, 2);
    cal(1, 2);
    sum += 2 * (____(5)____);
    std::cout << sum << "\n";
}

36. （1）处应填（ ）。

{{ select(36) }}

• a[u], a[v]
• c[u], c[v]
• q[0][v], q[0][u]
• q[u][v], q[v][u]

37. （2）处应填（ ）。

{{ select(37) }}

• c[i]++
• c[a[i]]++
• c[i] + a[i]
• c[a[i]] = 1

38. （3）处应填（ ）。

{{ select(38) }}

• 0
• a[i]
• c[i]
• c[a[i]]

39. （4）处应填（ ）。

{{ select(39) }}

• if (i >= c[1])
• else if (i >= c[1])
• if (i >= c[0] + c[1])
• else if (i >= c[0] + c[1])

40. （5）处应填（ ）。

{{ select(40) }}

• q[0][1] + q[0][2]
• q[1][0] + q[0][2]
• q[1][2] + q[2][0]
• q[1][0] + q[2][1]

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

第2题

自助餐厅有 $N$ 种菜，每种菜只能点一次。当点了某道菜时，这道菜会立即出现。吃第 $i$ 种菜耗时 $A_i$、美味度为 $B_i$。需要吃完一道菜才能点下一道。最后一道菜的点单时刻需要严格早于一个给定的整数 $T$。点单停止后，还可以继续吃端上来的菜。求可以得到的最大美味度总和。

int solve(int N, int T, int A[], int B[])
{
    int f[3001][3000] = {0};
    int g[3001][3000] = {0};
    for (int i = 0; i < N; ++i) {
        int a = A[i];
        int b = B[i];
        for (int x = ____(1)____ )
        {
            f[i + 1][x] = std::max(f[i][x], ____(2)____ );
        }
        for (int x = a - 1; x >= 0; x--)
        {
            f[i + 1][x] = f[i][x];
        }
    }
    for (int i = 0; i < N; ++i)
    {
        int a = A[____(3)____];
        int b = B[____(4)____];
        for (int x = T - 1; x >= a; x--)
        {
            g[i + 1][x] = std::max(g[i][x], g[i][x-a] + b);
        }
        for (int x = ____(5)____ )
        {
            g[i + 1][x] = g[i][x];
        }
    }
    int max = 0;
    for (int last = 0; last < N; ++last)
    {
        for (int t0 = 0; t0 < T; ++t0)
        {
            for (int t1 = ____(6)____; ____(7)____ < T; ++t1) {
                max = std::max(max, ____(8)____ );
            }
        }
    }
    return max;
}

41. （1）（2）处应填（ ）。

{{ select(41) }}

• a; x < T; x--，f[i][x - a] + b
• T - 1; x >= 0; x--，f[i][x + a] + b
• T - 1; x >= a; x--，f[i][x - a] + b
• T - 1; x >= 0; x--，f[i][x - a] + b

42. （3）（4）处应填（ ）。

{{ select(42) }}

• i, i
• N - i, N - i
• N - i - 1, N - i - 1
• i + 1, i + 1

43. （5）处应填（ ）。

{{ select(43) }}

• a - 1; x >= 0; x--
• a; x >= 0; x--
• T - 1; x >= 0; x--
• 0; x <= a; x++

44. （6）（7）处应填（ ）。

{{ select(44) }}

• 0, t1
• t0, t1
• t0, t0 + t1
• 0, t0 + t1

45. （8）处应填（ ）。

{{ select(45) }}

• f[last][t0] + g[N - last][t1] + B[last]
• f[last][t0] + g[last][t1] + B[last]
• f[last][t0] + g[N - 1 - last][t1]
• f[last][t0] + g[N - 1 - last][t1] + B[last]