清华大学 · 01_姚班_计算机科学

2026-07-28 · 备考资料 · 鸡蛋强基计划综合评价

姚班 · 计算机科学方向

Yao Class: Computer Science Track

A. 方向画像与考察重点

清华大学计算机科学实验班（姚班）由2000年图灵奖得主姚期智院士于2005年创办，现由交叉信息研究院（IIIS）统筹培养，设有计算机科学、人工智能、量子信息三大方向供学生自由选择。计算机科学方向以理论计算机科学为核心优势，覆盖算法、计算复杂性、密码学、量子计算基础等，强调严密数学训练与原始创新能力，而非单纯工程实现。其培养目标是造就能引领学科前沿的科学家与创业者。

2026年选拔于07-27至08-19中午12点报名，流程为初审→专业测试→认定→确认，坚持"宁缺毋滥"。专业测试与面试重在考察数理功底、抽象思维、问题建模能力与科研潜质，而非刷题熟练度。评委高度关注学生能否把陌生问题转化为可计算的数学模型，并用清晰逻辑推进论证。竞赛背景（数学/信息学）是加分项但不是门槛，真正的区分点在于思维的深度与表达的严谨。

面试常采用"追问式"：先问动机与经历，再抛出一个需要现场建模或推导的小问题，观察思考路径。因此备考既要夯实算法与离散数学基础，也要能流畅讲述自己为何适合理论计算机这条路，并展现出对姚班学术传统的尊重与理解。

关键词 8 条常考维度

算法与数据结构：复杂度分析、递归分治、动态规划、图遍历
计算理论：图灵机、可计算性、P/NP、停机问题
离散数学与组合：鸽笼原理、归纳法、计数与证明
数论与密码：模运算、同余、RSA公钥思想
数理建模：把现实/智力问题抽象为数学对象
学术视野：对理论计算机价值与姚期智贡献的了解
动机与规划：为何选姚班、为何选CS、长期目标
思维品质：抗挫力、追问下的临场推导与表达

B. 核心概念速查

速查表 8 条关键概念

大O记号：描述算法最坏情形时间/空间随输入规模的增长阶，忽略常数因子。
分治：将问题拆为同类子问题、递归求解后合并，如归并排序复杂度O(n log n)。
动态规划：对具最优子结构与重叠子问题者，以状态转移避免重复计算。
P与NP：P为多项式可解，NP为解可多项式验证；P=NP是否成立是核心开放问题。
图灵机：抽象计算模型，定义"可计算"边界，是复杂性理论基石。
停机问题：判定任意程序是否终止不可计算，证明用对角线/反证法。
鸽笼原理：n+1物放n笼必有一笼≥2，是组合存在性证明利器。
RSA思想：基于大数分解困难，用模幂与公私钥实现加密与签名。

C. 面试真题（Q1–Q20）

Q1你为什么想进姚班？是什么让你觉得这条路适合自己？

参考回答

我对"用严密数学刻画计算本身"的兴趣，源于高中信息学竞赛中第一次理解复杂度下界——原来程序快慢可以被证明而非仅测量。姚班由姚期智院士创办，以理论计算机科学见长，强调从算法、复杂性到密码学的完整训练，正契合我想做"根上的创新"而非重复造轮子的志向。我也认同其宁缺毋滥、小班科研的氛围：它逼人把基础打透。比起短期就业红利，我更看重能否在IIIS接触真正前沿的问题，并和同侪在高压中互相砥砺。如果有幸入选，我希望从计算理论起步，逐步走向量子信息与密码学的交叉。

备考提示：考察动机真伪与自我认知。避免空谈"清北光环"，用具体经历锚定兴趣来源，并体现对姚班定位的了解。

Q2在人工智能如此火热的当下，你为何坚定选计算机科学（偏理论）方向而非AI方向？

参考回答

AI方向解决"如何让机器表现得好"，而计算机科学方向追问"什么可被计算、什么是效率极限、如何安全地计算"。我认为前者建立在前者的地基上：深度学习的可解释性、泛化边界、隐私保护都回到信息论与复杂性。我选理论方向，是因为想掌握这些"第一性原理"，将来无论做AI安全还是密码学都更扎实。姚班的计算理论与密码学传统恰好提供这种底层训练。我并非排斥AI，而是相信只有理解计算的数学本质，才能在AI浪潮里做引领者而非跟随者——比如当下大模型的安全与对齐，本质是可证明保证的问题。

