中南大学781考研真题权威解析与备考指南

高频考点TOP 5：

• 二叉树遍历与构造（近5年必考）：如“已知中序+后序序列构造二叉树”“层序遍历非递归实现”
• 图的遍历与最短路径：Dijkstra、Floyd、Kruskal、Prim算法的实现与比较（2021、2023年均考）
• 排序算法稳定性与时间复杂度：快速排序、归并排序、堆排序的稳定性判断（2020、2022年填空题）
• 线性表操作优化：顺序表插入/删除的时间复杂度分析（2019年简答题）
• 哈希表冲突处理：开放定址法与链地址法的优劣对比（2023年简答题）

2023年典型例题解析：

【题干】设二叉树采用二叉链表存储，设计算法求其叶子节点个数。要求：写出算法思想、伪代码、时间复杂度。

解题要点：

• 算法思想：递归或层序遍历，统计左右孩子均为空的节点
• 伪代码需体现节点结构定义、递归终止条件、计数逻辑
• 时间复杂度O(n)，空间复杂度O(n)（递归栈）或O(n)（队列）

易错陷阱：忽略空树情况；递归中漏掉根节点为叶子的情况；混淆“叶子节点”与“度为1节点”。

命题规律：

年起，C/C++考查从“语法记忆”转向“代码理解与调试能力”，重点考查：

• 指针与引用的区别：2022年填空题“设有int p, a=5; p=&a; p=10; 则a=?”正确答案10，但32%考生误答5
• 虚函数与多态：2021年简答题“基类指针调用派生类同名函数的条件”
• STL容器特性：vector与list的适用场景（2023年选择题）
• 内存管理：new/delete与malloc/free的区别（2020年综合题）

2022年典型错题分析：

【题干】分析以下代码输出：

#include 
using namespace std;
class Base { public: void show() { cout << "Base"; } };
class Derived : public Base { public: void show() { cout << "Derived"; } };
int main() {
    Base b = new Derived();
    b->show();
    delete b;
    return 0;
}

【答案】Base（非Derived）｜原因：show()未声明为virtual，不构成多态；基类指针仅能访问基类版本

备考建议：重点掌握“虚函数表”机制，理解指针类型与对象类型不一致时的调用规则。

命题趋势：

从“单一算法实现”转向“算法选择与优化”：

• 贪心算法：2021年考“活动安排问题”，要求证明贪心选择性质
• 动态规划：2023年考“编辑距离问题”，需写出状态转移方程与边界条件
• 回溯与分支限界：2020年“0-1背包问题”对比解法效率

2023年综合题解析：

【题干】某社交网络有n个用户，m条关注关系（有向）。定义“影响力传播路径”为：从用户A出发，经至多k步关注链可到达的用户数。设计算法计算每个用户的影响力值。

解题思路：

1. 建模：将关注关系构造成有向图（邻接表存储）
2. 对每个用户执行BFS（广度优先搜索），限制层数≤k
3. 统计每轮扩展的节点数之和
4. 时间复杂度：O(n×(n+m))，空间复杂度：O(n)

创新点：将理论算法与实际场景结合，考查“抽象建模→算法选型→复杂度分析”全链条能力。

年中南大学信息科学与工程学院781科目相关专业录取情况：

• 计算机科学与技术：录取86人，初试平均分298（781科目92.3分）
• 软件工程：录取72人，初试平均分292（781科目89.6分）
• 人工智能（新增专业）：录取48人，初试平均分305（781科目103.1分）
• 关键发现：781成绩≥100分者，复试通过率91.7%；≤80分者，仅32.4%进入复试

启示：781是“生死线”，需全力冲刺100+！