2026年算法设计与分析期末回忆版[BUAA-算法]

填空选择题

$\Theta(n\log n) \quad \Theta(n) \quad \Theta(\log ^2n) \quad \Theta(n^2) \quad \Theta(1)$

1. $\sum_{i=1}^{n} \frac{\log n}{i}$的渐近表示为________。
2. qsort算法的最差时间复杂度是________。
3. BFS中入栈出栈的次数是________。
4. $T(n) = 3T(n/4) + n\log n$的渐近表示为________。

判断题

1. $P\subseteq NPC$
2. 若有$2-SAT \leq p 3-SAT$，则 P=NP。
3. $O(\sqrt{n})$时间复杂度的算法比$O(2^{\sqrt{\log n}})$时间复杂度的算法更优。
4. 一个大小为n的图，求是否包含大小为5的团可以在多项式时间内完成。

算法实例

一个强连通分量的图
(1) 给出第一遍 DFS 访问的次序
(2) 给出第二遍 DFS 每个点的开始时间和完成时间，并标明强连通分量

算法设计题

旅店有n个房间，每个房间配备有2把钥匙，现在有一间房间缺少了1把钥匙，给出k[1…2n-1]表示现有钥匙的房间号，例如，n=4, $k[7]=\{2,2,6,7,7,10,10\}$。设计一个算法找出缺少钥匙的房间编号，给出伪代码并分析时间复杂度，$O(\log n)$时间复杂度的算法可得满分。

算法设计题

一个小区有n台电梯，每个电梯需要在一个时间段内进行消毒，给出a[1…n]和b[1…n]分别表示每台电梯消毒的开始时间和结束时间，每次可以消毒该时间段内需要消毒的所有电梯，设计一个算法找出最少的消毒次数，给出伪代码并分析时间复杂度，$O(n\log n)$时间复杂度的算法可得满分。

算法设计题

校园内的教学楼之间的线路需要改造，给出一个无向连通图 G=(V,E)，其中每条边有拆除费用d[e]和维修费用m[e]，保证维修费用一定大于拆除费用。设计一个算法找出一棵生成树，使得拆除费用和维修费用之和最小，给出伪代码并分析时间复杂度，$O(E\log V)$时间复杂度的算法可得满分。

算法设计题

有n个项目可以投资，部分项目i有个依赖项目d[i]，保证如果一个项目被其他项目依赖，那么它不会再依赖其他项目，每个项目的成本为c[i]，收益为p[i]，设计一个算法找出在总成本不超过$M(M>n)$的情况下，能够获得的最大收益，给出伪代码并分析时间复杂度，$O(Mn)$时间复杂度的算法可得满分。

1. 假设一个项目最多只被一个项目依赖。
2. 假设一个项目可以被多个项目依赖。