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

剑桥大学三一学院 (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）？)

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

3、化简这个级数相乘完美证明算法的正确性。

【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 个完全相同的无标签节点，你总共可以构建出多少种结构独特的二叉树？请推导出一个通用公式，并说明计算该公式的计算复杂度。)

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号）。每天白天，警察可以检查恰好一个洞穴。请为警察设计一个策略，保证在有限的天数内抓到小偷。)

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

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

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

2、计算树的高度：高度为 h 的二叉树最多有个叶子节点。为了能够区分所有排列，必须满足：

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

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

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

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)。)

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 门？请画出电路并证明其布尔逻辑。)

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。请解释导致这一偏差的底层硬件原因。)

第三部分：图论与网络优化 (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.(在任何社交聚会中，总有一些人会互相握手。证明：握手次数为奇数的人的总数，必定是一个偶数。)

2、总度数公式：由于每条边都有两个端点，图内所有顶点的度数之和必定等于边数的两倍：这意味着总度数之和必定是一个偶数。

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

4、得出结论：因为偶数相加永远是偶数，为了让等式成立，奇数度数顶点的求和结果  也必须是偶数。若干个奇数相加想要得到偶数，奇数的个数（即人数）必须是偶数。

【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）很容易出现“无穷计数”问题。请解释一个简单的链路故障是如何导致路由器无休止地增加其距离度量的。)

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)。每个网格内都有一定数量黄金。你每一步只能向右或向下移动。设计一个高效的方法找到一条通往右下角的路径，使得收集的黄金总数最大，并说明其时间复杂度。)

1、拒绝暴力：指出如果用 DFS/暴力穷举，路径总数是，时间复杂度是指数级的 ，绝对不可行。

2、构建 DP 转移方程：设 为到达位置 (i,j) 所能获得的最大黄金数。由于只能从左边或上边走过来，状态转移方程为：