备考提示：考察方向选择是否经过深思。要展现"理论是根基"的辩证认识，而非贬低AI，体现交叉视野。

Q3姚班以"宁缺毋滥"和高强度著称，你如何看待这种压力？会不会担心跟不上？

参考回答

我把"宁缺毋滥"理解为对学术标准的坚守，而非对人的筛选恐吓——它保证同窗水平与讨论质量，这对理论学习者是稀缺资源。高强度方面，我高中同时准备竞赛与课业时已习惯把大目标拆成每日可执行的小证明，并用费曼式复述检验理解。我担心过"跟不上"，但更怕"不够主动"：理论计算机的难点往往在卡住后能否主动找文献、找老师追问。我的应对是建立错题/卡点本，把每次受挫转化为对某个概念的更深把握。压力若来自同侪，我会把它当作免费的智力激荡而非威胁。

备考提示：考察抗压与成长型思维。承认顾虑但给出具体应对机制，比空洞"我能扛"更有说服力。

Q4讲一次你彻底搞砸或长期卡住的经历，你从中学到了什么？

参考回答

高二时我卡在一道动态规划题两周，反复调状态定义却总差一个维度。后来发现根本问题是没先手写小规模样例找规律，而是直接套模板。我停下来用纸笔枚举n=1到5，才看清"阶段"应如何划分，最终把O(n³)优化到O(n²)。这次教训让我明白：理论问题先求"小例可验证"再谈推广，比盲目抽象更有效；也让我养成提交代码/证明前必先构造反例自测的习惯。它削弱了我对"聪明捷径"的迷信，转而信任系统化的建模流程——这恰是姚班研究所需要的踏实。

备考提示：考察反思深度。选真实、有技术含量的挫折，重点落在"认知升级"而非卖惨。

Q5你有过数学或信息学竞赛经历吗？评委想追问：那段经历对你学理论计算机具体有什么帮助？

参考回答

我有信息学竞赛背景，它给我的不是背过的模板，而是三种可迁移能力：一是复杂度直觉，看到问题本能估算下界与可行算法区间；二是构造与反例思维，命题"存在性"常需显式构造，而"不可能"要靠反例或归谬；三是把模糊需求形式化为状态与约束的能力。数学竞赛则强化了归纳法与组合论证。这些正是理论计算机的日常工具：证明算法正确需归纳，证下界需组合或 adversary 论证，设计协议需构造。竞赛还教会我在限定时间内保持冷静推导——面试现场题最需要的就是这种状态。

备考提示：即使无竞赛也可谈项目/自学。关键是把经历翻译成"理论计算机所需的具体能力"，而非罗列奖项。

Q6你未来五到十年的规划是什么？姚班会怎样融入其中？

参考回答

短期（本科）我希望在姚班打牢算法、复杂性与密码学基础，并尽早进组做科研，争取在理论或交叉方向产出一篇扎实的工作。中期我希望赴顶尖院所攻读博士，聚焦可证明安全或量子复杂性等"难而基础"的问题。长期我想成为既能发硬核论文、又能把理论转化为可靠系统的研究者，比如参与后量子密码标准或隐私计算落地。姚班提供的不是一张文凭，而是与图灵奖级学者对话、与极强同侪共学的环境，这正是我规划里"研究起点"不可替代的一环。我也留意到姚班校友在AI与安全创业上的成就，这给我"理论也能改变产业"的信心。

备考提示：考察目标清晰度与匹配度。规划要具体可执行，并明确点出姚班在你的路径中的独特作用。

Q7二分查找的前提与时间复杂度是什么？若数组有n个元素，最多比较几次？专业重点

参考回答

前提是序列已按关键字有序，且支持随机访问（如数组）。每次将搜索区间对半，排除一半元素，故时间复杂度O(log n)。最多比较次数为⌈log₂(n+1)⌉次（在"找到即停"的实现下），或⌊log₂n⌋+1次（循环至区间为空）。正确性靠循环不变式：每次缩小后目标若存在仍落在当前区间内。需注意边界：mid = lo + (hi-lo)/2 防溢出，且当 hi=mid-1 或 lo=mid+1 时要避免死循环。变体如"找第一个等于target的位置"要改为在相等时继续向左收缩并记候选。二分思想还可推广到"答案具有单调性"的最优化问题。

备考提示：常考边界与不变式。能写出不变式或分析⌈log₂(n+1)⌉会比只答O(log n)更得分。

