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

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

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

1. 十进制数 114 的相反数的 8 位二进制补码是（ ）。

{{ select(1) }}

• 10001110
• 10001101
• 01110010
• 01110011

2. 以下哪个网站不是 Online Judge（在线程序判题系统）？Online Judge 可以查看算法题目、提交程序并获得评测反馈。（ ）

{{ select(2) }}

• Luogu
• Gitee
• LeetCode
• Codeforces

3. 小 A 用字母 A 表示 1，B 表示 2，以此类推，用 26 表示 Z。对于 27 以上的数字，可以用两位或更长的字符串对应，例如 AA 对应 27，AB 对应 28，AZ 对应 52，AAA 对应 703。那么 BYT 对应的数字是（ ）。

{{ select(3) }}

• 2018
• 2020
• 2022
• 2024

4. UIM 拍摄了一张分辨率为 4096×2160 的照片，每个像素都是 24 位真彩色。在没有压缩的情况下，这张图片占用空间最接近（ ）。

{{ select(4) }}

• 8 MB
• 25 MB
• 200 MB
• 200 KB

5. 在一个长度为 n 的数组中找到第 k 大的数字，平均时间复杂度最低可以达到（ ）。

{{ select(5) }}

• $O(n)$
• $O(nk)$
• $O(nlog n)$
• $O(n^2)$

6. 对于“树”这种数据结构，正确的说法有（ ）。

① 一个有 n 个顶点、n-1 条边的图是树；② 一棵树中的任意两个顶点之间有且只有一条简单路径；③ 树中一定存在度数不大于 1 的顶点；④ 树可能存在环。

{{ select(6) }}

• ①②④
• ①②③
• ②③
• ①②

7. 博文中学进行了一次考试，优、良、及格、不及格的试卷分别有 10、13、14、5 张。现将试卷按等级分为 4 叠：每次把一叠含不同等级的试卷分成两堆，使两堆中没有相同等级的试卷，直至得到 4 叠。把一堆 n 张试卷分成两堆会产生 n 次“分卷子”操作。至少需要多少次操作？

{{ select(7) }}

• 84
• 93
• 78
• 85

8. 一棵二叉树的前序遍历为 HGBDAFEC，中序遍历为 BGHFAEDC。采用顺序存储，根结点下标为 1，结点 i 的左右孩子下标分别为 2i 和 2i+1，则数组最大下标至少为（ ）。

{{ select(8) }}

• 7
• 13
• 15
• 12

9. 在 C++ 中，如果 a=1, b=0, c=1，以下表达式中值为 1 的是（ ）。

{{ select(9) }}

• a&&b || b&&c
• a+b>c || b
• !(!c&&(!a||b))
• a+b+c

10. 在一个初始长度为 n 的链表中连续进行 k 次操作：每次读入 aᵢ、bᵢ，找到值为 aᵢ 的结点（保证存在），将 bᵢ 插入该结点前。在最理想情况下，不计待插入结点，最少可能访问多少个结点？

{{ select(10) }}

• n 次
• k 次
• nk 次
• n+k 次

11. A 班、B 班、C 班分别有 5、4、3 名风纪委员。现选取 6 名风纪委员巡逻，如果只关注各班派出的人数，有多少种不同方案？

{{ select(11) }}

• 9
• 12
• 15
• 18

12. 以下哪种排序算法的时间复杂度是 $O(n^2)$？

{{ select(12) }}

• 计数排序
• 插入排序
• 希尔排序
• 归并排序

13. 已知 rand() 可以生成 0 到 32767 的随机整数。若希望得到范围在 [a,b) 的随机整数，a、b 均是不超过 100 的正整数且 a<b，可行的表达式是（ ）。

{{ select(13) }}

• (rand()%(b-a))+a
• (rand()%(b-a+1))+a
• (rand()%(b-a))+a+1
• (rand()%(b-a+1))+a+1

14. 一个有 7 个顶点的完全图至少删掉多少条边才能变为森林？

{{ select(14) }}

• 16
• 21
• 15
• 6

15. 2020 年 8 月，第（ ）届全国青少年信息学奥林匹克竞赛在（ ）举行。

{{ select(15) }}

• 26，广州
• 26，长沙
• 37，广州
• 37，长沙

二、阅读程序（判断题请选择“正确”或“错误”；除特殊说明外，判断题 2 分、选择题 3 分，共 40 分）

程序（1）

#include <iostream>
using namespace std;
#define MAXN 20
int gu[MAXN][MAXN];
int luo(int n, int m) {
    if (n <= 1 || m < 2)
        return 1;
    if (gu[n][m] != -1)
        return gu[n][m];
    int ans = 0;
    for (int i = 0; i < m; i += 2)
        ans += luo(n - 1, i);
    gu[n][m] = ans;
    return ans;
}
int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < MAXN; i++)
        for (int j = 0; j < MAXN; j++)
            gu[i][j] = -1;
    cout << luo(n, m);
    return 0;
}

