剑桥大学丘吉尔学院（Churchill College）是剑桥本科计算机科学（Computer Science）招生规模最大的学院，长期在学业表现排名中蝉联榜首。丘吉尔学院的计算机面试极具特色：不强制要求考生具备高超的编程和代码技巧，而是极度看重硬核的离散数学思维、算法逻辑、递归与组合直觉，以及现场面对未知概念的“秒学现用”能力.计算机科学 (Computer Science)：每年招收 1–2 人。丘吉尔学院被公认为剑桥计算机资源和学术氛围最好的学院之一，虽然全球录取率极低（约9%），但每年基本都会有优秀的中国奥赛或神童级选手获录。第一题：图论、算法与网络拓扑 (Graph Theory & Routing)
【英文原题】：Imagine a social network where every pair of users is either friends or enemies. Prove that in any group of 6 users, there must exist either a trio of mutual friends or a trio of mutual enemies. How does this apply to complete graphs in CS?【中文翻译】：想象一个社交网络，任意两个用户之间要么是朋友，要么是敌人。证明：在任意 6 个人的群体中，必定存在 3 个人互相都是朋友，或者 3 个人互相都是敌人。这在计算机科学的完全图中有什么应用？【考官意图】：经典的拉姆齐定理（Ramsey's Theorem）母题。考查如何将现实问题抽象为图论（Graph Theory）中的顶点与边，以及运用鸽巢原理进行严谨的状态空间分类讨论。1、图论建模：将 6 个人视作完全图 K₆ 的 6 个顶点。朋友连红边，敌人连蓝边。2、局部节点突破：任选一个顶点 A。它与其他 5 个顶点相连，连线只有红、蓝两色。根据鸽巢原理，A 连出的 5 条边中，必然至少有 3 条边颜色相同（比如都是红边，连接 B, C, D）。3、子图边界分类：观察 B, C, D 这三个节点之间的连线：若 B, C, D 之间任意两点连了红边（例如 B-C 是红边），则 A-B-C 构成一个全红三角形（3人互为朋友）。若 B, C, D 之间没有任何红边，则它们之间只能全连蓝边，此时 B-C-D 构成一个全蓝三角形（3人互为敌人）。4、得出结论：无论如何，必然存在同色三角形（即引出计算复杂度中拉姆齐数的边界判定）。第二题：博弈论、递归与二进制策略 (Combinatorial Game Theory)
【英文原题】：There are two piles of stones: one with 7 stones and one with 5 stones. Two players take turns. In each move, a player can take any number of stones from one pile, or an equal number of stones from both piles. The player who takes the last stone wins. If you go first, what is your opening move to guarantee a win?【中文翻译】：有两堆石头，一堆有 7 个，另一堆有 5 个。两人轮流拿石头。每一步玩家可以从任意一堆中拿走任意数量的石头，或者从两堆中拿走相同数量的石头。拿走最后一个石头的人获胜。如果你先手，你的第一步应该怎么拿才能确保必胜？【考官意图】：经典的威佐夫博弈（Wythoff's Game）。考查对必败态（冷态/Safe States）的递归寻找，以及用算法状态机进行状态转移（State Transition）分析的直觉。1、逆向归纳必败态：设两堆剩下数量为 (x, y)。(0, 0) 是终点必败态。以此类推，容易验证 (1, 2) 也是必败态（无论先手怎么破坏，后手都能将其一步恢复成 (0,0) 或迫使对方送棋）。2、寻找黄金分割规律：通过递归推导，后续的必败态对为 (3, 5), (4, 7), (6, 10)... 它们满足差值递增且未出现过的最小正整数原则。3、制定第一步策略：当前状态是 (5, 7)，差值为 2。而差值为 2 的黄金必败态是 (3, 5)。4、执行操作：先手应该从两堆中同时拿走 2 个石头，使棋局变为 (3, 5) 的必败态丢给后手，从而锁定胜局。第三题：数据结构、树与逻辑深度 (Data Structures & Trees)
【英文原题】：A binary tree has 1000 nodes. What is the minimum possible height of this tree? What is the maximum possible height? Explain your answers using mathematical induction or properties of nodes.【中文翻译】：一个二叉树包含 1000 个节点。该二叉树可能的最小高度是多少？最大高度是多少？请利用数学归纳法或节点性质解释你的答案。【考官意图】：考查对基础数据结构（Data Structures）树形拓扑的理解，测试如何用对数（Logarithm）和线性极端边界来量化空间效率。1、高度定义定义明确：先向考官澄清你对高度（Height）的定义（是从根节点到叶节点的边数，还是层数。这里假设根节点为第 1 层）。2、最大高度（最坏情况）：树退化为一条链（每个节点只有一个子节点）。每个节点占一层，因此最大高度为 1000。3、最小高度（最好情况）：树为完全二叉树/满二叉树。高度为 h 的满二叉树最多能容纳
个节点。4、代数不等式求解：列出不等式：
。因为 2⁹ = 512，2¹⁰ = 1024，所以 最小高度为 10。第四题：位运算与位并行算法 (Bit Manipulation)
【英文原题】：Given an integer x, write a mathematical expression using bitwise operators
to check if x is a power of 2. Your expression must run in O(1) time without loops.【中文翻译】：给定一个正整数 x，写出一个使用位运算符（与、或、非、异或、左移、右移）的数学表达式，来检查 x 是否为 2 的幂。你的表达式必须在 O(1) 时间内运行，且不能使用任何循环。【考官意图】：考查对底层计算机二进制补码（Two's Complement）表示法的掌握，以及利用位运算（Bit Manipulation）优化算法复杂度的黑客思维。1、观察二进制特征：如果 x 是 2 的幂（如 4, 8, 16），其二进制形式有且仅有一个‘1’（例如 8 = 1000₂）。2、引入临近减法：思考 x - 1 的二进制特征（例如 8 - 1 = 7 = 0111₂）。可以发现，x 的那一位 ‘1’ 变成了 ‘0’，而后面所有的 ‘0’ 全变成了 ‘1’。3、位与运算闭环：将 x 与 x - 1 进行按位与（Bitwise AND）运算：
例如：
4、最终代数式：若结果为 0 且 x > 0，则 x 必定是 2 的幂。表达式为：(x > 0) && ((x & (x - 1)) == 0)。第五题：概率、期望值与随机算法 (Randomized Algorithms)
【英文原题】：An algorithm generates a random permutation of an array of n distinct elements. On average, how many elements remain in their original positions? Does this number change as n grows to infinity?【中文翻译】：一个算法将包含 n 个不同元素的数组生成一个随机排列。平均而言，有多少个元素会留在其原始位置？随着 n 趋近于无穷大，这个数量会发生变化吗？【考官意图】：考查概率论中极为精妙的“期望值的线性性质（Linearity of Expectation）”。中国学生极易在这里尝试用复杂的错位排列（Derangement）概率级数硬算，考官想看到的是优雅的拆解。1、引入指示随机变量（Indicator Variable）：设 
为一个随机变量。如果第 i 个元素随机后留在原位，(
= 1)；否则(
= 0)。2、求解单个概率：由于是完全随机排列，任何一个元素落在任意位置的概率都是均等的。因此，第 i 个元素刚好留在原位的概率 
3、计算单个期望值：
4、利用线性性质求总和：总留原位数 
无论这些变量之间是否独立，
5、得出震撼结论：平均而言，永远只有 1 个元素留在原位，与数组的规模 n 没有任何关系！第六题：密码学、逻辑与鸽巢高级原理 (Cryptography & Infinitude)
【英文原题】：Can you perfectly compress any file? Prove mathematically that there cannot exist a lossless compression algorithm that makes every possible file smaller.【中文翻译】：我们能完美压缩任何文件吗？从数学上证明：绝对不可能存在一个无损压缩算法，能让所有可能的输入文件都变小。【考官意图】：考查对无损压缩（Lossless Compression）和单射函数（Injective Function）本质的离散数学论证，测试反证法与信息论极限。1、反证法假设：假设存在这样一个完美的无损压缩算法 A，它能将任意长度为 N 比特的文件压缩到长度小于 N。2、计算计数空间：长度为 N 比特的二进制文件总共有 
个不同的可能。而所有长度小于 N 的文件（从 0 比特到 N-1 比特）的总可能数是
3、应用鸽巢原理引出矛盾：我们要把
个不同的“鸽子”（原始文件），放入
个“鸽巢”（压缩后的短文件）中。根据鸽巢原理，必然至少有两个不同的原始文件被压缩成了完全相同的短文件。4、结论：由于两个文件相同，解压时就无法无损还原，与“无损压缩”的定义相矛盾。因此不可能让所有文件变小（必然有部分文件变大）。第七题：信息论与二分搜索极限 (Information Theory)
【英文原题】：You have 8 identical-looking coins, but one is counterfeit and lighter than the others. You have a balance scale. What is the minimum number of weighings needed to find the fake coin? What if there are N coins?【中文翻译】：你有 8 枚外观完全相同的硬币，但其中有一枚是假币，且比真币轻。你有一个天平秤。请问找出这枚假币最少需要称几次？如果是 N 枚硬币呢？【考官意图】：考查决策树（Decision Tree）的分支效率以及信息熵（Information Entropy）的概念。中国学生往往本能采用二分法（Binary Search），但天平能提供三路分支，考官在看你是否具备最高的信息利用效率。1、识别天平的“三路分支”特征：每次把硬币放在天平两端，有三种结果：左重、右重、平衡。因此，每次称量最多能把可能的状态空间缩减为原来的1/3（信息基底为 3）。2、推导代数约束：若称量 k 次，最多能从 
个状态中分离出 1 个。3、针对 8 枚硬币求解：因为 3¹ = 3 < 8 ≤ 3² = 9，所以只需要 2 次。4、具体策略输出：第一次两边各放 3 枚（剩下 2 枚）。若平衡，假币在剩下的 2 枚里（再称1次即出）；若不平，假币在轻的那 3 枚里（再从这3枚里任选2枚放天平，即出）。5、通项公式：对于 N 枚硬币，最少需要 
次（向上取整）。第八题：微积分、复杂分析与算法复杂度 (Complexity & P-Space)
【英文原题】：Order the following functions by their growth rate as n → ∞:
Prove mathematically why n! grows faster than 
【中文翻译】：将下列函数按照当 n → ∞ 时的增长速率进行排序：
并从数学上证明为什么 n! 的增长速度快于
。【考官意图】：计算机科学最核心的渐进复杂度（Big-O Notation）排序。测试极限比较法和离散级数的处理。1、给出总排序（由慢到快）：
2、数理论证 n! 与
：写出它们的项展开比值：
3、分子分母放缩匹配：我们可以将该比值重写为 
4、极限逼近：由于从第三项开始，
最后一项 
整个乘积随着 n 的增加被不断乘以大于 1 的数，当 n → ∞ 时，比值趋近于无穷大。由此严格证明了 n! 是比 
更高阶的无穷大。第九题：自动机与形式语言逻辑 (Automata Theory & Logic)
【英文原题】：An alphabet consists of only two characters: {A, B}. A valid word is defined as any string where 'A' is never immediately followed by another 'A'. How many valid words of length n can be formed?【中文翻译】：一个字母表仅包含两个字符：{A, B}。一个“合法单词”被定义为任何‘A’后面绝不紧跟另一个‘A’的字符串。请问长度为 n 的合法单词一共有多少个？【考官意图】：考查组合结构中的动态规划思想，以及如何将边界约束转化为著名的斐波那契（Fibonacci）递推方程。1、定义递推变量：设长度为 n 的合法单词总数为 f(n)。情况一：如果单词以 ‘B’ 结尾，那么前面的 n-1 个字符可以是任何合法的长度为 n-1 的单词。这种情况有 f(n-1) 个。情况二：如果单词以 ‘A’ 结尾，由于 ‘A’ 后面不能跟 ‘A’，那么倒数第二个字符必须是 ‘B’（即以 ‘BA’ 结尾）。此时前面的 n-2 个字符可以是任何合法的长度为 n-2 的单词。这种情况有 f(n-2) 个。3、写出递推方程：f(n) = f(n-1) + f(n-2)。4、初始值对齐：长度 n=1 时有 {A, B} 共 2 个；长度 n=2 时有 {AB, BA, BB} 共 3 个。可见这是一个首项错位的斐波那契数列，
第十题：多线程、并发与死锁逻辑 (Concurrency & Deadlocks)
【英文原题】：Two threads are running concurrently. Thread 1 executes: Lock(A); Lock(B); DoWork(); Unlock(B); Unlock(A);. Thread 2 executes: Lock(B); Lock(A); DoWork(); Unlock(A); Unlock(B);. Explain how a deadlock occurs and how you would redesign the program to prevent it.【中文翻译】：两个线程正在并发运行。线程 1 执行：锁(A); 锁(B); 核心工作(); 释放(B); 释放(A);。线程 2 执行：锁(B); 锁(A); 核心工作(); 释放(A); 释放(B);。请解释死锁（Deadlock）是如何发生的，以及你将如何重新设计程序来防止死锁？【考官意图】：考查现代计算机操作系统（Operating Systems）中最经典的并发与死锁问题，测试对“循环等待（Circular Wait）”条件的识别与打破能力。1、时序复现死锁：若线程 1 率先获得了锁 A，与此同时，线程 2 率先获得了锁 B。接下来的时序中，线程 1 试图去获取锁 B，但发现已被线程 2 持有，于是挂起等待；线程 2 试图去获取锁 A，发现被线程 1 持有，同样挂起。2、定义死锁状态：双方都在等待对方释放资源，导致程序永久卡死，这就是死锁。3、抓出底层因果：死锁的根本原因在于两个线程获取锁的顺序不一致，形成了循环等待。4、架构优化设计（解决方案）：引入“锁的全局顺序化（Lock Ordering）”。强制规定任何线程若想同时获得 A 和 B，必须统一按照先锁 A、再锁 B 的顺序执行。这样线程 2 也改为先锁 A 再锁 B，彻底打破循环等待，从根本上杜绝死锁。
10个月宝宝每天需要喝多少奶粉？