Q8比较常见排序算法的时间复杂度，并说明为什么基于比较的排序下界是O(n log n)。专业重点

参考回答

插入、冒泡、选择为O(n²)；归并、堆排为O(n log n)且稳定/原地各有取舍；快速排序平均O(n log n)但最坏O(n²)。基于比较的排序下界证明用决策树：n个元素有n!种排列，每次比较产生二叉树的一个分支，从根到叶路径长度即比较次数。树高h需满足叶数2^h ≥ n!，故h ≥ log₂(n!)。由斯特林公式n!≈(n/e)^n√(2πn)，得log₂(n!)=Θ(n log n)，所以最坏比较次数Ω(n log n)。归并/堆排达到该下界。注意计数、基数排序不基于比较，可突破到O(n)（但依赖数据范围假设）。

备考提示：下界证明是经典题。能说出"决策树+log(n!)=Ω(n log n)"即体现理论功底。

Q9用分治思想解释归并排序，并分析其递归式与复杂度。专业重点

参考回答

归并排序将数组对半分为左右，递归排序后用一个O(n)的合并过程把两个有序序列归并。递归式 T(n)=2T(n/2)+O(n)。用主定理（a=2,b=2,f(n)=Θ(n)，恰为n^{log_b a}=n的Θ，属case 2）得 T(n)=Θ(n log n)。也可用递归树：每层代价O(n)，共log n层。它稳定且最坏也是Θ(n log n)，缺点需O(n)额外空间。分治的要点是子问题独立同构、合并代价可控。对比快排分治点选枢轴，归并选中点更稳。该思想是后续很多算法（如FFT、最近点对）的原型。

备考提示：主定理是分水岭。能写出递归式并套主定理/递归树，比只说"分成两半"专业得多。

Q10什么是动态规划？以0-1背包为例说明状态设计与转移。专业重点

参考回答

动态规划适用于具"最优子结构"（全局最优含局部最优）与"重叠子问题"的问题，通过状态+转移避免暴力枚举的重复。0-1背包：n件物品重量w_i、价值v_i，容量C，每件至多取一次。设 dp[i][c] 为前i件在容量c下的最大价值，转移 dp[i][c]=max(dp[i-1][c], dp[i-1][c-w_i]+v_i)（当c≥w_i）。基础 dp[0][*]=0。填表复杂度O(nC)，空间可滚动数组压到O(C)。关键在设计"维度"刻画决策所需的最小历史信息。若求具体方案则回溯选择。注意背包容量大时可用价值作状态（当价值范围小）或 meet-in-the-middle 优化。

备考提示：DP核心是"状态定义"而非代码。讲清为何这样定义能无后效性，是评委关注点。

Q11BFS和DFS的区别与典型应用？图的连通分量如何用它们求？专业重点

参考回答

BFS用队列按距起点层次扩展，求无权图最短路、连通性、二分图判定；DFS用栈/递归深入到底再回溯，善于拓扑排序、强连通分量、环检测。二者时间均O(V+E)。求无向图连通分量：从任一未访问点出发BFS/DFS，能达的全部标同一编号，重复直至所有点被覆盖，编号数即分量数。BFS空间最坏O(V)（宽层），DFS递归深度最坏O(V)可能栈溢出，可用显式栈。有向图强连通分量则需 Kosaraju 或 Tarjan（基于DFS的lowlink）。选择上：要"最近"用BFS，要"结构/回溯"用DFS。

备考提示：别只说"一个宽一个深"。点出数据结构、最短路/拓扑等各自擅长的应用场景才显专业。

Q12请解释P与NP，并谈谈你认为P=NP若成立会有什么后果。专业重点

参考回答

P是能在多项式时间内判定的语言类；NP是"解可在多项式时间验证"的语言类，显然P⊆NP。P=NP 问的是验证易是否意味着求解易。多数理论计算机科学家猜 P≠NP，因为它是上万NP完全问题（SAT、TSP、背包）高效求解的前提。若P=NP成立，后果深远：所有NP完全问题迎刃而解，密码学中的许多难题（如因式分解虽在NP∩co-NP但相关）根基动摇，药物分子匹配、运筹优化大幅提速；但同时也意味着许多"创造性搜索"失去难度壁垒。经典结果：若任一NP完全问题属P，则P=NP（归约传递性）。这题考的是概念清晰与对学科意义的理解。

