2012年中科大考研复试中的离散数学与编译原理试题

简介：
本资料提供了中国科学技术大学在2012年研究生入学考试复试中使用的离散数学和编译原理科目的试题，适合备考的学生参考学习。 ### 离散数学知识点解析 #### 前束合取范式 前束合取范式（PCNF）是一种将逻辑公式转换为特定形式的过程，这种形式使得所有量词都在公式的开头，之后跟着一个不包含任何量词的公式。这种形式对于自动化定理证明特别有用，因为它简化了公式的结构。 #### 逻辑等值关系证明 证明逻辑等值关系通常涉及应用逻辑代数的基本定律，如分配律、德摩根定律、结合律和交换律等。这些定律允许我们将复杂的逻辑表达式简化成更简单的形式，从而证明它们之间的等值性。 #### 集合上的二元关系 集合S上的二元关系R可以被定义为一组有序对，其中每个对（i, j）满足某种条件。在本例中，R1和R2分别是基于元素的倍数关系和小于关系定义的。合成关系R2R1和R1R2表示两个关系依次应用的结果，即对于所有x, y, z属于S，若存在z使得(x, z)属于R1且(z, y)属于R2，则(x, y)属于R2R1。类似地定义R1R2。 #### 关系的性质 关系图和关系矩阵是表示二元关系的两种常用方法。关系图直观展示了集合中的元素及其之间的连接，而关系矩阵则提供了关系的数学表示。关系的性质包括自反性、反自反性、对称性、反对称性和传递性，每种性质都有其特定定义。 #### 群论基本概念 群（Group）是抽象代数的一个基本概念，由一个集合和一个二元运算构成，满足封闭性、结合律以及单位元和逆元的存在。证明一个子集H是群的子群需要验证H在运算*下也构成群，即H自身满足所有群性质。 #### 图论中的度数和连通性 图论中节点的度数是指与其相邻边的数量。对于连通图G，如果每个节点的度数均为偶数，则可以证明去除任意一个节点v后的图G-v的连通分量数量不会超过v的度数的一半。这个定理基于欧拉路径和电路的概念。 #### 连通图的性质 对于任何连通图G，删除一个节点或一条边后，其连通性会受到影响。具体影响程度取决于图的具体结构。 ### 编译原理知识点解析 #### 最简确定有限自动机(DFA) DFA是最简确定有限自动机简称，用于识别正则语言的模型。构造接受(a|ab)*a*的DFA状态转换图需要理解该表达式的含义，并设计相应的状态图以确保每个状态对应于正则表达式的一部分并能正确识别所有字符串。 #### 文法的属性 证明一个文法既不是LL(1)也不是LR(1)，通常涉及分析其左递归、先验序列和冲突情况。LL(1)文法则要求无左递归且任何非终结符的先验序列都是唯一的，而LR(1)则更复杂。 #### 语法制导定义 语法制导定义（GDD）是编译器中嵌入语义动作的方法，在语法分析过程中执行计算。在此例中需要设计一个GDD以给定文法规则对输入句子中的每个a进行特定编号，这个规则遵循括号的作用域。 #### C语言函数调用和内存模型 C语言的函数f修改传递指针参数值反映了其函数调用内存模型：指针可用来改变被调用外部数据。理解这种机制对于正确处理数据结构和动态内存管理至关重要。 #### C语言函数参数类型 在示例中，`fun`期望一个特定类型的指针但直接传递了一个局部变量导致了类型不匹配错误；尝试将char与int之间指针相减会导致编译错误因它们的布局及大小不同。 #### 类型表达式的类型 C语言中表达式`&i - &j`和`&i - &k`的类型取决于操作数类型和编译器处理方式。当k为char时，执行此操作导致编译错误；若将k改为int，则可以进行相减得到两个地址间距离的结果（以int表示）。