离散数学

（by 猪精，成长中的懒羊羊...）

1. 证明从自然数集合到自然数集合的所有函数与实数集等势

2. 甲乙丙丁四人玩传球游戏，从甲传出，第六次回到甲手里的传法有多少种（不能自己给自己传）

3. 非降路径问题（屈书有） 1）求共有多少种 2）证明：不穿过对角线的非降路径共有C(2n,n)/(n+1)种，其中C(n,m)代表组合数 参见屈婉玲离散数学第二版第248页例12.9

4. 群论证明题 s,k是G的子群，k是s的子群，证明：[G:k]=[G:s][s:k] 如果是无限群，等号表示等势

5. 证明：竞赛图都有哈密顿通路

6. 证明：图的生成树的计数（所有可能情况数）等于删去一条边后图的生成树的计数加上这条边缩去后的图的生成树的计数(边的收缩定义见屈书)

编译原理

（by 周小伦）

• 写一个正则表达式的所表达的意思
• 判断所给出的两个文法是否具有二义性，并举出例子
• 由LR（1）文法得到LALR文法不可能产生什么冲突，为什么
• 已给出文法判断是否为LL(1)文法，（判断后为否）在不修改原意的基础上做最少的改变使其变为LL（1）文法
• 根据表达式及翻译方案建立注释语法书并给出翻译结果（带回填），该题请参照龙书本科版p248 例6.17 表达式不一样但是体型完全相同
• 根据产生式集建立LR（0）自动机（求出项集簇、GOTO函数），并判断该文法是否为SLR文法

补充1 （不知道有没有记错）

（by 洛）

离散：

上面第4题，我记得题目的条件是k属于s，分两种情况证明那个等式：题目中的群是有限群或者无限群。

第6题我记得是，证明图的所有不同的生成树的个数=删去一条边后图的不同生成树个数+收缩一条边后图的不同生成树个数。

编译：

上面的第5题，我记得题目给的表达式是x==y&&z==0||a==b（形式大概是这样，具体记不清了），然后给了一个图，在紫龙书完整版上是在264页图6-43，要求根据该翻译方案写出生成的三地址代码，从序号100开始，然后给出注释语法分析树。（答案的形式应该类似于紫龙书完整版265-266页的图6-44和6-45）

第6题，我记得题目还要求画出LR（0）自动机（可以用编号代表各个项集，比如I0可以用0来表示），求出FIRST和FOLLOW，最后判断是否为SLR的时候，最好还求一下ACTION函数。

上面的前三题是小题，分值小，后三题是大题。

我记得还有一道小题，给出三个变量，三个寄存器的内容和一段汇编代码，求这段代码执行之后变量和寄存器内容的变化。