考研数据结构习题推荐2026｜2026考研数据结构习题2026权威汇总与深度解析

归并排序（Merge Sort）是典型稳定排序算法：

1. 分：递归将数组二分至单元素
2. 治：合并两个有序子数组，比较时相等元素保留原顺序

时间复杂度：最好、最坏、平均均为O(n log n)

空间复杂度：O(n)（需辅助数组）

稳定性：稳定（合并时当a[i] == b[j]时，先取a[i]）

class ListNode {
    constructor(val) {
        this.val = val;
        this.next = null;
    }
}
class LinkedList {
    constructor() {
        this.head = null;
        this.size = 0;
    }
    // 在第index位置插入（0 ≤ index ≤ size）
    insert(index, val) {
        if (index < 0 || index > this.size) return false;
        const newNode = new ListNode(val);
        if (index === 0) {
            newNode.next = this.head;
            this.head = newNode;
        } else {
            let prev = this.head;
            for (let i = 0; i < index 
- 1; i++) prev = prev.next;
            newNode.next = prev.next;
            prev.next = newNode;
        }
        this.size++;
        return true;
    }
    // 删除第index位置节点（0 ≤ index < size）
    remove(index) {
        if (index < 0 || index >= this.size) return null;
        let removed;
        if (index === 0) {
            removed = this.head.val;
            this.head = this.head.next;
        } else {
            let prev = this.head;
            for (let i = 0; i < index 
- 1; i++) prev = prev.next;
            removed = prev.next.val;
            prev.next = prev.next.next;
        }
        this.size--;
        return removed;
    }
    // 遍历打印
    traverse() {
        let current = this.head;
        let result = [];
        while (current) {
            result.push(current.val);
            current = current.next;
        }
        return result.join(' → ');
    }
}

class TreeNode {
    constructor(val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}
class BST {
    constructor() {
        this.root = null;
    }
    insert(val) {
        const newNode = new TreeNode(val);
        if (!this.root) {
            this.root = newNode;
            return true;
        }
        let current = this.root;
        while (true) {
            if (val < current.val) {
                if (!current.left) {
                    current.left = newNode;
                    return true;
                }
                current = current.left;
            } else if (val > current.val) {
                if (!current.right) {
                    current.right = newNode;
                    return true;
                }
                current = current.right;
            } else {
                return false; // 不允许重复值
            }
        }
    }
    search(val) {
        let current = this.root;
        while (current) {
            if (val === current.val) return true;
            if (val < current.val) current = current.left;
            else current = current.right;
        }
        return false;
    }
}

KMP算法核心思想：利用匹配失败后已匹配部分的信息，避免主串指针回溯

1. 计算模式串T的next数组（最长公共前后缀长度）
2. 匹配时：
   • 若s[i] == t[j]，i++，j++
   • 若不等，j = next[j-1]（关键优化点）

function buildNext(t) {
    const next = [0];
    let j = 0;
    for (let i = 1; i < t.length; i++) {
        while (j > 0 && t[i] !== t[j]) j = next[j 
- 1];
        if (t[i] === t[j]) j++;
        next[i] = j;
    }
    return next;
}
function kmp(s, t) {
    const next = buildNext(t);
    let i = 0, j = 0;
    while (i < s.length && j < t.length) {
        if (s[i] === t[j]) { i++; j++; }
        else j = j === 0 ? 0 : next[j 
- 1];
    }
    return j === t.length ? i 
- j : -1;
}

时间复杂度：O(n + m)（n为主串长度，m为模式串长度）

问题：设计一个系统，支持用户实时查询最近10分钟内点击量最高的100个页面（Top-K）

设计方案：堆 + 哈希表 + 时间窗口

1. 用最小堆维护Top-100（堆顶为最小值）
2. 哈希表记录页面ID→堆中索引（O(1)定位）
3. 时间窗口：每分钟清理过期记录（堆中节点带时间戳）

优势：

• 查询Top-K：O(1)
• 更新点击：O(log k)（k=100）
• 空间复杂度：O(k + n)（n为活跃页面数）