一、单项选择题
- $\color{green}{A.O(n + e)}$
DFS
DFS算法是一一个递归算法,需要借助一个递归工作栈,故它的空问复杂度为O(V)。
遍历图的过程实质上是对每个顶点查找其邻接点的过程,其耗费的时间取决于所采用结构。邻接表表示时,查找所有顶点的邻接点所需时间为O(E),访问顶点的邻接点所花时间为O(V),
此时,总的时间复杂度为$O(V + E)$邻接矩阵表示时,查找每个顶点的邻接点所需时间为O(V),要查找整个矩阵,故总的时间度为$O(V ^ 2)$
v为图的顶点数,E为边数。
二、程序阅读题
2.
5)(2.5分)若输入的 d[i] 为 i ,此程序①平均的时间复杂度和②最坏情况下的时间复杂度分别是
$\color{green}{A. O(n), O(n ^ 2)}$
期望时间复杂度为
$$ \color{green}{T(n)=T(n / 2) + n = Θ(n)} $$
最坏情况的时候,每次 rand() 出的 x 都是 L,那么 b 会从 R 一直跑到 L+1,时间复杂度就是
$$ \color{green}{T(n) = T(n − 1) + n = Θ(n ^ 2)} $$
6)(2.5分)若输入的d[i]都为同一个数,此程序平均的时间复杂度是
$\color{green}{D. O(n ^ 2)}$
随机了个寂寞。
每次 a 不变,b 要从 R 跑到 L 。然后在跑子程序。
所以结果为 $\color{green}{O(n^2)}$
3.
4.(2.5分)若输入的第一个字符串长度由100个不同的字符构成,第个字符串是第一个字符串的倒序,输入的m为0,则输出为()
$$ 每次操作旋转一段字符串([0,m]或[m,n])。问几次 st0 可以和 st1 相等。 用的是双向搜索。 $$
$\color{green}{D.-1}$
-
m == 0后相当于啥都没干
(4分)若两个字符串的长度均为 n ,且 0<m<n−1 ,且两个字符串的构成相同(即任何一个字符在两个字符串中出现的次数均相同),则下列说法正确的是()。提示:考虑输入与输出有多少对字符前后顺序不样
$\color{green}{C.若n为奇数、m为偶数,则输出可能小于0。}$
小于 0 就是无解。
C中,凑偶数,就有可能无法凑成奇数。
故选 C 。
三、完善程序
干得漂亮,第二大题只对了一个空
2.
1.①处应填().
A. x>>=1
B. x^=x&(x^(x+1))
C. x-=x|-x
D. x^=x&(x^(x-1))
-
很 lowbit
2.②中应填()
A. (a & MS) << B
B. a >> B
C. a & (1 << B)
D. a & (Ms << B)
-
第二题,根据题目中 x 的定义。
那么 x 为 a 的 B 位的数。
故选 B 。
3.③中应填()
A. -INF
B. Max[y][x]
C. 0
D. Max[x][y]
-
此时 Max 并未赋值。排除 B 和 D 。
空串的值为 0 。
4.④中应填()
A. Max[x][z]+w(y^z)
B. Max[x][z]+w(a^z)
C. Max[x][z]+w(x^(z<<B))
D. Max[x][z]+w(x^z)
-
根据 Max[x][z] 可得,这次是在变换 y 。
而 y^z 就是补充 z 剩下的 1 的贡献。
5.⑤中应填()
A. to_max(Max[y][z],v+w(a^(z<<B)))
B. to_max(Max[z][y],v+w((x^z)<<B)
C. to_max(Max[z][y],v+w(a^(z<<B)))
D. to_max(Max[x][z],v+w(y^z))
-
易得这次是固定 y ,变换 x 。
故排除 A 和 D 。
变换 x 的值也时时更新。
和上一题一样,x^z 是补充 z 剩下的 1 的贡献。
再回题目看概念,下一个位置的高 8 位是x 。
所以 x 需要恢复到高位的贡献,再与 v 相加。