剑桥大学圣约翰学院计算机专业面试真题25
剑桥大学圣约翰学院（St John's College）的计算机科学（Computer Science）本科面试具有极高的选拔性。根据圣约翰学院官方介绍，计算机科学面试通常分为两场（每场 20-25 分钟）：一场偏向纯数学（Mathematics），一场偏向计算机科学与逻辑算法（Computer Science）。
圣约翰学院作为科学重镇，其计算机面试几乎不考具体的编程语言语法（如 Python 或 Java 怎么写），而是极其纯粹地考察离散数学、算法效率（Big-O）、组合博弈论以及现场解决未知逻辑难题的能力。
一、 算法、数据结构与复杂度（Algorithms & Complexity）
1. 寻找重复的数字（Finding the Duplicate）
【真题】English:You are given an array of n+1 integers where each integer is between 1 and n inclusive. Prove that there must be at least one duplicate. How can you find it efficiently if the array is read-only and you have O(1) extra space?中文： 给你一个包含 n+1 个整数的数组，其中每个整数都在 1 到 n 之间（包含 1 和 n）。证明其中至少有一个重复的数字。如果数组是只读的，且你只有 O(1) 的额外空间，你该如何高效地找到它？第一问考察离散数学中经典的“鸽巢原理（Pigeonhole Principle）”。第二问是硬核算法设计，测试学生能否打破常规的“哈希表（需要 O(n) 空间）”或“排序（需要修改数组）”思维，巧妙利用快慢指针进行链表环检测（Floyd's Cycle Detection）。第一步（证明）： 根据鸽巢原理，将 n+1 个数字（鸽子）放入 n 个不同的数值位置（鸽巢）中，必然至少有一个位置包含大于或等于两只鸽子。第二步（空间限制）： 因为空间是 O(1)，不能建新数组；因为只读，不能原地排序。第三步（算法抽象）： 将数组视为一个隐式链表，其中索引 i 指向节点 A[i]。由于存在重复数字，这个链表必然包含一个“环”。使用“快慢指针（弗洛伊德判圈算法）”，快指针一次走两步，慢指针一次走一步，它们必然在环内相遇。相遇后，将其中一个指针放回起点，两个指针同时一次走一步，再次相遇的点即为重复的数字。时间复杂度 O(n)，空间复杂度 O(1)。2. 天平称重找坏球（Counterfeit Coin Problem）
【真题】English: You have 9 identical-looking coins, but one is a counterfeit and is slightly heavier than the rest. Using a balance scale, what is the minimum number of weighings required to find the counterfeit coin? Can you generalise this to n coins?中文： 你有 9 枚外表完全一样的硬币，其中有一枚是假币，它比真币略重一点。在使用天平的情况下，最少需要称几次才能找出这枚假币？你能将这个结论推广到 n 枚硬币吗？考察对“决策树（Decision Tree）”和信息论中“信息量（Information Entropy）”的本质理解。计算机科学的核心就是如何利用最少的步骤划分最大的搜索空间。误区警示： 很多学生习惯二分法（Binary Search），分成 4、4、1 称，这需要 3 次，不是最优解。正确切入（三分法）： 天平秤有三种状态：左重、右重、平衡。因此每次称量最多可以把搜索空间切分成 3 部分。第一步： 将 9 枚硬币分成三组（3, 3, 3）。称量前两组：如果平衡，假币在第三组；如果不平衡，假币在重的那组。一次称量直接锁定 3 枚硬币。第二步： 将剩下的 3 枚硬币再分成三组（1, 1, 1），重复上述步骤。只需 2 次 即可找出假币。第三步（一般化推广）： 对于 n 枚硬币，最少称量次数为
（向上取整）。二、 逻辑、博弈与离散数学（Logic & Discrete Maths）
3. 海盗分金币（Pirates and Gold）
【真题】English:5 rational, perfectly logical pirates have 100 gold coins to share. They allocate them based on seniority (Pirate 1 to 5). Pirate 1 proposes a split. All pirates vote. If 50% or more agree, the split happens. If not, Pirate 1 is thrown overboard, and Pirate 2 proposes. What should Pirate 1 propose to maximize his gold while surviving?中文： 5 个绝对理性且精通逻辑的海盗要分 100 枚金币。他们按照资历从大到小（海盗 1 到 5）排序。海盗 1 提出分配方案，所有人投票。如果有 50% 或以上的人同意，方案通过；否则海盗 1 会被喂鲨鱼，由海盗 2 继续提方案。海盗 1 应该如何提方案，才能在保命的前提下拿到最多金币？考察逻辑学中的“逆向归纳法（Backward Induction）”和博弈论中的纳什均衡。这是评估计算机学生处理复杂条件分支和状态机的必考题。核心思维： 从只剩最后 2 个海盗（海盗 4 和 5）的最简单情况开始反向推导。第一步（剩4、5）： 海盗 4 只需投自己一票就达到 50%，所以他会提（100，0），海盗 5 什么也拿不到。因此海盗 5 的“心理预期保底”是 0。第二步（剩3、4、5）： 海盗 3 知道海盗 5 害怕海盗 4 的方案。所以海盗 3 给海盗 5 1枚金币贿赂他，方案为（99, 0, 1）。海盗 5 必然同意（1 > 0）。此时海盗 4 的保底变成 0。第三步（剩2、3、4、5）： 海盗 2 需要 2 票。他贿赂海盗 4 给 1 枚金币。方案为（99, 0, 1, 0）。第四步（5人完整情况）： 海盗 1 需要 3 票（包含自己）。他需要贿赂在海盗 2 的方案里拿 0 枚金币的人（即海盗 3 和海盗 5）。方案为：海盗 1 拿 98 枚，给海盗 3 拿 1 枚，给海盗 5 拿 1 枚。方案（98, 0, 1, 0, 1）完美通过。4. 2xN 房间铺地砖（Tiling a Room）
【真题】English:You need to tile a room of size 2 × n using tiles of size 2 × 1 and 2 × 2. How many ways can you tile the room? Write down the recurrence relation.中文： 你需要用大小为 2 × 1 和 2 × 2 的地砖去铺满一个大小为 2 × n 的房间。一共有多少种不同的铺法？请写出其递推关系式。计算机系极其重视“递推式（Recurrence Relation）”的建立。这不仅是数学，更是动态规划（Dynamic Programming）算法的灵魂。情况一：放一块 2 × 1 的地砖（竖着放），前面还剩 2 × (n-1) 的空间，有 f(n-1) 种。情况二：放两块 2 × 1 的地砖（横着叠放），前面还剩 2 × (n-2) 的空间，有 f(n-2) 种。情况三：放一块 2 × 2 的大方砖，前面同样剩 2 × (n-2) 的空间，有 f(n-2) 种。第一步（定义状态）： 设铺满 2 × n 房间的方法总数为 f(n)。第二步（寻找边界/最后一步）： 考虑房间最右侧的铺法。第三步（合成分支）： 综上所述，递推关系式为：f(n) = f(n-1) + 2f(n-2)。已知初始条件 f(1)=1, f(2)=3。三、 概率与计算机数学（Probability & Maths for CS）
5. 翻硬币直到连续两次正面（Coin Tossing Expectation）
【真题】English: You flip a fair coin repeatedly. What is the expected number of flips required to get two consecutive heads (HH)?中文： 你连续抛掷一枚均匀的硬币。请问，想要获得连续两次正面（HH）出现，所需的期望抛掷次数是多少？考察对“期望值（Expected Value）”和马尔可夫链（Markov Chain）状态转移的计算能力，这在网络协议丢包重传算法中经常用到。第二步（第一抛分支）： 第一抛如果是反面（概率 0.5），则浪费了 1 步且状态回到原点，后续还需要 E 步。如果是正面（概率 0.5），进入“已有一个H”的状态，设在该状态下还需要 e₁ 步。因此得到方程一：E = 1 + 0.5E + 0.5e₁第三步（第二抛分支）： 在“已有一个H”的状态下抛第二两。如果是正面（概率 0.5），游戏结束（再花 1 步）；如果是反面（概率 0.5），前功尽弃，状态清零（再花 1 步外加重新开始的 E 步）。因此得到方程二：e₁ = 1 + 0.5(0) + 0.5E第四步（联立求解）： 将方程二代入方程一，化简可得 E = 6 次。6. 逻辑悖论：蓝色眼睛的岛民（Blue-Eyed Islanders）
【真题】English:On an island, there are 100 people with blue eyes and some with brown eyes. No one knows their own eye color. If anyone finds out they have blue eyes, they must leave the island at midnight. One day, a traveler arrives and announces to everyone: "At least one of you has blue eyes." What happens next?中文：一个岛上有 100 个蓝眼睛的人和若干绿眼睛的人。所有人都在外表上能看到别人的眼睛颜色，但无法知道自己的。规则是：任何人一旦确定自己是蓝眼睛，必须在当天午夜离开。某天，一个外来旅行者对全岛公开宣布：“你们当中至少有一个人是蓝眼睛。”接下来全岛会发生什么？考察分布式系统或人工智能里极其高级的“公共知识（Common Knowledge）”逻辑概念。假设 n=1（只有 1 个蓝眼）： 听到宣布后，他环顾四周没看到别人是蓝眼，立刻确定自己就是那唯一的一个，第 1 天午夜他就会离开。假设 n=2（有 2 个蓝眼 A 和 B）： 第一天 A 看到 B 是蓝眼，心想如果全岛只有 1 个蓝眼，B 第一天夜里就会走。然而第 1 天夜里 B 没走。第 2 天白天 A 看到 B 还在，意识到“说明 B 也看到了一个蓝眼，那就是我！”，于是第 2 天夜里 A 和 B 同时离开。最终结论： 依此类推，全岛有 100 个蓝眼睛的人。在听到旅行者宣布后的前 99 天里，什么事也不会发生。到了第 100 天的午夜，所有 100 个蓝眼睛的人将会同时离开这条岛。四、 离散结构与图论（Graph Theory & Networks）
7. 握手定理与图的度数（The Handshaking Lemma）
【真题】English:Prove that in any group of people, the number of people who have shaken hands an odd number of times must be even.中文： 证明：在任何人群中，跟别人握手次数为奇数的人的总人数，必然是一个偶数。图论（Graph Theory）的基础入门题。考察学生能否自发地将现实人群抽象为“图”，将“人”转化为节点（Vertices），将“握手”转化为边（Edges）。第一步（图论抽象）： 设图为 G=(V,E)。每个人的握手次数就是该节点的度数（Degree）。第二步（核心定理）： 每一条边（每一次握手）都必然连接两个不同的节点。如果把所有节点的度数加起来（\(\sum deg(v)\)），每条边都被重复计算了正好 2 次。因此：所有节点的度数之和等于边数的 2 倍（\(\sum deg(v) = 2\vert{}E\vert{}\)）。第三步（奇偶性推导）： 既然度数总和是 2|E|，那么总和必然是一个偶数。度数总和可以拆分为：[所有度数为偶数的节点之和] + [所有度数为奇数的节点之和] = 偶数。因为偶数之和永远是偶数，所以[所有度数为奇数的节点之和]也必须是偶数。而若干个奇数相加想要得到偶数，奇数的个数（即人数）必须是偶数个。8. 二叉树的节点与叶子（Binary Tree Properties）
【真题】English:Prove by induction that in a full binary tree (where every node has either 0 or 2 children), the number of leaf nodes is always exactly one more than the number of internal nodes with two children.中文： 用数学归纳法证明：在一棵满二叉树中（每个节点要么没有子节点，要么有两个子节点），叶子节点（Leaf Nodes）的数量总是比拥有两个子节点的内部节点（Internal Nodes）的数量恰好大 1。考察对核心数据结构（树形结构）的深刻理解，以及使用严谨的数学归纳法（Mathematical Induction）在数据结构上进行正确性证明的能力。第一步（奠定基题 Base Case）： 当树只有 1 个根节点时，叶子数 L=1，双子内部节点数 I=0。满足 L = I + 1。第二步（归纳假设 Inductive Hypothesis）： 假设对于包含 k 个内部节点的满二叉树，结论
成立。第三步（归纳递推）： 考虑给这棵树增加节点。由于必须保持“满二叉树”的性质，我们只能选择现有的某一个叶子节点，为它长出 2 个新的子节点。这个操作导致：原先的 1 个叶子节点变成了拥有两个子国家的内部节点（内部节点数 +1）；同时，新长出了 2 个叶子节点（叶子节点数 -1 + 2 = +1）。因为叶子节点和内部节点同步 +1，它们之间“差值为1”的比例完美保持，因此对所有满二叉树均成立。五、 体系结构、系统与超纲延伸（Systems & Advanced Topics）
9. 内存调度：LRU 缓存设计（LRU Cache Logic）
【真题】English: Imagine a computer storage system that can only hold 3 items at a time. It uses the Least Recently Used (LRU) policy to evict items when full. If the system receives a data access sequence: A, B, C, D, A, B, E, A, B. Show the final state of the cache and count the number of cache misses.中文： 想象一个计算机存储系统，它一次只能容纳 3 个数据项。当缓存满时，它使用“最近最少使用（LRU）”策略来淘汰旧数据。如果系统按顺序接收到数据访问请求：A, B, C, D, A, B, E, A, B。请展示缓存的最终状态，并计算“缓存未命中（Cache Misses）”的总次数。考察对计算机底层操作系统内核（缓存淘汰算法）现场模拟、追踪和状态更新的细心程度。读 C -> [A, B, C] (Miss 3)读 D -> 缓存满，淘汰最久没用的 A -> [B, C, D] (Miss 4)读 A -> 缓存满，淘汰最久没用的 B -> [C, D, A] (Miss 5)读 B -> 缓存满，淘汰最久没用的 C -> [D, A, B] (Miss 6)读 E -> 缓存满，淘汰最久没用的 D -> [A, B, E] (Miss 7)读 A -> 缓存已有 A (Hit!) -> 调整使用顺序，A 变成最新 -> [B, E, A]读 B -> 缓存已有 B (Hit!) -> 调整使用顺序，B 变成最新 -> [E, A, B]最终答案： 最终缓存状态为 [E, A, B]，缓存未命中总数为 7 次。10. 超纲文书深挖：什么是 P vs NP？（The P vs NP Problem）【真题】English: You stated in your Personal Statement that you read about computational complexity. Can you explain to me, in simple terms, what the 'P vs NP' problem is? Why is it considered the most important open question in Computer Science?中文： 你在个人陈述（PS）中提到你读过关于计算复杂度的内容。你能用通俗易懂的语言向我解释一下什么是“P vs NP”问题吗？为什么它被认为是计算机科学中最重要的未解之谜？严厉打击文书代写或对高级概念浅尝辄止。考官不仅测试你的真实知识储备，还考察你作为未来的科学家，如何把复杂的专业词汇（多项式时间、非确定性图灵机）还原为外行也能听懂的直观逻辑。P集合代表着一类“很容易解答”的问题（比如把一堆数字从小到大排序），计算机可以在多项式（有限、高效）的时间内算出答案。NP集合代表着一类“很难解答，但一旦给你答案，你很容易去验证对错”的问题（比如数独游戏，或者走迷宫。让你解出来很难，但如果我给你一份填好的数独，你扫一眼就能判定它对不对）。P vs NP 的核心本质就是： 是不是所有“容易被验证对错”的问题，本质上都隐藏着一个“很容易被解出来”的绝妙算法，只是我们人类目前还没找到？（Is verification inherently easier than generation?）如果 P = NP，意味着世界上所有加密算法（如网银加密、比特币）都将在瞬间被攻破；而所有复杂的科学难题（如蛋白质结构预测）都能用电脑轻松秒杀。在面试圣约翰学院计算机系时，“沉默”是最大的敌人。面试官宁可听到一个效率不高的暴力解法（Brute Force），也不希望看到一个学生坐在那里冥思苦想 5 分钟一言不发。因为只有当你把不完美的思路说出来，面试官才能抓到机会给你一两句关键的提示（Hint），看你能不能像优秀的程序员一样快速调整代码（Refactor）并迭代出最优解。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至23467321@qq.com举报，一经查实，本站将立刻删除;如已特别标注为本站原创文章的，转载时请以链接形式注明文章出处，谢谢！
