模拟试题（C语言为例）[下学期]

(共42张PPT)
程序设计语言模拟试题（一）
一、填空（30）
1）语言的标准化有 和 两个种类。
2）基于解释型语言的源程序，不产生目标机器代码，只是产生更易于执行的 ，然后由软件解释执行。
中间代码
专有化标准
共识性标准
3）一个数据对象的可能的值由 决定。
数据类型
4）未初始化的变量是已经创建单位赋值的数据对象，从数据对象拥有的左右值的角度看，它只有 ，但无 。
左值
5）一般，标量数据对象随计算机的 不同而变化。
硬件结构
6）类型检查涉及到实际参数的数据类型与可允许的参数数据类型相比较，判断两个类型相同的方法有 和 。
名字相同
右值
结构相同
7）在计算机软件开发领域，抽象原则的运用非常广泛，概括起来，可分为 和 两类。
过程抽象
8）在面向对象的系统中，对象之间的联系是通过
来实现的。
消息传递
9）通常，对象之间传递的消息应该含有下述信息
、 、 和 。
对象名
10）从来源角度考虑，继承可以分为 和
两种。
单重继承
数据抽象
方法名
实际参数
回答信息
多重继承
11） 和 是程序执行顺序控制需要考虑的两个方面。
顺序控制
12）顺序控制可以分为 、 、
和 四种。
优先级控制
13）不能被再分解成更小真程序的真程序叫做
。
基本程序
14）当一个可见数据对象在单一引用环境中有多个名字时，则这些名字称之为该数据对象的 。
别名
数据控制
条件控制
基于规则的控制
调用控制
15）直接从自由空间表列进行分配空间的存储管理有两种实现技术： 和 。
首次满足技术
16）异常有两个来源： 和
。
虚拟计算机检测到的
最佳满足技术
由程序设计语言语义产生的
二、简述（30）
1）请阐述类和对象之间的关系。
参考答案
2）请说明后缀语义表示法的计算规则。
参考答案
3）请阐述采用无用单元解决悬挂引用问题的基本思想。
参考答案
4） 试阐述任务存储管理中三种实现方法（单栈、多栈和单堆）的基本原理，各适合应用的场合以及各有的特点？
参考答案
5）以你所熟悉的一种语言为例，说明有哪些方法可以增加程序的可读性。
参考答案
三、 简单赋值语句的基本BNF文法如下： （10）
<赋值语句> ::= <变量> = <算术表达式>
<算术表达式> ::= <项>|<算术表达式> + <项> | <算术表达式> - <项>
<项> ::= <因子>| <项> <因子> | <项> <因子>
<因子> ::= <变量>| <数字> | （<算术表达式>）
<变量> ::= <标识符>| <标识符>[下标]
<下标> ::= <算术表达式>| <下标>，<算术表达式>
请将该简单赋值语句的利用扩充的BNF文法定义。
参考答案
四、 结果分析（10）
1）请写出下列程序的输出结果
int x=1, y=1;
void P(int x)
{ x++; y+ =x; printf(“x=%d, y=%d\n”,x,y); }
main()
{ P(y); printf(“x=%d, y=%d\n”,x,y);}
2）假设按值-结果方式进行参数传递，则输出结果是什么？
参考答案
五、 请定义一个类，并构造在两个整数中取大者和在三个整数中取最大者的重载方法和引用方法。（10）
参考答案
六、试构造C语言赋值语句T = B * C <= D + E / F – G的语法树。（10）
参考答案
程序设计语言模拟试题（二）
一、填空（30）
1） 程序的一般计算模型有： 、 、基于规则语言和 等四种。
答案：命令式语言、应用式语言、向对象语言
2）基于编译型语言的源程序在执行之前需先被转换成可执行的 。
答案：目标机器语言
3）若要求程序中的语句每一元素必须在一输入行的指定位置书写，则该语言的语法是 格式的。
答案：固定字段
4） 翻译一般可分为 和 两个阶段。
答案：源程序分析、目标代码生成
5）实际计算机的数据存储区的结构相对简单，以 方式组成字节或字（线性结构），具有 特性。
答案：比特流、静态
6）固定长度的字符串表示可用硬件直接支持，但其他串的表示以及串操作一般是用 来实现。
答案：软件模拟
7）数据结构的基本存储表示方法有 和 两种。
答案：顺序表示 、链式表示
8）具有相同内部成员（即具有相同的存储表示）的数据对象被认为 。
答案：类型相同
9）数据抽象把系统中需要处理的 和施加在它之上的 结合在一起，根据功能、性质、作用等因素抽象成不同的抽象数据类型。
答案：数据、操作
10）定义一个类型，一般需要从类型标识、 和
三个方面加以描述。
答案：属性说明、成员方法
11）在面向对象的系统中，对象间的相互作用是通过对象之间 来体现的。
答案： 发送消息的方式
12）如果类class仅仅是一个模板，而不能用于声明对象，则这种类称之为 。
答案： 抽象类
13）程序执行顺序的控制涉及到两个方面， 和
。
答案：顺序控制、数据控制
14）if语句通常用 和 指令来实现。
答案：硬件支持的分支、转移
15）子程序的活动包含两个部分： 和 。
答案: 代码段、活动记录
16）一般，表达式内的数据控制采用 方式，而表达式以外的数据控制 方式。
答案：直接传递、采用名字的使用和名字的引用
17）存储管理的三个主要方面是： 、 和
。
答案：初始分配、存储单元回收、压缩与再用
18）如果允许子程序在全部执行完之前返回到它们的调用者，这种子程序叫做 。
答案：协同程序
二、简述（30）
1）试比较无用信息和悬挂引用的危害性。
参考答案
2）请阐述重载和复用的特点，在两种情况下如何区分对方法的引用。
参考答案
3）试阐述保留和删除方式的实现原理、使用场合和各自特点？
参考答案
4）请比较翻译与解释的异同点。
参考答案
5）如果我们将一台计算机定义为算法和数据结构的集合，则这样的一台计算机可以采用哪些方式来实现。
参考答案
三、 1） 试写出<符号整数>的基本BNF文法和扩充的BNF文法。（8）
2） 如果有以下基本BNF文法规则： （5）
::=[, ] |
::= | ()
::=x |y
请构造符号串[y,[(x),y]]的语法树。
参考答案
四、结果分析（12）
1）请写出下列程序的输出结果
program main(input,output)
var i,j,k,m: integer;
procedure Q(var j: integer, m: integer)
begin
i:= i+k;
m:= j+1;
writeln(i,j,k,m);
end;
参考答案
procedure P(var i: integer, j: integer)
var k: integer;
begin
k:=4; i:= i+k; j:= j+K;
Q (i,j);
end;
begin (* start main*)
i:= 1; j:= 2; k := 3;
P (i,k);
writeln(i,j,k,m);
end; (* end main*)
2）假设，Pascal语言采用动态域规则，则上述程序的输出结果是什么？
五、试举例说明，程序设计语言中解决二义性的方法（10）
参考答案
六、Fortran语言中的向量以列优先存储，现假设已知元素A[I,J-1]的虚拟地址，试在A[I,J-1]的虚拟地址基础上，计算元素A[I,J]的虚拟地址（10）
参考答案
对象是对现实世界中事物的抽象，是面向对象程序的基本封装单位，是类的实例.
类是对象的抽象，是数据和操作的封装体.
类与对象之间的关系就如同一个模具与用这个模具铸造出来的铸件之间的关系一样。也就是说，类与对象之间的关系是抽象与具体的关系。在面向对象的程序设计中，对象被称作类的一个实例，而类是对象的模板。类是多个实例的综合抽象，而实例又是类的个体实物。
类与对象之间的关系
后缀表示计算仍然使用执行堆栈处理，规则是：
1) 如果是操作数，则压栈；
2) 如果是n元操作符，那么其操作数必然是栈顶的n个项目，则n个操作数弹栈，操作计算，并将操作结果压栈。
后缀语义表示法的计算规则
为了避免悬挂引用，宁可允许产生无用单元。当自由空间表列中的单元完全用完，又需要新的存储空间的时候，当前的计算暂时挂起，调用一个特别的无用单元回收过程，该过程能在堆中确定无用单元，并把它们送回到自由空间表列中，原先被挂起的计算又恢复继续进行，无用单元又开始增加直到自由空间完全用光，这时，再次调用无用单元回收过程，如此循环。
无用单元解决悬挂引用问题的基本思想
单栈：栈和堆分别创建在主存储器的两端，如果它们相遇，那么就没有了可用空间，程序必须终止。它能够充分地利用了存储空间。它是通常采用的方法。
单堆：所有存储空间都是堆，每个栈由从堆中分配的活动记录链接而成。这种方法总是可行的，特别适用于有限存储空间的系统。其缺点：1）额外的时间开销很大；2）严重的存储器碎片问题：由于活动记录可变长。
多栈：每个任务在存储器中有自已独立的栈，如果任何栈与它的下一段存储空间相遇，那么程序必须终止。在有了现代的虚拟存储系统的情况下，该方法是一种有效的解决方法。操作系统的存储管理可用来管理这样的多个栈，这使得语言翻译器的工作大大减轻，除了设置栈的初始地址外，语言翻译器并不需要做其他什么工作。
单栈、多栈和单堆
以C语言为例，增加可读性的方法有：
1）用自然语句格式：如x=y+z;
2）结构化：如C语言采用模块化结构，函数可单独定义;
3）自由使用关键字和噪声码：如if-else, switch, while等
4）注释：如可用“;”，等加以注释。
5）不限标识符长度：C语言中的标识符长度基本不受限制。
6）助记符：如C语言中的保留字等。
7）自由域格式：C语言一行可书写多条语句，且位置自由。
8）完整的声明：C语言中所有变量都必须先声明，后使用。
增加程序的可读性
三、
<赋值语句> ::= <变量> = <算术表达式>
<算术表达式> ::= <项>{ [+ | -] <项>}*
<项> ::= <因子> { [+ | -] <因子>}*
<因子> ::= <变量>| <数字> | （<算术表达式>）
<变量> ::= <标识符>| <标识符>[下标]
<下标> ::= <算术表达式>{，<算术表达式>}*
四、 1）请写出下列程序的输出结果
int x=1, y=1;
void P(int x)
{ x++; y+ =x; printf(“x=%d, y=%d\n”,x,y); }
main()
{ P(y); printf(“x=%d, y=%d\n”,x,y); }
2）假设按值-结果方式进行参数传递，则输出结果是什么？
解答：1）c程序按值传递。结果为：x= 2, y= 3
x=1, y= 3
2）按值-结果传递。结果为：x= 2, y= 3
x=1, y= 2
五、
六、构造C语言赋值语句T = B * C <= D + E / F – G的语法树
=
<=
T
C
B
/
*
E
F
G
-
+
D
比较无用信息和悬挂引用的危害性
无用单元可能使程序无法继续执行：
如果无用单元数目增加，那么程序可用空间便逐渐减小，则程序可能由于缺少自由空间而无法继续执行。
悬挂引用可能引起混乱：
如果一个程序试图通过一个悬挂引用修改一个早已释放了的结构，则在自由空间表列上相应单元中的内容可能不注意地被修改。
如果这种修改覆盖的是一个连接某一单元到另一个单元的指针，则整个剩下的自由空间表列可能变成不完全的自由空间表列。如果在随后的操作中，有存储分配器试图使用这个被覆盖的指针单元，则有可能导致难以料想的结果。
阐述重载和复用的特点
在两种情况下如何区分对方法的引用
在同一类中定义了多个同名而不同内容的成员方法时，我们称这些方法是重载的方法。重载的方法主要通过形式参数列表中参数的个数、参数的数据类型和参数的顺序等方面的不同来区分。
允许子类对父类的同名方法重新进行定义，即在子类中定义与父类中已定义的相同名而内容不同的方法。这种多态被称为覆盖.由于覆盖的同名方法是存在于子类对父类的关系中，所以只需在方法引用时指明引用的是父类的方法还是子类的方法，就可以很容易地把它们区分开来。
保留和删除方式的实现原理、使用场合和各自特点
保留方式的实现方法是：将包含保留变量的局部环境表作为子程序代码段的一部分而生成。删除方式的实现方法是：将包含删除变量的局部环境表作为子程序活动记录的一部分。
保留方式允许程序员书写对历史敏感的子程序。保留方式比较耗费存储空间，所有子程序的局部环境表存在于整个运行过程中。删除方式节省内存空间，只有那些正在运行或挂起的子程序需保留局部环境表。
翻译与解释的异同点
相同点：二者都接受高级语言作为输入。
不同点：
功能不同：翻译将源程序—>等价的目标语言程序；解释直接执行源程序（用户角度看）。
顺序控制：翻译遵循输入的物理序列语句；解释遵循程序的逻辑控制流程。
执行次数：翻译对每条语句只处理一次；解释则可能对同一条语句反复解释处理（如循环），也可能完全忽略一些语句（如控制流不能到达的语句）。
信息完整性：翻译可能造成源程序信息丢失，调试、测试较为困难；解释不会。
代价：翻译需要耗费更大的存储空间；解释需要较长的执行时间（解码时间）。
如果我们将一台计算机定义为算法和数据结构的集合，则这样的一台计算机可以采用哪些方式来实现。
通过硬件实现：直接使用物理设备支持算法和数据结构；
通过固件实现：使用微程序设计实现支持算法和数据结构；
通过软件模拟：构造一种算法和数据结构支持源程序的算法和数据结构；
上述方法的综合：直接利用计算机的硬件、软件和/或微程序支持。
三、 1）
基本BNF文法
<符号整数>::= <无符号整数>| - <无符号整数>
<无符号整数>::= <数字>| <无符号整数> <数字>
<数字>::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
扩充的BNF文法
<符号整数>::= [ - ] <数字> { <数字> }*
<数字>::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
2） 构造符号串[y,[(x),y]]的语法树。


