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

本卷共 43 题，满分 100 分。

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

1. 以补码存储的 8 位有符号整数 10110111 的十进制表示为（ ）。

{{ select(1) }}

• -73
• 183
• 72
• -72

2. 现有一段 24 分钟的视频文件，帧率为 30 Hz，分辨率为 $1920\times1080$，每帧是 32 位真彩色图像，视频编码算法达到 25% 的压缩率。该视频文件占用的存储空间约为（ ）。

{{ select(2) }}

• 668 GiB
• 334 GiB
• 85 GiB
• 500 GiB

3. 链接器的功能是（ ）。

{{ select(3) }}

• 把源代码转换成特定硬件平台的机器指令
• 把机器指令组合成完整的可执行程序
• 把源代码转换成可执行程序
• 把高级语言翻译成低级语言

4. 对一个有 $n$ 个顶点、$m$ 条边的带正权有向简单图使用 Dijkstra 算法计算单源最短路。若所用堆可以在 $\Theta(\log n)$ 时间查询最小值、在 $\Theta(\sqrt n)$ 时间合并两个堆、在 $\Theta(1)$ 时间将堆内一个元素变小，并在 $\Theta(\log n)$ 时间弹出最小值，则整个算法的时间复杂度为（ ）。

{{ select(4) }}

• $\Theta(n\sqrt n+m\log n)$
• $\Theta((n+m)\log n)$
• $\Theta(m+n\log n)$
• $\Theta(m\sqrt n+n\log n)$

5. 具有 $n$ 个顶点、$m$ 条边的连通图采用邻接矩阵存储，进行深度优先遍历的时间复杂度为（ ）。

{{ select(5) }}

• $\Theta(n^3)$
• $\Theta(n^2)$
• $\Theta(n+m)$
• $\Theta(m^2)$

6. 下列算法中，没有运用分治思想的一项是（ ）。

{{ select(6) }}

• 归并排序算法
• 求二叉树的前序遍历
• 快速排序算法
• 求二叉树的层次遍历

7. 前缀表达式 * + a b + c d 的中缀形式是（ ）。

{{ select(7) }}

• (a + b) * (c + d)
• a + b * c + d
• a * b + c * d
• (d + c) * (b + a)

8. 有 5 个分别标号为 1 到 5 的小球和 5 个同样标号的盒子。将小球随机放入盒子，每个盒子恰放 1 个小球，每个盒子中的小球都与盒子标号不同的概率是（ ）。

{{ select(8) }}

• $\frac{24}{625}$
• $\frac7{20}$
• $\frac{43}{120}$
• $\frac{11}{30}$

9. 设 x=true, y=false, z=true。以下逻辑表达式的值为 true 的是（ ）。

{{ select(9) }}

• $(\lnot x\lor y)\land z$
• $(y\land z)\lor(x\land y)$
• $(x\land y)\lor z$
• $(x\land z)\land y$

10. 某算法的计算时间满足 $T(n)=3T(n/2)+\Theta(n)$，$T(1)=\Theta(1)$，则其时间复杂度为（ ）。

{{ select(10) }}

• $\Theta(n)$
• $\Theta(n^{\log_2 3})$
• $\Theta(n\log n)$
• $\Theta(n^{\log_2 3}\log n)$

11. 在一条长度为 1 的线段上随机取一点，再在以原线段左端点和该点为端点的线段上随机取一点，则以两次取得的点为端点的线段的期望长度是（ ）。

{{ select(11) }}

• $\frac12$
• $\frac13$
• $\frac14$
• $\frac23$

12. 以下排序算法中，最好情况下时间复杂度与最坏情况下时间复杂度相同的是（ ）。

{{ select(12) }}

• 选择排序
• 冒泡排序
• 插入排序
• 快速排序

13. 有 4 个结点和 4 条边的有标号简单无向图的数量是（ ）。

{{ select(13) }}

• 15
• 16
• 6
• 4

14. 1946 年，（ ）提出了存储程序原理，奠定了现代电子计算机的基本结构。

{{ select(14) }}

