初赛第十一场比赛试卷

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

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

1. 网址 www.gespoj.com 当中，顶级域名是（ ）。

{{ select(1) }}

• www
• cn
• com
• luogu

2. 以下物品可以携带进 CSP 第二轮测试考场的是（ ）。

{{ select(2) }}

• 可以发出巨大响声的发光机械键盘
• 写有 kkksc03 签名的《深入浅出程序设计竞赛 基础篇》的封皮
• 印有 dzd 照片（已设法获得其授权）的文化衫 T 恤
• 具有拍照功能的游标卡尺

3. 将元素 a,b,c,d,e,f 依次入栈，则以下选项中不可能的出栈序列是（ ）。

{{ select(3) }}

• b,d,c,f,e,a
• f,e,d,c,b,a
• d,c,e,b,f,a
• d,c,f,b,e,a

4. “流程结构”包括顺序结构、分支结构和循环结构。下列诗歌片段中体现循环结构的是（ ）。

{{ select(4) }}

• 如果还能找到你，就让风儿告诉你。
• 只要我还能够行走，只要我还能够张望，只要我还能够呼吸，就一直走向前方。
• 昔闻洞庭水，今上岳阳楼。
• 啊如果我在战斗中牺牲，啊朋友再见吧，再见吧，再见吧！如果我在战斗中牺牲，你一定把我来埋葬。

5. 已知两个二进制整数 $a=1010001010_{(2)}$、$b=1110100110_{(2)}$，则表达式 (a&b)^(a|b) 的值为（ ）。

{{ select(5) }}

• $0011011010_{(2)}$
• $0100101100_{(2)}$
• $0011010010_{(2)}$
• $0100101000_{(2)}$

6. 一个有 10 个结点的有向图，要使得每一个满足 $1 \le i,j \le 10, i \ne j$ 的点对 $(i,j)$ 都存在一条从 $i$ 到达 $j$ 的路径，至少需要连（ ）条有向边。

{{ select(6) }}

• 9
• 10
• 19
• 20

7. 观察下列代码：

int a[] = {5, 4, 3, 2, 1};
auto p = a + 3;
auto q = &p;
(*q)++;
auto k = *p;

其中，$k$ 的类型以及 $k$ 的值分别为（ ）。

{{ select(7) }}

• int 类型，值为 1
• int 类型，值为 3
• int 指针类型，值为 a 数组下标为 3 的元素的地址
• int 指针类型，值为 a 数组下标为 4 的元素的地址

8. 中缀表达式 a+(b+c)-d*e/f 改写成后缀表达式为（ ）。

{{ select(8) }}

• a b + c + d e * f / -
• a b c + + d e * f / -
• a b + c + d * e f / -
• a b c + + d * e / f -

9. 一张大小为 $6114 \times 8192$ 的 24 位彩色图片，使用 .bmp 格式存储，占用的空间大小约为（ ）。

{{ select(9) }}

• 144 MiB
• 288 MiB
• 1152 MiB
• 48 MiB

10. 以下程序片段的时间复杂度为（ ）。

int cnt = 0;
for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j += i) {
        for (int k = 1; k <= n; k += j) {
            ++cnt;
        }
    }
}

提示：$\frac{n}{1^1}+\frac{n}{2^1}+\cdots+\frac{n}{n^1}\approx C_1\log n$，$\frac{n}{1^2}+\frac{n}{2^2}+\cdots+\frac{n}{n^2}\approx C_2$，其中 $C_1,C_2$ 均为常数。

{{ select(10) }}

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

11. 依次抛出四个六面骰子，按照抛出顺序将骰子上的数值记为 $a,b,c,d$。则 $a<b$、$b>c$、$c<d$ 同时成立的概率为（ ）。

{{ select(11) }}

• $95/648$
• $4/27$
• $5/27$
• $1/6$

12. 十进制小数 $0.3$ 转写成八进制为（ ）。

{{ select(12) }}

• $0.3$
• $0.2314631\ldots$
• $0.2046204\ldots$
• $0.3333333\ldots$

13. 观察如下代码片段：

union U {
    bool flag1, flag2, flag3, flag4, flag5;
    signed short a;
    unsigned short b;
    enum E {
        CardA = 0, CardB = 1,
        CardC = 2, CardD = 142857
    } e;
} u;

其中 sizeof(u) 的值为（ ）。

{{ select(13) }}

• 4
• 8
• 13
• 16

