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

例题21

1、知识点总结

死循环的特征：

语法是否正确？

一个死循环，例如 for (int i = 0; i >= 0; i++) {}，它的语法是完全正确的。编译器会愉快地接受它，不会报任何语法错误。

程序能否运行？

可以。程序会成功编译并开始运行。

行为是否符合预期？

不符合。程序员的意图是让循环在某个条件下结束，但由于逻辑设计上的缺陷，循环永远无法满足退出条件。程序会一直“卡”在循环里，无法继续执行后续代码，也无法正常退出。

这是一种典型的“逻辑错误”，即程序的实际行为与设计者的意图不符。

根据我们的知识点总结，这种“语法正确但逻辑错误”的问题，正是语义错误的典型特征。

2、选项分析

A. 语法: 错误。死循环的语法是正确的，编译器无法发现。

B. 语用: 不够准确。死循环不仅仅是代码风格或效率问题，它是一个根本性的逻辑缺陷，导致程序无法完成其预定功能。

C. 语义: 正确。死循环是典型的语义错误，因为它违反了程序的逻辑意图。

D. 语境: 不是一个标准的错误分类，且与死循环的性质不符。

3、最终答案：C

例题22

1、知识点总结

这道题考察的是使用正则表达式来描述一个特定模式的字符串集合。要解决这类问题，需要理解正则表达式的基本运算符：

连接 : ab 表示字符'a'后面紧跟着字符'b'。

或 / 并集: a|b (有时也写作 a+b) 表示可以是字符'a'或者字符'b'。

克林闭包 / 星号 : a* 表示字符'a'可以出现0次或多次（例如：空字符串, "a", "aa", "aaa", ...）。

括号: (ab)* 表示字符串"ab"这个整体可以出现0次或多次（例如：空字符串, "ab", "abab", ...）。

2、选项分析

字符串中的1可以随时出现，任意多次。这可以用1*来表示。0必须成对出现才能保证是偶数个。一个“对”就是00。但是，0和0之间可能被1隔开。例如0110也是偶数个0。因此，我们可以把“生成两个0”的最小单元看作是 0 后面跟上任意个1，然后再跟上一个0，即 01*0。在这些“成对的0” (01*0) 之间，以及在字符串的开头和结尾，都可以有任意数量的1。

3、最终答案：B

例题23

1、知识点总结

类型系统是程序设计语言的一个核心组成部分，它是一套规则，用于为程序中的各种值（变量、表达式、函数等）分配和管理名为“类型”的属性。

类型系统的主要作用/优点:

• 类型检查: 最重要的作用。通过在编译时或运行时检查操作的合法性，可以防止大量的类型错误，如将字符串和整数相加、调用对象上不存在的方法等。这大大减少了运行时错误，提高了程序的可靠性。
• 空间分配: 编译器根据数据类型，可以精确地知道需要为变量分配多少内存空间，从而实现高效的内存布局。
• 封装意图: 类型为数据赋予了“含义”。int 不仅仅是4个字节，它代表一个整数。Date 不仅仅是8个字节，它代表一个日期。这使得程序员可以从底层的二进制表示中解放出来，在更高的抽象层次上思考问题。
• 代码自解释: 明确的类型声明本身就是一种很好的文档。当看到一个函数签名 float calculatePrice(int quantity, float unitPrice) 时，我们能立刻理解它的输入和输出是什么，而不需要去阅读函数的具体实现。
• 编译器优化: 当编译器知道一个变量的精确类型时，它可以生成更优化的机器码。例如，知道一个数是整数，就可以使用高效的整数运算指令，而不是更慢的浮点数运算指令。

静态类型 vs. 动态类型:

• 静态类型语言 (Statically Typed): 在编译时进行类型检查。变量的类型在声明时就已确定，不能改变。优点是错误能被尽早发现，且通常运行效率更高。代表语言：C, C++, Java, C#, Go, Rust。

• 动态类型语言 (Dynamically Typed): 在运行时进行类型检查。变量没有固定类型，可以随时指向不同类型的值。优点是编码灵活、快速。缺点是很多错误只能在运行时才能发现，且有轻微的性能开销。代表语言：Python, JavaScript, Ruby, PHP。

2、选项分析

虽然定义动态数据结构的节点时，需要为节点本身及其包含的数据指定类型（例如 struct Node { int data; Node* next; }），但“类型”本身的作用是定义节点的静态结构和内存布局，而不是实现其“动态”的特性。动态性是由指针/引用带来的，与数据类型定义的目的没有直接关系。换句话说，类型系统是定义数据结构“积木块”的工具，而动态性则是通过指针/引用将这些“积木块”灵活地“链接”起来的能力。因此，说类型的作用是“便于定义动态数据结构”是不准确的。

3、最终答案：D

例题24

1、知识点总结

• C 语言指针

定义: 指针是一个变量，其存储的值是另一个变量的内存地址。

指针算术: C 语言支持对指针进行加减运算。这些运算是基于其所指向的数据类型的大小进行的，而不是简单的地址数值加减。这是实现高效数组和内存操作的关键。

指针的指向: 指针可以指向内存中任何位置的数据，包括栈、堆和静态数据区。

• C 语言变量

定义: 一块有名字的、用于存储数据的内存区域，其值在程序运行过程中可以改变。

属性: 每个变量都有类型（如int, char, float）、名称、值和地址。

• C 语言常量 

定义: 值在程序运行过程中不可改变的量。