• 艾伦·麦席森·图灵（Alan Mathison Turing）
• 约翰·冯·诺依曼（John von Neumann）
• 克劳德·艾尔伍德·香农（Claude Elwood Shannon）
• 罗伯特·塔扬（Robert Tarjan）

15. 在计算机非专业级别软件能力认证 CSP-S 进行时，下列行为中被允许的是（ ）。

{{ select(15) }}

• 使用 SSH 协议远程登录其他计算机以获取试题等文件
• 编写程序在评测环境中修改输入文件
• 使用 U 盘拷贝题目、下发文件或自己的代码供赛后复盘
• 通过枚举输入文件的可能情况获得答案并写入源代码

二、阅读程序（程序一）

#include <cstdio>
#include <cstring>

using namespace std;

char s[10000];
int cnt[26];

int main() {
    scanf("%s", s);
    for (int i = 0; i < strlen(s); ++i) {
        if (cnt[s[i] - 'a'] <= 50) {
            s[strlen(s)] = s[i];
        }
        ++cnt[s[i] - 'a'];
    }
    printf("%s\n", s);
    return 0;
}

假设初始时输入的字符串长度不超过 500，且不是空串。

16. 将程序第 11 行中的 ++i 改为 i++，程序运行结果不会改变。（ ）

{{ select(16) }}

• 正确
• 错误

17. 将程序第 11 行改为 for (int i=0, len=strlen(s); i<len; ++i)，程序运行结果不会改变，同时运行效率将得到提升。（ ）

{{ select(17) }}

• 正确
• 错误

18. 对于任意一个包含 a 到 z 全部字符、且各字符出现次数均不少于 50 的字符串 $b$，总存在一个字符串 $a$，使字符串 $a$ 输入程序后的输出为字符串 $b$。（ ）

{{ select(18) }}

• 正确
• 错误

19. 程序输出字符串的长度一定不小于 1300（$1300=50\times26$）。（ ）

{{ select(19) }}

• 正确
• 错误

20. 设输入字符串长度为 $x (1\le x\le 500)$，输出字符串长度为 $y$，则关于 $x,y$ 的关系正确的是（ ）。

{{ select(20) }}

• 对全部输入字符串都有 $x=y$
• 对全部输入字符串都有 $x<y$
• 有些输入满足 $x=y$，有些满足 $x<y$，但不存在 $x>y$
• 有些输入满足 $x=y$，有些满足 $x>y$，还有些满足 $x<y$

21. 设字符串 $w$ 为 abcdefghijklmnopqrstuvwxyz。若输入为 $w$ 重复两次的结果，则输出为（ ）。

{{ select(21) }}

• $w$ 重复 50 次
• $w$ 重复 51 次
• $w$ 重复 52 次
• $w$ 重复 53 次

二、阅读程序（程序二）

#include <cstdio>

const int N = 5010;
const int M = 20010;
const int inf = 1073741823;

int e, bg[N], nx[M], to[M], wt[M];

inline void link(int u, int v, int w) {
    to[++e] = v;
    nx[e] = bg[u];
    wt[e] = w;
    bg[u] = e;
}

int n, m, u, v, w;
int f[N], h[N << 1];

void update(int x, int y) {
    x += n - 1;
    for (h[x] = y; x; x >>= 1)
        h[x >> 1] = f[h[x]] < f[h[x ^ 1]] ? h[x] : h[x ^ 1];
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i != m; ++i) {
        scanf("%d%d%d", &u, &v, &w);
        link(u, v, w);
    }
    int nn = n << 1;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j != nn; ++j)
            h[j] = 0;
        for (int j = 0; j <= n; ++j)
            f[j] = inf;
        f[i] = 0;
        update(i, i);
        for (int j = i; true; j = h[1]) {
            if (f[j] == inf) break;
            for (int k = bg[j]; k; k = nx[k]) {
                if (f[j] + wt[k] < f[to[k]]) {
                    f[to[k]] = f[j] + wt[k];
                    update(to[k], to[k]);
                }
            }
            update(j, 0);
        }
        for (int j = 1; j <= n; ++j)
            printf("%d%c", f[j], "\n "[j != n]);
    }
    return 0;
}

