程序设计语言概论 复习题 2008.12

第一章 程序设计语言研究 概念 简述 分析 程序设计语言 好的程序设计语言应具备的基本性质 语言的四种基本范型 试根据好语言的判断标准，分析你所熟悉的一种语言能够成功的原因，并指出该系列标准是否有必要进一步扩充？ 设某语言支持三种基本数据类型：integer,real, char，以及两种结构数据类型：array和record。试用正交性来评价下面的两种设计的优缺点： (a) 数组和记录的元素既可以是基本数据类型，也可以是数组或记录。 (b) 数组和记录的元素可以是整型的或实型的。字符型的数组称为string并给予特别对待。记录的元素可以是字符型的，也可以是数组。数组的元素既不能是记录，也不能是数组，但允许定义多维数组。

第二章 语言设计问题 概念 简述 分析 虚拟计算机 影响程序设计语言设计的主要因素。 翻译和解释，软件仿真和翻译的异同及优缺点。 绑定及绑定时间，分析x:=x+1在不同绑定时间可能涉及到的绑定。

第三章 语言翻译 概念 简述 分析 语法和语义，正则表达式，FSA，PDA，语法分析树 语法的一般准则。 语法的基本元素。 翻译的阶段。 常见的语义分析功能。 分析 给出SSS|(S)|()的无歧义文法。 设S是一个字符串集合，其中的字符串能被某个有限状态自动计识别，SR是由S中的字符串的反文构成的集合，试证明： SR的所有字符串也能被某个有限状态自动机识别。 证明： anbn不能被FSA识别，但可以被PDA识别。

第四章 程序语言的性质 概念 简述 分析 属性文法、指称语义、停机问题 乔姆斯基分级文法的类别、及其基本形式 语义的基本模型 解释说明为什么下列文法能（或者不能）被正则文法识别： EE+T|T TT*P|P Pi 图灵机、及其结构、操作和运行原理。 证明有下列文法产生的语言是正则语言： S  aSa | a

第五章 基本数据类型 概念 简述 分析 数据对象，数据类型，常量和变量，强类型，类型转换 数据对象的基本属性。 声明数据对象的目的。 数据类型的规约和实现各包括哪些内容。 从你所熟悉的语言中，找出一种具有如下特征的基本操作，描述其基调及特征： (a) 具有一个隐含参数 (b) 有副作用 (c) 在其所规定的定义域内，对某些数据对象无定义 (d) 它是自修改的。 分析 比较静态和动态类型检查的优缺点。

第五章 基本数据类型（续） 分析 设str(i:j)是一个字符串选择操作，即从字符串str中选择从i到j的字符构成一个新的字符串。当赋值语句中，源操作数和目的操作数都是字符串选择操作时，例如 str(i:j) := str(k:l)，其中所选择的字串可能会有重叠，这时可能会有多种含义，试给出两种不同的操作含义（可以用两段代码来表示）。 用所熟悉的程序设计语言，试编写两段涉及指针创建和释放的程序，其中第一段程序会导致内存垃圾，第二段则会导致引用悬空。

第六章 封装 概念 简述 分析 数据结构，抽象数据类型，子程序定义，子程序激活，类型定义 举例说明结构数据类型“一维数组”的规约应包括的主要属性。 创建新类型及其操作的基本机制。 举例说明信息隐蔽和封装的区别。 描述类型相等的判定方式，并比较其不同。 分析 分析要将子程序的功能精确地表示成数学函数可能存在的问题。 给出两条按照结构等价来断定向量是否类型相等的规则。类似地，给出三条按照结构等价来断定记录类型的数据对象是否类型相等的规则。 假设语言BL中包含一个堆栈数据结构和三个相关的操作：NewTop(S,E)将元素E加入堆栈S的栈顶，PopTop(S)删除堆栈S的栈顶元素，GetTop(S)返回堆栈S的当前栈顶元素的指针。试问：这三个操作的设计是否合适？如果不合适，请重新给出定义。

第七章 继承 概念 简述 分析 继承，封装，派生类，抽象类，多态 类及对象间的关系。 多态及其形式。 试建立下列对象的类层次图，并通过继承定义适当的函数集计算体积、面积、和直径： box(盒子), circle(圆), rectangle(长方形), triangle(三角形), polygon(多边形), line(直线), point(点), object(对象), quadrilateral(四边形), sphere(球形), square(正方形), trapezoid(梯形), parallelogram(平行四边形), hexagon(六边形), pentagon(五边形), pyramid(椎形), cone(圆锥体).

第八章 顺序控制 概念 简述 分析 积极计值规则，隋性计值规则，副作用，合式程序，素程序 表达式的线性记法，并简述其中一种表达方式的计值方法。 语句级顺序控制的主要形式。 结构化程序设计的基本原则。 分析 证明：对于任意N>1，都存在一个有N个节点的素程序。 对如下的Pascal迭代语句： for simple_variable := initial_value to final_value do statement 分析在下列不同情形下的优点和实现方法： (a) initial_value和final_value只在for语句第一次执行时计值。 (b) initial_value和final_value在每次循环回来时都计值。

第九章 子程序控制 概念 简述 分析 关联，引用环境，静态和动态作用域，关联的保留和删除，形参，实参 子程序调用的“拷贝”规则及使用“拷贝”规则来实现子程序调用的控制机制时的前提条件。 简述数据控制的中心问题。 静态和动态作用域规则 什么是数据对象的别名，并举例说明。 分析 考虑下面的程序： Program Main(…); Var Y: integer; Procedure P(X: integer); Begin X:=X+1; write(X, Y) End; Begin Y:=1; P(Y); write(Y) End 分别给出(a)按值，(b)按名，(c)按值-结果，和(4)按引用传递参数的情形下的打印结果。

第九章 子程序控制(续) 设有如下的一段子程序代码,参数Expr和Index是按名传递的，LB和UP是按值传递的： real procedure Sum(Expr, Index, LB, UB); real Expr; integer Index, LB, UB; begin real Temp; Temp = 0; for Index := LB step 1 until UB do Temp := Temp + Expr; Sum := Temp end Sum; a). 怎样调用Sum可以返回矩阵real array D[1..50, 1..50]的主对角线元素之和？ b). 怎样调用Sum可以返回前100个非负奇数的平方和？