分类: 字面常量是直接写在代码中的值，如 10, 3.14, 'c', "text"。它们本身就隐含了类型；符号常量是使用 const 关键字或 #define 预处理指令定义的有名字的常量。

属性: 常量也有类型和值，但通常我们不关心它的地址，并且最重要的是它不可被赋值。

• 类型系统

C 语言是一种静态强类型语言。静态: 变量和常量的类型在编译时就已确定。强类型: 编译器会严格检查不同类型数据之间的运算是否合法，不允许隐式的、不安全的类型转换。在 C 语言中，所有的数据（无论是变量还是常量）都必须有明确的类型。这是语言安全性和编译器工作的基础。

2、选项分析

A. 在 C 语言中，对指针变量进行算术运算是没有意义的

• 这个说法是错误的。 对指针进行算术运算（主要是加法和减法）是 C 语言强大和灵活性的核心体现之一，也是其最常用的功能。

• 指针加法: ptr + n 表示将指针 ptr 向前移动 n 个其所指向的数据类型大小的单位。例如，如果 p 是一个 int* 指针，p+1 会将地址增加 sizeof(int) 个字节，使其指向数组的下一个整数。这在遍历数组时非常有用。

• 指针减法: ptr - n 同理。两个同类型指针相减 ptr1 - ptr2 可以得到它们之间相隔的元素个数。

• 因此，指针算术运算是非常有意义的。

B. 在 C 语言中，指针变量必须由动态产生的数据对象来赋值

• 这个说法是错误的。 指针变量可以指向任何合法的内存地址。

• 它可以指向静态/全局变量的地址：int g_var; int *p = &g_var;

• 它可以指向栈上（自动）变量的地址：void func() { int stack_var; int *p = &stack_var; }

• 它当然也可以指向堆上动态分配的数据对象的地址：int *p = (int*)malloc(sizeof(int));

• 因此，指针的赋值来源非常广泛，并不局限于动态产生的数据对象。

C. 在 C 语言中，变量和常量都具有类型属性

• 这个说法是正确的。 这是静态类型语言的一个基本特征。

D. 在 C 语言中，变量和常量都可以被赋值

• 这个说法是错误的。 这混淆了变量和常量的根本区别。变量核心特性就是它的值可以改变，因此可以被赋值。常量核心特性就是它的值在定义后不能被改变。

3、最终答案：C

例题25

1、选项分析

3、最终答案：B

例题26

1、知识点总结

这道题考察的是根据给定的上下文无关文法的产生式，推导出它所能生成的语言（字符串集合）的通用范式。

已知文法 G[S]:

开始符号: S

产生式规则: S → aSa (递归规则)              S → b (终止规则)

核心问题: 从开始符号 S 出发，利用这两条规则，可以生成什么样的字符串？

识别文法模式:

• S → aSb: 生成 aⁿbⁿ 类型的语言 (左右配对)。

• S → aSa: 生成 aⁿ...aⁿ 类型的语言 (回文结构)。

• S → aS: 生成 aⁿ... 类型的语言 (前缀重复)。

• S → Sa: 生成 ...aⁿ 类型的语言 (后缀重复)。

通过识别这些基本的产生式模式，可以快速判断文法所生成语言的大致结构。本题的 S → aSa 和 S → b 组合，就是一个典型的“回文”结构，中心对称点是 b。

2、选项分析

3、最终答案：B

例题27

1、最终答案：D

例题28

1、选项分析

2、最终答案：D

例题29

1、知识点总结

2、选项分析

这段代码有一个非常常见但致命的错误。在 while(i<10) 这一行的末尾，多了一个分号 (;)。在 C 语言中，一个单独的分号 ';' 表示一个空语句 (null statement)。因此，while(i<10); 实际上被编译器解释为：

• 循环条件: i < 10

• 循环体: 一个空语句 ``;`

这会产生一个无限循环。

• 程序开始时，i = 0。

• while 循环检查条件 0 < 10，为真。

• 执行循环体，也就是那个空语句 ``;。执行空语句不产生任何效果，i` 的值仍然是 0。

• 再次检查循环条件 0 < 10，仍然为真。

• 再次执行空语句...

• 这个过程会无限地进行下去，i 的值永远不会改变，循环条件 i<10 永远为真。程序会卡在这里，永远不会执行到后面的 {i=i+1;} 代码块。

3、最终答案：D

例题30

1、知识点总结

有限自动机 :

• 一个计算模型，用于识别特定的字符串集合（称为语言）。

• 由五个部分组成：状态集、字母表（允许的输入字符）、转移函数、一个初始状态和一个或多个接受状态。

状态转换图:

• 有限自动机的一种可视化表示。

• 节点 (圆圈): 代表状态。

• 初始状态: 通常有一个无源的箭头指向。

• 接受状态 (终止/终结状态): 通常用双重圆圈表示。

• 有向边 (带标签的箭头): 代表状态转移。p --c--> q 表示在状态 p 读入字符 c 后，会转移到状态 q。

字符串的识别/接受:

• 一个字符串能被自动机“识别”或“接受”，指的是从初始状态开始，按照字符串的字符顺序进行状态转移，当所有字符处理完毕后，自动机最终停留在一个接受状态。

• 如果在转移过程中，某个状态对当前字符没有对应的出边，则转移失败，字符串被拒绝。

• 如果字符串处理完后，停留在非接受状态，字符串也被拒绝。

2、最终答案：A