2019-转专业到计科经验_How-to-transfer-to-the-Department-of-Computer-Science-and-Technology.md

2019 转专业到计科经验分享

---

机试

在计拔匡院的OJ上测的.

1. 括号匹配, 用栈即可.
2. 路径异或, 树上BFS.
3. special judge

笔试

1. $A$: 所有无穷收敛的有理数列的集合, 若${a_n} \in A$, $lim_{n \rightarrow \infty} a_n = x$, 则$x$一定是有理数吗, 还有第二小题.

解: 梅加强老师数学分析习题有很多类似的.

2. 二部图$G$的顶点集可以划分为两个不相交的子集$U$和$V$, 图中的每条边都有一端在$U$中, 另一端在$V$中，$U$中有2019个顶点，$U$中每个顶点的出度至少为$\frac{|V|}{2}$.

   1. 证明：$V$中一定存在一个子集$X$，$|X| \leq 10$，$U$中的每一个顶点都在$X$中有一个邻居。

   解: (有点难, 我证的可能是伪证)

   考虑$V$中度数最大的点$v_1$, 有$\frac{2019|V|}{2} \leq |E(G)| \leq d(v_1)$, 即$\frac{2019}{2} \text{取整} \leq d(v_1)$.

   考虑以下算法:

   令$V^{\prime} = V - v_1, G^{\prime} = G - v_1$, $E(G^{\prime}) \leq \frac{2019}{2}$.

   取$V^{\prime}$中度数最大的点$v_2$. 有 $$ d(v_2)(|G^{\prime}|) = d(v_2)(|V| - 1) \geq \frac{2019(|V| - 1)}{2^2} \ \Rightarrow d(v_2) \geq \frac{2019}{2^2} \ ... $$ 重复到$v_{10}$, 此时$\frac{2019}{2^{10}} < 1$.

3. 8阶群一定有4阶子群吗？（证明或举反例）

解: 曲老师离散数学书上有证明6阶群必有3阶子群, 证明思路为使用Lagrange定理分类讨论.

4. 构造一个函数$f(x, y)$, 使$g(y) = \int_0^1f(x, y) dx$在$(0, 1)$上连续, 对任意$a \in (0, 1)$, $h(y) = f(a, y)$在$(0, 1)$上不连续.

解: 很有趣的题, 我当时构造了一个在$x = y$上的Dirac函数, $\delta$函数. 详细地说, 在定义域为$xy$平面上当$x = y$时, $f(x, y) \rightarrow +\infty$(类似Dirac function零点位置)而其他为零, 也即对于垂直于$xy$平面且与$x$轴平行的平面 与 $f(x, y)$相截的图形就是一个平移后的Dirac函数, 所以$g(y) = \int_0^1f(x, y) dx$在$(0, 1)$上连续. 与$y$轴平行同理. 不连续用定义说明即可.

5. 数电简单题.

面试

1. 修了哪些课程, 成绩如何, 之后根据这些课程提问.
2. 数理逻辑: 谓词逻辑和一阶逻辑的区别
3. ICS: PA做了啥
4. 关于获奖的一些问题
5. 然后开始闲聊

努力就好! 🌟

Update at 2020-2-3 19:29:42, 别怕, 武汉加油, 中国加油!