备考提示：务必说清"验证≠求解"以及NP完全归约的传递性，表态可保守但逻辑要稳。

Q13什么是图灵机？它如何定义"可计算"的边界？专业重点

参考回答

图灵机是1936年提出的抽象计算模型：一条无限带、一个读写头、有限状态控制器，按转移函数逐步演算。若某函数能被某图灵机在有限步内对每输入停机并输出，则称其（图灵）可计算。丘奇-图灵论题猜想：所有"直觉上可计算"的函数恰是图灵可计算的——这是定义而非可证定理，但已被lambda演算、递归函数等等价模型强力支撑。它划出了可计算与不可计算的边界：存在图灵机算不出的问题（如停机问题）。现代计算机是图灵机的物理受限实现，故图灵机也是复杂性类P/NP的载体。理解它，就从工程层面上升到"什么是计算"的哲学与数学层面。

备考提示：区分"丘奇-图灵论题"是约定而非证明，并联系到可计算性边界，体现理论素养。

Q14停机问题为什么不可判定？请给出一个证明思路。专业重点

参考回答

假设存在判定器 H(p,x) 能判定程序p在输入x上是否停机。构造新程序 D(p)：若 H(p,p) 说停机，则 D 进入死循环；若说不停机，则 D 停机。现在问 D(D) 行为：若 H(D,D) 判其停机，则 D 按构造死循环，矛盾；若判不停机，则 D 反而停机，亦矛盾。故 H 不可能存在，停机问题不可判定。本质是反证+自指（类似康托尔对角线、罗素悖论）。推论丰富：类型检查、程序等价、Post对应等许多问题也不可判定（可归约到停机）。这揭示了"普遍自动化推理"的固有极限，是理论计算机最深刻的结论之一。

备考提示：自指构造是核心。能写出 D 的对角化逻辑，比泛泛而谈"无法判断"得分高很多。

Q15鸽笼原理是什么？能否举一个它在算法/组合中的存在性证明应用？专业重点

参考回答

鸽笼原理：把 n+1 个物体放入 n 个盒子，必有至少一个盒子含≥2个物体；加强形式：放 m 物入 n 盒，则某盒≥⌈m/n⌉。应用举例：证明任意 n+1 个不超过 2n 的不同正整数中，必有两个互素——不行，更标准的是：从 {1,2,…,2n} 任取 n+1 个数，必有两个数其中一个整除另一个（将数按"奇数部分"分组，共 n 组，取 n+1 个必同组，同组两数呈倍数）。算法中它用于鸽巢哈希冲突论证、以及"若元素数超过状态数则必重复"——如 Floyd 判圈算法正确性依赖：序列进入环后，快慢指针在有限步内必在环上某点相遇，本质是有限状态+必然重复。它也是很多下界与存在性结论的捷径。

备考提示：准备1-2个干净的存在性证明（倍数分组/Floyd判圈），能现场推导最佳。

Q16用数学归纳法证明：前n个正整数之和为 n(n+1)/2，并说明归纳法在算法正确性中的作用。专业重点

参考回答

归纳：基础 n=1，左=1，右=1·2/2=1 成立。假设对 n=k 成立，即 S(k)=k(k+1)/2。则 S(k+1)=S(k)+(k+1)=k(k+1)/2+(k+1)=(k+1)(k/2+1)=(k+1)(k+2)/2，即对 k+1 成立。故对所有 n 成立。归纳法在算法中地位关键：循环不变式本质就是归纳——证明"每轮迭代前性质成立且保持，终止时即目标成立"，如插入排序、Dijkstra 的正确性都靠它。递归算法的正确性也常对每个递归深度归纳。它把"无限多情形"化为"一步推导+假设"，是理论计算机最常用的证明骨架。

备考提示：归纳步骤务必写清从k到k+1的代数。能联系循环不变式，显示你懂它如何用于算法。

Q17解释模运算的基本性质，并说明RSA公钥加密为什么是安全的（思想层面）。专业重点

参考回答

模运算：a≡b (mod n) 当 n|(a-b)。性质有同余可加、乘、幂：(a·b) mod n = ((a mod n)(b mod n)) mod n，故可用快速幂高效算大数模幂。RSA：选大素数 p,q，n=pq，φ(n)=(p-1)(q-1)；选 e 使 gcd(e,φ)=1，d=e⁻¹ mod φ。公钥 (e,n) 加密 c=m^e mod n，私钥 d 解密 m=c^d mod n（因 c^d≡m^{ed}≡m^{1+kφ}≡m mod n，用欧拉定理）。安全性基于"已知 n 难分解出 p,q，从而难求 φ 与 d"——大整数分解是 believed 难问题（属NP∩co-NP，未证P≠NP下仍实用安全）。这是理论计算机把数论转化为现实安全的典范。

