南京大学—计算机专业考研复习资料—离散部分题解及编译题目补充.docx

《南京大学—计算机专业考研复习资料—离散部分题解及编译题目补充.docx》由会员分享，可在线阅读，更多相关《南京大学—计算机专业考研复习资料—离散部分题解及编译题目补充.docx（1页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、离散题目楼上两位已经说得很详尽了，说一下个人对部分题目的理解。2.计数问题先给每道题分12分，还剩80-12x6=8分。这8分是没有区别的，要分给6道题，问题 转化为将8个不可辨识的小球放入6个可辨识的盒子中，解决此类问题书上的计数部分有相 应的公式(参见推荐教材P130定理2及其相关例题，以及P133不可辨别的物体与可辨别 的盒子，例题9好像公式套错了？主要看例9下面的公式)，因此方案有：C(6+8-l, 6-l) = C(13, 5).(1)假设存在孤立的城市(即孤立点)，此城市与其他城市没有道路(即边)，那么其他 n-1个城市最多有(n-l)(n-2)/2 = C(n-l,2)条边(即当

2、其他n-1个城市为n-1阶完全图时)，所 以加上那个没有边的孤立城市，最多共有C(n-1,2)条边，这与边数mC(n-l,2)矛盾，所以 假设不成立，即没有孤立城市存在。(2)此题是2002年真题卷子上第三题的原题，证哈密顿回路，解法也一样，可参考之。4 .推荐教材P61例20原题编译原理编译考的不难，在楼上两位之外再补充和细化一下部分题n。1 .填空题(1)写出正则表达式：以不同字母开头和结尾的ab串(4分)(2)给出一段含数组的三地址代码，让画DAG图(6分).已知nfa,求dfa2 .写出正则表达式：amb其中m为偶数，n为奇数.(即2楼的第3题)给出java语法的产生式求：first集和follow集：求LL分析表.参考2楼的第2题3 .(即2楼的第5题)给出用&连接的布尔表达式，给出四元式(缺少跳转地址)，形如(注 意，下面的代码是自己杜撰的，仅用于说明题目的形式，真正的布尔表达式与四元式应经 忘了)ab & cd100： (j,a,b,(J)101：102： gc,d,(_)103： (j,求:(1)写出布尔表达式的truelist和falselist的内容;(2)在四元式中填上相应的标号。