冠军资讯
木木不是木每年的 408 考研真题都会涌现出一批易错知识点，这些知识点往往看起来简单，实则暗藏玄机。本文将针对 2022 年和 2023 年的 408 考研真题，整理并深度剖析那些高频易错的知识点，希望能帮助大家避开雷区，顺利上岸。
线性表：看似简单，实则步步惊心
易错点 1：链表的删除操作
问题场景重现： 给定一个单链表，删除值为 x 的所有节点。
底层原理深度剖析： 很多人在删除链表节点时，容易忽略头节点和连续多个 x 节点的情况。需要维护一个前驱节点指针，以便在删除当前节点后，正确连接链表。
具体的代码/配置解决方案：
void deleteNodes(ListNode* head, int x) {
ListNode* dummyHead = new ListNode(-1); // 引入哑节点，简化头节点删除逻辑
dummyHead->next = head;
ListNode* prev = dummyHead;
ListNode* curr = head;
while (curr != nullptr) {
if (curr->val == x) {
prev->next = curr->next; // 删除当前节点
ListNode* temp = curr; // 暂存当前节点，避免内存泄漏
curr = curr->next; // 更新当前节点
delete temp; // 释放内存
} else {
prev = curr; // 更新前驱节点
curr = curr->next; // 更新当前节点
}
}
head = dummyHead->next; // 更新头节点
delete dummyHead;
}
实战避坑经验总结： 一定要使用哑节点，简化头节点删除逻辑；删除节点后要记得释放内存，避免内存泄漏；考虑连续多个 x 节点的情况，前驱节点指针的更新要格外小心。
易错点 2：顺序表的插入操作
问题场景重现： 在一个已排序的顺序表中插入一个元素，保持顺序表的有序性。
底层原理深度剖析： 顺序表的插入需要移动元素，很多人容易忽略边界情况，例如插入到表头或表尾的情况。还需要注意，如果顺序表已满，需要先扩容。
具体的代码/配置解决方案：
bool insertSorted(int arr[], int& len, int capacity, int val) {
if (len == capacity) {
return false; // 顺序表已满，插入失败
}
int i = len - 1;
while (i >= 0 && arr[i] > val) {
arr[i + 1] = arr[i]; // 将大于val的元素后移
i--;
}
arr[i + 1] = val; // 插入元素
len++; // 更新顺序表长度
return true;
}
实战避坑经验总结： 考虑顺序表已满的情况，及时扩容；注意边界情况，例如插入到表头或表尾；插入后需要更新顺序表的长度。
树与二叉树：递归虽美，陷阱重重
易错点 1：二叉树的遍历
问题场景重现： 给定一个二叉树，写出其后序遍历的非递归算法。
底层原理深度剖析： 后序遍历的非递归算法较为复杂，需要使用栈来模拟递归的过程。难点在于判断何时访问根节点，需要维护一个前驱节点指针，记录上次访问的节点。
具体的代码/配置解决方案：
vector<int> postorderTraversal(TreeNode* root) {
vector<int> result;
if (!root) return result;
stack<TreeNode*> s;
TreeNode* prev = nullptr;
TreeNode* curr = root;
while (curr || !s.empty()) {
while (curr) {
s.push(curr);
curr = curr->left;
}
curr = s.top();
if (!curr->right || curr->right == prev) {
result.push_back(curr->val);
s.pop();
prev = curr;
curr = nullptr; // 关键：置为空，避免重复访问左子树
} else {
curr = curr->right;
}
}
return result;
}
实战避坑经验总结： 理解后序遍历的特点，需要先访问左右子树，再访问根节点；维护一个前驱节点指针，判断何时访问根节点；栈的使用是关键，模拟递归过程。
易错点 2：平衡二叉树的调整
问题场景重现： 给定一个二叉排序树，插入一个节点后，使其重新平衡。
底层原理深度剖析： 平衡二叉树的调整涉及到四种旋转操作：LL、RR、LR、RL。需要根据不同的情况选择不同的旋转操作。很多人容易搞混这四种旋转操作。
具体的代码/配置解决方案： (此处省略具体的 AVL 树旋转代码，篇幅有限，主要考察理解四种旋转的原理)
实战避坑经验总结： 理解四种旋转操作的原理，画图辅助理解；分清楚哪种情况需要哪种旋转；注意更新节点的高度信息。
图：算法虽多，理解为王
易错点 1：图的遍历
问题场景重现： 给定一个图，判断其是否为连通图。
底层原理深度剖析： 可以使用深度优先搜索或广度优先搜索来判断图的连通性。需要注意，图可能存在多个连通分量。只有当从任意一个节点出发，能够访问到所有其他节点时，图才是连通图。
具体的代码/配置解决方案： (此处省略具体的 DFS/BFS 代码，篇幅有限，主要考察算法理解)
实战避坑经验总结： 选择合适的遍历算法，深度优先搜索或广度优先搜索；注意处理多个连通分量的情况；理解连通图的定义。
易错点 2：最短路径算法
问题场景重现： 给定一个带权图，求从起点到终点的最短路径。
底层原理深度剖析： 可以使用 Dijkstra 算法或 Floyd 算法求解最短路径。Dijkstra 算法适用于单源最短路径，Floyd 算法适用于多源最短路径。需要注意，Dijkstra 算法不能处理负权边的情况。
具体的代码/配置解决方案： (此处省略具体的 Dijkstra/Floyd 代码，篇幅有限，主要考察算法理解)
实战避坑经验总结： 选择合适的算法，Dijkstra 算法或 Floyd 算法；注意 Dijkstra 算法不能处理负权边的情况；理解最短路径的定义。