16. luo 函数中，参数 m 的值不可能是奇数。（ ）

{{ select(16) }}

• 正确
• 错误

17. 若将第 11 行循环条件中的 < 改为 <=，程序的输出结果可能会改变。（ ）

{{ select(17) }}

• 正确
• 错误

18. 若删除第 8、9、13 行，程序运行结果不变。（ ）

{{ select(18) }}

• 正确
• 错误

19. 在添加合适头文件后，将第 19～21 行替换为 memset(gu, 255, sizeof(gu)); 可以起到相同作用。（ ）

{{ select(19) }}

• 正确
• 错误

20. 若输入数据为 4 8，则输出为（ ）。

{{ select(20) }}

• 7
• 8
• 15
• 16

21. 最坏情况下，此程序的时间复杂度是（ ）。

{{ select(21) }}

• $O(m^2n)$
• $O(nm!)$
• $O(n^2)$
• $O(n^2m)$

二、阅读程序（判断题请选择“正确”或“错误”；除特殊说明外，判断题 2 分、选择题 3 分，共 40 分）

程序（2）

#include <cstdio>
#include <cstring>
using namespace std;
int n, m;
int f[101][101];
int F[101][101];
int main() {
    scanf("%d%d", &n, &m);  // n 的值在 1 到 100 之间
    memset(f, -1, sizeof(f));
    for (int i = 1; i <= m; i++) {
        int u, v, w;  // w 的值在 0 到 10000 之间
        scanf("%d%d%d", &u, &v, &w);
        f[u][v] = f[v][u] = w;
    }
    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                if (f[i][k] != -1 && f[k][j] != -1)
                    if (f[i][j] == -1 || f[i][j] > f[k][j] + f[i][k])
                        f[i][j] = f[i][k] + f[k][j];
    int ans = 2147483647;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) {
            for (int x = 1; x <= n; x++)
                for (int y = 1; y <= n; y++)
                    F[x][y] = f[x][y];
            F[i][j] = F[j][i] = 0;
            for (int x = 1; x <= n; x++)
                for (int y = 1; y <= n; y++)
                    if (F[x][y] == -1 || F[x][y] > F[x][i] + F[i][y])
                        F[x][y] = F[x][i] + F[i][y];
            for (int x = 1; x <= n; x++)
                for (int y = 1; y <= n; y++)
                    if (F[x][y] == -1 || F[x][y] > F[x][j] + F[j][y])
                        F[x][y] = F[x][j] + F[j][y];
            int res = 0;
            for (int x = 1; x <= n; x++)
                for (int y = 1; y < x; y++)
                    res += F[x][y];
            ans = min(res, ans);
        }
    printf("%d\n", ans);
    return 0;
}

22. 将第 14～16 行从外层到内层的循环变量依次调整为 i、j、k，程序运行结果不变。（ ）

{{ select(22) }}

• 正确
• 错误

23. 这个程序的时间复杂度和 m 无关。（ ）

{{ select(23) }}

• 正确
• 错误

24. 第 20 行的 ans 若初始化为 $10^7$，可能无法得到正确结果。（ ）

{{ select(24) }}

• 正确
• 错误

25. 若将第 27～30 行与第 31～34 行两个部分互换，程序运行结果不变。（ ）

{{ select(25) }}

• 正确
• 错误

26. 若输入数据为 4 5/1 2 3/1 3 6/2 3 4/2 4 7/3 4 2（其中 / 为换行符），则输出为（ ）。

{{ select(26) }}

• 14
• 18
• 21
• 28

27. 这个程序使用了（ ）算法。

{{ select(27) }}

• Floyd
• Dijkstra
• Prim
• Kruskal

二、阅读程序（判断题请选择“正确”或“错误”；除特殊说明外，判断题 2 分、选择题 3 分，共 40 分）

程序（3）

#include <bits/stdc++.h>
using namespace std;
#define MOD 19260817
#define MAXN 1005
long long A[MAXN][MAXN] = {0}, sum[MAXN][MAXN] = {0};
int n, m, q;
int main() {
    A[1][1] = A[1][0] = 1;
    for (int i = 2; i <= 1000; i++) {
        A[i][0] = 1;
        for (int j = 1; j <= i; j++)
            A[i][j] = (A[i - 1][j] + A[i - 1][j - 1]) % MOD;
    }
    for (int i = 1; i <= 1000; i++)
        for (int j = 1; j <= 1000; j++)
            sum[i][j] = (sum[i - 1][j] + sum[i][j - 1]
                         - sum[i - 1][j - 1] + A[i][j] + MOD) % MOD;
    int q;
    cin >> q;
    while (q--) {
        int n, m;
        cin >> n >> m;
        cout << sum[n][m] << endl;
    }
    return 0;
}

28. 当 i<=j 时，A[i][j] 的值是 0。（ ）

{{ select(28) }}

• 正确
• 错误

