软考中级习题与解答——第二章_程序语言与语言处理程序（2）

例题11

例题12

1、知识点总结

2、选项分析

A. 可用正则式 a*b* 表示

• 这个说法是错误的。 正则表达式 a*b* 表示“零个或多个 a”后面跟着“零个或多个 b”。它能匹配 aaabb，ab，aaabbbb 等 a 和 b 的数量不相等的字符串。而语言 L 严格要求 a 和 b 的数量必须相等。因此，a*b* 描述的语言集合远大于 L

B. 不能用正则式表示，但可用不确定的有限自动机识别

• 这个说法是错误的。 根据克莱尼定理 (Kleene's Theorem)，正则表达式、确定的有限自动机 (DFA) 和不确定的有限自动机 (NFA) 在表达能力上是完全等价的。如果一个语言不能用正则表达式表示，那么它也绝对不能被任何有限自动机（无论是DFA还是NFA）所识别。

C. 可用正则式 aᵐbᵐ 表示

• 这个说法是错误的。 aᵐbᵐ 不是一个标准的正则表达式。正则表达式的语法中不包含这种用来表示“计数和回溯引用”的变量 m。标准的正则表达式只能表达有限次的重复（如 a{5}）或者不确定但无关联的重复（如 a*）。它无法表达“b 的数量必须等于前面 a 的数量”这种依赖关系。

D. 不能用正则式表示，但可用上下文无关文法表示

• 这个说法是正确的。

• 为什么不能用正则式表示？ 正则表达式的计算模型是有限自动机。有限自动机的核心特征是它只有有限的内存（即它的状态）。要识别 aᵐbᵐ，自动机必须在读取 a 的时候“记住” a 的数量，然后在读取 b 的时候进行“核对销账”。如果 m 可以是任意大的数字，那么有限个状态是绝对无法记住任意数量的 a 的。这就是正则语言的泵引理 所要证明的核心。

• 为什么可用上下文无关文法表示？ 上下文无关文法 (Context-Free Grammar, CFG) 的计算模型是下推自动机，它比有限自动机多了一个无限容量的栈 (Stack)。这个栈完美地解决了“计数”问题。我们可以用一个简单的上下文无关文法来定义语言 

3、最终答案：D

例题13

1、知识点总结

这道题考察的是上下文无关文法 (Context-Free Grammar, CFG) 所定义的语言 (Language) 的精确概念。

根据形式语言的标准定义，一个文法 G 所产生的语言 L(G) 是指：从开始符号 S 出发，经过零次或多次产生式的推导，所能得到的所有完全由终结符组成的字符串的集合。

2、选项分析

A. 从 S 出发推导出的包含 V 和 T 中所有符号的串

• 这个说法是错误的。 V 本身就包含了 T (V = N ∪ T)，所以说“包含V和T中所有符号”是冗余的。更重要的是，语言的最终句子不能包含非终结符 (N 中的符号)。推导过程中的中间字符串可以包含非终结符，但一旦推导结束，得到的就是语言中的一个句子，它必须只由终结符构成。

B. 从 S 出发推导出的只包含 V 中所有符号的串

• 这个说法是错误的。 V 包含了非终结符 N。语言的定义明确排除了含有非终结符的串。

C. 从 S 出发推导出的只包含 T 中所有符号的串

• 这个说法是正确的。 这完全符合语言 L(G) 的标准定义。推导必须从 S 开始，并且最终得到的字符串里只能包含终结符集合 T 中的符号。

D. T 中所有符号组成的串

• 这个说法是错误的。 这描述的是所有可能由终结符组成的字符串的集合（通常表示为 T*，即 T 的克莱尼闭包），但它没有考虑文法规则 (P) 的约束。一个字符串即使全部由终结符构成，如果它不能从开始符号 S 通过产生式推导出来，那么它就不属于该文法所定义的语言。

3、最终答案：C

例题14

1、知识点总结

DFA 到正则表达式的转换:

• 核心思想: 识别出从初始状态出发，并最终能回到接受状态的所有路径模式。
• 常用方法:
• 状态排除法 (State Elimination): 这是一个通用的算法，通过逐步消除非初始/终结状态，并用正则表达式来标记状态间的路径，最终得到一个从初始状态到终结状态的单一正则表达式。
• 观察和推导 (本题使用): 对于状态较少的简单 DFA，可以通过直接观察和分析路径来构建正则表达式。关键是识别出“自循环”和“往返循环”的基本模式，然后思考如何组合它们。

正则表达式的等价性:

• (A|B)* = (A*B*)* = (A*|B*)*
• (A*B)*A* = A*(BA*)* (Arden's Rule)
• R(S|T) = RS | RT (分配律)
• 理解这些代数规则有助于简化和判断正则表达式的等价性。在本题中，我们推导出的 (1 | 01*0)* 与选项 D (1*(01*0)*)* 是等价的，因为 1*(01*0)* 的重复，实际上就覆盖了 1 和 01*0 的任意组合。

分析 DFA 的语言:

• 语言: DFA 所能接受的所有字符串的集合。
• 分析技巧:确定初始状态和接受状态。找出在接受状态下的自循环，这通常对应正则表达式中的 *。找出从一个接受状态出发，经过其他状态再回到接受状态的“回路”，这是构成正则表达式的核心模块。将这些模块用连接、或 (|)、闭包 (*) 组合起来。

• 把 * 看作是一个魔法咒语，意思是“前面的东西，来0次或任意多次都行”。它代表重复任意次（包括0次）。看到 A*，就读作“0个或多个A”。

• 把 | 看作是菜单上的分割线，表示“或者”、“二选一”。它代表选择。看到 A|B，就读作“A 或者 B”。

2、选项分析

组合路径:

一个被接受的完整字符串，可以由这两种路径任意组合而成。

• 可以只走路径一（只输入 1）：1*

• 可以只走路径二（输入一个 01*0 块）：01*0

• 可以先走一段路径一，再走一段路径二：1*(01*0)

• 可以先走路径二，再走路径一：(01*0)1*

• 可以多次重复走路径二：(01*0)(01*0)... -> (01*0)*

• 可以任意地、以任意顺序组合这两种路径。

一个通用的正则表达式来表示“由 A 和 B 两种模式任意组合形成的字符串”是 (A|B)*。然而，在这里，1* 模式可以出现在 01*0 模式的“内部”和“外部”。

3、最终答案：D

例题15

1、选项分析

这道题考察的是确定性有限自动机（DFA）的最小化这一核心概念。DFA 最小化的目标是找到一个状态数最少的、且与原 DFA 等价的新 DFA。这个过程的关键步骤就是找出并合并等价状态。

两个状态等价（或称“可以合并”）的条件:
两个状态 p 和 q 是等价的，当且仅当满足以下两个条件：

• 同质性: 状态 p 和 q 要么都是接受状态，要么都不是接受状态。

• 转移一致性: 对于字母表中的任意一个输入符号 c，从 p 和 q 出发经过 c 转换后，到达的新状态也必须是等价的。

2、最终答案：B

例题16

1、知识点总结

2、选项分析

Case 1: f2(a) 采用引用调用

在引用调用方式下，f2 的形参 y 会成为 f1 中实参 a 的一个别名 (Alias)。它们指向同一块内存地址。因此，在 f2 内部对 y 的修改，会直接影响到 f1 中的 a。

Case 2: f2(a) 采用传值调用

在传值调用方式下，f2 的形参 y 会得到实参 a 的一个副本。y 和 a 是两个独立的变量，存储在不同的内存地址。因此，在 f2 内部对 y 的修改，不会影响到 f1 中的 a。

3、最终答案：B

例题17

1、知识点总结

while 循环：先判断循环条件，若条件为真则执行循环体，否则不执行循环体。循环体执行次数可能为 0 次或多次，循环条件判断次数为 “循环体执行次数 + 1（最后一次判断条件为假时）”。

do - while 循环：先执行循环体，再判断循环条件，循环体至少执行 1 次。循环条件判断次数等于循环体执行次数（每次执行完循环体都要判断条件）。

2、选项分析

• 选项 A：while 能实现的功能，do - while 也能实现，只是执行逻辑（先判断还是先执行）不同，并非功能有差异，所以 A 错误。
• 选项 B：循环条件相同时，两者执行效率没有绝对的高低之分，主要差异是执行逻辑（先判断还是先执行），而非效率，所以 B 错误
• 选项 C：对于 while 循环，假设循环体执行了 n 次，那么循环条件判断了 (n + 1) 次（最后一次判断条件为假，不执行循环体），所以循环体执行次数比循环条件判断次数少 1；对于 do - while 循环，循环体执行了 n 次，循环条件也判断了 n 次（每次执行完循环体都判断），所以循环体执行次数等于循环条件判断次数，C 正确。
• 选项 D：do - while 循环体执行次数等于循环条件判断次数，并非 “多 1”，所以 D 错误。

3、最终答案：C

例题18

1、知识点总结

核心规则：一个字符串被DFA接受，当且仅当从初始状态开始，按顺序读取字符串中的每一个字符，并根据转移函数进行状态转换，当所有字符都读取完毕后，DFA最终停留的状态是一个接受状态。

2、选项分析

本道题应该是有误，应该是能被该DFC接受的是什么 

3、最终答案：C

例题19

1、知识点总结

这道题主要考察编程语言中一个非常基础且核心的概念：变量的作用域 (Scope)。作用域决定了一个变量可以在程序的哪个部分被访问和修改。

全局变量 (Global Variables):

• 定义: 在所有函数体之外定义的变量。

• 生命周期: 从程序开始运行直到程序结束。

• 作用域: 在整个程序的所有地方都是可见和可访问的（除非被同名的局部变量覆盖）。

• 题目中的全局变量: 题目明确指出 “设某程序中定义了全局整型变量 x 和 y”。

局部变量 (Local Variables):

• 定义: 在函数体内部定义的变量。

• 生命周期: 从定义它的那一行代码开始，到它所在的函数执行结束为止。每次调用函数时，都会为局部变量重新分配内存；函数返回后，其内存被释放。

• 作用域: 仅在定义它的那个函数内部可见和可访问。

函数参数 (Function Parameters):

• 定义: 在函数声明的括号内定义的变量，用于接收调用者传入的值。

• 作用域: 和局部变量一样，函数参数只在该函数内部有效。它们在函数被调用时创建，在函数返回时销毁。

作用域覆盖/隐藏 (Scope Shadowing):

• 规则: 如果在一个内部作用域（如函数内）定义了一个与外部作用域（如全局）同名的变量，那么在这个内部作用域中，局部变量会“覆盖”或“隐藏”全局变量。

• 效果: 在该函数内部，任何对这个变量名的引用，都将指向这个新定义的局部变量，而不是全局变量。全局变量在该函数内部将变得不可见。

2、最终答案：C

例题20

1、选项分析

A. 算法的时间、空间复杂性与实现该算法所采用的程序设计语言相关

• 分析: 这是一个非常经典的概念辨析。算法的复杂性（时间复杂度和空间复杂度）是用来衡量算法本身效率的数学度量，它描述的是随着输入规模（n）的增长，算法所需执行的操作次数（时间）或占用内存空间（空间）的增长趋势。它是一个抽象的、理论上的概念，用大O表示法（如O(n), O(n²), O(log n)）来体现。

• 结论: 算法的复杂性与具体的编程语言无关。一个O(n²)的冒泡排序算法，无论用C语言、Java还是Python实现，它的时间复杂度依然是O(n²)。虽然不同语言实现的具体运行时间会有差异（比如C语言通常比Python快），但这不改变其复杂度的量级。因此，这个叙述是错误的。

B. 面向对象程序设计语言不支持对一个对象的成员变量进行直接访问

• 分析: 这个叙述的关键在于“不支持”。面向对象编程（OOP）的核心思想之一是封装 (Encapsulation)，即隐藏对象的内部状态，只通过公共的方法（getter/setter）来暴露。这是为了保护数据的完整性和一致性。

C. 与汇编语言相比，采用脚本语言编程可获得更高的运行效率

• 分析: 这考查的是不同层次语言的执行效率。

  • 汇编语言 (Assembly Language): 是最接近机器码的低级语言。它直接操作硬件寄存器和内存地址，几乎没有任何抽象层，因此编译后生成的机器码效率极高。

  • 脚本语言 (Scripting Language): 如Python, JavaScript, Ruby等，是高级语言，通常是解释执行的（或者带有即时编译 JIT）。它们有大量的抽象层（如动态类型、垃圾回收），这极大地提高了开发效率，但也带来了显著的运行效率开销。

• 结论: 汇编语言的运行效率远远高于脚本语言。因此，这个叙述说脚本语言效率更高，是完全错误的。

D. 面向对象程序设计语言不支持过程化的程序设计，只支持面向对象程序设计

• 分析: 这个叙述同样过于绝对化。

  • 过程化程序设计 (Procedural Programming): 以过程（或函数）为中心，将问题分解为一系列的步骤和函数调用来解决。

  • 面向对象程序设计 (Object-Oriented Programming, OOP): 以对象为中心，强调数据和操作数据的行为封装在一起。

• 关系: 面向对象语言是在过程化语言的基础上发展而来的，它们是兼容的，而不是互斥的。几乎所有的面向对象语言（如Java, C++, Python）都完美支持过程化编程。

  • 你可以在一个Java类的main方法里，完全不创建任何自定义对象，只调用一系列静态方法来完成一个任务，这就是一个典型的过程化程序。

  • C++更是直接从C语言（一个纯粹的过程化语言）发展而来，完全兼容其过程化范式。

• 结论: “不支持过程化”和“只支持面向对象”的说法是错误的。面向对象语言通常是多范式 (multi-paradigm) 语言，它们支持面向对象，同时也支持过程化，甚至函数式编程

2、最终答案：B