14. 已知某种可用来维护序列的数据结构，支持 $\Theta(\log n)$ 向某个位置后面插入元素、$\Theta(n)$ 查询某个元素的排名、$\Theta(n\log n)$ 遍历整个序列，那么用上述三种操作实现插入排序的最坏时间复杂度为（ ）。

{{ select(14) }}

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

15. 2023 年是 CCF（中国计算机学会）第（ ）次举办 CSP-J/S（计算机非专业级别的软件能力认证）。

{{ select(15) }}

• 27
• 28
• 5
• 4

二、阅读程序（程序输入不超过数组或字符串定义的范围；除特殊说明外，判断题 2 分，选择题 3 分，共计 40 分）

程序（1）

#include <iostream>
#include <cstring>
using namespace std;
string s, t;
string a, b;
int main() {
    getline(cin, s);
    getline(cin, a);
    getline(cin, b);
    for (int i = 0; i < s.size(); i++) {
        bool flag = true;
        if (i + a.size() <= s.size()) {
            for (int j = 0; j < a.size(); j++) {
                char p = s[i + j], q = a[j];
                if ('a' <= p && p <= 'z') p = p - 'a' + 'A';
                if ('a' <= q && q <= 'z') q = q - 'a' + 'A';
                if (p != q)
                    flag = false;
            }
        } else
            flag = false;

        if (flag == true) {
            t += b;
            i += a.size() - 1;
        } else
            t += s[i];
    }
    cout << t << endl;
    return 0;
}

保证输入的三行字符串长度均不超过 $10^3$，且每个字符串均由 ASCII 可见字符或空格组成且非空。

16. 保持 s,b 的字母大小写不变，将 a 里的小写英文字母改写成大写、将大写英文字母改写成小写，输出结果不变。（ ）

{{ select(16) }}

• 正确
• 错误

17. 每次调用 s.size() 的复杂度是 $O(1)$，但若把 s.size() 替换成 s.length()，调用的复杂度将会变成 $O(l)$，其中 $l$ 是 s 当前的长度。这是因为 s.length() 作为 strlen() 函数的 string 版本，会每次重新计算 s 最后一个元素的位置。（ ）

{{ select(17) }}

• 正确
• 错误

18. 当输入的字符串 s,a,b 均由小写字母 a 或 b 组成，记 s,a,b 的长度分别为 $n,m,k$，则程序的时间复杂度最坏为 $O(nm+nk)$。（ ）

{{ select(18) }}

• 正确
• 错误

19. 当输入的字符串 s,a,b 均由小写字母 a 组成，记 s,a,b 的长度分别为 $n,m,k$，且有 $n>m>k$，那么上述程序的总复杂度为 $O(n)$。（ ）

{{ select(19) }}

• 正确
• 错误

20. 针对下列输入数据，程序的输出为（ ）。

National Olympiad in Informatics A154
A
C

{{ select(20) }}

• National Olympiad in Informatics C154
• NCtionCl OlympiCd in InformCtics C154
• National!
• Nctioncl Olympicd in Informctics C154

21. 针对下列输入数据，程序的输出为（ ）。

abaabaaabaaaabaaaaabababab
aa
ab

{{ select(21) }}

• abABbABBbABBBbABBBBbababab
• ababbabbbabbbbabbbbbababab
• ababbababababbabababababab
• 程序陷入死循环/非正常退出，无法正常输出

二、阅读程序（程序输入不超过数组或字符串定义的范围；除特殊说明外，判断题 2 分，选择题 3 分，共计 40 分）

程序（2）

#include <iostream>
using namespace std;

int a[100005], b[100005], n, m;

void very_quick_sort(int l, int r, int p, int q) {
    if (l >= r || p > q) { // ①
        return;
    }
    int mid = (l + r) / 2;
    int p0 = p - 1;
    int q0 = q + 1;
    for (int i = p; i <= q; i++) {
        if (a[i] > mid) b[++p0] = a[i];
        else            b[--q0] = a[i];
    }
    for (int i = p; i <= q; i++)
        a[i] = b[i];
    very_quick_sort(mid + 1, r, p, p0);
    very_quick_sort(l, mid, q0, q);
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    very_quick_sort(1, m, 1, n);
    // ②
    for (int i = 1; i <= n; i++)
        cout << a[i] << " ";
    cout << endl;
    return 0;
}

保证输入的 $n$ 不超过 $10^5$，$m$ 不超过 $10^9$，且 $1 \le a_1,a_2,\ldots,a_n \le m$。

22. （1 分）上述代码实现了一种排序算法，可以将 a 数组按照从小到大的顺序排序。（ ）