备考提示：能写出解密成立依赖的欧拉定理 m^{ed}≡m mod n，并点明安全假设是分解困难。

Q18现场思维题：估算北京市需要多少盏路灯？请展示你的建模与推算过程。专业重点

参考回答

用自上而下的数量级估计。北京建成区面积约 1500 km²，假设道路网占约 15% 即 225 km²；若主干/次干/支路平均路宽折算成"等效道路长度×单侧布灯密度"，可换思路：估算道路总长。假设路网密度使每 km²对应 2 km 道路，则总长≈3000 km。路灯间距市区约 30–40 m，取 35 m，则单侧每 km≈28 盏；考虑双向/多车道多数路段双侧布灯，得每 km≈50 盏。3000 km×50≈15 万盏。再加小区、广场等，量级在 10^5–10^6。关键是量纲与假设透明：评委看的是"拆因子—给依据—算量级"的建模能力，而非精确数。可反过来用"北京约 2000 万人口、每 100 人摊 1 盏"交叉验证量级一致。

备考提示：费米题重过程不重答案。务必分步、标注假设、做交叉验证，体现结构化思维。

Q19从理论视角看，高级语言、编译与操作系统分别解决了什么"计算"层面的问题？专业重点

参考回答

高级语言用抽象语法把"人的意图"形式化为与机器无关的程序，核心是符号系统与类型论（保证部分正确性）。编译器把源程序等价变换为目标代码，涉及自动机（词法）、文法（语法）、图着色（寄存器分配）等理论，本质是"程序间保持语义的翻译"。操作系统管理并发与资源，其背后的并发模型（Petri网、CSP）、调度复杂性、互斥的正确性（如 Peterson 算法、锁的进展性/无饥饿性）都可被严格证明。三者共同把"图灵机级的裸计算"封装成可靠、可组合、可验证的系统——理论计算机科学的价值正在于为这些工程提供可证明的正确性与效率保证。

备考提示：从"抽象/等价变换/并发正确性"三处扣理论，别只罗列OS功能，要上升到可证明性。

Q20你了解姚期智院士的哪些学术贡献？比如"百万富翁问题"或"姚氏原理"，谈谈理论计算机科学的实用价值。专业重点

参考回答

姚院士的核心贡献在密码学与计算理论。经典"百万富翁问题"（1982）问：两富翁如何比较谁更富而不泄露具体资产？他由此开创安全多方计算（MPC），用混淆电路/秘密共享使多方在互不信任下联合计算而保隐私——这正是今天隐私计算、联邦学习的理论源头。另一贡献是通信复杂性中的"姚氏原理"（Yao's minimax principle）：随机通信复杂度的下界可由最差分布的对偶给出，成为该领域基石。这些说明理论计算机绝非象牙塔：MPC支撑金融风控、区块链，复杂性理论界定什么是"本质上算不动"的。姚班把这种"从根本问题长出产业"的传统带给学生，是我向往的根因。

备考提示：能准确说出MPC与通信复杂性原理并点出其产业映射，是展现"懂姚班"的加分杀手锏。

D. 备考要点

备考建议针对姚班CS方向的专业化准备

筑牢三门基础：算法与数据结构、离散数学、计算理论（自动机/可计算性/复杂性）是面试硬通货，建议以《算法导论》《离散数学及其应用》为纲系统过一遍并动手证。
练"现场推导"：每日挑1道需证明/估算的小题（下界、归纳、鸽笼、费米估算）， aloud 讲清思路，模拟追问环境。
准备个人叙事：把竞赛/项目经历翻译成"理论所需能力"，并写一版关于动机、失败、规划的连贯自我介绍（Q1–Q6）。
读姚院士代表作科普：理解MPC、通信复杂性、量子计算相关的通俗综述，能用自己的话复述其思想与意义。
关注流程节点：2026报名07-27至08-19 12:00，初审→专业测试→认定→确认，材料真实、体现科研潜质胜于堆奖。
心态：评委看思维路径而非标准答案；遇到不会的题，展现"如何拆解未知"比硬编更受赏识。