中科大编译原理 2012复试笔试题

1. (4分) 求与下述公式逻辑等值的前束合取范式：

y)  (y)R(y, z)) (z)Q(x, z) (x) (P(x,2. (8分) 对于命题公式P、Q、R，证明以下等值关系：

(1) (PQ)(RQ)(PR)Q

(2) P(QR)Q(PR)

3. (8分)

(1) 定义集合S={1,2,3,4,5}上的二元关系R1={| j = i 或 j = i / 2}, R2={ | i < j}，求合成关系R2R1和R1R2.

(2) 写出R2的关系图和关系矩阵，并指出其是否自反、反自反、对称、反对称、传递？

4. (8分) 设是群，H是G的非空子集。

证明：若任给a, b ∈ H，都满足a*b-1∈H， 则是的子群。

5. (6分) 证明：图G连通，每个结点的度数均为偶数，则对G的任意结点v，w(G-v)<=1/2d(v)。其中d(v)表示节点v的度数，w(G)表示图G的连通分图的个数。

6. (6分) 设G为连通图，任给节点v∈V(G)，是否有w(G-v)<=2?任给边e∈E(G)，是否有w(G-e)<=2?请分别给出证明或反例。

编译原理

1. （8分）画出接受(a|ab)*a*所描述语言的最简DFA的状态转化图。 2. （6分）试证明如下文法既不是LL(1)文法，也不是LR（1）文法。 A->aAa|a 3. （8分）有文法如下：

S->(L) S->a L->L,S L->S 假设我们对输入句子中每一个a进行编号。方法如下：将配对的括号看作一个“作用域”，当进入一个作用域时，接着“当前序号”进行连续编号；当退出一个作用域时，则恢复在进入该作用域时的那个“当前序号”。对于句子（a,(a,(a,a),(a))),编号为1 2 3 4 3。试写一个语法制导定义，实现上序编号。

4. （6分）C语言函数f的定义如下：

Int f(int x, int *py, int **ppz){

**ppz += 1; *py += 2; x*=3; return x + *py + **ppz; }

若c为整型变量，执行下面代码后d和c的值分别为多少,为什么？ a = &b; b = &c; c = 5; d = f(c, b, a);

5. (6分）一个C语言程序如下：

Void fun(struct{int x; double r;} *val){ } Main(){

Struct{int x; double r;} *val; Fun (val, 1); }

改程序在X86/Linux机器下报告错误信息如下： （省略，若干个警告，一个错误）

请解释为什么会报告上述的警告和错误。

6. （6分）如果变量i和j都是int类型，k是char类型，请写出表达式&i、&k和表达式&i-&j的类型表达式。为帮助你回答问题，下面给出程序作为提示 #include

Main() {

Int i, j; Char k;

Printf (\"%d %d\\n\}

它编译是输出如下错误：

Type.c: in function‘main':

Type.c:6:error:invalid operands to binary -

如果将k的类型改成int，则程序编译通过且运行时输出1 2。