{{ select(22) }}

• 正确
• 错误

23. 如果在程序开始之前向 b 数组里写入数据（保证不会发生数组越界），则上述代码的输出不会发生变化。（ ）

{{ select(23) }}

• 正确
• 错误

24. 若 $n=m$，存在某种数据构造方式，使得上述代码运行的时间复杂度为 $O(n^2)$，这是因为算法本身是对快速排序的改进，但这种改进不能避免由于对数组的划分不够均等而在极端数据下导致复杂度退化。（ ）

{{ select(24) }}

• 正确
• 错误

25. 如果将 ① 处的 l >= r 条件删除（同时删除 || 使得程序能正常编译运行），程序的时间复杂度不会发生变化；而将 p > q 条件删除，程序在某些数据下的运行效率将会明显降低。（ ）

{{ select(25) }}

• 正确
• 错误

26. 不认为 $n,m$ 同阶，即可能出现 $n$ 远大于 $m$ 或者 $m$ 远大于 $n$ 的情况。则该程序的最坏时间复杂度为（ ）。

{{ select(26) }}

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

27. 若输入数据为：

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

那么在程序执行到 ② 位置时，b 数组内的值为（ ）。

{{ select(27) }}

• [10,8,3,5,1,3,2,2,5,4]
• [3,5,1,3,2,2,5,4,10,8]
• [10,8,5,5,4,3,3,2,2,1]
• [1,2,2,3,3,4,5,5,8,10]

二、阅读程序（程序输入不超过数组或字符串定义的范围；除特殊说明外，判断题 2 分，选择题 3 分，共计 40 分）

程序（3）

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int mod = 1000000000 + 7;
int w0[100005];
int w1[100005];
int w2[100005];
int n, m, k, f[100005], d[100005], id[100005];
vector<int> e[100005];

void dfs(int u, int fa) {
    d[u] = d[fa] + 1;
    f[u] = fa;
    for (auto &v : e[u]) if (v != fa) {
        dfs(v, u);
    }
}

bool cmp(int a, int b) {
    return d[a] < d[b];
}

