当前位置：首页>面试真题>剑桥三一学院计算机面试真题25

剑桥三一学院计算机面试真题25

2026-06-24 17:56:54

剑桥大学三一学院 (Trinity College) 的计算机科学 (Computer Science) 本科面试通常包含 2 场，每场约 30 分钟。三一学院作为剑桥计算机科学的顶尖圣地，其面试以极其硬核的离散数学推导、算法渐进复杂度分析（Big-O）以及复杂逻辑系统构建著称。

考官极其反感死记硬背某种编程语言的语法。线上面试（使用 Miro 共享白板）时，他们更看重你在不依赖任何代码的环境下，如何将文字问题转化为严谨的图论、组合数学或递归数学模型。

基于刚结束不久的上一季真实面试复盘（2025年1月入学/2024年底主面）以及三一计算机教学组的考核内核，为您梳理 10 道原汁原味的三一学院计算机科学本科面试真题：

第一部分：算法、复杂度与组合离散数学 (Algorithms & Discrete Maths)

1. 【高频热题】未知长度数据流的“随机蓄水池抽样”

【2025年入学真题】 You are receiving a stream of data elements one by one. The total number of elements N is unknown and too large to fit into memory. How can you design an algorithm to choose exactly one element at random, such that every element has an equal probability (1/N) of being selected?(你正在逐个接收一个数据流。数据总数 N 是未知的，且由于太大而无法全部存入内存。你如何设计一个算法，随机选择其中恰好一个元素，使得每个元素被选中的概率完全相等（均为 1/N）？)

考官意图：考查概率算法设计与数学归纳法证明能力，这是大数据流处理中的经典“蓄水池抽样 (Reservoir Sampling)”问题。

备考切入路径：

1、算法设计：始终保存当前选中的那个元素。当收到第 k 个元素时，以 1/k 的概率决定用这个新元素替换掉旧元素，以 1 - 1/k 的概率保持原状。

2、数学归纳法证明（在白板上列出概率乘积）：

1、当数据流结束于第 N 个元素时，第 N 个元素被选中的概率显然是 1/N。

2、对于任意先前的第 i 个元素 (i < N)，它能留到最后的概率 = 它在第 i 步被选中的概率 × 之后每一步它都没被替换的概率：

3、化简这个级数相乘

完美证明算法的正确性。

2. 【递归与树论】统计所有不同形态的二叉树数量

【2025年入学真题】Given n identical unlabeled nodes, how many structurally unique binary trees can you construct? Derive a general formula and state its computational complexity to calculate.(给定 n 个完全相同的无标签节点，你总共可以构建出多少种结构独特的二叉树？请推导出一个通用公式，并说明计算该公式的计算复杂度。)

考官意图：考查将数据结构（二叉树）转化为组合数学递推关系（Recurrence Relation）的能力，引出著名的卡特兰数 (Catalan Numbers)。

备考切入路径：

1、拆解根节点：设 f(n) 为 n 个节点组合出的独特二叉树数量。拿出一个节点作为根节点，剩下的 n-1 个节点分给左子树（k 个）和右子树（n-1-k 个）。

2、列出递推式：

其中基准情况 f(0)=1, f(1)=1。

3、高级跨越：向考官指出这正是卡特兰数，通用闭项公式为

如果用动态规划（DP）去计算这个递推式，时间复杂度为 O(n²)。

3. 【博弈与二分搜索】小偷与警察的图论追逐

【2025年入学真题】 A thief is hiding in one of n linear, connected caves (numbered 1 to n). Every night, the thief must move to an adjacent cave (e.g., from cave 3, he must move to 2 or 4). Every daytime, a policeman can check exactly one cave. Design a strategy for the policeman to guarantee catching the thief in a finite number of days.(一个小偷躲在 n 个排成一条直线的相连洞穴里（编号 1 到 n）。每天晚上，小偷必须移动到相邻的洞穴（例如从3号洞只能移到2或4号）。每天白天，警察可以检查恰好一个洞穴。请为警察设计一个策略，保证在有限的天数内抓到小偷。)

考官意图：考查奇偶性状态空间（Parity State Space）的建模与搜索策略设计。

备考切入路径：

