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

1. NOI Linux 系统中，用于调出文件夹内所有文件的命令是()。{{ select(1) }}

• cd
• ls
• find
• pwd

2. 三进制下的整数 1 010 201$_3$ 和 -212102$_3$ (这是负数) 的和在三进制下等于多少()。{{ select(2) }}

• 21 022$_3$
• 12 022$_3$
• 2 000 010$_3$
• 101 102$_3$

3. 表达式的中缀形式是 (a + b * c) / (d + e)，请问其后缀形式是()。{{ select(3) }}

• /*+abc+de
• /+a*bc+de
• ab+c*de+/
• abc*+de+/

4. 令根节点的高度为 1，则一棵含有 2024 个节点的二叉树的高度至多为()。{{ select(4) }}

• 10
• 11
• 12
• 2024

5. 对于长度为 5 的排列 p，有多少个满足:存在 1 ≤ k ≤ 3使 P$_1$ < P$_2$ < ··· P$_k$ > P$_k$$_+$$_1$ > ··· > P$_5$()。{{ select(5) }}

• 10
• 11
• 16
• 120

6. 字符 a, b, c, d, e ,f 在文本中出现的频率为 5%, 13%, 45%, 9%, 16%, 12%。为其用 01 进行哈夫曼编码合理的是()。{{ select(6) }}

• 1111, 100, 0110, 110, 101
• 1010, 001, 00, 1001, 010, 1000
• 000, 011, 11, 011, 10, 010
• 1010, 111, 01, 1011, 00, 110

7. 从线段上随机挑选两个点，其距离不小于线段长度一半的概率为()。{{ select(7) }}

• 1/3
• 2/3
• 1/4
• 1/2

8. 从男女数量相同的 8 个人中随机选取三个人做大作业。则选出的 3 个人不都是同性的概率为()。{{ select(8) }}

• 1/7
• 6/7
• 25/28
• 2/7

9. 下列有关排序的说法不正确的是()。{{ select(9) }}

• 桶排序是一种有效的排序方式，时间复杂度为O(n + V)
• 堆排序是一种有效的排序方式，是一种稳定排序
• multiset 是一种有效的数据结构，可以用来排序，但是常数很大
• 归并排序的最劣复杂度为 O(nlogn)

10. 已知运算优先级:￣ > ∩ > U。下列表达式的值与取值为 0, 1 的变量 x、y、z 有关的是()。{{ select(10) }}

• (x U y)∩( ￣x U ￣y)
• ￣x U ￣y U (x ∩ y)
• ￣y ∩ ((x U z) ∩ y U y)
• (x ∩ y U (y ∩ ￣z) U (￣ z ∩ x)

以上代码片段中，若 x, y ,z > 0，且函数执行过程中变量的值不会超过类型范围,则代码可简写为()。{{ select(11) }}

• y += (x + y) << (z - 1)
• y = (x + y) << z - 1
• x = ((x + y) >> (z + 1)) + x
• y = ((y + x) << z) + y

12. 给出一棵节点乱序编号的有 7 个节点的满二叉树的中序遍历结果: 7, 1, 3, 5, 2, 6, 4。下列说法错误的是()。{{ select(12) }}

• 若单节点的深度为，则该二叉树重新定根后最大深度最大为 5
• 节点 1, 2 的最近公共祖先为节点 5
• 节点 2 的兄弟是节点 4，父亲是节点 6
• 节点 2 是某个节点的右儿子

13. 维护一个双向链表，其中 next 是直系后缀, prev 是直系前驱。下列语句中删除元素 x 的方式正确的是()。{{ select(13) }}

• x.prev.next = x.next, x.next.prev = x.prev
• x.next = x.prev.next, x.prev = x.next.prev
• x.prev.next = x.next.prev = x
• x.prev.next = x.prev, x.next.prev = x.next

14. 阅读以下关于正则表达式的段落:

##正则表达式

此处我们考虑一个正则表达式由英文小写字母和特殊字符?,*,+表示。特殊字符只会在小写字母的后面出现。

若 ? 跟在一个字母后面，则这个字母可以删去或保留。如ca?b 可以变成 cab 或 cb。

若 * 跟在一个字母后面，则这个字母可以刪去或保留或复制多遍。如 ca*b 可以变成 cab,cb,caaaaaaab 等等。

若 + 跟在一个字母后面，则这个字母保留或复制多遍，，但不能删除。如 ca*b可以变成 cab,caaaaaaab 等等，但不能变成 cb。

综合举例:da*b?c+可以变成:daaacc,dabc,dcc,dabccc等，不能变成 dabbc,daab,dacb,aaacc 等

对于正则表达式s和标准串t，我们定义匹配程度f(s,t)为,s可以变成t中的多少个本质不同的非空子串。即实质相同但位置不同的子串算作相同。

根据以上材料，求f(a+a?b*aa?b+,aaabbaabbb)。

{{ select(14) }}

• 12
• 13
• 14
• 15

15. HTTP协议是()层协议?。{{ select(15) }}

• 数据链路层
• 网络层
• 传输层
• 应用层

二，阅读程序(判断题正确填 “T”，错误填“F”，共计40分)

(一)

■判断题

16. 将第 7 行“int x, y, z;” 移动到第2、3 行之间不会影响程序运行的结果。()( 1.5 分){{ select(16) }}

• 正确
• 错误

17. 当输人为“1 2 1”时，输出为“3”。()( 1.5 分){{ select(17) }}

• 正确
• 错误

18. 输出的答案总大于输人的第 3 个数z。()( 1.5 分){{ select(18) }}

• 正确
• 错误

■选择题

19. 将第4行 “((x << 1)+(y >> 1)) | z” 改为()会影响程序运行的结果。( 3 分){{ select(19) }}

• (x << 1 + y >> 1) | z
• (x * 2 + y / 2) | z
• (x << 1)+ (y >> 1) | z
• 以上答案都不对

20. 当输入为 “3 4 10” 时，输出为()。( 3 分){{ select(20) }}

• 8
• 10
• 11
• 15

21. 当输人为 “13 24 35” 时，输出为()。( 3 分){{ select(21) }}

• 34
• 35
• 39
• 55

(二)

其中输入的变量满足:2 ≤ n ≤ 500, 1 ≤ b$_i$ ≤ m ≤ 5000。

■判断题

22. 将程序第 9 行的 for (int j = 0; j < n ; ++j)改为 for (int j = i ; j < n ; ++j)，则程序运行不会发生错误，结果不变()( 1.5 分){{ select(22) }}

• 正确
• 错误

23. 将程序第 9 行的 if( b[i] > b[j] )改为 if( b[i] >= b[j])，则程序运行不会发生错误，结果不变。()( 1.5 分){{ select(23) }}

• 正确
• 错误

24. 将程序第 14 行的 for (int i = 1; i <= m+1;++i)改为 for(int i = 1; i <= m; ++i)，则程序运行不会发生错误，结果不变。()( 1.5 分){{ select(24) }}

• 正确
• 错误

25. 该程序求出了最小的大于 1 的正整数 k 使得所有 b$_i$ 模 k 同余。()。( 2.5 分){{ select(25) }}

• 正确
• 错误

■选择题

26. 该程序的时间复杂度是()。( 3 分){{ select(26) }}

• O($n^2$ + m)
• O($n^2$ + $m^2$)
• O($n^2$ + mlogm)
• O(nlogn + $m^2$)

27. 若输人为如下内容，则输出为()。( 4 分) 输入: {{ select(27) }}

• 13
• 1
• 3
• 101

(三)

■判断题

28. 因为 MAXN 等于 5001，所以程序可以在没有 UB 的情况下正常执行 N = 5000。()( 1.5 分){{ select(28) }}

• 正确
• 错误

29. 在第 29 行执行完毕后，始终有 cntA[2N] ≠ cntB[2N]。()( 1.5 分){{ select(29) }}

• 正确
• 错误

30. 若x$_i$ = 1，那么程序输出的结果是 N! mod 998244353。()( 1.5 分){{ select(30) }}

• 正确
• 错误

■选择题

31. 若 N = 3, x = [1, 1, 4, 5, 1, 4]，则输出为()。( 4.5 分){{ select(31) }}

• 18
• 17
• 16
• 15

32. 若 N = 7, x = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]，则输出为()。( 4 分){{ select(32) }}

• 141 120
• 5040
• 254 016 000
• 3 651 360

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

(一) 模拟队列、栈

输人一个正整数 n，表示操作数。然后输人 n 个操作。操作 1 表示在循环队列中插入一个数，操作 2 表示在循环队列中退出一个数并输出，操作 3 表示在栈中插人一个数，操作 4 表示在栈中退出一个数并输出。

33. (1)处应填()。{{ select(33) }}

• head == tail
• tail == size
• (tail + 1) % size == head
• (head + 1) % size == tail

34. (2)处应填()。{{ select(34) }}

• (head + 1) % size == tail
• head == tail
• tail == -1
• head == -1

35. (3)处应填()。{{ select(35) }}

• (head + 1) % size == tail
• head == tail
• tail == -1
• head == -1

36. (4)处应填()。{{ select(36) }}

• top++
• ++top
• top--
• --top

37. (5)处应填()。{{ select(37) }}

• top++
• ++top
• top--
• --top

(二) MEX序列

给定一个序列 a$_1$,…,a$_n$, 和常数 k, 你希望对每个 1 ≤ l ≤ r ≤ n, mex(a$_1$,…,a$_r$)≠k，请问你最少需要修改多少 a$_i$ 使得条件成立。此外，构造任意一个合法的修改后序列 a’$_1$,…,a'$_n$。

定义一个序列的 mex 为该序列中未出现的最小自然数。

对于所有的输入数据保证: 1 ≤ n ≤ 10$^6$, 1 ≤ a$_i$ ≤ 10$^9$, 1 ≤ k ≤10$^9$。

38. (1)处应填()。{{ select(38) }}

• true
• a[j] <= m
• a[j] <= K
• a[j] != m

39. (2)处应填()。{{ select(39) }}

• K = N;
• K = min(K, N);
• K= min(K, 2 * N);
• K = min(K, N + 1)

40. (3)处应填()。{{ select(40) }}

• 0
• 1
• K
• a[1]

41. (4)处应填()。{{ select(41) }}

• a[i] == K
• a[i] >= K
• cnt[a[i]] == 0
• cnt[a[i]] == 1

42. (5)处应填()。{{ select(42) }}

• a[i]
• tag[i] ? 0 : a[i]
• tag[i] ? K : a[i]
• tag[i] ? a[i] : K