29. 当 i>j 时，A[i][j] 的值相当于从 i 个不同元素中取出 j 个元素的排列数。（ ）

{{ select(29) }}

• 正确
• 错误

30. sum[i][j] 的值（1<j<i≤1000）不小于 sum[i-1][j-1] 的值。（ ）

{{ select(30) }}

• 正确
• 错误

31. 若将第 12 行改为 A[i][j]=(A[i-1][j]+A[i-1][j-1]+MOD)%MOD;，程序运行结果不变。（ ）

{{ select(31) }}

• 正确
• 错误

32. A[i][j]（1≤i≤10，1≤j≤10）的所有元素中，最大值是（ ）。

{{ select(32) }}

• 126
• 276
• 252
• 210

33. 若输入数据为 1/5 3（其中 / 为换行符），则输出为（ ）。

{{ select(33) }}

• 10
• 35
• 50
• 24

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

程序（1）

（封禁账号）现有 n 个账号（编号为 1 到 n），每个账号都有一个关注者，第 i 个账号的关注者是 aᵢ。管理员要封禁一些账号；若封禁了第 i 个账号，为了不打草惊蛇，就不能封禁它的关注者 aᵢ。求最多可以封禁多少个账号。输入第一行是不超过 300000 的整数 n，第二行是 n 个 1 到 n 的整数 aᵢ；输出一个整数表示答案。

#include <cstdio>
using namespace std;
#define MAXN 300005
int n, ans = 0, a[MAXN], in[MAXN] = {0};
bool vis[MAXN] = {0};
void dfs(int cur, int w) {
    if (vis[cur])
        return;
    vis[cur] = true;
    if (w == 1) ans++;
    ①
    if (②)
        dfs(a[cur], ③);
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        in[a[i]]++;
    }
    for (int i = 1; i <= n; i++)
        if (!in[i]) ④;
    for (int i = 1; i <= n; i++)
        if (⑤) dfs(i, 0);
    printf("%d\n", ans);
    return 0;
}

34. ①处应填（ ）。

{{ select(34) }}

• a[cur] = cur;
• in[a[cur]] = 0;
• in[a[cur]]--;
• in[cur]--;

35. ②处应填（ ）。

{{ select(35) }}

• in[a[cur]] != 0 || w == 1
• in[a[cur]] == 0 || w == 0
• in[a[cur]] != 0 || w == 0
• in[a[cur]] == 0 || w == 1

36. ③处应填（ ）。

{{ select(36) }}

• 0
• 1
• w
• 1-w

37. ④处应填（ ）。

{{ select(37) }}

• dfs(i, 1)
• dfs(i, 0)
• dfs(a[i], 1)
• dfs(a[i], 0)

38. ⑤处应填（ ）。

{{ select(38) }}

• !in[i]
• in[i]
• !vis[i]
• vis[i]

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

程序（2）

（烧作业）某课外作业布置了 N（3≤N≤100000）个题目，第 i 题得分为 aᵢ。作业总分为去掉得分最小的一题后，其余题目得分的平均值。前 K（1≤K≤N-2）题被烧毁后，只对第 K+1 题到最后一题按上述规则计分。求能取得最高得分的所有 K，并按升序输出。输入各题得分均为不超过 10000 的非负整数。

#include <cstdio>
#include <cmath>
#define min(a,b) (a<b?a:b)
#define MAXN 100002
using namespace std;
int n, k[MAXN], cnt = 0;
int s[MAXN], minScore, sum;
double maxAverage = 0, nowAverage;
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &s[i]);
    minScore = s[n];
    ①;
    for (int i = n - 1; i >= 2; i--) {
        minScore = min(minScore, s[i]);
        ②;
        nowAverage = ③;
        if (nowAverage > maxAverage) {
            ④
            maxAverage = nowAverage;
        } else if (fabs(nowAverage - maxAverage) < 1e-6)
            ⑤;
    }
    for (int i = cnt; i >= 1; i--)
        printf("%d\n", k[i]);
    return 0;
}

39. ①处应填（ ）。

{{ select(39) }}

• sum = n
• sum = s[1]
• sum = s[n]
• sum = 0

40. ②处应填（ ）。

{{ select(40) }}

• sum = maxAverage * (n-i)
• sum += s[i]
• sum += s[n-i]
• sum = s[i] + minScore

41. ③处应填（ ）。

{{ select(41) }}

• (double)(sum + minScore)/(n-i)
• sum * 1.0/(n-i)
• (int)(sum - minScore)/(n-i)
• (double)(sum - minScore)/(n-i)

42. ④处应填（ ）。

{{ select(42) }}

• k[++cnt] = i;
• k[cnt++] = i-1;
• cnt = 1; k[cnt] = i-1;
• cnt = 0; k[cnt] = i;

43. ⑤处应填（ ）。

{{ select(43) }}

• k[cnt++] = i;
• k[++cnt] = i-1;
• k[cnt++] = n-i;
• k[cnt] = i;