2006年11月软考辅导班资料：程序设计语言基础试题

●若正规表达式r=(a|b|c)(0|1)*，则L(r)中有（1）个元素。

[供选择的答案]

（1）A．12  B．18   C．6   D．无穷

[参考答案]

（1）D

[试题分析]

在本题中要求的根据正规表达式，确定其正规集合的元素个数。这里关键是理解闭包的概念。因为式中有（0|1）^*，因此可以表示任意长度的0串或者1串。选D。

●已知文法G(E)

    　　E→T|E＋T

    　　T→F|T *F

    　　F→(E)|i

句型(T *F＋i)的语法树中短语有（2），素短语（3），其中最左素短语是（4）。

[供选择的答案]

（2）A、2个  B、3个   C、4个      D、5个

（3）A、1个  B、2个   C、3个      D、4个  　　　

（4）A、 (T*F＋i)   B、T*F＋i       C、T*F    D、i

[参考答案]

（2）C  （3）B  （4）C

[试题分析]

短语、直接短语、最左直接短语（句柄）、素短语、最左素短语以及推导、最左（最右）推导都是文法中最基本的概念。它们的定义相对比较抽象，因此我们可以借助语法推导树来理解。

    首先根据本题提供的文法和句型得到语法推导树如下：

    从语法树我们可以看出，短语就是位于同一个非终端结点的所有叶子结点，比如T*F、i就是是相对于T的短语，T*F+i是相对于S的短语, i是相对于F的短语。共有4个，选C。而直接短语则进一步要求这些叶子结点的非终端结点是它们的直接父结点。因此可以T*F、i都是该句型的直接短语。语法树上最左的直接短语就是句柄，本题中是T*F。

    所谓素短语是指这样一个短语，它至少含有一个终结符，并且除它自身之外不再含任何更小的素短语。最左素短语则指处于句型最左边的那个素短语。因此本题中的素短语是i、T*F，共两个，选B。而最左素短语是T*F，选C。

    对于这类型的题，还可能涉及到两个概念：最左推导和最右推导。最左推导是指任何一步推导过程σ→β，都是对σ中的最左非终结符进行替换。因此，在语法树中也很容易看出，如果语法树中的只有最左的非终结符结点（包括各级结点）具有其子树，则它就是最左推导。最右推导与之类似，最右推导也称规范推导。

● 在下面的程序中，若实参a与形参x以引用调用(call by reference)的方式传递信息，则输出结果为（5）；若实参a与形参x以值调用(callbyvalue)的方式传递信息，那么输出结果为（6）。

[供选择的答案]

（5） A．1　B．2　C．3　D．4
（6） A．1　B．2　C．3　D．4

[参考答案]

（5）D   （6）A

[试题分析]

本题考察的是函数调用中实参和形参的交换过程，C语言中通过传值的方式将实参传给形参，主调函数与被调用的函数之间传递数据的方式有两种，即被调用的函数返回值给主调函数和通过参数返回数据。也就是传值调用和引用调用两种。

在本题中，Mainprogram是主调函数，addone是被调用的函数，第一次是引用调用，对a的修改是针对实际参数的修改，具体过程如下：

a:=x+1；//x是指向a的，所以本式中a=2;x=1;

x:=x+2；//x被改变，x与相同，x=x+2=2+2=4

因为x是指向a的，所以a是4；

第二次调用的是值调用，具体过程如下：

a:=1；       //a=1;

a:=x+1；//在addone中a=2,在Mainprogram中a=1;

x:=x+2；     //改变了x的值并不能改变a的值

所以a=1