程序输入一张带边权的有向图。

22. 将程序中所有的 != 替换为 <，程序仍能正常运行且输出结果不变。（ ）

{{ select(22) }}

• 正确
• 错误

23. 为了保证程序正常运行，输入的边数必须不大于 $2\times10^4$。（ ）

{{ select(23) }}

• 正确
• 错误

24. 程序的输出是一个 $n\times n$ 的整数矩阵。（ ）

{{ select(24) }}

• 正确
• 错误

25. 将程序第 34 行的 j=0 替换为 j=1，程序仍能正常运行且输出结果不变。（ ）

{{ select(25) }}

• 正确
• 错误

26. 当图中所有边的边权均为相同的正整数，且 $\sum_i w_i<1073741823$ 时，update 函数被调用的次数为（ ）。

{{ select(26) }}

• $\Theta(n^2)$
• $\Theta(nm)$
• $\Theta(n^2+nm)$
• $\Theta(n\min(n,m))$

27. 当输入边权均为正整数时，程序在最坏情况下的时间复杂度为（ ）。

{{ select(27) }}

• $\Theta(n^3)$
• $\Theta(n^2\log n+nm)$
• $\Theta(nm\log n)$
• $\Theta(n^2m)$

二、阅读程序（程序三）

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

#define N 105
#define INF 1e9

int dis1[N][N], dis2[N][N];
int mp[N][N], n, m;

void fun1(int dis[N][N]) {
    static bool vis[N];
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            dis[i][j] = mp[i][j];
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) vis[j] = 0;
        for (int k = 1; k <= n; k++) {
            int now = 0;
            for (int j = 1; j <= n; j++) {
                if (!vis[j] && (!now || dis[i][now] > dis[i][j]))
                    now = j;
            }
            vis[now] = 1;
            for (int j = 1; j <= n; j++) {
                if (!vis[j] && dis[i][j] > dis[i][now] + mp[now][j]) {
                    dis[i][j] = dis[i][now] + mp[now][j];
                }
            }
        }
    }
}

void fun2(int dis[N][N]) {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            dis[i][j] = mp[i][j];
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            for (int k = 1; k <= n; k++) {
                dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
            }
        }
    }
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i == j) mp[i][j] = 0;
            else mp[i][j] = INF;
        }
    }
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        mp[u][v] = w;
    }
    fun1(dis1);
    fun2(dis2);
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (dis1[i][j] != dis2[i][j])
                ans++;
        }
    }
    cout << ans << endl;
    return 0;
}

输入满足 $1\le n\le 100$，$1\le m\le \frac{n(n-1)}2$；只保证不存在重边，即不存在 $(u_i,v_i)=(u_j,v_j)$（$i ≠ j$）；边权 $w_i\in[1,10^6]$。如果 $u$ 到 $v$ 不可达，则认为距离为 INF。

28. 代码中的 dis1[i][j] 不一定是从 $i$ 到 $j$ 的最短路。（ ）

{{ select(28) }}

• 正确
• 错误

29. 程序输出可能为 1。（ ）

{{ select(29) }}

• 正确
• 错误

30. 将第 19 行的 k <= n 修改为 k < n，不影响答案。（ ）

{{ select(30) }}

• 正确
• 错误

31. 对于稀疏图（$n,m$ 不同阶），fun1() 对单个 $i$ 求出全部 dis[i][j]，最快可以做到 $\Theta((n+m)\log m)$。（ ）

{{ select(31) }}

• 正确
• 错误

32. 对于下列输入，程序输出为（ ）。

5 8
3 2 2
2 4 2
1 4 3
3 1 2
4 3 3
5 2 3
1 5 1
1 2 2

{{ select(32) }}

• 2
• 3
• 4
• 5

33. 若输入数据中 $n=5$，输出 ans 的最大可能值为（ ）。

{{ select(33) }}

• 4
• 5
• 6
• 7

三、完善程序（程序一：装备穿戴问题）

