-
Notifications
You must be signed in to change notification settings - Fork 111
2019南大CS考研复试笔试回忆
(by 仰望星空)
1.命题逻辑
题设：三个孩子玩泥巴，有人头上沾了泥巴。每个孩子看不到自己的，但能看到别人的。
父亲对三个孩子说：你们中至少有一个人头上有泥巴。接着问：你们知不知道自己头上有没有泥巴呢？
所有孩子答不知道；父亲问第二次同样问题，所有孩子答不知道；父亲问第三遍，所有孩子答知道了。
（1）建立数学模型，描述该问题。
（2）用你的模型求解哪个或哪几个孩子头上有泥巴；
（3）求证：K个孩子同时回答知道了当且仅当父亲问了K次（这个记不清了，大致意思是这样）。
2.递推式，等势的证明
题设：F0=[0,1]，F1=[0,1/3]∪[2/3,1],F3=[0,1/9]∪[2/9,1/3]∪[2/3,7/9]∪[8/9,1]..
即Fn+1是将Fn的每个区间三等分，并保留第一段和最后一段得到的集合
记C为无穷次这样操作后得到的点集
注：原题的表述非常清楚，而且这个分法和点集都有专业术语，但是我忘了
（1）给出Fn的递归递推式；
（2）求证|C|=阿列夫1（即C与实数集等势）。
3.不知道,可能是布尔代数
题目：x×y = (xVy)×(xBy)，x,y∈[0,31]，x,y是整数。
×是普通乘法，V和B分别是按位或 和 按位与运算（B在原题里的符号是倒着的V，也就是且，我打不出但不影响）。
求满足方程的解的个数。
4.群
题目：（1）证明六阶群必有3阶元；
（2）证明n阶群必有p阶元，其中P是n的质因子。
5.图的连通性
题目：求证G是3-点连通图 当且仅当 G是轮图。
6.二部图的匹配
题目：专业术语我忘了，只能用我的语言说，如果有大佬表述更清楚，希望能再说一下。
设一个集合组={A1,A2,A3,...An}，
如果从A1到An中各取一个元素，组成集合{b1,b2,...,bn}，
能够做到这n个元素互不相同，则称这个集合组有QQQ（一个术语，三个字母,我用QQQ代替）。
举例集合组为{A1,A2,A3,A4}，
A1={1,3},A2={2,3,4},A3={3,2},A4={4,3},则集合组存在QQQ，集合为{1,2,3,4}或者{1,3,2,4}。
如果A1中删掉元素1，则不存在QQQ，因为找不到一个这样的集合，使得该集合中的元素互不相同且来自集合组中的不同集合。
求证：集合组{A1,A2,A3,...An}存在QQQ 当且仅当 集合组中任意K个集合的并集中的元素个数不小于K。
(by 仰望星空)
1.写出正则表达式所描述的语言（类似龙书题目3.3.2）。
2.有关寄存器的题目，应该是第七章内容。（6分）
3.龙书6.6.1。
4.请写一个DFA，它接受所有被3整除的二进制数（接受如11=3，110=6，不接受101=5等等）。
5.给一个文法，判断是不是二义性的，类似书上的if else那道例题。
6.SLR分析的全步骤，包括求FIRST和FOLLOW，求LR(0)项集，求GOTO，最后问文法是不是SLR的（26分）。
7.第九章的定值数据流，这题19分，以前从来没考过。没看完全不会写（比如我），希望后来的人不要放弃编译的任何一章（1-9章节）。
我的表述能力一般，如果有大佬能描述的更好请补充。
复习建议：编译看1-9章，不要只看前六章，然后把南大本科留的作业题都弄懂即可。
离散不会也不用担心，大家都不会，hh。等大佬的建议吧。