南邮数据结构考研真题权威解析平台

树结构：非线性结构的核心

树是南邮数据结构考研真题的难点模块，分值占比约25分，重点考查二叉树的遍历、线索化、哈夫曼树及树与二叉树的转换。

叉树遍历的递归与非递归实现

年编程题要求“非递归实现中序遍历”，标准解法使用栈模拟递归过程：

void InOrderTraversal(BiTree T) {
    SqStack S;
    InitStack(S);
    BiTree p = T;
    while (p || !StackEmpty(S)) {
        if (p) {
            Push(S, p);
            p = p->lchild;
        } else {
            Pop(S, p);
            visit(p); // 访问结点
            p = p->rchild;
        }
    }
}

易错点：忘记在访问结点后转向右子树；栈初始化缺失；循环条件遗漏栈非空判断。

叉排序树（BST）的插入与删除

年简答题考查“在二叉排序树中删除值为x的结点”，需分三种情况处理：

1. 结点为叶子：直接删除
2. 结点只有左子树或右子树：用其子树替代
3. 结点有左右子树：用其左子树的最大值或右子树的最小值替代，再删除替代结点

真题示例：删除值为50的结点后，需确保二叉排序树性质不变（左子树所有值 < 根 < 右子树所有值）。

哈夫曼树与哈夫曼编码

年综合应用题要求“构造哈夫曼树并计算WPL（带权路径长度）”，权重为{5,9,12,13,16,45}，构造过程如下：

• 初始6棵树：5,9,12,13,16,45
• 合并5+9=14 → {12,13,14,16,45}
• 合并12+13=25 → {14,16,25,45}
• 合并14+16=30 → {25,30,45}
• 合并25+30=55 → {45,55}
• 合并45+55=100 → 根

最终WPL = 5×4 + 9×4 + 12×3 + 13×3 + 16×3 + 45×1 = 224。

图结构：复杂关系建模的关键

图是南邮数据结构考研真题的高阶模块，分值约20-25分，重点考查图的存储结构、遍历算法、最小生成树、最短路径与拓扑排序。

图的存储结构选择

年选择题考查“稀疏图适合用邻接表存储，稠密图适合用邻接矩阵”，依据是：

• 邻接矩阵：空间复杂度O(n²)，适合顶点数少、边数多的稠密图
• 邻接表：空间复杂度O(n+e)，适合顶点数多、边数少的稀疏图

真题数据：某图有1000个顶点、2000条边，则邻接表存储需约2000×2（双向图）+1000×指针域 ≈ 5KB，而邻接矩阵需1000×1000×1bit ≈ 125KB。

最短路径算法：Dijkstra与Floyd

年编程题要求“用Dijkstra算法求单源最短路径”，核心步骤如下：

1. 初始化：S={源点}，dist[]为源点到各点直接距离
2. 循环n-1次：从V-S中选dist最小的顶点u加入S
3. 更新：对所有v∈V-S，若dist[u]+arc[u][v] < dist[v]，则更新dist[v]

时间复杂度O(n²)，若用堆优化可达O((n+e)logn)。

拓扑排序与AOV网

年综合应用题考查“课程安排的拓扑排序”，给定先修关系：

• C1→C2, C1→C3
• C2→C4, C3→C4, C3→C5
• C4→C6, C5→C6

拓扑序列可能为：C1,C2,C3,C4,C5,C6 或 C1,C3,C2,C5,C4,C6 等，但C1必在C6前，C4、C5必在C6前。

排序与查找：算法设计的核心能力

排序与查找是南邮数据结构考研真题的高频模块，每年必考15-20分，重点考查算法原理、时间复杂度分析及稳定性判断。

排序算法对比表

分查找的边界处理

年填空题考查“在有序数组[1,3,5,7,9]中查找元素5，返回下标”，正确答案为2（0-based）。真题易错点：

• 循环条件应为low <= high，而非<
• 中点计算应为mid = low + (high
- low)/2，避免整数溢出
• 边界更新：左边界low = mid + 1，右边界high = mid
- 1

哈希表的冲突处理

年简答题考查“开放定址法中的线性探测与二次探测”，给定哈希函数H(k) = k mod 7，关键字序列{15, 22, 30, 35}的存储过程：

• mod 7 = 1 → 存入1
• mod 7 = 1 → 冲突，线性探测→2
• mod 7 = 2 → 冲突，线性探测→3
• mod 7 = 0 → 存入0

次探测法可避免“一次聚集”，但可能产生“二次聚集”，实际应用中常采用双重哈希（如H_i(k) = (H(k) + iH'(k)) mod m）。

动态数据结构与算法优化

动态结构与优化是南邮数据结构考研真题的高阶考查点，近年出现频率上升，重点考查递归优化、动态规划、贪心算法等。

递归转迭代：斐波那契数列

递归实现：F(n) = F(n-1) + F(n-2)时间复杂度O(2ⁿ)，存在大量重复计算。

优化方案1（动态规划）：

int fib(int n) {
    if (n <= 1) return n;
    int a = 0, b = 1, c;
    for (int i = 2; i <= n; i++) {
        c = a + b;
        a = b;
        b = c;
    }
    return b;
}

时间复杂度O(n)，空间复杂度O(1)。

贪心算法：活动安排问题

给定n个活动{1,2,...,n}，每个活动有开始时间s_i与结束时间f_i，要求选择最多的不重叠活动：

1. 按结束时间f_i升序排序
2. 依次选择与已选活动不重叠的活动（s_j ≥ f_k）

年真题示例：活动区间为[1,4)、[3,5)、[0,6)、[5,7)、[3,8)、[5,9)、[6,10)、[8,11)、[8,12)、[2,13)、[12,14)，最优解为4个活动（[1,4)、[5,7)、[8,11)、[12,14)）。

算法优化策略总结

• 时间优化：降低时间复杂度（如O(n²)→O(nlogn)），使用空间换时间（哈希表、预计算）
• 空间优化：原地操作（如链表反转）、滚动数组（DP优化）、复用临时变量
• 剪枝策略：回溯算法中提前终止无效分支
• 缓存机制：记忆化递归（Memoization）避免重复计算