1、核心破局点（考虑奇偶性变化）：小偷每天移动，这意味着他所在洞穴编号的奇偶性每晚都会交替改变。

2、第一阶段策略：假设小偷第一天在偶数洞穴。警察可以依次检查 2, 3, 4, ..., n-1 号洞穴。如果小偷真的初始在偶数洞，由于警察的推进速度与小偷移动步调一致，必然会把小偷逼入绝境并抓住。

3、第二阶段策略：如果警察走完这一轮没抓住，说明先前的假设错误——小偷第一天在奇数洞穴。由于经过了这轮移动，小偷现在的洞穴奇偶性已经由于天数发生了翻转。警察只需要再次执行一遍 2, 3, 4, ..., n-1 的检查序列，由于奇偶性已经对齐，这次必定能 100% 抓到小偷。

4. 【排序算法边界】比较排序算法的理论下界证明

【2025年入学真题】Prove from first principles why no comparison-based sorting algorithm can achieve an average or worst-case time complexity better than

从第一性原理证明，为什么任何基于元素间两两比较的排序算法，其平均或最坏情况下的时间复杂度都不可能超越

考官意图：测试对决策树模型（Decision Tree Model）和信息论极限的深刻理解。

备考切入路径：

1、建立决策树：对于 n 个元素，一共有 n! 种不同的初始排列可能性。排序的过程本质上是通过两两比较，在二叉决策树中找到那一条对应正确顺序的唯一叶子节点。

2、计算树的高度：高度为 h 的二叉树最多有

个叶子节点。为了能够区分所有排列，必须满足：

3、两边取对数并应用斯特林公式：

根据斯特林近似（Stirling's Approximation），

因此，树的最小深度（即最少比较次数）h 必定是

第二部分：系统、逻辑与数据表示 (Systems & Logic)

5. 【数据结构优化】设计 O(1) 复杂度的“最小栈”

【2025年入学真题】 Design a Stack data structure that supports standard push and pop operations, but also has a function "getMin()" which returns the smallest element currently in the stack. All three operations must run in O(1) time complexity.

(设计一个栈（Stack）数据结构，除了支持标准的 push 和 pop 操作外，还拥有一个 "getMin()" 函数用于返回当前栈内的最小元素。这三个操作的时间复杂度都必须是 O(1)。)

考官意图：考查空间换时间（Space-Time Trade-off）的架构设计直觉以及状态同步维护能力。

备考切入路径：

1、核心解法（双栈协同）：单栈结构无法在 pop 时实时更新最小值。破局点在于维护一个辅助栈（Min-Stack）。

2、push 逻辑：主栈正常压入元素 x；辅助栈压入 min(x,辅助栈栈顶)。

3、pop 逻辑：主栈和辅助栈同时弹出栈顶元素。

4、getMin 逻辑：直接返回辅助栈的栈顶元素。由于所有操作仅涉及对两个栈顶的操作，耗时恒定，完美达到 O(1)。

6. 【布尔代数】用最少数量的逻辑门重构异或门 (XOR)

【2025年入学真题】You are only allowed to use 2-input NAND gates (与非门). What is the minimum number of NAND gates required to build a 2-input XOR gate (异或门)? Draw the circuit and prove its Boolean logic.

(你只被允许使用 2 输入的 NAND 门（与非门）。构建一个 2 输入的 XOR 门（异或门）最少需要多少个 NAND 门？请画出电路并证明其布尔逻辑。)

考官意图：考查布尔代数简化、德·摩根定律（De Morgan's Laws）的应用以及电路基元优化能力。

备考切入路径：

1、结论：最少需要 4 个 NAND 门。

2、布尔公式推导：

将其转化为纯 NAND（求反再求反）的形式：

3、电路连接（口述画图）：第一个 NAND 门接收输入 A 和 B，输出记为

第二个 NAND 门接收 A 和 Z；第三个 NAND 门接收 B 和 Z。第四个 NAND 门接收第二和第三个门的输出，最终输出即为

7. 【计算机体系结构】浮点数表示法的精度丢失陷阱

【2025年入学真题】In many programming languages, executing 0.1 + 0.2 does not equal 0.3, but rather 0.30000000000000004. Explain the underlying hardware reason for this discrepancy.(在许多编程语言中，执行 0.1 + 0.2 的结果不等于 0.3，而是 0.30000000000000004。请解释导致这一偏差的底层硬件原因。)

