2020数据结构考研真题10套｜权威解析与系统备考指南

树与图：平衡树、哈希表与图算法的综合应用

典型真题（上交大·2020·第15题）：设计一个支持以下操作的数据结构：① 插入键值对；② 删除指定键；③ 查询键是否存在；④ 查询键的前驱（小于该键的最大键）；⑤ 查询键的后继（大于该键的最小键）。要求所有操作时间复杂度为O(log n)。

命题意图：考查平衡二叉搜索树（如AVL、红黑树）的实际应用能力。标准解法是使用红黑树（C++的std::map即基于红黑树），但需手写实现以理解其旋转与重平衡机制。

核心机制：红黑树通过五条性质（根黑、红父必黑、黑高一致等）保证最坏情况下O(log n)时间复杂度。插入时可能触发：左旋、右旋、颜色翻转三种操作；删除时则需处理双黑节点问题，通过旋转与颜色调整恢复平衡。

Node insert(Node root, int key) {
    if (!root) return new Node(key, BLACK);
    if (key < root->key) root->left = insert(root->left, key);
    else if (key > root->key) root->right = insert(root->right, key);
    // 插入后修正红黑性质（省略具体旋转逻辑）
    return balance(root);
}

图算法重点：2020年真题对Dijkstra、Floyd、Kruskal、Prim算法考查深入。例如清华第10题要求用Dijkstra+堆优化求单源最短路径，并分析其时间复杂度（O((V+E) log V)）；哈工大第12题则要求实现Kruskal算法并用并查集优化连通性判断，强调路径压缩（find(x)）与按秩合并（union(x,y)）的结合使用。

排序与查找：高效算法的工程实现

典型真题（浙大·2020·第8题）：给定一个长度为n的整数数组，其中可能存在重复元素。请设计一个算法，在O(n)时间复杂度内找出所有出现次数大于n/3的元素（最多两个），空间复杂度O(1)（不计输出空间）。

命题意图：考查Boyer-Moore Majority Vote Algorithm的扩展应用。标准解法是维护两个候选元素与计数器，遍历数组时：
① 若当前元素等于候选1，则c1++；② 否则若等于候选2，则c2++；③ 否则若c1=0，则候选1=当前元素，c1=1；④ 否则若c2=0，则候选2=当前元素，c2=1；⑤ 否则c1--, c2--。最后二次遍历验证候选是否满足条件。

vector majorityElement(vector& nums) {
    int cand1 = 0, cand2 = 1, cnt1 = 0, cnt2 = 0;
    for (int x : nums) {
        if (x == cand1) cnt1++;
        else if (x == cand2) cnt2++;
        else if (cnt1 == 0) { cand1 = x; cnt1 = 1; }
        else if (cnt2 == 0) { cand2 = x; cnt2 = 1; }
        else { cnt1--; cnt2--; }
    }
    // 验证
    cnt1 = cnt2 = 0;
    for (int x : nums) {
        if (x == cand1) cnt1++;
        else if (x == cand2) cnt2++;
    }
    vector res;
    if (cnt1 > nums.size()/3) res.push_back(cand1);
    if (cnt2 > nums.size()/3) res.push_back(cand2);
    return res;
}

查找算法延伸：2020年真题还考察了二分查找的变体，如清华第6题要求在旋转排序数组中查找最小值（存在重复元素），需处理nums[mid] == nums[right]的边界情况，避免死循环；复旦第9题则要求在有序矩阵（行、列均递增）中查找目标值，可采用从右上角开始的“Z字形搜索”，时间复杂度O(m+n)。

动态数据结构：跳表、Trie与LFU缓存设计

典型真题（复旦·2020·第14题）：实现一个支持get(key)与put(key,value)操作的LFU（Least Frequently Used）缓存，要求两者时间复杂度均为O(1)。缓存容量为capacity，当缓存满时，移除使用频率最低的键；若频率相同，则移除最近最少使用的键。

命题意图：考查对双向链表与哈希表组合应用的掌握。标准解法是：
① 使用哈希表keyMap存储键到结点的映射；
② 使用哈希表freqMap存储频率到双向链表头的映射，链表按访问时间排序（头新尾旧）；
③ 维护最小频率minFreq。

每次get操作：若键存在，更新其频率（从旧频链表移除，加入新频链表头部），若旧频链表空且为minFreq，则更新minFreq；put操作：若键已存在，则更新值并调用get；若不存在，创建新结点，若缓存满，则从minFreq链表尾部删除结点，再插入新结点至频率1的链表头部。

其他动态结构：2020年哈工大第18题要求实现Trie树支持前缀统计；武大第20题考察跳跃表（Skip List）的插入逻辑，需随机决定层数并更新各层指针。这些题目均强调：动态结构的设计需兼顾时间效率与空间开销，且对边界条件（如空树、单结点）处理要求严格。

算法设计：贪心、动态规划与回溯的实战技巧

典型真题（北大·2020·第22题）：给定n个活动，每个活动有开始时间s[i]和结束时间f[i]（s[i] < f[i]），要求选择最多的互不重叠活动（即活动时间区间不相交）。证明贪心策略（按结束时间升序选择）是最优的，并给出算法。

命题意图：考查贪心算法的正确性证明能力。标准解法：
① 按f[i]升序排序；
② 选择第一个活动，然后依次选择与已选活动不重叠且结束时间最早的活动。

最优性证明：设贪心解为G = {g₁, g₂, ..., gₖ}，最优解为O = {o₁, o₂, ..., oₘ}（m > k）。因贪心选择结束最早，必有f(g₁) ≤ f(o₁)；又因活动不重叠，o₂的开始时间≥f(o₁) ≥ f(g₁)，故g₂可选，归纳可得gᵢ可与oᵢ一一对应，即k ≥ m，矛盾。因此贪心解即为最优解。

int maxActivities(vector>& acts) {
    sort(acts.begin(), acts.end(), [](auto& a, auto& b){
        return a.second < b.second;
    });
    int count = 0, lastEnd = INT_MIN;
    for (auto& act : acts) {
        if (act.first >= lastEnd) {
            count++;
            lastEnd = act.second;
        }
    }
    return count;
}

动态规划重点：2020年清华第23题要求求解“编辑距离”（Levenshtein Distance），需构建dp[i][j]表示text1前i字符转为text2前j字符的最小操作数，状态转移方程为：
dp[i][j] = dp[i-1][j-1]（若相等）
min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1（否则）

回溯法应用：如南京大学第21题要求生成所有括号组合（n对括号），需用回溯控制左括号数量≤n、右括号≤左括号，确保合法性。易搜职考网统计显示，2020年真题中动态规划与回溯题占比超35%，是高分关键。