有 $n$ 件装备，穿戴第 $i$ 件装备需要玩家的力量值至少为 $a_i$，穿戴后力量值增加 $b_i$。求能够以某种顺序穿戴全部装备所需的最小初始力量值。

输入第一行为整数 $n (1\le n\le 10^3)$；第二行有 $n$ 个整数 $a_i (0\le a_i\le 10^9)$；第三行有 $n$ 个整数 $b_i (0\le b_i\le 10^6)$。

提示：使用二分加贪心，先对装备排序，再二分答案并按顺序验证。

#include <cstdio>
#include <algorithm>

using namespace std;

const int maxn = 1005;

int n;
int a[maxn], b[maxn], c[maxn];

bool Comp(const int &x, const int &y) {
    // 你可以简单地认为括号内的内容等价于 (int x, int y)
    return ①;
}

bool check(int x) {
    for (int i = 1; i <= n; ++i) {
        int u = c[i];
        if (②) {
            x += b[u];
        } else {
            return false;
        }
    }
    return true;
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) scanf("%d", a + i);
    for (int i = 1; i <= n; ++i) scanf("%d", b + i);
    for (int i = 1; i <= n; ++i) c[i] = i;
    sort(c + 1, c + 1 + n, Comp);
    int ans = 1145141919;
    for (int l = 1, r = ans, mid = (l + r) / 2; ③; mid = (l + r) / 2)
        if (check(mid)) {
            ans = mid;
            ④;
        } else {
            ⑤;
        }
    printf("%d\n", ans);
    return 0;
}

34. ①处应填（ ）。

{{ select(34) }}

• a[x] > a[y]
• a[x] < a[y]
• a[x] >= a[y]
• a[x] <= a[y]

35. ②处应填（ ）。

{{ select(35) }}

• x < a[i]
• x < a[u]
• x >= a[i]
• x >= a[u]

36. ③处应填（ ）。

{{ select(36) }}

• l < r
• l <= r
• check(l)
• check(r)

37. ④处应填（ ）。

{{ select(37) }}

• r = mid - 1
• r = mid + 1
• l = mid - 1
• l = mid + 1

38. ⑤处应填（ ）。

{{ select(38) }}

• r = mid - 1
• r = mid + 1
• l = mid - 1
• l = mid + 1

三、完善程序（程序二：打音游）

一款音游共有 $n$ 个音符，将一千万分平分给所有音符得到基础分 $x=10^7/n$（保留非整数部分）。其中 $m$ 个音符根据是否击中可获得 $x+1$ 分或 0 分；其余 $n-m$ 个音符根据击中精度可获得 $x+1、x、x/2、0$ 分之一。总得分向下取整。给定 $n,m$，求可能得到的不同分数数量。

输入为两个非负整数 $n,m$，满足 $1\le n\le 10^7$，$0\le m\le n$；输出一个正整数。

#include <iostream>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    if (m == n) {
        cout << ① << endl;
        return 0;
    }
    long long M = 10000000;
    int ans = ②;
    int lst = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j >= 0; --j) {
            int lower = max(0, ③);
            int upper = i - j;
            int base = ④;
            ans += upper - lower + 1;
            if (lower + base <= lst) ans -= lst - (lower + base) + 1;
            lst = ⑤;
        }
    }
    cout << ans << endl;
    return 0;
}

39. ①处应填（ ）。

{{ select(39) }}

• -1
• n - 1
• n
• n + 1

40. ②处应填（ ）。

{{ select(40) }}

• -1
• 0
• 1
• n

41. ③处应填（ ）。

{{ select(41) }}

• i - (n - m) - 1
• i - (n - m) - j
• i - (n - m)
• i - (n - m) + 1

42. ④处应填（ ）。

{{ select(42) }}

• (2 * i + j) * M / (2 * n)
• (2 * i - j) * M / (2 * n)
• i * M / n + j * M / (2 * n)
• i * M / n - j * M / (2 * n)

43. ⑤处应填（ ）。

{{ select(43) }}

• base + upper
• base + upper + 1
• base + lower
• base + lower + 1