考官意图：考查对 IEEE 754 浮点数标准 内存二进制编码、有限尾数截断（Floating-point Precision）的底层硬件常识。

备考切入路径：

1、进制转换死循环：计算机底层使用二进制存储。十进制的 0.1 转化为二进制是 0.0001100110011...₂（0011无限循环），0.2 也是无限循环小数。

2、有限精度截断：由于硬件中寄存器的位数（如 IEEE 754 双精度浮点数只有 52 位尾数/Mantissa）是有限的，计算机被迫对这个无限循环的小数进行四舍五入的截断（Rounding Error）。

3、误差累加：存储在内存里的 0.1 和 0.2 本身就已经是带有微小偏大误差的近似值，当它们在 ALU 中相加时，截断误差进一步累加，再转换回十进制时就暴露出了最后的末尾数字。

第三部分：图论与网络优化 (Graph Theory & Networks)

8. 【经典图论】证明握手定理与奇数度节点的偶数性

【2025年入学真题】 In any social gathering, some people shake hands. Prove that the number of people who shake hands an odd number of times must be even.(在任何社交聚会中，总有一些人会互相握手。证明：握手次数为奇数的人的总数，必定是一个偶数。)

考官意图：考查将现实场景抽象为图的度数定理（Handshaking Lemma）的离散数学基本功。

备考切入路径：

1、图论建模：将每个人视为图中的一个顶点（Vertex），每一次握手视为连接两个顶点的一条边（Edge）。顶点的度数（Degree）即为该人的握手次数。

2、总度数公式：由于每条边都有两个端点，图内所有顶点的度数之和必定等于边数的两倍：

这意味着总度数之和必定是一个偶数。

3、奇偶分拆：将所有顶点分为两组：度数为偶数的顶点组和度数为奇数的顶点组。

4、得出结论：因为偶数相加永远是偶数，为了让等式成立，奇数度数顶点的求和结果

也必须是偶数。若干个奇数相加想要得到偶数，奇数的个数（即人数）必须是偶数。

9. 【分布式网络】互联网路由中的“无穷计数”故障

【2025年入学真题】In computer networking, distance-vector routing protocols (like RIP) are prone to a problem called "Count-to-Infinity". Explain how a simple link failure can cause routers to endlessly increase their distance metrics.(在计算机网络中，距离矢量路由协议（如 RIP）很容易出现“无穷计数”问题。请解释一个简单的链路故障是如何导致路由器无休止地增加其距离度量的。)

考官意图：考查分布式系统中的异步信息依赖环路（Routing Loops）分析能力。

备考切入路径：

1、构建拓扑结构：设路由器 A 连着节点 X，路由器 B 连着 A。B 知道“通过 A 到达 X 的距离是 2”。

2、链路断开瞬间：A 到 X 的链路突然断开了。A 知道自己去不了 X 了（距离设为 ∞）。但还没来得及通知 B，B 的定期更新报文传给了 A：“我能去 X，距离是 2”。

3、错误信息成环：A 收到后误以为“哦，那我可以借道 B 去 X，距离变成 2+1=3”。紧接着 A 通知 B 自己的新距离，B 收到后又更新为 3+1=4……两个路由器由于相互盲目依赖对方过时的路由表，形成死循环，度量值无休止递增直至触发上限。

10. 【动态规划】寻找网格路径中的最大财富值

【2025年入学真题】 You are placed at the top-left corner (0,0) of an m × n grid. Each cell contains a certain amount of gold. You can only move either down or right at any step. Design an efficiency approach to find the path to the bottom-right corner that maximises the total gold collected. State the time complexity.(你被放置在一个 m × n 网格的左上角 (0,0)。每个网格内都有一定数量黄金。你每一步只能向右或向下移动。设计一个高效的方法找到一条通往右下角的路径，使得收集的黄金总数最大，并说明其时间复杂度。)

考官意图：考查动态规划 (Dynamic Programming) 状态转移方程的构建以及相较于暴力穷举（Explosive Search）的复杂度缩减。

备考切入路径：

1、拒绝暴力：指出如果用 DFS/暴力穷举，路径总数是