[ , < S> ]
y
[ , < S> ]
[
,
[
( x ) ,
Y ] ]
( )




四、结果分析（12）
1）输出结果
program main(input,output)
var i,j,k,m: integer;
procedure Q(var j: integer, m: integer)
begin (* j=5, m=7 *)
i:= i+k; (* i=5+3=8, 全局i ,k *)
m:= j+1; (* m=8+1=9, 局部j, m *)
writeln(i,j,k,m); (* 8,8,3,9 *)
end;
procedure P(var i: integer, j: integer)
var k: integer;
begin (* i=1, j=3 *)
k:=4; i:= i+k; j:= j+K;
(* i=5, j=7 *)
Q (i,j);
end;
begin (* start main*)
i:= 1; j:= 2; k := 3; m := 4;
P (i,k);
writeln(i,j,k,m);
(* 8,2,3,4, 全局i,j,k,m *)
end; (* end main*)
1->5->8
全局i
P.i
Q.j
2）假设，Pascal语言采用动态域规则，则上述程序的输出结果是：
program main(input,output)
var i,j,k,m: integer;
procedure Q(var j: integer, m: integer)
begin (* j=5, m=7 *)
i:= i+k; (* i=5+4=9, 全局i , P.k *)
m:= j+1; (* m=9+1=10, 局部j, m *)
writeln(i,j,k,m); (* 9,9,4,10 *)
end;
procedure P(var i: integer, j: integer)
var k: integer;
begin (* i=1, j=3 *)
k:=4; i:= i+k; j:= j+K;
(* i=5, j=7 *)
Q (i,j);
end;
begin (* start main*)
i:= 1; j:= 2; k := 3; m := 4;
P (i,k);
writeln(i,j,k,m);
(* 9,2,3,4, 全局i,j,k,m *)
end; (* end main*)
1->5->9
全局i
P.i
Q.j
五、解决方法1：插入定界符，如
if (ConE1) if (ConE1)
{ if (ConE2) S1； 或 { if (ConE2) S1}；
else S2；} else S2；
解决方法2：在二者语义中强制的选择一种作为合法的解释，如就C,Pascal 语言中使用就近匹配原则，即else与最近的 if 匹配。
解决方法3：改造语法表示，如
Pasacl和C语言中：用[]表示数组，（）表示函数，所以A[i,j]理解为数组引用， A(i,j)解释为函数调用。从而避免了Fortran语言中的数组与函数引用二义性。
六、假设定义：A: array[1..3, 2..5];
即LB1=1, UB1=3, LB2=2, UB2=5。
[2,4]
[1,3]
[1,4]
[1,5]
[2,2]
[2,3]
[1,2]
[2,5]
[3,2]
[3,3]
[3,4]
[3,5]
[1,2]
[2,2]
[3,2]
[1,3]
[2,3]
[3,3]
[1,4]
[2,4]
[3,4]
[1,5]
[2,5]
[3,5]
现假设已知：A[2,4]的地址，需要计算V[2,5]的地址：则
Add(A[2,5]) = Add(A[2,4])+列的长度(3)。
行长度：S=（UB1-LB1+1）*E
可见，以列为主存储时：
Add(A[I,J]) = Add(A[I,J-1])+S