第20套终于刷到了这个系列的里程碑位置。我备考大学院情报系笔试的时候一直把《线性代数数据结构》这套组合当作复习主轴的缩影一套题里一个在练数学推导的严谨性一个在练逻辑抽象和代码落地的能力正好覆盖了入试笔试最看重的两类思维。如果你也正在准备大学院入试或者准备国内408方向的考研笔试这套第20回的练习题值得你从头到尾完完整整做一遍而不是只看答案。这套练习我做完花了大概70分钟严格模拟考试节奏。交卷后复盘发现里面设置的题目非常典型线性代数部分集中在特征值、方程组、二次型数据结构部分集中在双端队列、二叉树、图、排序。没有偏题怪题但每一道都有陷阱属于那种你觉得自己会但一做就错的题。这篇文章我就把整套题拆开讲把解题过程、背后的原理、以及我在做题时踩过的坑都写清楚尤其是那些答案书上不会告诉你的应试细节。1. 第20套练习在押什么题型结构与考察逻辑1.1 为什么情报系入试几乎必考这两科我当初决定考情报系大学院的时候最困惑的一件事是为什么笔试总要考线性代数和数据结构跟计算机最直接相关的操作系统、计算机网络反而放在后面后来复习时间长了才想明白这两科不是单纯考知识点而是在考一种算法化思维的能力。线性代数在笔试题里的角色是计算与推理的基础设施。特征值分解、矩阵秩、线性方程组的解结构这些东西是机器学习、图像处理、数值计算等研究方向的地基。老师出这道题看的是你能不能把抽象的矩阵运算落实成具体的数字结果以及你敢不敢面对复杂计算时不跳步。数据结构则更直接它考察你对信息组织方式的理解。数组、链表、树、图、哈希表这些是程序的骨架不管你是做系统软件还是应用开发都逃不过它们。这两个科目还有一个共同点都强调结构的把握。线性代数研究向量空间和线性映射的结构数据结构研究数据元素之间的关系结构。所以在第20套这种练习中我能明显感觉到出题人有意让两科形成呼应前面的矩阵就是后面的二维数组特征向量就是空间中的有序映射跟你用邻接矩阵存图时的索引逻辑完全是一回事。这种跨科目的底层关联才是应试中最值得抓住的东西。1.2 第20套题目的整体结构、时间分配与目标整套练习合计10道题主观题为主满分100分。线性代数5道数据结构5道题型分布如下科目题型题量分值线性代数特征值与特征向量计算1题10分线性代数含参数线性方程组判定1题12分线性代数二次型标准化与正定性1题12分线性代数向量组线性相关性计算题1题8分线性代数矩阵运算与秩的性质概念题1题8分数据结构双端队列相关题型1题10分数据结构二叉树遍历与重建1题12分数据结构图的存储数组法与遍历1题12分数据结构排序算法过程与性质分析1题8分数据结构哈希表冲突处理计算1题8分我的建议时间分配是线性代数部分45分钟数据结构部分45分钟剩余20分钟检查。为什么要这样分配因为线代题的运算量集中在前面脑子清醒的时候算特征值和方程组最不容易错而数据结构的代码分析题需要仔细读题放到注意力稍微放松的后半段做反而合适。实际做题的时候我给自己定的目标是简单计算题保证全对复杂题至少拿下第一问。这10道题里至少6道属于细心就能全对的送分题你没必要追求全卷满分但送分题一定不能丢。2. 线性代数真题拆解第20套里的三道必练题2.1 【問1】矩阵特征值分解一道10分钟内必须拿下的题这道题给了一个具体的2阶矩阵A [ 1 2 ] [ 2 1 ]要求求特征值和特征向量并利用特征值分解计算 A^10。这题思路清晰但计算量不小很考验基本功。先求特征值写出特征多项式det(A - λI) | 1-λ 2 | | 2 1-λ | (1-λ)^2 - 4 λ^2 - 2λ - 3 (λ - 3)(λ 1)所以特征值是 λ1 3λ2 -1。这一步比较简单但有个小坑特征多项式展开之后要记得验根。两个特征值要满足迹等于2两个根之和是3 (-1) 2要满足行列式等于-3两个根之积是3 × (-1) -3。我每次算完都会拿这两个条件快速验证一遍避免符号搞错。接下来求对应特征向量。对 λ 3(A - 3I)v 0 → [ -2 2 ][x] [0] [ 2 -2 ][y] [0]得到 -2x 2y 0即 x y。取特征向量 v1 (1, 1)^T。对 λ -1(A I)v 0 → [ 2 2 ][x] [0] [ 2 2 ][y] [0]得到 x y 0取特征向量 v2 (1, -1)^T。到这里如果题目只要求特征值和特征向量你已经可以拿满分了。但这道题的第二问才是精髓要计算 A^10。常规做法是把矩阵连乘10次理论上能算但极不现实考试时间也支撑不了。正确的思路是特征值分解。设 P [ v1 v2 ] [ 1 1 ] [ 1 -1 ]则 P^(-1) A P diag(3, -1)所以 A P diag(3, -1) P^(-1)。又因为 P 满足 P^(-1) (1/2)P这个阶矩阵的逆等于自身乘以1/2原因是行列式为-2且矩阵对称所以A^10 P diag(3^10, (-1)^10) P^(-1) (1/2) · [ 1 1 ] [ 59049 0 ] [ 1 1 ] [ 1 -1 ] [ 0 1 ] [ 1 -1 ]具体计算先算中间部分的乘积最后结果是A^10 [ 29525 29524 ] [ 29524 29525 ]这道题做错的人主要错在两个地方。一是特征向量不归一化就直接套公式二是忘记 P^(-1) 是带系数的。我特别想提醒你用特征值分解做矩阵幂的时候P^-1 一定不能漏写。很多同学算到最后一步发现结果不对称回头检查才发现忘记了 P 的逆。矩阵幂的结果对于对称矩阵通常保持结构特征这里对角线相等副对角线相等你可以用这个规律来检验最终结果。2.2 【問2】含参数线性方程组三种解的判定条件这道题是给了一个含参数 k 的三元线性方程组要求讨论 k 取什么值时方程组有唯一解、无解、无穷多解。题目形式如下x y kz 1 x ky z 1 kx y z -2这种含参方程组的讨论在入试和考研中都是高频题。它的标准做法不是简单地算行列式而是先对增广矩阵做行变换边化简边讨论。写出增广矩阵[ 1 1 k | 1 ] [ 1 k 1 | 1 ] [ k 1 1 | -2 ]用第一行消去下面两行的x项。第二行减第一行得到(k - 1)y (1 - k)z 0 即 (k - 1)(y - z) 0第三行减第一行的 k 倍得到(k - 1)x (1 - k)z -3 即 (k - 1)(x - z) -3注意这里不能盲目把 (k-1) 除掉因为 k 1 时整个式子会变成 0 0 或 0 -3这是讨论的关键节点。分情况讨论当 k 1 时方程组变成三个方程x y z 1、x y z 1、x y z -2。前两个方程一样第三个方程与前两个矛盾所以方程组无解。这里就是判断无解的典型信号化简后出现了 0 常数 的形式。当 k ≠ 1 时可以继续化简。由 (k-1)(x-z) -3 得到 x z - 3/(k-1)。由 (k-1)(y-z) 0 得到 y z。代入原方程第一式z - 3/(k-1) z kz 1 整理(k 2)z (k 2)/(k - 1)现在需要再讨论 k -2 的情况。当 k -2 时等式变为 0 · z 0这时 z 是自由变量方程组有无穷多解。当 k ≠ -2 时z 1/(k - 1)y zx z - 3/(k-1) -2/(k-1)方程组有唯一解。所以完整的结论k 的取值解的个数k 1无解k -2无穷多解k ≠ 1 且 k ≠ -2唯一解这道题我做完后特地重新验证了 k -2 的情况。以 z t 为自由变量则 y tx t 1代入三个方程都能成立说明确实是无穷多解。验证这一步极其重要因为只讨论到行列式不为零还不够含参方程组必须在除参以后重新检查是否出现了矛盾或恒等。这个习惯建议你从备考早期就养成到了考场才不会慌。2.3 【問3】二次型的正定性判断与正交变换最后一道线代大题是关于二次型标准化。题目给了一个三元二次型f(x1, x2, x3) 2x1² 5x2² 5x3² 4x1x2 - 4x1x3 - 8x2x3第一问判断这个二次型是否正定第二问通过正交变换将其化为标准形。这道题直接考察矩阵与二次型的对应关系。首先写出二次型对应的对称矩阵A [ 2 2 -2 ] [ 2 5 -4 ] [ -2 -4 5 ]判断正定性有两条路可以走。第一条是顺序主子式法一阶顺序主子式 D1 2 0 二阶顺序主子式 D2 | 2 2 ; 2 5 | 10 - 4 6 0 三阶顺序主子式 D3 det(A)。算 det(A)按第一行展开det(A) 2 × (5×5 - (-4)×(-4)) - 2 × (2×5 - (-4)×(-2)) (-2) × (2×(-4) - 5×(-2)) 2 × 9 - 2 × 2 (-2) × 2 18 - 4 - 4 10 0三个顺序主子式都大于0所以二次型正定。这一步用顺序主子式法最直接而且计算量小。第二问正交变换化标准形需要求出矩阵 A 的特征值。这里我踩过一个坑试图直接硬解三阶行列式展开的特征多项式结果算到一半符号就乱了。正确做法是先用特征多项式性质缩小范围。矩阵 A 的迹为 2 5 5 12行列式为 10所有二阶主子式之和为 6 9 6 21。所以特征多项式为det(A - λI) -λ³ 12λ² - 21λ 10也就是要解 λ³ - 12λ² 21λ - 10 0。这时候不要盲目猜根先看常数为 -10试 λ 1代入得 1 - 12 21 - 10 0说明 λ 1 是一个根。再因式分解(λ - 1)(λ² - 11λ 10) 0 (λ - 1)(λ - 1)(λ - 10) 0所以特征值是 λ 1二重和 λ 10。对应的正交变换标准形就是f y1² y2² 10y3²到这一步标准形的答案就出来了。后面的正交矩阵 Q 的构造本质上是求特征子空间的标准正交基。我强烈建议你在这道题上养成一个习惯先利用迹、行列式、顺序主子式这些不变量去猜特征值结构再验证而不是一上来就死算。第20套这道题就是典型的背公式容易做对难的题它要求你对矩阵的代数不变量非常敏感。3. 数据结构真题拆解树、图、排序与双端队列3.1 【問4】双端队列概念、循环数组实现以及双栈方案的坑数据结构部分第一道就来了一个有意思的题双端队列double-ended queue。它给你一个概念判断题和一个小设计题。概念上双端队列是允许在队列两端进行插入和删除操作的线性表也就是你既可以 popleft 也可以 popright。实现层面笔试里最常考的实现方式是循环数组。为什么用循环数组而不用简单的线性数组因为双端队列需要频繁在头部操作如果线性数组从头部删除所有元素都要前移时间复杂度是 O(n)。用循环数组配合头指针 front 和尾指针 back就能让两端的插入、删除都是 O(1) 的均摊复杂度。核心逻辑是入队操作back (back 1) % capacity在 back 处放入元素出队操作取 front 处元素front (front 1) % capacity队空条件front back队满条件(back 1) % capacity front。注意这个实现中通常要浪费一个数组位置来区分队空和队满否则两个条件都是 front back无法区分。笔试中很多同学容易在这个细节上栽跟头。我在第一次写循环数组的时候也是忘记了保留空位结果队空和队满判定混在一起调试了很久。配套的附加题是用两个栈实现双端队列。这道题的正确结论是用两个栈实现普通队列很容易但实现双端队列相当困难或者说很难做到所有操作都是高效的 O(1)。原因在于栈是 LIFO后进先出而双端队列需要在两端都做到 FIFO 语义。有人会想出这样的方案front 栈负责头部操作back 栈负责尾部操作当 front 栈空时把 back 栈全部倒入 front 栈。我尝试过最终发现这个方案在某些操作序列下会出错。举个例子先后 pushBack(2)、pushBack(3)再 pushFront(1)。此时 front 栈是 [1]back 栈是 [2,3]。当连续两次 popFront 时第一次从 front 栈弹出 1正确第二次 front 栈空了于是把 back 栈全部倒入 front 栈back 栈栈顶是 3倒入后 front 栈变成 [3,2]弹出的是 3而按双端队列的顺序现在前端的元素应该是 2。这就说明双栈方案的 naive 版本有致命缺陷。笔试里如果时间允许把这个反例写出来比硬写代码更得分它能展示你真的理解了栈和队列的根本差异。3.2 【問5】二叉树遍历前序中序还原二叉树这道题给了一棵二叉树的前序遍历序列和中序遍历序列要求还原这棵二叉树并写出后序遍历序列。题目是我刷题时经常见到的经典款但每次做都值得认真对待因为它能一次性检查你对三种遍历顺序的掌握程度。题目给出前序遍历A B D C E 中序遍历B D A E C前序遍历的第一个节点一定是根节点。所以 A 是根。在中序遍历中根节点 A 的左边是左子树的中序序列右边是右子树的中序序列。于是左子树中序为 B D右子树中序为 E C。接下来处理左子树。前序遍历序列中紧接着根节点 A 后面的是 B D这个顺序就是左子树的前序遍历。左子树前序为 B D中序为 B D。前序的第一个节点是 B所以 B 是左子树的根。中序序列为 B DB 在 D 前面说明 D 是 B 的右孩子。再处理右子树。前序中的右子树部分是 C E根是 C。中序序列为 E CE 在 C 前面说明 E 是 C 的左孩子。还原出来的树结构就是A为根左孩子B右孩子CB 的右孩子是DC 的左孩子是E。这颗树的后序遍历是D B E C A。这道题我做完之后特意写了个快速验证方法把还原出来的树再手动跑一遍三种遍历前序是 ABDCE中序是 BDAEC全部吻合说明还原无误。这个方法虽然原始但非常有效笔试时多花两分钟检查不算浪费。另外题目还有一个第二问用非递归方式完成后序遍历。许多同学只会写递归版本遇到非递归就卡住了。我分享一个常用的双栈法思路维护两个栈s1 负责遍历节点s2 负责记录访问路径。出栈顺序稍微绕但核心逻辑是先把根节点压入 s1循环弹出 s1 栈顶节点并把该节点压入 s2然后将该节点的左右孩子依次压入 s1。因为栈的 LIFO 特性s2 最终弹出的顺序正好是后序遍历。这个技巧对笔试中的代码填空题特别有用建议熟记。3.3 【問6】图的存储与排序算法408常考点速过这道题是一个综合题考查两个常态化考点图的存储结构以及排序算法的稳定性。图的部分给了一个带权无向图要求写出用邻接矩阵和邻接表存储时的表示方式并分析两者的空间复杂度。邻接矩阵适合稠密图空间复杂度 O(n²)判断两点之间是否有边只需 O(1) 时间邻接表适合稀疏图空间复杂度 O(n e)遍历某个顶点的所有邻接点是 O(deg(v))。这里我还想提一个408考纲里反复出现的细节用数组模拟邻接表也就是链式前向星。这种写法比链表更高效笔试写代码时不容易写崩。核心代码框架如下struct Edge { int to, w, next; // to: 终点, w: 边权, next: 下一条边 } edge[MAXM]; int head[MAXN], cnt 0; void addEdge(int u, int v, int w) { edge[cnt] {v, w, head[u]}; head[u] cnt; } // 遍历 u 的所有邻接边 for (int i head[u]; i ! -1; i edge[i].next) { int v edge[i].to; // 处理 u - v 这条边 }这种用数组代替指针的实现方式在笔试中最大的好处是省去了动态内存分配的麻烦也便于快速调试。我第一次在题目里写链式前向星的时候老是把 next 指针的含义搞混后来记住了next 指向的是同一起点的上一条边在数组中的下标就再也没错了。排序算法的部分题目给了一组数据要求写出第一趟快速排序的结果。快速排序的核心是挖坑填数分治。以序列 49, 38, 65, 97, 76, 13, 27, 49 为例取第一个元素49作为枢轴。从右往左找比49小的数找到27填入左边的坑从左往右找比49大的数找到65填入右边的坑。反复这个过程第一趟结束时序列会变成 27, 38, 13, 49, 76, 97, 65, 49此时49已经落在最终位置左右两边分别递归排序。我强烈建议你在平时练习时把每一趟快排的结果都完整写下来因为复试面试时考官经常让你口头描述排序过程练过和没练过差别很大。另外一个高频记忆点是排序稳定性特别是408选择题里经常考的几种。我把常见结论整理成这样一份表排序算法平均时间复杂度最坏时间复杂度空间复杂度稳定性冒泡排序O(n²)O(n²)O(1)稳定直接插入排序O(n²)O(n²)O(1)稳定简单选择排序O(n²)O(n²)O(1)不稳定快速排序O(n log n)O(n²)O(log n)不稳定堆排序O(n log n)O(n log n)O(1)不稳定归并排序O(n log n)O(n log n)O(n)稳定希尔排序约O(n^1.3)与增量序列有关O(1)不稳定判断稳定性的口诀非常简单只要存在跨距离交换基本都不稳定。选择排序会跨过中间元素直接交换所以不稳定快排的交换是跨距离的堆排的调整也是跨层交换。插入排序和冒泡排序只与相邻元素交换不会破坏相对顺序所以稳定。归并排序的合并过程中遇到相等元素时优先取左边元素也能保持稳定。这些规律比死记硬背靠谱得多。4. 笔试现场的常见错误与自查清单4.1 考生最容易在什么地方丢分刷了这么多套题我发现笔试丢分往往不是因为你不会而是因为你陷入了一些固定的坏习惯。我把这些常见错误整理成踩坑清单每一届备考的人几乎都会中招几条线性代数符号错误。特征值符号写反是高频错误。特征多项式写成 det(λI - A) 和 det(A - λI) 特征值相同但展开后的首项符号不同很多同学写到一半突然换写法结果符号错乱。含参数方程组只讨论行列式。有人一看到参数就直接算系数矩阵行列式令行列式为0得出结论k不确定时无解或无穷多解。这是不对的行列式为0只能说明矩阵不满秩还要结合增广矩阵的秩一起判断否则会漏掉 k1 那种行列式已经非0但方程矛盾的情况。数据结构边界条件漏判。链表的头节点可能为空循环队列的 front 和 back 的更新顺序容易颠倒二叉树递归时忘了判断 root 为 NULL。这些错误我真挚地建议你在平时写代码的时候把所有空满只有一个元素的特殊情况单独列出来检查一遍。哈希表冲突处理不写完整过程。哈希表相关的题目通常需要展示发生了几次冲突每次探测的位置很多同学习惯直接写结果导致过程分几乎全丢。排序算法过程不写中间结果。让考官看到你每一步的分治过程比只写个最终序列得分多得多尤其是快排和堆排的建堆过程。4.2 我总结的自查三件套做完第20套卷子以后我用一套自查流程检查整张卷子花了大约15分钟查出3处计算失误。这个习惯建议你也建立起来。第一线性代数部分用不变量复查。特征值的和等于矩阵的迹特征值的积等于矩阵的行列式。二次型的标准形系数之和等于矩阵的迹。只要发现这些不变量对不上说明某个环节算错了马上回头找。这个方法几乎不用花额外时间却极其有效。第二数据结构部分用小样例复现复查。写出树的遍历序列后重新用原始数据跑一遍写出快排过程后检查左侧所有元素是否都小于枢轴、右侧所有元素是否都大于等于枢轴。很多错误在这一步就能暴露。第三检查时间分配。如果你发现线性代数部分花了超过60分钟那数据结构的大题必然时间不够考场上确实遇到这种情况时果断放弃最后一问的细节把已有步骤和时间用于其他题目的检查。平时练习也建议严格卡时间第20套我给自己定的时间是70分钟实际使用草稿纸写过程、答题纸写结论的方式减少誊写失误。5. 第20套之后的复习方向以我个人的经验作为结尾刷到第20套意味着你已经完成了大部分基础阶段的积累。这时候不要再盲目开新题而是应该回头做两件事。第一把过去20套练习里所有错题重做一遍尤其是那些因为计算失误或者边界条件丢分的题重做比做新题更有价值。第二开始整理一页纸速查表把特征多项式的展开技巧、循环队列的满空判断、排序稳定性口诀、快排的每一轮模板都浓缩成关键词考前最后一周只看这张纸。我个人备考到后期最大的感受是大学院笔试的题目其实不难难的是在有限时间内稳定输出。所谓稳定输出就是你在平时练习中养成的每一步都有依据、每一步都能验证的好习惯。第20套这套题对我而言是一个转折点做完它之后我明显感觉到自己做线性代数时的计算错误率下降了很多做数据结构题时也不再害怕边界条件了。这套练习没有什么特别的技巧它考验的就是你能否把基本功扎扎实实练到肌肉记忆的程度。最后再分享一个小技巧我每次刷完一套题都会把错题按计算型错误和思路型错误分类记录。计算型错误占总量的七成以上也就是说只要细心你就能立刻提分。下一套题试着把速度放慢一点点先把符号和边界条件看清楚再动笔结果一定比你现在想的更好。