考生注意事项

• 试题纸共有 12 页，答题纸共有 1 页，满分 100 分。请在答题纸上作答，写在试题纸上的一律无效。
• 不得使用任何电子设备（如计算器、手机、电子词典等）或查阅任何书籍资料。

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

1. 网址 www.luogu.com.cn 当中，顶级域名是（　）。 {{ select(1) }}

• www
• cn
• com.cn
• 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) }}

• 如果还能找到你，就让风儿告诉你。
  ——《Artificial Emotions》
• 只要我还能够行走，只要我还能够张望，只要我还能够呼吸，就一直走向前方。
  ——《Песня отревожной молодости》
• 昔闻洞庭水，今上岳阳楼。
  ——《登岳阳楼》
• 啊如果我在，战斗中牺牲，啊朋友再见吧，再见吧，再见吧！如果我在，战斗中牺牲，你一定把我来埋葬。
  ——《Bella Ciao》

5. 已知两个二进制整数 $a,b$：$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. 观察下列代码：

其中，$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\times8192$ 的 24 位彩色图片，使用 .bmp 格式存储，占用的空间大小约为（　）。 {{ select(9) }}

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

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

提示：

$$\frac{n}{1^1}+\frac{n}{2^1}+\frac{n}{3^1}+\cdots+\frac{n}{n^1}\approx C_1\log n$$$$\frac{n}{1^2}+\frac{n}{2^2}+\frac{n}{3^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\cdots$
• $0.2046204\cdots$
• $0.3333333\cdots$

13. 观察如下代码片段：

其中，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. 今年是 CCF（中国计算机学会）第（　）次举办 CSP-J/S（计算机非专业级别的软件能力认证）？ {{ select(15) }}

• 27
• 28
• 5
• 4

二、阅读程序（除特殊说明外，判断题 2 分，选择题 3 分，共计 40 分）

程序输入不超过数组或字符串定义的范围。判断题选择“正确”或“错误”。

第一题

保证输入的三行字符串长度均不超过 $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
• 程序陷入死循环/非正常退出，无法正常输出

第二题

保证输入的 $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]

第三题

保证输入的 $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 分）

第一题：序列问题

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

提示：对于任意的 $a_i\ne a_j$，可以发现 $(i,j)$ 或 $(j,i)$ 能对答案产生 1 的贡献，因此我们只需要用总的对数减去 $a_i=a_j$ 的 $(i,j)$ 数量，就能得到答案。

试补全程序。

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

第二题：异或和

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

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

试补全程序。

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