一、单项选择
1.在 Linux 系统终端中,用于列出当前目录下所含的文件和子目录的命令为($\color{green}{A.ls}$)。
ls 命令用于显示指定工作目录下之内容(列出目前工作目录所含之文件及子目录)。look son(子目录)
cd 命令用于切换当前工作目录。change duty
cp 命令主要用于复制文件或目录。copy
all
我也不知道这干啥
前序遍历和中序遍历相同的二叉树为且仅为($\color{green}{D.非叶子结点只有右子树的二叉树}$)。
眼瞎了注意是 !叶子结点
有如下递归代码
solve(t, n):
if t == 1 return 1
else return 5 * solve(t - 1, n) mod n
则 solve(23,23) 的结果为($\color{green}{A.1}$)。
表格的列与列之间毫无联系枚举可得第23列是
1
5
2
10
4
20
8
17
16
11
9
22
18
21
13
19
3
15
6
7
12
14
**1**(第23个数)
一定要枚举完啊!!!
12.斐波那契数列的定义为: $F_1 = 1, F_2 = 1,F_n = F_{n−1} + F_{n−2}$(n≥3) 。现在用如下程序来计算斐波那契数列的第 n 项,其时间复杂度为($\color{green}{}$)。
F(n):
if n<=2 return 1
else return F(n-1) + F(n-2)
$A. O(n)$
$B. O(n ^ 2)$
$C. O(2 ^ n)$
$D. O(nlogn)$
$T(n)=T(n−1)+T(n−2)$
所以复杂度也是 $O(F_n)$
那为什么是$O(2 ^ n)$
斐波那契数列的时间复杂度同样使用递归调用的次数×每次调用的时间复杂度得到的
由于每次调用的时间复杂度是$O(1)$ 所以计算递归调用的次数即可
递归二叉树最多有$n - 1$层,就算他是$n$, 所以就会有 $2 ^ n$个节点(当然肯定小)每次是$O(1)$,即$$O(2 ^ n)$$
二、阅读程序
一、
-
首先先看一下程序,通过求 t 可以猜出这是三维坐标系。还有 r 可以大致猜测是球。
因为 cos60∘ = 0.5 ,而 60∘ 在弧度制0~2π下就是 π/3
可以猜测一下,因为 $V=4/3πr^3$ , r 是 π/3 ,所以本题和球关系很大,而 d 是半径。
16.将第 21 行中 t 的类型声明从 int 改为 double ,不会影响程序运行的结果。(True)
没有任何下取整的操作,并且结果也是 double 不影响。
19.(2 分)当输入为0 0 0 1 1 0 0 1时,输出为1.3090。(True)
结果为 5π/12 估算一下就差不多
20.当输入为1 1 1 1 1 1 1 2时,输出为($\color{green}{D.4.1888}$)。
A. 3.1416 B. 6.2832 C. 4.7124 D. 4.1888
走特判,所以 $4/3πr^3$ 直接带进去,其中 r 取 1
21.(2.5 分)这段代码的含义为($\color{green}{C.求球的体积交}$)。
根据特判的 min ,所以判断是交。
二、
-
-
- 阅读程序后,发现这是在求最大子段和。
-
22.程序总是会正常执行并输出两行两个相等的数。(True)
确实。判对
23.第 28 行与第 38 行分别有可能执行两次及以上。( )
考虑二分到最边界,此时 (n,n+1) 会分成 (n,n) 和 (n+1,n+1) 。
相等情况被特判走了,所以不会走那两行特判。若开头输入的 n<0 ,也只会分别执行一次。
24.当输入为5 -10 11 -9 5 -7时,输出的第二行为“7”。( )
需要注意 5 为 n
所以这一段的最大字段和为 11 。
25.solve1(1, n) 的时间复杂度为($\color{green}{B.O(n)}$)。
$T(n)=2T(n/2)+1$
$T(n)=2n−1$
26.solve2(1, n) 的时间复杂度为($\color{green}{C. O(nlogn)}$)。
$T(n)=2T(n/2) + n$
$O(nlogn)$
27.当输入为10 -3 2 10 0 -8 9 -4 -5 9 4时,输出的第一行为($\color{green}{B.17}$)。
注意 10 是 n
所以最大字段和为 2 10 0 -8 9 -4 -5 9 4 ,为 17 。
-
-
- 粗略扫过去可以发现是加密和解密过程。
-
28.程序总是先输出一行一个整数,再输出一行一个字符串。(False)
可能因为空串没东西
29.对于任意不含空白字符的字符串 str1,先执行程序输入0 str1,得到输出的第二行记为 str2;再执行程序输入1 str2,输出的第二行必为 str1。(True)
既然是加密和解密,这两个必然相同
30.当输入为1 SGVsbG93b3JsZA==时,输出的第二行为HelloWorld。(False)
手动模拟
33.(4 分)当输入为0 CSP2021csp时,输出的第二行为($\color{green}{D}$)。
模拟 D
四、完善程序
(魔法数字)小 H 的魔法数字是 4 。给定 n ,他希望用若干个 4 进行若干次加法、减法和整除运算得到 n 。但由于小 H 计算能力有限,计算过程中只能出现不超过 M=10000 的正整数。求至少可能用到多少个 4 。
例如,当 n=2 时,有 2=(4+4)/4,用到了 3 个 4,是最优方案。
试补全程序。
$\color{DeepSkyBlue}{本题类似 dijkstra ,每次选择已经确定最小操作的数字来转移到其他数字}$
而 vis 记录已经确定不会再更改操作数的数。
①处应填($\color{green}{D.F[4] = 1}$)
首先 4 需要的操作数是 1 ,1 需要的是 2 。
对于程序来说,都是小操作数转移到大操作数。
②处应填($\color{green}{A.!Vis[n]}$)
结束条件首先肯定是 n 已经算出来了。
但 r 似乎对本题没有任何影响……
当 $F_n$ 有值时也不一定是最优的,只有当 $F_n$ 作为可以去转移别人的时候才是最优的。
④处应填($\color{green}{C.Vis[i]}$)
两个数转移到新的数,只有当这两个数都是最优的时候,才能保证本次转移不会白转移(指其中一个数再更新本次转移作废)
2。
(RMQ 区间最值问题)给定序列 a1,…,an,和 m 次询问,每次询问给定 l,r,求 max{a1,…,an} 。
为了解决该问题,有一个算法叫 the Method of Four Russians ,其时间复杂度为 O(n+m) ,步骤如下:
建立 Cartesian(笛卡尔)树,将问题转化为树上的 LCA(最近公共祖先)问题。
对于 LCA 问题,可以考虑其 Euler 序(即按照 DFS 过程,经过所有点,环游回根的序列),即求 Euler 序列上两点间一个新的 RMQ 问题。
注意新的问题为 ±1 RMQ,即相邻两点的深度差一定为 1 。
下面解决这个 ±1 RMQ 问题,“序列”指 Euler 序列:
设 t 为 Euler 序列长度。取 b=⌈log2t2⌉。将序列每 b 个分为一大块, 使用 ST 表(倍增表)处理大块间的 RMQ 问题,复杂度 O(tblogt)=O(m) 。
(重点)对于一个块内的 RMQ 问题,也需要 O(1) 的算法。由于差分数组 2b−1 种,可以预处理出所有情况下的最值位置,预处理复杂度 O(b2b) ,不超过O(n) 。
最终,对于一个查询,可以转化为中间整的大块的 RMQ 问题,以及两端块内的 RMQ 问题。
试补全程序。
我大受震撼。
先把程序大概扫一遍,懂在干嘛。话说为什么我考试的时候都没看到差分这句话?
38.①处应填($\color{green}{A. p->son[0] = S[top–]}$)
39.②处应填($\color{green}{D. S[top]->son[1] = p}$)
这部分是在建笛卡尔树,笛卡尔树就是对于序列区间 (l,r) ,选取最大值 x 做为这区间的根,然后再跑 (l,x−1) 和 (x+1,r) ,再和这两个区间的根连边。
可以用单调栈来解决。对于栈顶小于当前元素的情况,显然可以不断弹出,使当前元素找到他最大的左二子。
而上述操作结束后,栈顶的元素就比当前元素大,所以可以先把栈顶的右儿子设为当前元素。若后面出现更大的也会覆盖掉。
40.③处应填($\color{green}{A. x->dep < y->dep}$)
其实在建完笛卡尔树后,val 就没有用处了。
这部分的 min 是在处理 st 的时候用的,所以是考虑深度。
41.④处应填($\color{green}{D. A[i * b + j]->dep < A[i * b + j - 1]->dep}$)
首先前面都说了 val 已经没有用了(
因为只有 +1 和 −1 两种情况,所以按照题目说法,这里的二进制也是表示这个,用来存储本块内的情况。
42.⑤处应填($\color{green}{D. v += (S >> (i - 1) & 1) ? -1 : 1}$)
这里是预处理出块内所有的 2b−1 种情况,方便到时候 O(1) 算。
因为刚刚是后者小于前者时为 1 。所以为 1 的时候应该 −1 ,反之 +1 。
另外注意一下 i 是从 1 开始的。
43.⑥处应填($\color{green}{C. (Dif[p] >> (l - p * b)) & ((1 << (r - l)) - 1)}$)
对于一个块内的查询 (l,r) 。
这里的 S 是要确认本区间的状态。
而刚刚的 Dif 已经预处理好了,p 是块的位置。