int main() {
    cin >> n >> m >> k;
    for (int i = 2; i <= n; i++) {
        int u, v;
        cin >> u >> v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    dfs(1, 0); // ①
    for (int i = 1; i <= m; i++) {
        int x, w;
        cin >> x >> w;
        w1[x] = (w1[x] + w) % mod;
        w2[x] = (w2[x] + w) % mod;
    }
    for (int i = 1; i <= n; i++)
        id[i] = i;
    sort(id + 1, id + 1 + n, cmp);
    for (int i = 1; i <= k; i++) {
        for (int j = n; j >= 1; j--) {
            int x = id[j];
            for (auto &y : e[x]) if (y != f[x]) {
                w1[y] = (w1[y] + w1[x]) % mod;
            }
            w1[x] = 0;
        }
        for (int x = 1; x <= n; x++)
            w1[x] = (w1[x] - w0[x] + mod) % mod,
            w0[x] = 0;
        for (int j = 1; j <= n; j++) { // ②
            int x = id[j];
            if (f[x]) {
                w1[f[x]] = (w1[f[x]] + w2[x]) % mod;
                w2[f[x]] = (w2[f[x]] + w2[x]) % mod;
                w0[x] = (w0[x] + w2[x]) % mod;
                w2[x] = 0;
            }
        }
    }
    for (int i = 1; i <= n; i++)
        cout << w1[i] << " ";
    return 0;
}

保证输入的 $n,m$ 不超过 $10^5$，$k$ 不超过 20，且 $1 \le x_i \le n$，$0 \le w_i < 10^9+7$。

28. 如果更改 ① 处 dfs(1, 0) 为 dfs(n, 0)，则输出结果可能有变化。（ ）

{{ select(28) }}

• 正确
• 错误

29. （1 分）如果 $k=n$，那么输出结果均为 0。（ ）

{{ select(29) }}

• 正确
• 错误

30. 如果将 ② 处 for (int j=1; j<=n; j++) 改为 for (int j=n; j>=1; j--)，那么对于任意合法的输入数据，更改前后程序的输出均相同。（ ）

{{ select(30) }}

• 正确
• 错误

31. （2 分）该程序的时间复杂度为（ ）。

{{ select(31) }}

• $\Theta(nmk)$
• $\Theta(nk+m)$
• $\Theta(km+n)$
• $\Theta(n+m+2^k)$

32. 对于以下输入数据，输出结果为（ ）。

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

{{ select(32) }}

• 0 7 0 2 2
• 2 7 2 3 2
• 5 2 1 1 1
• 0 2 1 1 2

33. 对于以下输入数据，输出结果为（ ）。

9 9 2
1 2
1 7
2 3
2 4
7 8
4 5
4 6
8 9
1 1
2 10
3 100
4 1000
5 10000
6 100000
7 1000000
8 10000000
9 100000000

{{ select(33) }}

• 10001100 1110000 1001 101 100010 10010 100000010 1 1000000
• 0 0 1 1 10 10 0 1 1000000
• 11001110 1111100 1001 110101 100010 10010 110000010 100000001 1000000
• 11001111 1111112 1121 111121 112010 112010 111000012 112000001 121000000

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

程序（1）：序列问题

给定序列 $a_n$，求有多少对 $(i,j)$ 满足 $a_i<a_j$。数据满足 $n \le 10^6$，$a_i \le 10^9$。

提示：对于任意 $a_i \ne a_j$，$(i,j)$ 或 $(j,i)$ 能对答案产生 1 的贡献，因此可以用总对数减去 $a_i=a_j$ 的 $(i,j)$ 数量。试补全程序。

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

const int Maxn = ①;
int n, a[Maxn];
long long s[Maxn], ans;

bool check(int l, int r) {
    if (s[r] - s[l - 1] == ②) return true;
    return false;
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    sort(a + 1, a + n + 1);
    for (int i = 1; i <= n; i++)
        s[i] = s[i - 1] + a[i];
    ans = ③;
    for (int i = 1; i <= n;) {
        int l = i, r = n, pos = n;
        while (④) {
            int mid = (l + r) >> 1;
            if (check(i, mid))
                l = mid + 1, pos = mid;
            else
                r = mid - 1;
        }
        ans -= ⑤;
        i = pos + 1;
    }
    cout << ans;
}

34. ① 处应填（ ）。

{{ select(34) }}

• 1e6 + 7
• 1000000
• 1e6
• 1000000000000

35. ② 处应填（ ）。

{{ select(35) }}

• (r - l + 1) * a[l]
• s[r] - s[l - 1]
• 1LL * (r - l + 1) * a[l]
• a[1] = 0

36. ③ 处应填（ ）。

{{ select(36) }}

• n * (n + 1) / 2
• 1LL * n * (n + 1) / 2
• n * (n - 1) / 2
• 1LL * n * (n - 1) / 2

37. ④ 处应填（ ）。

{{ select(37) }}

• l < r
• l <= r
• l <= r + 1
• l > r

38. ⑤ 处应填（ ）。

{{ select(38) }}

• (pos - l + 1) * (pos - l) / 2
• 1LL * (pos - l + 1) * (pos - l) / 2
• (pos - i + 1) * (pos - i) / 2
• 1LL * (pos - i + 1) * (pos - i) / 2

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

程序（2）：异或和

给定序列 $a_n$，求其所有子区间异或和的和。某个区间的异或和是将区间内的所有数字进行异或运算。其中 $n \le 10^5$，$0 \le a_i \le 10^9$。

提示：对每一位独立计算，对右端点扫描，并用异或前缀和辅助统计。试补全程序。

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

const int N = 1e5 + 7;
int n, a[N], cnt[2];
long long ans;

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i], ①;
    for (int bit = ②; ③; bit--) {
        cnt[0] = cnt[1] = 0;
        for (int i = 0; i <= n; i++) {
            cnt[④]++;
            ans += 1LL * ⑤;
        }
    }
    cout << ans;
}

39. ① 处应填（ ）。

{{ select(39) }}

• a[i - 1] ^= a[i]
• a[i] ^= a[i - 1]
• a[i - 1] += a[i]
• a[i] += a[i - 1]

40. ② 处应填（ ）。

{{ select(40) }}

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

41. ③ 处应填（ ）。

{{ select(41) }}

• bit
• bit >= n
• bit - 1
• ~bit

42. ④ 处应填（ ）。

{{ select(42) }}

• (a[i] >> bit) & 1
• a[i] & (1 << bit)
• a[i] & (1LL << bit)
• (a[i] >> bit) ^ 1

43. ⑤ 处应填（ ）。

{{ select(43) }}

• cnt[(a[i] >> bit) & 1] << i
• cnt[((a[i] >> bit) & 1) ^ 1] << bit
• cnt[(a[i] >> bit) & 1] << bit
• cnt[((a[i] >> bit) & 1) ^ 1] << i