Description
**一，单项选择题（共15题，每题2分，共计30分：每题有且仅有一个正确选项）**
1. NOI Linux 系统中，用于调出文件夹内所有文件的命令是()。
* cd
* ls
* find
* pwd
2. 三进制下的整数 1 010 201$_3$ 和 -212102$_3$ (这是负数) 的和在三进制下等于多少()。
* 21 022$_3$
* 12 022$_3$
* 2 000 010$_3$
* 101 102$_3$
3. 表达式的中缀形式是 (a + b * c) / (d + e)，请问其后缀形式是()。
* /*+abc+de
* /+a*bc+de
* ab+c*de+/
* abc*+de+/
4. 令根节点的高度为 1，则一棵含有 2024 个节点的二叉树的高度至多为()。
* 10
* 11
* 12
* 2024
5. 对于长度为 5 的排列 p，有多少个满足:存在 1 ≤ k ≤ 3使 P$_1$ < P$_2$ < ··· P$_k$ > P$_k$> ··· > P$_5$()。
* 10
* 11
* 16
* 120
6. 字符 a, b, c, d, e ,f 在文本中出现的频率为 5%, 13%, 45%, 9%, 16%, 12%。为其用 01 进行哈夫曼编码合理的是()。
* 1111, 100, 0110, 110, 101
* 1010, 001, 00, 1001, 010, 1000
* 000, 011, 11, 011, 10, 010
* 1010, 111, 01, 1011, 00, 110
7. 从线段上随机挑选两个点，其距离不小于线段长度一半的概率为()。
* 1/3
* 2/3
* 1/4
* 1/2
8. 从男女数量相同的 8 个人中随机选取三个人做大作业。则选出的 3 个人不都是同性的概率为()。
* 1/7
* 6/7
* 25/28
* 2/7
9. 下列有关排序的说法不正确的是()。
* 桶排序是一种有效的排序方式，时间复杂度为O(n + V)
* 堆排序是一种有效的排序方式，是一种稳定排序
* multiset 是一种有效的数据结构，可以用来排序，但是常数很大
* 归并排序的最劣复杂度为 O(nlogn)
10. 已知运算优先级:￣ > ∩ > U。下列表达式的值与取值为 0, 1 的变量 x、y、z 有关的是()。
* (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)
11.
以上代码片段中，若 x, y ,z > 0，且函数执行过程中变量的值不会超过类型范围,则代码可简写为()。
* 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。下列说法错误的是()。 * 若单节点的深度为，则该二叉树重新定根后最大深度最大为 5 * 节点 1, 2 的最近公共祖先为节点 5 * 节点 2 的兄弟是节点 4，父亲是节点 6 * 节点 2 是某个节点的右儿子 13. 维护一个双向链表，其中 next 是直系后缀, prev 是直系前驱。下列语句中删除元素 x 的方式正确的是()。 * 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)。 * 12 * 13 * 14 * 15 15. HTTP协议是()层协议?。 * 数据链路层 * 网络层 * 传输层 * 应用层 **二，阅读程序(判断题正确填 “T”，错误填“F”，共计40分)** (一)   ■判断题 16. 将第 7 行“int x, y, z;” 移动到第2、3 行之间不会影响程序运行的结果。()( 1.5 分) * 正确 * 错误 17. 当输人为“1 2 1”时，输出为“3”。()( 1.5 分) * 正确 * 错误 18. 输出的答案总大于输人的第 3 个数z。()( 1.5 分) * 正确 * 错误 ■选择题 19. 将第4行 “((x << 1)+(y >> 1)) | z” 改为()会影响程序运行的结果。( 3 分)
* (x << 1 + y >> 1) | z
* (x * 2 + y / 2) | z
* (x << 1)+ (y >> 1) | z
* 以上答案都不对
20. 当输入为 “3 4 10” 时，输出为()。( 3 分)
* 8
* 10
* 11
* 15
21. 当输人为 “13 24 35” 时，输出为()。( 3 分)
* 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 分) * 正确 * 错误 23. 将程序第 9 行的 if( b[i] > b[j] )改为 if( b[i] >= b[j])，则程序运行不会发生错误，结果不变。()( 1.5 分)
* 正确
* 错误
24. 将程序第 14 行的 for (int i = 1; i <= m+1;++i)改为 for(int i = 1; i <= m; ++i)，则程序运行不会发生错误，结果不变。()( 1.5 分) * 正确 * 错误 25. 该程序求出了最小的大于 1 的正整数 k 使得所有 b$_i$ 模 k 同余。()。( 2.5 分) * 正确 * 错误 ■选择题 26. 该程序的时间复杂度是()。( 3 分) * O($n^2$ + m) * O($n^2$ + $m^2$) * O($n^2$ + mlogm) * O(nlogn + $m^2$) 27. 若输人为如下内容，则输出为()。( 4 分) 输入:  * 13 * 1 * 3 * 101 (三)   ■判断题 28. 因为 MAXN 等于 5001，所以程序可以在没有 UB 的情况下正常执行 N = 5000。()( 1.5 分) * 正确 * 错误 29. 在第 29 行执行完毕后，始终有 cntA[2N] ≠ cntB[2N]。()( 1.5 分) * 正确 * 错误 30. 若x$_i$ = 1，那么程序输出的结果是 N! mod 998244353。()( 1.5 分) * 正确 * 错误 ■选择题 31. 若 N = 3, x = [1, 1, 4, 5, 1, 4]，则输出为()。( 4.5 分) * 18 * 17 * 16 * 15 32. 若 N = 7, x = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]，则输出为()。( 4 分) * 141 120 * 5040 * 254 016 000 * 3 651 360 **三、完善程序（单选题，每小题3分，共计30分）** (一) 模拟队列、栈 输人一个正整数 n，表示操作数。然后输人 n 个操作。操作 1 表示在循环队列中插入一个数，操作 2 表示在循环队列中退出一个数并输出，操作 3 表示在栈中插人一个数，操作 4 表示在栈中退出一个数并输出。    33. (1)处应填()。 * head == tail * tail == size * (tail + 1) % size == head * (head + 1) % size == tail 34. (2)处应填()。 * (head + 1) % size == tail * head == tail * tail == -1 * head == -1 35. (3)处应填()。 * (head + 1) % size == tail * head == tail * tail == -1 * head == -1 36. (4)处应填()。 * top++ * ++top * top-- * --top 37. (5)处应填()。 * 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)处应填()。 * true * a[j] <= m * a[j] <= K * a[j] != m 39. (2)处应填()。 * K = N; * K = min(K, N); * K= min(K, 2 * N); * K = min(K, N + 1) 40. (3)处应填()。 * 0 * 1 * K * a[1] 41. (4)处应填()。 * a[i] == K * a[i] >= K
* cnt[a[i]] == 0
* cnt[a[i]] == 1
42. (5)处应填()。
* a[i]
* tag[i] ? 0 : a[i]
* tag[i] ? K : a[i]
* tag[i] ? a[i] : K
