计算机科学论坛--2007年南京大学计算机系复试笔试题（回忆版）

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

（本文由『计算机科学论坛』→『计算机考研交流』版Logician提供，转载请注明出处）

离散数学部分（共80分）

1、用集合定义有序对的方法有很多种，证明下面这种定义也是可行的（即，证明<a,b>=<c,d>当且仅当a=c且b=d）：定义<x,y>={{{x},Φ},{{y}}}。（15分）

2、证明<Z_6，⊙>上有且仅有6个自同态，并证明其中有且仅有2个自同构。其中⊙为模6加法运算。（15分）

3、设G为连通图，证明G中任意两条最长路径必有公共点。（15分）

4、对于一阶谓词系统PK，记S为PK中的所有公式的集合。在S上定义等价关系≈如下：对任意α,β∈S，令α≈β当且仅当PK├α←→β。记B={[α]|α∈S上的公式，[α]为S关于≈的等价类}。在B上定义二元关系≤如下，对任意[α],[β]∈B，令[α]≤[β]当且仅当PK├α→β。证明：<B,≤>是一个布尔代数。（20分）

5、有200名学生要到一家公司参加面试。面试的流程是，面试者先进入会议室，然后要看一个小时的公司历史展览，然后参加一个小时的面试。会议室于早上8:00:00打开，于上午10:59:59关闭。面试者必须逐个进入会议室，且只能在每分钟开始的那一个时刻（如8:00、8:01等）进入，且当有面试正在举行时，会议室不允许进新成员。只有在会议室关闭后，面试时间才有可能延长。问，这一天最多能有多少学生参加面试。（15分）

（本文由『计算机科学论坛』→『计算机考研交流』版Logician提供，转载请注明出处）

编译原理部分（共70分）

1、有文法G[E]如下：
    E::=E+T|E-T|E
    T::=T*F|F
    F::=(E)|i
其中i为整数。
A) 消除上述文法的左递归（5分）
B) 用递归子程序法写出上述文法的识别程序（5分）
C) 假设i由词法分析程序给出，其值由i.val给出，试修改上述识别程序，使其能正确计算出表达式的值。（5分）

3、给出L={a^n b^m c^k | m=n+k, n≥1, m≥1, k≥1}的文法描述。（5分）

4、对于语言{{0}{1}}
A) 给出与之等价的NFA（5分）
B）把上述NFA确定化成DFA并将其最小化（10分）

5、指出下面这个流图中的可用表达式（可以不必写出数据流方程），并进行“消除公共子表达式”全局优化。（15分）
（图略）

（本文由『计算机科学论坛』→『计算机考研交流』版Logician提供，转载请注明出处）

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

离散第5题是很诡异的。
我一直不明白这题到底想说/考什么……
感觉有一些问题没有交待清楚，比如“参观1小时后，是否必须立即面试”，11点关闭会议室后，是否仍可以开始新的面试……
不懂……

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

好难呀!那题完全不懂要考什么, 今年估计又有一匹人复试要挂了....

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

挂不了
南大的笔试及格线很低
去年才65分

以下是引用DavidPotter在2007-4-4 10:32:00的发言：
好难呀!那题完全不懂要考什么, 今年估计又有一匹人复试要挂了....

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

我第一题也没看明白...
题目的意思是不是要在定义<x,y>={{{x},Φ},{{y}}}下,证明<a,b>=<c,d>当且仅当a=c且b=d?
不过第三题我倒是会做,哈~最近在看图论,嘿嘿~

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

以下是引用Logician在2007-4-4 16:51:00的发言：
挂不了
南大的笔试及格线很低
去年才65分

[quote]以下是引用DavidPotter在2007-4-4 10:32:00的发言：
好难呀!那题完全不懂要考什么, 今年估计又有一匹人复试要挂了....
[/quote]

去年我们那边有两个人,初试成绩都挺高的, 结果疏忽了复试...

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

谢谢!
这些题有的看不懂.看来还要好好下功夫.

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

第五题似乎是图论的问题，又像是考偏序的调度应用，不懂，继续看，希望来得及啊


	W 3 C h i n a ( since 2003 ) 旗下站点苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》	101.074ms