说实话能把一套大学院笔试练习系列刷到第10回的人基本都已经过了“到底要不要考修士”的摇摆期进入了真正拼执行力的阶段。这个位置很微妙不像刚开始那样充满新鲜感也还没到临考前的紧迫冲刺它是知识体系开始成型的转折点。我见过太多人在这里松懈下来结果前9回的积累全打了折扣。这次的练习主题依旧是大学院入试笔试的两大核心线性代数和数据结构。前者是绝大多数理工科研究室的入学门槛后者是情报系考生拉开分差的主战场。把这两科放在同一套练习里不是因为它们在内容上有什么直接关联而是因为两者的备考节奏天然互补——线性代数考的是计算熟练度和概念严密性数据结构考的是抽象思维和边界条件意识。交替训练可以避免长时间啃同一类问题导致的思维疲劳这也是我一直坚持这套系列采用混合题型的原因。这篇文章我会把第10回练习涉及的题型、解题思路、易错点全部拆开讲并附上完整的真题模拟题和解析。无论你是刚开始准备笔试还是已经刷过不少过去问这篇内容都可以直接拿来对照自测。1. 整体设计与思路拆解1.1 为什么是“线性代数数据结构”这个组合先说说这个组合的逻辑。日本大学院入试的笔试科目往往不是单一的一门课而是由数学基础加专业基础组成。情报系最典型的搭配就是数学线性代数、微积分加上数据结构与算法。而线性代数又是其中出题最稳定的科目——矩阵运算、行列式、特征值、线性空间这几个大方向几乎年年出现题型变化有限非常适合通过反复练习拿到稳定分数。数据结构则相反出题形式灵活同样是考一棵二叉树可以考遍历序列推导、可以考递归实现、可以考平衡调整甚至可以在同一道题里把插入、删除、复杂度全串起来。这种灵活性导致很多考生在考场上不是“不会做”而是“会做但答不全”。把两科放在同一套练习里还有一个很实际的原因考试当天你需要在有限时间内完成多个科目大脑需要在不同思维模式之间快速切换。平时的混合练习就是最接近考场状态的模拟。单科刷题再熟练如果切换效率低考场上照样吃亏。1.2 系列练习的编排逻辑与第10回定位这套系列从第1回开始编排遵循的是一个递进原则前几回聚焦单一知识点的基础计算中间几回开始加入概念辨析题到了第10回这个节点题目难度和综合度都要上一个台阶。前9回如果认真做下来你手里应该已经有了一份自己的错题记录。第10回的核心目标有三个一是把线性代数中容易混淆的概念比如秩、零空间、特征多项式放在一起对比考核二是把数据结构里那些需要“手写代码思路”的题目做一轮强化三是检验前9回积累的解题速度——这一回的题目量我特意加了一成要求大家压缩单题耗时。我在设计第10回题目时刻意避开了纯记忆型问题。大学院笔试真正筛选的从来不是“知不知道”而是“会不会用”。比如特征值那道题直接给矩阵求特征值是最基础的考法但第10回我换成了“先求特征值再判断是否可对角化并写出对角化矩阵”一步比一步深任何一个环节有漏洞都会暴露出来。2. 线性代数核心题型拆解2.1 行列式计算技巧比硬算更重要行列式是大学院笔试的常驻题型但它很少单独出题更多是作为矩阵运算、特征值求解的前置步骤。很多考生在行列式上丢分不是不会算而是选错了计算方法。3阶以下的行列式直接用萨鲁斯法则没问题但一旦出现参数比如含 ( x ) 的对角占优矩阵硬展开就会陷入冗长的代数运算。我看到不少考生的答案纸上写满了展开式最后结果却因为一个符号错误全部作废。正确的做法是先观察矩阵结构有没有行和相等、有没有可提取公因子、能不能用倍加操作制造零元素。举一个第10回练习中的典型例子[ A \begin{pmatrix} 2 1 0 \ 1 2 1 \ 0 1 2 \end{pmatrix} ]这种三对角矩阵直接展开其实也不难但如果你能看出它可以按第一行展开然后利用余子式递推的思路计算量会明显下降而且不容易出错。第一步按第一行展开得到[ \det(A) 2 \cdot \det\begin{pmatrix}2 1 \ 1 2\end{pmatrix} - 1 \cdot \det\begin{pmatrix}1 1 \ 0 2\end{pmatrix} ]注意第二项的符号是负号这是按行展开时最容易被忽略的地方。继续算[ 2 \cdot (2 \times 2 - 1 \times 1) - (1 \times 2 - 1 \times 0) 2 \times 3 - 2 4 ]答案本身不难但整个过程中“按第一行展开时正负号交替出现”这个点我在批改这类练习时经常看到有人踩坑。另外一个技巧是如果矩阵某一行或某一列零元素特别多务必从那一行或那一列展开这会直接砍掉一大半计算量。2.2 特征值特征向量从计算到应用的完整链路特征值和特征向量是线性代数笔试的重头戏几乎没有哪个学校会跳过这个考点。基础考法是给出具体矩阵求特征值和特征向量进阶考法则涉及对角化、判断矩阵是否可对角化、利用特征值求矩阵幂。先看最核心的计算流程。对矩阵 ( A )先写出特征多项式[ \det(A - \lambda I) 0 ]解出特征值后对每个特征值 ( \lambda_i )代入齐次方程组[ (A - \lambda_i I)\mathbf{x} 0 ]求出基础解系。这一步是整个流程的瓶颈因为大多数考生会在这里犯两个错误一是代入特征值时把矩阵抄错二是求基础解系时自由变量的选取混乱导致同一个特征值的特征向量在不同步骤里“长相不同”。第10回练习里有一道这样的题[ A \begin{pmatrix} 2 1 \ 1 2 \end{pmatrix} ]特征多项式是[ \det\begin{pmatrix}2-\lambda 1 \ 1 2-\lambda\end{pmatrix} (2-\lambda)^2 - 1 0 ]解得 ( \lambda_1 3, \lambda_2 1 )。对 ( \lambda_1 3 )[ \begin{pmatrix}-1 1 \ 1 -1\end{pmatrix} ]这个方程只有一条独立约束( x_1 x_2 )所以特征向量可取 ( (1, 1)^T )。对 ( \lambda_2 1 )[ \begin{pmatrix}1 1 \ 1 1\end{pmatrix} ]约束是 ( x_1 -x_2 )特征向量可取 ( (1, -1)^T )。到这里大部分考生都能做对但第10回的练习在这之后增加了一问写出 ( P^{-1}AP ) 的对角化结果。这要求你同时保证特征向量矩阵 ( P ) 的列顺序与特征值顺序一致以及 ( P^{-1} ) 计算正确。很多人在前面都对了最后却因为特征向量顺序和特征值顺序没对应上白白丢分。这里我分享一个考场上的小习惯求完特征向量后立刻在草稿纸上写出“特征值1对应向量A特征值2对应向量B”的对应清单然后再组装对角化矩阵。这个习惯可以避免绝大多数顺序错误。2.3 线性空间概念题答出评分点才是关键除了计算题很多大学院的笔试题会出概念证明题比如线性无关的判定、子空间的证明、秩与维数的关系。这类题目的特点是计算量不大但对表述的严密性要求很高。以“判断一组向量是否线性无关”为例标准流程是设线性组合等于零然后证明所有系数必须为零。实际操作中常见的问题是考生只写出了“假设 ( c_1\mathbf{v}_1 c_2\mathbf{v}_2 \cdots c_n\mathbf{v}_n 0 )”然后直接跳到“所以线性无关”中间没有展示系数求解过程。在笔试评分中中间步骤就是采分点缺失意味着拿不到全分。另一个高频考点是子空间判定。记住三条性质包含零向量、对加法封闭、对数乘封闭。我在批改中经常看到有人只验证了前两条漏了第三条或者把“包含零向量”误写成“非空集合”。这里要特别提醒如果题目给的集合定义本身就包含零向量那么“包含零向量”这条可以简要说明后跳过不需要重复证明。第10回概念题的设置思路是给出一个具体的向量集合要求判断它是不是某个向量空间的子空间并说明理由。这种题的本质是考察你有没有真正理解“封闭性”而不是背结论。3. 数据结构核心题型拆解3.1 复杂度分析先找到基本操作再谈阶数数据结构的笔试几乎必考复杂度分析。最基础的考法是给一段伪代码让你算时间复杂度的阶数进阶考法是在二叉搜索树、堆、图的算法里让你分析最坏情况和平均情况。我总结过一套通用的解题顺序第一步找到“基本操作”是什么——通常是循环体里最内层的那条语句第二步写出基本操作执行次数关于输入规模 ( n ) 的表达式第三步用大O记号化简。举第10回的一道经典嵌套循环题for (i 1; i n; i) { for (j i; j n; j) { sum A[i][j]; } }最内层语句sum A[i][j]的执行次数是[ n (n-1) (n-2) \cdots 1 \frac{n(n1)}{2} ]所以时间复杂度是 ( O(n^2) )。这道题几乎所有人都会但真正值得注意的变体是循环边界改成j i; j n; j 2或者外层循环i每轮翻倍。一旦循环变量跳跃步长不是1累加表达式的计算就容易出错。递归算法的复杂度分析是另一个失分重灾区。很多考生见到递归就写 ( O(2^n) )但分治类的归并排序复杂度是 ( O(n\log n) )。判断的依据是递推公式如果问题规模每次减半并且每层合并操作是线性的那么递推式是 ( T(n) 2T(n/2) O(n) )结果是 ( O(n\log n) )。如果递推式是 ( T(n) 2T(n-1) O(1) )那才是指数级。这两者之间的差别就是“规模减半递推”和“规模减一递推”考试中经常混在一起考。3.2 树与遍历递归思维是地基二叉树和二叉搜索树是数据结构笔试的必考模块。遍历类的题目有几种变化的出题方式给出前序和中序求后序、给出中序和后序还原树、给出层序判断某一节点位置。这些题的核心都在于理解“根节点在中序序列中的位置把左右子树分开”这一条原则。第10回练了一道给出前序序列ABDECF和中序序列DBEAFC要求还原二叉树并写出后序遍历的题。还原的思路是前序的第一个元素是根节点A在中序中找到A左侧DBE是左子树中序右侧FC是右子树中序。对应前序中BDE是左子树前序CF是右子树前序。递归处理左子树前序第一个是B中序DBE中B左侧是D右侧是E所以B的左孩子是D右孩子是E。右子树同理根是C左孩子F。最终后序遍历是DEBFCA。这道题的隐藏考点是只给前序和后序是无法唯一确定二叉树的但给前序加中序或后序加中序就可以。有些学校会专门出一问考察这一点哪怕不算分答出来也能给阅卷老师留下好印象。BST的操作题在笔试中通常不要求写出完整代码但要求描述插入和删除的逻辑。删除节点的三种情况是必须默写的叶子节点直接删、只有一个孩子用孩子顶替、有两个孩子则用左子树最大节点或右子树最小节点替换。我在练习中特别强调一个细节两个孩子的删除场景下替换节点要先摘下来再替换如果替换节点本身还有孩子还要处理它的孩子归属这个步骤在笔答时很容易漏掉。3.3 排序与哈希背复杂度表不如理解过程排序算法部分是数据结构的“期末感”最强的内容大学院笔试的考法通常是给出一个具体序列让你写出每一趟排序后的中间结果。冒泡排序、插入排序、选择排序、快速排序、归并排序是最高频的五种。我见过无数考生在快速排序上翻车要么是选取基准值的方式和题目预设不一致导致中间结果对不上要么是递归分段时边界处理错误。这里给大家一个建议做题前先看题目问的是“以第一个元素为基准”还是“以最后一个元素为基准”然后严格按这个规则手算。不要默认用教材里的某一种实现。哈希部分的考点集中在冲突处理和散列表的查找长度计算。线性探测法、链地址法、平方探测法三种方法都要会算。第10回练了一道有代表性的题一个容量为7的散列表哈希函数 ( h(k) k \bmod 7 )依次插入5、12、26、19用线性探测处理冲突最后要求计算每个元素的探测次数和平均查找长度。这题不难但计算量大考场上最容易犯的错误是取模算错或者插入26时脑子还在上一题的余数里没切出来。排序和哈希的共同特点就是看起来需要记忆实际上只要你把过程完整走一遍每个细节自然就记住了。我不建议背复杂度表因为笔试真正考察的是“你是真的会还是只会背”。4. 第10回实战题目与详细解析4.1 线性代数实战题附完整解析题目一已知矩阵[ A \begin{pmatrix} 3 0 0 \ 0 2 1 \ 0 1 2 \end{pmatrix} ]求 ( A ) 的特征值和特征向量并判断 ( A ) 是否可对角化。若可对角化写出对角化矩阵 ( P ) 和 ( P^{-1}AP )。解析这是一个分块对角矩阵左上角是 ( 1 \times 1 ) 的 ( [3] )右下角是 ( 2 \times 2 ) 的矩阵 ( \begin{pmatrix}2 1 \ 1 2\end{pmatrix} )。分块对角矩阵的特征值就是各分块特征值的并集。右下角分块的特征值上面已经算过是3和1再加上左上角的3所以 ( A ) 的特征值是 ( \lambda 3 )重根和 ( \lambda 1 )。对 ( \lambda 3 )解 ( (A - 3I)\mathbf{x} 0 )[ \begin{pmatrix}0 0 0 \ 0 -1 1 \ 0 1 -1\end{pmatrix} ]从这个方程组得到约束 ( x_2 x_3 )( x_1 ) 自由。所以对应特征向量可取 ( (1, 0, 0)^T ) 和 ( (0, 1, 1)^T )。对 ( \lambda 1 )解 ( (A - I)\mathbf{x} 0 )[ \begin{pmatrix}2 0 0 \ 0 1 1 \ 0 1 1\end{pmatrix} ]得到 ( x_1 0 )( x_2 -x_3 )特征向量取 ( (0, 1, -1)^T )。因为特征值3对应两个线性无关的特征向量所以三个特征向量线性无关矩阵可对角化。取[ P \begin{pmatrix} 1 0 0 \ 0 1 1 \ 0 1 -1 \end{pmatrix} ]则[ P^{-1}AP \begin{pmatrix} 3 0 0 \ 0 3 0 \ 0 0 1 \end{pmatrix} ]这道题的完整链路覆盖了分块矩阵求特征值、重根特征向量的计算、可对角化判定三个核心考点是第10回练习中最有价值的一道题。题目二判断向量组 ( \mathbf{v}_1 (1, 2, 3)^T )( \mathbf{v}_2 (1, 1, 1)^T )( \mathbf{v}_3 (2, 1, 0)^T ) 是否线性无关。解析设 ( c_1\mathbf{v}_1 c_2\mathbf{v}_2 c_3\mathbf{v}_3 0 )得到方程组[ \begin{cases} c_1 c_2 2c_3 0 \ 2c_1 c_2 c_3 0 \ 3c_1 c_2 0 \end{cases} ]解这个方程组由第三个方程得到 ( c_2 -3c_1 )代入第一个方程得到 ( c_1 - 3c_1 2c_3 0 )即 ( -2c_1 2c_3 0 )所以 ( c_3 c_1 )。代入第二个方程( 2c_1 - 3c_1 c_1 0 )恒成立。因此 ( c_1 ) 自由取 ( c_1 1 ) 得到非零解。结论该向量组线性相关。这题的陷阱在于方程组恒成立那一行很容易被忽略导致误判为线性无关。遇到这类情况正确的做法是把自由变量显式写出来。第10回设置这道题的目的就是提醒大家线性相关的判定标准是“是否存在不全为零的系数”而不是“是否立刻能看出非零解”。4.2 数据结构实战题附完整解析题目三对序列[5, 2, 8, 1, 9, 4]进行快速排序以每个子数组的第一个元素为基准写出第一趟划分后的结果并说明此时基准元素的最终位置。解析第一趟以第一个元素5为基准。用经典的双指针法从右往左找比5小的元素找到4从左往右找比5大的元素找到8。交换8和4的位置序列变成[5, 2, 4, 1, 9, 8]。继续右指针从8往左找到1左指针从1往右找到9交换1和9序列变成[5, 2, 1, 9, 4, 8]。左右指针相遇在位置30-based将基准5与当前位置的9交换吗这里需要特别提醒不同教材对快速排序的扫描规则不同。如果采用“先移动右指针找到小于基准的值停下再移动左指针找到大于基准的值停下两指针相遇时把基准与相遇位置元素交换”的规则第一趟结束后基准5最终应该落在左子序列和右子序列的分界处。这个实现细节必须按照你目标学校的教材约定来写。我给出的写法是右指针停在1的位置左指针停在9的位置两指针未越界则交换得到[5, 2, 1, 4, 9, 8]然后右指针再往左跳过4直到相遇与基准交换后得到[4, 2, 1, 5, 9, 8]。基准5的最终位置是下标3。这道题暴露出的最大问题是同一个序列按不同教材的快速排序实现中间结果可能完全不同。所以考场上一旦遇到排序题先看题目给了什么约定不要拿自己默认的实现方式硬套。题目四给定散列表容量 ( m 7 )哈希函数 ( h(k) k \bmod 7 )用线性探测法依次插入键值 5、12、26、19写出插入完成后的散列表状态。解析5插入位置5。12的哈希值是12 mod 7 5冲突线性探测到位置6放入。26的哈希值是26 mod 7 5冲突探测位置6也冲突探测位置0空放入。19的哈希值是19 mod 7 5冲突位置6冲突位置0冲突位置1空放入。最终散列表为位置0存26位置1存19位置2到4为空位置5存5位置6存12。如果题目继续问平均查找长度成功查找时各元素的探测次数分别为5探测1次12探测2次26探测3次19探测4次平均是 ( (1234)/4 2.5 )。这道题是哈希考点的标准模板务必保证能默写整个流程。4.3 答题顺序与时间分配第10回新增的实战要求第10回除了题目难度升级我在答题时间上也做了调整。建议线性代数部分控制在35到40分钟数据结构部分控制在40到45分钟留出10分钟作为检查缓冲。大学院笔试的时间本来就紧检查时间不是用来重新做题的而是用来做两种检查一是回看有没有没写的空题二是重新验算所有计算类题目的关键中间步。具体到单题时间分配行列式和特征值计算题每题最多8分钟超时就标记跳过。概念证明题最多10分钟因为这类题需要组织语言。数据结构里的复杂度分析题控制在5分钟内树的遍历题8分钟内排序中间过程题6分钟内哈希计算题6分钟内。我在练习时一直用手机计时训练自己对时间的敏感度。5. 常见失分点与避坑经验5.1 计算失误的高发区线性代数的计算失误集中在三个地方行列式展开的符号、特征方程整理成多项式时的展开错误、求特征向量时代入特征值后矩阵抄错。前两个是纯粹的运算粗心第三个往往是考场紧张导致的手脑不一致。我的建议是做行列式展开时每一步都写出“按第几行展开”以及展开后的符号规则不要跳步。做特征值计算时先用 ( \lambda 0 ) 代入验证特征多项式是否等于行列式本身这个特殊情况用来检查特征多项式有没有写错。做特征向量时算出结果后立刻回代原方程验证只需要几十秒就能避免一个致命错误。在数据结构这边排序题的失分经常是“基准选取规则不一致”“一趟划分的边界没写清楚”“交换后忘记继续移动指针”。哈希的失分则集中在取模计算错误和线性探测时“循环回到表头”的处理遗漏。5.2 概念表述的失分雷区概念题最可惜的失分不是“不会”而是“会但没写到采分点上”。以子空间证明题为例参考答案的评分标准通常有三个采分点零元存在、加法封闭、数乘封闭。很多考生会用一句话带过“显然满足三条性质”这在笔试中拿不到分。正确的做法是对每个性质都明确写出“对任意 ( u, v \in W )( u v ) 仍然属于 ( W )”这样的标准句式并且用集合的定义条件说明为什么成立。不要觉得啰嗦大学院笔试的改卷本身就是要从你的文字中找证据。另外一个表述雷区是把“线性无关”和“线性表示唯一”混为一谈。这两个概念是等价的但答题时必须先声明你用的是哪一个定义再基于它展开推理。跳步使用等价定义在口述中没问题在笔答中容易被扣分。5.3 时间不够用的深层原因不少考生觉得考试时间不够其实根源不是做题慢而是“把时间花在了犹豫上”。我在前9回的练习反馈里反复看到一种情况一道题写了三行觉得不对划掉重写又写了两行又觉得哪里怪再划掉。来回几次10分钟就没了。解决这个问题的办法只有一个在平时练习中建立“一旦开始写就必须写完”的纪律。哪怕写到一半发现思路不对也要强行把当前错误思路的完整结果写出来对比题目要求后再决定是否换方向。这个习惯看起来反直觉但实际上能大幅减少无意义的涂改时间。第10回练习我已经要求按这个纪律执行效果比单纯刷题量好得多。6. 刷到第10回之后的复习安排与个人体会第10回是这套练习的分水岭。从这一回开始我不建议大家再继续按知识点章节刷题了而应该切换到“混合套题”模式。具体做法是每周至少做两整套完整的笔试模拟题每套题都严格计时并且每套题结束后用当天的时间完成错题复盘。复盘不是把正确答案抄一遍而是针对每道错题写下“错误原因”和“下次应对动作”——比如“特征向量忘记回代验证”你就给自己写一句“每次求完特征向量必须回代”。这个动作坚持两周正确率会有肉眼可见的提升。另一个建议是建立一份“概念速查笔记”把每章的核心定义和常用定理整理成两三行一条的卡片形式。不是为了背而是为了在考场上快速定位。我看到很多考生的笔记是教材的缩印版什么都有等于什么都没抓。真正有效的速查笔记应该是自己写的、只有自己看得懂的、一页纸能覆盖一科的。最后再分享一个我从多次练习中总结出来的小技巧每次做完一套题把错题对应的考点在考纲上做一个标记。连续三次在同一个考点出错就说明这不是粗心问题而是方法问题需要专门找同类题集中攻坚。这个方法让我在后期复习时不再平均用力而是把时间集中在真正该补的地方。如果你当前也处在“刷了不少题但成绩没起色”的阶段我的建议是先停下来做一套完整的自测记录每道题的错误类型再用这一篇文章里的方法逐项对照。应对大学院笔试勤奋只是底线精准才是你超过别人的关键。
