2025-2026学年第一学期数据结构真题解析
时间复杂度分析
题目 1
分析下列递归函数的时间复杂度：
int f(int m)
{
if(m <= 1) return 1;
else return f(m - 1) + f(m - 1) + f(m - 1);
}设运行时间为 $T(m)$。当 $m>1$ 时，函数会递归调用三次 $f(m-1)$，因此
不断展开可得
取 $k=m-1$，得到
因此时间复杂度为 $O(3^m)$，更准确地说是 $\Theta(3^m)$。
题目 2
分析下列函数的时间复杂度：
int sub2(int m, int n)
{
int i, j, t, r = 0;
for (i = 0; i < n; i++)
for (j = 0; j <= n; j = j + 2) {
t = 1;
while (t < m / 2 - 1) t = t * 2;
r = r + t;
}
return r;
}最外层循环执行 $n$ 次。
第二层循环中 $j$ 每次增加 2，因此执行次数约为
最内层 while 循环中，$t$ 从 1 开始不断乘 2：
直到达到 $m/2-1$，故执行次数为
三层相乘：
二叉排序树
已知一棵二叉排序树节点的数据为整数，其前序遍历序列如下：
（1）画出该二叉排序树的逻辑结构
二叉排序树如下：
📐 TikZ 图表（请在 PDF 版本中查看完整图表）
前序遍历的第一个元素 60 为根节点。
随后按二叉排序树规则依次插入：
- 40 $<60$，放在 60 的左子树；
- 35 $<60$ 且 $<40$，放在 40 左侧；
- 48 $<60$ 且 $>40$，放在 40 右侧；
- 54 $<60$、$>40$、$>48$，放在 48 右侧；
- 69 $>60$，放在 60 右侧；
- 82 $>60$ 且 $>69$，放在 69 右侧。
（2）根据前序遍历序列构造二叉排序树的算法思路
依次扫描前序序列，将每个元素按照二叉排序树的插入规则插入当前树中即可。
设前序序列为 $a_1,a_2,\dots,a_n$：
- 先令 $a_1$ 为根节点；
- 对 $i=2,3,\dots,n$：
- 若 $a_i$ 小于当前节点关键字，则进入左子树；
- 若 $a_i$ 大于当前节点关键字，则进入右子树；
- 直到遇到空指针，在该位置建立新节点。
若树高为 $h$，单次插入复杂度为 $O(h)$，总复杂度为 $O(nh)$； 平均情况下约为 $O(n\log n)$，最坏退化成链时为 $O(n^2)$。
多个栈共享连续存储空间
设有 $N(N>0)$ 个栈，其元素类型相同，在任何时刻这 $N$ 个栈的元素个数之和不超过 $M(M>0)$，要求采用一片连续的内存空间存储这 $N$ 个栈。请给出一种实现方法，并说明进栈、 出栈操作及时间复杂度。
采用“数组模拟链式栈 + 空闲链表”的方法。所有栈共享一块长度为 $M$ 的连续数组， 每次进栈和出栈的时间复杂度均为
开设如下连续数组与辅助变量：
ElemType data[M]; // 存放元素
int next[M]; // 模拟链指针
int top[N]; // top[k] 为第 k 个栈的栈顶下标
int freeHead; // 空闲结点链表表头初始化时：
并令
组成空闲链表。
\paragraph{进栈 push(k,x)}
- 从空闲链表取出一个下标 $p$；
- 存入 $data[p]=x$；
- 令 $next[p]=top[k]$；
- 更新 $top[k]=p$。
\paragraph{出栈 pop(k)}
- 取 $p=top[k]$；
- 更新 $top[k]=next[p]$；
- 将结点 $p$ 重新放回空闲链表。
所有步骤只涉及常数次下标访问与赋值，因此：
这种方法不会给每个栈预先固定空间，因此只要所有栈元素总数不超过 $M$，空间就可以充分共享。
关键路径
软件项目包含 7 个子任务：
| 子任务 | 持续时间（天） | 开始条件 |
| $a_1$ | 2 | 无 |
| $a_2$ | 3 | 无 |
| $a_3$ | 2 | $a_1$ 完成 |
| $a_4$ | 3 | $a_1$ 完成 |
| $a_5$ | 3 | $a_2$ 完成 |
| $a_6$ | 3 | $a_3$ 完成 |
| $a_7$ | 3 | $a_4$ 与 $a_5$ 均完成 |
（1）分别缩短 $a_1,a_2,a_6$ 的持续时间，能否使项目提前完成？
计算各任务最早完成时间：
因此项目总工期为
主要路径长度：
所以关键路径为
- 缩短 $a_1$：$a_1$ 不在当前关键路径上，不能使 9 天工期提前；
- 缩短 $a_2$：$a_2$ 位于关键路径上，适当缩短可使项目提前完成；
- 缩短 $a_6$：该任务所在分支 7 天完成，早于总工期 9 天，不能使项目提前。
（2）判断给定子任务持续时间缩短能否使项目提前完成的算法思路
将任务依赖关系建成 DAG，分别计算修改前、修改后的最长路径（项目工期），比较两者即可。
算法步骤：
- 将每个子任务及其先后约束建立成有向无环图；
- 对 DAG 做拓扑排序；
- 按拓扑序进行动态规划，计算每个任务的最早开始时间： @@BLOCK_29@@
- 得到原项目总工期 @@BLOCK_30@@
- 将指定任务持续时间改为缩短后的值 $d'(x)$，再次计算总工期 $T'$；
- 若 $T'
该方法比单纯判断“任务是否在某一条关键路径上”更稳妥，因为当存在多条关键路径时， 缩短其中一条路径上的单个任务未必能缩短整个项目工期。
若有 $V$ 个任务、$E$ 条依赖关系，一次计算复杂度为
算法设计一：Huffman 树权值序列
在 Huffman 树中，从根节点到叶节点路径上所经过节点（包括根和叶）的权值序列称为权值序列。 节点权值为正整数。
（1）判断下列两组序列能否属于同一棵 Huffman 树
第（1）组
两条路径从根 36 后立即分叉为 20 与 16，且
这满足同一父节点两个孩子权值之和等于父节点权值的要求。
各路径对应的兄弟子树权值分别为：
以及
从根向叶观察，兄弟子树权值不出现违反 Huffman 合并次序的增大，因此可兼容。
第（2）组
两条路径在根 50 后分叉为 30 与 20，且
第一条路径的兄弟权值为：
第二条路径的兄弟权值为：
均与 Huffman 自底向上的非递减合并次序相容，因此可以属于同一棵 Huffman 树。
第（3）组
两条路径共同经过
之后在节点 20 处分叉为 11 与 9，并且
第二条路径继续：
相应兄弟权值为
不存在结构冲突，因此可以兼容于同一棵 Huffman 树。
第（4）组
根节点处虽然有
但第二条路径中
意味着节点 36 的另一个孩子权值必须为
也就是说 36 要由 10 与 26 合并得到。
然而根的另一棵子树权值为 14。按照 Huffman 算法，每一步必须选择当前权值最小的两个结点合并。 当 10、14、26 同时作为候选子树存在时，不可能跳过较小的 14 而选择 10 与 26 合并， 因此与 Huffman 贪心合并规则矛盾。
所以不能属于同一棵 Huffman 树。
（2）算法思路与 C/C++ 描述
核心检查三类条件：
- 每条路径权值必须严格递减；
- 两条路径第一次分叉时，两个分叉孩子权值之和必须等于共同父节点权值；
- 由相邻节点差值得到的“兄弟子树权值”必须与 Huffman 自底向上的合并次序相容。
对序列
若它是一条根到叶路径，则每一步的兄弟子树权值为
因为父节点权值等于两个孩子权值之和。
按 Huffman 合并过程从叶向根看，被合并结点的权值总体不能逆着贪心次序变化； 因此从根向叶看，相应兄弟子树权值不能出现明显的“先小后大”冲突。
下面给出适合本题判定的课程级算法描述：
#include <bits/stdc++.h>
using namespace std;
bool validPath(const vector<long long>& s) {
if (s.empty()) return false;
// 根到叶权值必须严格递减
for (int i = 0; i + 1 < (int)s.size(); ++i) {
if (s[i] <= s[i + 1]) return false;
}
// diff[i] 是该层另一棵兄弟子树的权值
vector<long long> diff;
for (int i = 0; i + 1 < (int)s.size(); ++i) {
diff.push_back(s[i] - s[i + 1]);
}
// 从根向叶，兄弟子树权值不应出现与 Huffman
// 自底向上非递减合并顺序冲突的增大
for (int i = 0; i + 1 < (int)diff.size(); ++i) {
if (diff[i] < diff[i + 1]) return false;
}
return true;
}
bool canBeInSameHuffmanTree(const vector<long long>& A,
const vector<long long>& B) {
if (!validPath(A) || !validPath(B)) return false;
if (A[0] != B[0]) return false; // 根权必须相同
int n = A.size(), m = B.size();
int p = 0;
// 找最长公共前缀
while (p < n && p < m && A[p] == B[p]) ++p;
// 两个不同叶路径中，一条不能是另一条的严格前缀
if (p == n || p == m) return false;
// 第一次分叉：两个孩子必须互为兄弟
// 它们的权值之和必须等于共同父节点
long long parent = A[p - 1];
if (A[p] + B[p] != parent) return false;
return true;
}设两序列长度分别为 $n,m$，扫描与检查均为线性时间，因此
额外空间若不显式保存差分数组可降为
说明：上述判定采用本题常见的数据结构课程口径，即利用 Huffman 节点权值和、 首次分叉兄弟关系以及贪心合并次序进行兼容性检查。
算法设计二：删除最小堆堆顶并重排
$n$ 个盒子按 $1\sim n$ 编号，卡片满足：
拿走编号 1 的卡片后，将其余 $n-1$ 张卡片重排到 $1\sim n-1$，仍满足该规则， 并使翻看卡片标记值次数尽可能少。
（1）算法思路
该结构本质上是一个小根堆。删除堆顶后，将原来第 $n$ 个盒子的卡片移到根， 再执行向下调整（sift down）。
具体步骤：
- 拿走盒子 1 中的最小元素；
- 将盒子 $n$ 的最后一张卡片移动到盒子 1；
- 当前结点若有两个孩子，只翻看两个孩子并选择标记值较小者；
- 将当前卡片与较小孩子比较：
- 若当前值不大于较小孩子，调整结束；
- 否则交换，并继续向下一层调整。
为了减少翻看次数，已经翻看过的卡片值应缓存，不重复翻看。 每下降一层至多新翻看两个孩子，路径高度为 $O(\log n)$。
（2）C/C++ 算法描述与复杂度
#include <bits/stdc++.h>
using namespace std;
// b[1..n] 初始满足小根堆性质
// 删除 b[1] 后，将堆规模变成 n-1
void deleteMin(vector<int>& b, int& n) {
if (n <= 0) return;
// 将最后一个元素移到堆顶
b[1] = b[n];
--n;
int i = 1;
while (2 * i <= n) {
int child = 2 * i; // 左孩子
// 若右孩子存在，选择更小的孩子
if (child + 1 <= n && b[child + 1] < b[child]) {
++child;
}
// 已满足小根堆性质
if (b[i] <= b[child]) break;
swap(b[i], b[child]);
i = child;
}
}时间复杂度：
每次交换后至少下降一层，而完全二叉树高度为
因此向下调整最多进行 $O(\log n)$ 层。
若按“翻看卡片”计数，并缓存已看过的值，则每层至多查看两个孩子， 总查看次数也是
最短路问题：按时间上线的城市
共有 $N$ 座城市，编号 $0$ 到 $N-1$。城市 $i$ 在时间 $u_i$ 上线， 且
有 $M$ 条无向带权边。询问 $(a,b,t)$ 按 $t$ 非递减给出： 在第 $t$ 天，只允许经过已经上线的城市，求 $a$ 到 $b$ 的最短路； 若不可达或端点未上线，输出 $-1$。
算法思路
采用增量 Floyd 算法。
由于城市上线时间有序、询问时间也不下降，可以随着时间推进， 把新上线的城市依次加入 Floyd 的“允许作为中间点”的集合。
初始化距离矩阵：
有边 $(i,j,w)$ 时：
其他为无穷大。
维护指针 $k$，表示编号小于 $k$ 的城市已经作为中间点加入。
处理询问 $(a,b,t)$ 前，不断加入所有满足
的城市 $k$。每加入一个城市 $k$，执行一次 Floyd 松弛：
然后：
- 若 $u_a>t$ 或 $u_b>t$，输出 $-1$；
- 若 $dist[a][b]=\infty$，输出 $-1$；
- 否则输出 $dist[a][b]$。
C++ 参考代码
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = (1LL << 60);
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N, M;
cin >> N >> M;
vector<int> u(N);
for (int i = 0; i < N; ++i) cin >> u[i];
vector<vector<ll>> dist(N, vector<ll>(N, INF));
for (int i = 0; i < N; ++i) dist[i][i] = 0;
for (int e = 0; e < M; ++e) {
int x, y;
ll w;
cin >> x >> y >> w;
dist[x][y] = dist[y][x] = min(dist[x][y], w);
}
int Q;
cin >> Q;
int k = 0; // [0, k-1] 已经被允许作为中间点
while (Q--) {
int a, b, t;
cin >> a >> b >> t;
// 按时间增量加入新上线城市
while (k < N && u[k] <= t) {
for (int i = 0; i < N; ++i) {
if (dist[i][k] == INF) continue;
for (int j = 0; j < N; ++j) {
if (dist[k][j] == INF) continue;
dist[i][j] = min(
dist[i][j],
dist[i][k] + dist[k][j]
);
}
}
++k;
}
// 源点或终点尚未上线
if (u[a] > t || u[b] > t || dist[a][b] == INF) {
cout << -1 << '\n';
} else {
cout << dist[a][b] << '\n';
}
}
return 0;
}复杂度分析
每个城市只会被加入一次。每加入一个城市 $k$，进行一次 $N^2$ 级别松弛， 所以总计：
每个询问除增量更新外只需 $O(1)$ 输出判断，因此总时间复杂度为
距离矩阵空间复杂度为
样例
输入：
4 5
1 2 3 4
0 2 1
2 3 1
3 1 2
2 1 4
0 3 5
4
2 0 2
0 1 2
0 1 3
0 1 4输出：
-1
-1
5
4- $t=2$ 时城市 2 尚未上线，因此 $(2,0,2)$ 输出 $-1$；
- $t=2$ 时虽然城市 0、1 已上线，但当前不存在仅经过已上线城市的可达路径，输出 $-1$；
- $t=3$ 时城市 0、1、2 上线，可走 $0\to2\to1$，代价 $1+4=5$；
- $t=4$ 时城市 3 也上线，可走 $0\to2\to3\to1$，代价 $1+1+2=4$。
总结
本卷主要考查以下知识点：
- 递归与多重循环的时间复杂度分析；
- 二叉排序树的构造与遍历；
- 多栈共享存储空间；
- AOE/DAG 中的关键路径与项目工期；
- Huffman 树权值关系与贪心合并思想；
- 小根堆删除堆顶后的向下调整；
- 按时间增量开放中间点的 Floyd 最短路。