2026年（2023级）考试题目汇总

笔试

大班离散。2小时，闭卷。

1.

给出一些自然语言表述，请用谓词逻辑刻画并用谓词逻辑的证明系统，证明某个自然语言表述。

2.

对于Sierpiński carpet
分型n次后的图形，用数学归纳法证明其面积等于某个表达式a_n，周长等于某个表达式b_n。然后求\lim_{n\to\inf}a_n和\lim_{n\to\inf}b_n。开放问题：从中你发现集合大小和图形复杂度之间的联系？

3.

P(S)为S的幂集。求证：

P(A)\cap P(B)=P(A\cap B)

P(A)\cup P(B)=P(A\cup B) \Leftrightarrow A\subseteq B \vee B\subseteq A

4.

一颗无根树，有L个叶子,I个内部节点。内部节点度都为3，叶子度为1。求证：

1. $L=I+2$

2. 总边数E=2L-3.

5.

证明：有限半群(A,\circ)如果满足消去律（a\circ b=c\circ b\Rightarrow a=c;a\circ b=a\circ c\Rightarrow b=c），则A是群。

提示：按这个思路证明
1. 存在e既为左单位元，又为右单位元
2. \forall x\in A, \exists x^{-1}\in A, s.t.~ x\circ x^{-1}=x^{-1}\circ x=e

6.

用Hall Marriage Theorem证明k-正则二部图有perfect matching。

7.

有一个12阶群G。证明：
1. Sylow 3-子群个数n_3=1或4.如果n_3=1，这个子群是正规子群。
2. 忘了
3. 如果n_3=4，那么G\cong A_4

机试

2小时，闭卷。中位170/300，300分1人，200分第二名。

1.

给出数字的ascii art，给你一个数字n，请给出n的ascii art。
例如告诉你2、0、1、6每个都是怎么画的，给出n=2016,输出:

  .--.       .-.    .--.    .--.   
 ;  _  \   /    \  (_  |   / ,  ;  
(___)` |  |  .-. ;   | |  | .(___) 
     ' '  | |  | |   | |  | | _    
    / /   | |  | |   | |  | '` `.  
   / /    | |  | |   | |  | .-,  . 
  / /     | '  | |   | |  | |  | | 
 / '____  '  `-' /   | |  . `-'  ; 
(_______)  `.__,'   (___)  '.__.'  

2.

一个机器人，每次可以向前跳1格或者2格，但是不能连续两次跳两格，求跳了n格的方案数。

例如，n=12,ans=88。

对于70%, n\leq 10^8

对于100%, n\leq 10^{10}

3.

题面中给出了三种字母的ascii art印章：A、B、C。给你一个256*256的黑白两色网格图，图上在某些位置印了这三种字母的ascii art，印出来的印章可以任意旋转、缩放，但是仍然满足：
1. 缩放旋转后的单个印章的图案仍然满足四联通
2. 印章不会相互接触
3. 印章的transformation不会改变原有印章中enclosed white space的数量。enclosed white space是指一块4联通的白色区域，这个区域不能碰到画布边缘。

求图里印了多少个A、B、C。

字母数量小于等于40.

面试

根据学号分为第一组和第二组。第一组主要为聊天，第二组主要为基本知识。

第一组问题示例

• 自我介绍，参加了什么活动，做了什么项目，担任什么职务
• 讲一讲实习/科研/项目经历
  • 基于该经历可能会考察后续问题或专业知识问题。
• 强基课程安排如何？是否有时间做科研？
• 你的未来发展安排如何？导师找到了吗？
• Vibe coding大模型会不会取代程序员？

第二组问题示例

• 讲一个排序算法，这个算法时间空间复杂度怎么算？
• 组合逻辑和时序逻辑电路的区别
• 计网和图算法
• 算法 + 密码学
• 堆的定义，从离散数学角度讨论堆，为什么堆要是完全二叉树
• 计网里路由路径怎么选择？如果没有全局视野呢？
• prim 正确性
• dijkstra算法内容与分析，时间复杂度是多少？所有点两两之间的最短路怎么求？