1、数据库系统工程师-程序设计语言处理程序及答案解析(总分：62.00，做题时间：90 分钟)某一非确定性有限自动机(NFA)的状态转换图如图 6-1 所示，该 NFA 等价的正规式是 (1) ，与该 NFA 等价的 DFA 是 (2) 。（分数：2.00）A.0*|(0|1)0B.(0|10)*C.0*(0|1)0)*D.0*(10)*(2). （分数：1.00）A.B.C.D.某一确定性有限自动机(DFA)的状态转换图如图 6-5 所示，令 d=0|1|2|9，则以下字符串中，不能被该DFA 接受的是 (3) ，与该 DFA 等价的正规式是 (4) 。 (其中， 表示空字符)3857 1.2E
2、+5 -123 .576E10（分数：2.00）A.、B.、C.、D.、A.(-d|d)d*E(-d|d)d*|(-d|d)*.d*(|E(-d|d)d*)B.(-d|d)dd*(.|)d*|(|E(-d|d)d*)C.(-|d)dd*E(-|d)d*|(-d|d)dd*.d*(|E(-|d)d*)D.(-d|d)dd*E(-d|d)d*|(-d|d|)dd*.d*(|E(-dd*|dd*)1.对于以下编号为、的正规式，正确的说法是 (5) 。(aa*|ab)*b (a|b)*b (a|b)*|aa)*b（分数：1.00）A.正规式、等价B.正规式、等价C.正规式、等价D.正规式、互不等价2.
3、高级程序设计语言中用于描述程序中的运算步骤、控制结构及数据传输的是 (6) 。（分数：1.00）A.语句B.语义C.语用D.语法(7) 是面向对象程序设计语言不同于其他语言的主要特点，是否建立了丰富的 (8) 是衡量一个面向对象程序设计语言成熟与否的重要标志之一。（分数：2.00）A.继承性B.消息传递C.多态性D.静态联编A.函数库B.类库C.类型库D.方法库3.“title style=“italic“science/title“，是 XML 中一个元素的定义，其中元素的内容是 (9) 。（分数：1.00）A.titleB.stvleC.italicD.science4.下面关于编程语言的
4、各种说法中， (10) 是正确的。（分数：1.00）A.由于 C 语言程序是由函数构成的，因此它是一种函数型语言B.Smalltalk、C+、Java、C#都是面向对象语言C.函数型语言适用于编写处理高速计算的程序，常用于超级计算机的模拟计算D.逻辑型语言是在 Client/Server 系统中用于实现负载分散的程序语言5.在面向对象的语言中， (11) 。（分数：1.00）A.类的实例化是指对类的实例分配存储空间B.每个类都必须创建一个实例C.每个类只能创建一个实例D.类的实例化是指对类进行初始化6.给定 C 语言的数据结构struct Tint w；union Tchar c； int I
5、； double d； )U；假设 char 类型变量的存储区大小是 1 字节，int 类型变量的存储区大小是 4 字节， double 类型变量的存储区大小是 8 字节，则在不考虑字对齐方式的情况下，为存储一个 struct T 类型变量所需要的存储区域至少应为 (12) 字节。（分数：1.00）A.4B.8C.12D.17在过程式程序设计()、数据抽象程序设计()、面向对象程序设计()、泛型(通用)程序设计()中，C+语言支持 (13) ，C 语言支持 (14) 。（分数：2.00）A.B.C.D.A.B.C.D.7.若程序运行时系统报告除数为 0，这属于 (15) 错误。（分数：1.00
6、）A.语法B.静态语义C.动态语义D.运算对象不匹配在下列程序中：Program test(input，output)；var i，j：integer；procedure calc(p1，p2：integer)；begin p2：=p2*p2 p1：=p1-p2；p2：=p2-p1；endcaicbeginmainI：=2；j：=3；calc(i，j)；write(j)；endmain当参数传递采用引用方式(Call by Reference)时，所得结果 j= (16) ；当参数传递采用换名方式(Call by Name)时，所得结果 j= (17) ：当参数传递采用赋值方式(Call by
7、 Value)时，所得结果 j= (18) 。递归是程序设计中很重要的一种控制结构，通常实现递归时，采用的数据结构是 (19) 。对那些既可以用递归方式，也可以用循环方式求解的问题，就执行效率而言 (20) 。（分数：5.00）A.0B.3C.5D.6E.10F.16G.20H.28A.0B.3C.5D.6E.10F.16G.20H.28A.0B.3C.5D.6E.10F.16G.20H.28A.数组B.栈C.队列D.循环链表A.难以断定B.两者相同C.循环优于递归D.递归优于循环文法 G=(VT，V N，P，S)的类型由 G 中的 (21) 决定。若 GO=(a，b，S，X， Y，P，S)，
8、P 中的产生式及其序号如下：1：SXaaY2：XYY|b3：YXbX|a则 GO 为 (22) 型文法，对应于 (23) ，由 GO 推导出句子 aaaa 和 baabbb 时，所用产生式序号组成的序列分别为 (24) 和 (25) 。（分数：5.00）A.VTB.VNC.PD.SA.0B.1C.2D.3A.图灵机B.下推自动机C.有限状态自动机D.其他自动机A.13133B.12312C.12322D.12333A.13133B.12312C.12322D.12333一个命题的可判定性是指：存在一种算法能给出该命题成立与否的结论。给定文法 G，只有当 G 为 (26) 时，命题“L(G)是空
9、集、有限集或无限集”才是可判定的，当给出两个不同文法 G1 和 G2，只有当 G1，G2都是 (27) 时命题“L(G1)L(G2)”才是可判定的。（分数：2.00）A.1 型B.2 型C.3 型D.0 型E.2 型或 3 型F.1 型或 2 型或 3 型G.0 型或 1 型或 2 型或 3 型A.1 型B.2 型C.3 型D.0 型E.2 型或 3 型F.1 型或 2 型或 3 型G.0 型或 1 型或 2 型或 3 型有限状态自动机可用 5 元组(V T，Q，q 0，Q f)来描述，它可对应于 (28) 。设有一有限状态自动机 M 的定义如下：VT0，1，Qq 0，q 1，q 2) 定义为
10、：(q 0，0)=q 1 (q 1，0)=q 2(q 2，1)=q 2 (q 2，1)=q 2Qf=q2。M 是一个 (29) 有限状态自动机，它所对应的状态转换图为 (30) ，它所能接受的语言可以用正则表达式表示为 (31) ，其含义为 (32) 。（分数：5.00）A.0 型文法B.1 型文法C.2 型文法D.3 型文法A.歧义的B.非歧义的C.确定的D.非确定的(3).注：其中“-”表示开始状态，“+”表示终止状态。（分数：1.00）A.B.C.D.A.(0|1)*B.00(0|1)*C.(0|1)*00D.0(0|1)*0A.由 0 和 1 所组成的符号串的集合B.以 0 为头符号和
11、尾符号，由 0 和 1 所组成的符号串的集合C.以两个 0 为结束的，由 0 和 1 所组成的符号串的集合D.以两个 0 为开始的，由 0 和 1 所组成的符号串的集合用高级语言编写程序时，子程序调用语句中的实际参数必须与子程序说明中的形式参数在 (33) 上保持一致。在允许子程序递归调用的高级语言环境中，需用动态存储管理方法，它通常使用一个 (34) 存入子程序的调用记录，调用记录可包括：全局量存储区域的 (35) ；调用点所在子程序的 (36) ；调用点的 (37) ；形式参数和实际参数的通信区域；返回值；本子程序的局部量和临时变量存储区域等。（分数：5.00）A.个数、类型B.个数、顺序
12、C.个数、格式、顺序D.个数、类型、顺序A.线性表B.队列C.堆D.下堆栈A.子程序首地址B.调用记录首地址C.参数地址D.寄存器地址E.返回地址F.开始地址A.子程序首地址B.调用记录首地址C.参数地址D.寄存器地址E.返回地址F.开始地址A.子程序首地址B.调用记录首地址C.参数地址D.寄存器地址E.返回地址F.开始地址语法分析方法大体上可分成自顶向下和自底向上两种。自底向上分析法，是从输入符号串开始逐步进行 (38) ，直至 (38) 成文法的起始符号。自顶向下分析法，则是从文法的起始符号开始反复使用产生式进行 (39) ，直至 (40) 出输入符号串。算符优先文法是一种自底向上分析方法
13、，其特点是文法的产生式中 (41) 。自顶向下的分析方法，通常要求文法的产生式 (41) ，如 (42) 文法就是一种可以自顶向下分析的文法。（分数：5.00）A.递归B.综合C.回归D.推导E.分解F.归约A.递归B.综合C.回归D.推导E.分解F.归约A.不含两个相邻的非终结符B.不含两个相邻的终结符C.不含 产生式D.不含长度为 1 的产生式A.不以非终结符开头B.不以终结符开头C.不含左递归D.不含右递归A.LR(I)B.LL(I)C.SLR(I)D.LALR(I)假设某程序语言的文法如下：SSaT|TTTbR|RRPdR|PPfSg|e其中 Vra，b，d，e，f，g；V nS，T，
14、R，P；S 是开始符号，那么，此文法是 (43) 文法。这种文法的语法分析通常采用优先矩阵。优先矩阵给出了该文法中各个终结符之间的优先关系(大于、小于、等于和无关系)。在上述文法中，某些终结符之间的优先关系如下：b (44) a；f (45) g；a (46) a；d (47) d。（分数：5.00）A.五则文法B.算符文法C.二义文法D.属性文法A.大于B.小于C.等于D.无关系A.大于B.小于C.等于D.无关系A.大于B.小于C.等于D.无关系A.大于B.小于C.等于D.无关系假设某程序语言的文法如下：Sa|b|(T)TTdS|S其中：V t(a，b，d，(，)，V nS，T，S 是开始符
15、号。考察该文法，称句型(Sd(T)db)是 S 的一个 (48) 。其中 (49) 是句柄： (50) 是素短语； (51) 是该句型的直接短语； (52) 是短语。（分数：5.00）A.最左推导B.最右推导C.规范推导D.推导A.SB.bC.(T)D.Sd(T)A.SB.bC.d(T)D.Sd(T)A.SB.S，(T)，bC.S，(T)，TdS，bD.(Sd(T)db)A.(Sd(T)db)B.d(T)C.TdD.Sd(T)d考察下列文法：G(V T，V N，E，P)其中：V T+，*，(，)，iVNE，T，FE 是开始符号；P：EE+T|TTT*F|FF(E)|iF*F+T 是该文法的一个
16、句型，其中 (53) 是句柄， (54) 是素短语。 (55) 是该句型的直接推导， (56) 是该句型的最左推导。 (57) 是该文法的一个句子。（分数：5.00）A.FB.F*FC.F+TD.F*F+TA.FB.F*FC.F+TD.F*F+TA.F*F+iB.F*F+T*FC.F*F+F*FD.i*i+TA.F*F+T*FB.F*F+TC.F*(E)+TD.(E)*F+TA.T+(i+i)B.i+(i+F)C.iD.(E)已知一不确定的有限自动机(NFA)如图 6-6 所示，采用子集法将其确定化为 DFA 的过程如表 6-1 所示。状态集 T1 中不包括编号为 (58) 的状态；状态集 T
17、2 中的成员有 (59) ；状态集乃等于 (60) ；该自动机所识别的语言可以用正则式 (61) 表示。（分数：4.00）A.2B.4C.3D.5A.1，3，4，5，ZB.2，3C.6D.4，5，ZA.ZB.6C.4，5，Z)D.A.(0，1)*B.(0*|1*)*001C.(0*|1*)*0(0|1)*D.(0*|1*)0(01)*8.程序设计语言引入“类”的概念是为了解决数据保护问题。C+语言将类的成员封装在类体之中，使之具有一定的存取规则，这些规则规定了存取类的成员的权利，其中，对于用 private 说明的成员，它 (62) 。（分数：1.00）A.既能被该类的成员函数访问，又能被外界
18、直接访问B.只能被该类的成员函数访问，外界不能直接访问C.不能被该类的成员函数访问，只能被外界直接访问D.既不能被该类的成员函数访问，也不能被外界直接访问数据库系统工程师-程序设计语言处理程序答案解析(总分：62.00，做题时间：90 分钟)某一非确定性有限自动机(NFA)的状态转换图如图 6-1 所示，该 NFA 等价的正规式是 (1) ，与该 NFA 等价的 DFA 是 (2) 。（分数：2.00）A.0*|(0|1)0B.(0|10)* C.0*(0|1)0)*D.0*(10)*解析：(2). （分数：1.00）A. B.C.D.解析：分析我们先介绍有关概念和规则。1有限状态自动机一个确
19、定的有限状态自动机 M(记做 DFA)是一个五元组：M(，Q，q 0，F，)其中：(1)Q 是一个有限状态集合；(2)是一个字母表，其中的每个元素称为一个输入符号；(3)q0Q，称为初始状态；(4)F*Q，称为终结状态集合；(5) 是一个从 Q(Q 与的笛卡儿乘积)到 Q 的单值映射：(q，a)=q (q，qQ， a)表示当前状态为 q，输入符号为 a 时，自动机将转换到下一个状态 q，q称为 q 的一个后继。若 Q=q1，q 2，q n)，a 1,a2,，a n)，则(q i，a j)nm 是一个 n 行 m 列矩阵，称为 DFA 的状态转换矩阵，或称转换表。有限状态自动机可以形象地用状态转
20、换图表示，设有限状态自动机：DFA M=(S，A，B，C，f，1，0，S，f，)，其中：(S，0)=B，(S，1)=A，(A，0)=f，(A，1)=C，(B，0)=C，(B，1)=f，(C，0)=f，(C，1)=f其对应的状态转换图如图 6-2 所示。*图 6-2 中的圈表示状态结点，其中双圈表示终结状态结点。而边表示状态的转换，代表映射。边上的符号表示此转换需要输入的符号，代表映射的输入。对于上的任何字符串 w*，若存在一条从初态结点到终态结点的路径，在这条路径上的所有边的符号连接成的符号串恰好是 w，则 w 被 DFA 所识别(或接受、读出)。 DFA 所能识别的符号串的全体记为 L(M)
21、，称为 DFA 所识别的语言。如果对所有 W*，以下述的递归方式扩张 的定义：(q，)=q(q，wa)=(q，w)，a)，对任何 a，qQ我们则可以把 DFA 所识别的语言形式定义为：L(M)w|w*，若存在 qF，使 (q 0，w)q前面介绍的是确定的有限自动机，即一个状态对于特定的输入字符有一个确定的后继状态。而当一个状态对于特定的输入字符有一个以上的后继状态时，我们称该有限自动机为非确定有限自动机(记做 NFA)，其形式定义如下。一个非确定的有限自动机 M 是一个五元组：M(，Q，q 0，F，)其中，Q，q 0，F 的意义和 DFA 的定义一样，而 一个从 Q到 Q 的子集的映射，即 ：
22、Q2 Q，其中 2Q是 Q 的幂集，即 Q 的所有子集组成的集合。与 DFA 一样，NFA 同样可以用状态转换图表示，所不同的是，在图中一个状态结点可能有一条以上的边到达其他状态结点。同样，对于任何字符串 W*，若存在一条从初态结点到终态结点的路径，在这条路径上的所有边的符号连接成的符号串恰好是 w，则称 w 为 NFA 所识别(或接受或读出)。若 q0正几这时 q0既是初始状态，也是终结状态，因而有一条从初态结点到终态结点的 -路径，此时空符号串可以被 NFA接受。 NFA 所能识别的符号串的全体记为 L(M)，称为 NFA 所识别的语言。对任何一个 NFA，都存在一个 DFA使 L(M)L
23、(M)，这时我们称 M与 M 等价。构造与 M 等价的 M的基本方法是让 M的状态对应于 M 的状态集合。即如果有 (q，a)q 1，q 2，q n)，则把q1，q 2，q n)看做 M的一个状态，即 M中的状态集合 Q的一个元素。对于一个 NFA，如果我们把 扩展为从 QU到 2Q的映射，则我们称该自动机为带 -转移的非确定有限自动机。同样，对于带 -转移的非确定有限自动机，我们也可以构造与之等价的不带 -转移的非确定有限自动机。2正规表达式正规表达式(正规式)是一个十分有用的概念，它紧凑地表达有限自动机所接受的语言。对正规表达式的递归定义为：一个正规表达式是按照一组定义规则由一些较简单的正
24、规表达式所组成的。在字母表上的正规表达式可以使用以下规则定义：(1) 和 是上的正规表达式，它们所表示的语言分别为和 。(2)如果 a 是内的一个符号，则 a 是一个正规表达式，所表示的语言为a，即包含符号串 a 的集合。(3)如果 r 和 s 分别是表示语言 L(r)和 L(s)的正规表达式，那么：(r)|(s)是一个表示 L(r)L(s)的正规表达式。(r)(s)是一个表示 L(r)L(s)的正规表达式。(r)*是一个表示(L(r)*的正规表达式。(r)是一个表示 L(r)的正规表达式。通常在正规表达式中，一元运算符“*”具有最高的优先级，连接运算具有次优先级，运算符“|”具有最低优先级，
25、这三个运算都是左结合的。每一个正规表达式只都对应一个有限自动机 M，使 M 所接受的语言就是正规表达式的值。经过以下步骤可以从一个正规表达式 R 构造出相应的有限自动机 M。首先定义初始状态 S 和终止状态 f 并且组成有向图，如图 6-3 所示。*然后反复应用以下规则：*直到所有的边都以中的字母或 标记为止。由此产生了一个带 -转移的非确定有限自动机，然后可以通过上面介绍的方法，把该自动机转换成确定有限状态自动机。3试题解答从图 6-1 可以看出，从 q0状态出发，可以只输入若干个 0，仍然回到 q0状态；也可以只输入若干个 0，经由 q1状态后再回到 q0状态；还可以输入 1 后，到达 q
26、1，然后再输入 0，回到 q0状态。因此，得出其正规式为(0|(0|1)0) T根据正规式之间的代数性质得 0*(0|1)0)*根据图 6-1 的 NFA，下面求与之等价的 DFA。T0-closureq 0=q0，T 0未被标记，为子集中唯一成员；令 T1-closuremove(T 0，0)q 0，q 1，将 T1加入子集；令 T2-closuremove(T 0，1)q 1，将 T2加入子集：-closuremove(T 1，0)q 0，q 1)，即 T1，已经在子集中；-closuremove(T 1，1)q 1)，即 T2，已经在子集中；-closuremove(T 2，0)q 0，
27、即 T0，已经在子集中。因此，构造了三个子集 T0q 0、T 1q 0，q 1、T 2q 1，如图 6-4 所示。*首先，将图 6-4 中状态分为终态和非终态两个子集即(T 0，T 1)，T 2)，再进行子集划分，观察第一个子集T 0，T 1，输入 0 和 1 后成为的状态一样。因此，T 0，T 1)两个状态可以合并成为一个状态，变换即得选项 A 的状态。某一确定性有限自动机(DFA)的状态转换图如图 6-5 所示，令 d=0|1|2|9，则以下字符串中，不能被该DFA 接受的是 (3) ，与该 DFA 等价的正规式是 (4) 。 (其中， 表示空字符)3857 1.2E+5 -123 .57
28、6E10（分数：2.00）A.、B.、 C.、D.、解析：A.(-d|d)d*E(-d|d)d*|(-d|d)*.d*(|E(-d|d)d*) B.(-d|d)dd*(.|)d*|(|E(-d|d)d*)C.(-|d)dd*E(-|d)d*|(-d|d)dd*.d*(|E(-|d)d*)D.(-d|d)dd*E(-d|d)d*|(-d|d|)dd*.d*(|E(-dd*|dd*)解析：分析题目第一问是判断备选答案中有哪些字符串不能被 DFA 接受。现在逐个对其进行判别，这样有利于对 DFA功能的理解和后面的解题。首先看 3857，这个字符串中的元素全部是数字，从 DFA 的初态 0 输入一个数
29、字，进行到状态 1，在状态 1输入数字还是回到状态 1，如果还想往后走，必须要输入字符“”或是字符“E”，但 3857 中不存在这样的字符，所以无法到达终态，因此不能被 DFA 接受。接着看 1.2E+5，这个不用判断就知道不行，因为“+”在此 DFA 中无法识别。再看-123.，此串能从始点顺利到达终点(状态 0状态 4状态 1状态 1状态 1状态 5)，所以此串可以被 DFA 接受。最后看.576E10，第一个字符“”在初始状态无法被识别，所以此串也不能被 DFA 识别。接下来是把 DFA 转化为正规式，我们用排除法来解这个题，首先可以排除的是 B 和 D，很明显(-d|d)dd*所表达的
30、串会比 DFA 所描述的串多一个 d。再看 C 选项(-|d)dd*E(-|d)d*|(-d|d)dd*.d*(|E(-|d)d*)。其中的(-|d)dd*E(-|d)d*表示的路径是不经过状态 5 的路径。后面的(-d|d)dd*.d*(|E(-|d)d*)是指经过状态 5 的路径。这里的(-d|d)dd*，也是多出了一个 d，所以 C 也可以排除，答案就只能是 A 了。1.对于以下编号为、的正规式，正确的说法是 (5) 。(aa*|ab)*b (a|b)*b (a|b)*|aa)*b（分数：1.00）A.正规式、等价B.正规式、等价C.正规式、等价 D.正规式、互不等价解析：分析由正规式产
31、生的字串为 a*b 或(ab)*b；产生的字串为 a*b 或 b*b、产生的字串为 a*b 或 b*b。因此，正规式、等价。2.高级程序设计语言中用于描述程序中的运算步骤、控制结构及数据传输的是 (6) 。（分数：1.00）A.语句 B.语义C.语用D.语法解析：分析程序设计语言的基本成分：包括数据、运算、控制和传输。数据成分是程序操作的对象，具有存储类别、类型、名称、作用域和生存期等属性，使用时要为它分配内存空间。数据包括常量、变量、全局量、局部量。运算成分指明允许使用的运算符号及运算规则。函数：函数的定义，函数的声明，函数的调用。函数的定义包括函数首部和函数体。函数应先声明后引用。函数调用
32、时实参与形参间交换信息的方法有传值调用和引用调用两种。传值调用中，若函数调用时以实参向形参传递相应类型的值，则这种方式下，形参将不能向实参返回信息；除非使用指针作形参，在调用时先对实参进行取址运算，然后将实参地址传递给指针形参，这样才可以实现被调用函数对实际参数的修改。程序设计语言是用于编写计算机程序的语言。它的基础是一组记号和一组规则。根据规则由记号构成的记号串的总体就是语言。在程序设计语言中，这些记号串就是程序。程序设计语言包含三个方面，即语法、语义和语用。语法表示程序的结构或形式，即表示构成程序的各个记号之间的组合规则，但不涉及这些记号的特定含义，也不涉及使用者。语义表示程序的含义，即表
33、示按照各种方法所表示的各个记号的特定含义，但也不涉及使用者，语用表示程序与使用者的关系。在高级程序设计语言中，语句用于描述程序中的运算步骤、控制结构及数据传输。(7) 是面向对象程序设计语言不同于其他语言的主要特点，是否建立了丰富的 (8) 是衡量一个面向对象程序设计语言成熟与否的重要标志之一。（分数：2.00）A.继承性 B.消息传递C.多态性D.静态联编解析：A.函数库B.类库 C.类型库D.方法库解析：分析面向对象程序设计语言的特点主要有继承性、封闭性、多态性。继承性(Inheritance)是指，在某种情况下，一个类会有“子类”。子类比原本的类(称为父类)要更加具体化，子类会继承父类的
34、属性和行为，并且也可包含它们自己的。它的子类会继承这些成员。这意味着程序员只需要将相同的代码写一次。这是其他类型的程序语言所不具备的。封装性(Encapsulation)是指面向对象程序设计隐藏了某一方法的具体执行步骤，取而代之的是通过消息传递机制传送消息给它。多态性 (Polymorphism)指方法在不同的类中调用可以实现的不同结果。因此，两个甚至更多的类可以对同一消息做出不同的反应。是否建立了丰富的类库是衡量一个面向对象程序设计语言成熟与否的重要标志之一。3.“title style=“italic“science/title“，是 XML 中一个元素的定义，其中元素的内容是 (9) 。
35、（分数：1.00）A.titleB.stvleC.italicD.science 解析：分析“title style=“italic“science/title”是一个 XML 元素的定义，其中 title 是元素标记名称：style 是元素标记属性名称；italic 是元素标记属性值；science 是元素内容。4.下面关于编程语言的各种说法中， (10) 是正确的。（分数：1.00）A.由于 C 语言程序是由函数构成的，因此它是一种函数型语言B.Smalltalk、C+、Java、C#都是面向对象语言 C.函数型语言适用于编写处理高速计算的程序，常用于超级计算机的模拟计算D.逻辑型语言是在
36、 Client/Server 系统中用于实现负载分散的程序语言解析：分析函数是一种对应规则(映射)，它使定义域中每个元素和值域中唯一的元素相对应。函数式语言是一类以-演算为基础的语言，其代表为 LISP，主要用于人工智能领域。逻辑型语言是一类以形式逻辑为基础的语言，其代表是建立在关系理论和一阶谓词理论基础上的PROLOG。PROLOG 有很强的推理功能，适用于书写自动定理证明、专家系统和自然语言理解等问题的程序。5.在面向对象的语言中， (11) 。（分数：1.00）A.类的实例化是指对类的实例分配存储空间 B.每个类都必须创建一个实例C.每个类只能创建一个实例D.类的实例化是指对类进行初始化
37、解析：分析本题考查面向对象程序设计语言中类的实例化概念。类是用户定义的类型。与语言定义的基本类型一样，有了类型后，就可以定义(创建)该类型的变量，其含义是系统为变量分配存储空间。对于程序中定义的类，并不要求一定要创建其实例，对实例的数目也没有限制。创建类的实例时，系统需要为该实例分配存储空间。6.给定 C 语言的数据结构struct Tint w；union Tchar c； int I； double d； )U；假设 char 类型变量的存储区大小是 1 字节，int 类型变量的存储区大小是 4 字节， double 类型变量的存储区大小是 8 字节，则在不考虑字对齐方式的情况下，为存储一
38、个 struct T 类型变量所需要的存储区域至少应为 (12) 字节。（分数：1.00）A.4B.8C.12 D.17解析：分析union T 定义 T 为一个共用体，它所占用的存储空间的大小是它所包含的元素中占用存储空间最多的那个，即 d 的存储空间 8 字节，int w 要占用存储空间 4 字节，所以存储一个 struct T 类型变量所需要的存储区域至少应为 4+8=12 字节。在过程式程序设计()、数据抽象程序设计()、面向对象程序设计()、泛型(通用)程序设计()中，C+语言支持 (13) ，C 语言支持 (14) 。（分数：2.00）A.B.C.D. 解析：A. B.C.D.解析
39、：分析现代的 C+语言支持过程式程序设计，数据抽象，面向对象程序设计，泛型程序设计等多种程序设计风格，可以充分满足用户和系统对于开放性、高效率、兼容性和扩展性的各种苛刻需求。C 语言只支持过程式程序设计。7.若程序运行时系统报告除数为 0，这属于 (15) 错误。（分数：1.00）A.语法B.静态语义C.动态语义 D.运算对象不匹配解析：分析在程序执行期间，会有许多意外的事件发生。例如，程序申请内存时没有申请到、对象还未创建就被使用、死循环等，称为运行错误。根据错误的性质将运行错误分为错误与异常两种类型。程序进入了死循环或内存溢出，这类现象称为错误或致命性错误。错误只能在编程阶段解决，运行时程
40、序本身无法解决，只能依靠其他程序干预，否则会一直处于一种不正常的状态。运算时除数为 0，或操作数超出数据范围，打开一个文件时发现文件不存在，网络连接中断等，这类运行错误现象称为异常。对于异常情况，可在源程序中加入异常处理代码，当程序出现异常时，由异常处理代码调整程序运行流程，使程序仍可正常运行直到正常结束。由于异常是可以检测和处理的，所以产生了相应的异常处理机制。而错误处理一般由系统承担。对于一个应用软件，异常处理机制是不可缺少的。该题中出现的是语义错误，但不是编译的时候出现的，是运行的时候出现的，所以是动态语义错误。在下列程序中：Program test(input，output)；var
41、i，j：integer；procedure calc(p1，p2：integer)；begin p2：=p2*p2 p1：=p1-p2；p2：=p2-p1；endcaicbeginmainI：=2；j：=3；calc(i，j)；write(j)；endmain当参数传递采用引用方式(Call by Reference)时，所得结果 j= (16) ；当参数传递采用换名方式(Call by Name)时，所得结果 j= (17) ：当参数传递采用赋值方式(Call by Value)时，所得结果 j= (18) 。递归是程序设计中很重要的一种控制结构，通常实现递归时，采用的数据结构是 (19)
42、。对那些既可以用递归方式，也可以用循环方式求解的问题，就执行效率而言 (20) 。（分数：5.00）A.0B.3C.5D.6E.10F.16 G.20H.28解析：A.0B.3C.5D.6E.10F.16 G.20H.28解析：A.0B.3 C.5D.6E.10F.16G.20H.28解析：A.数组B.栈 C.队列D.循环链表解析：A.难以断定B.两者相同C.循环优于递归 D.递归优于循环解析：分析一个过程的过程体若包含对其自身的调用，则称此过程是直接递归的。若一个过程的过程体调用某过程，而该过程又调用原过程或经一系列调用后又回到对原过程的调用，则称此原过程是间接递归的。通常实现递归时采用的数
43、据结构是栈，这是因为栈有先进后出的特性，可以保存调用时的“现场”，并在调用结束时恢复“现场”。栈是实现递归的简单途径。对于既可用递归方式求解，也可用循环方式求解的问题，就执行效率和资源而言，显然是循环优于递归，因为递归的开销大。当用户在调用点调用一个过程时，会通过参数传送信息，一个过程的形式参数用来向过程传送信息的标志符，实际参数用来在调用点向被调用过程传送信息。形式参数和实际参数之间的关系通常按位置来标定，不同程序语言所规定的参数信息传送方式不同。当采用引用方式或换名方式时，在过程中对形式参数的调用本质上是对实际参数单元的引用。先是给形式参数赋初值，而后，在过程中对该形式参数的赋值最终引起调
44、用程序中实际参数值的改变。在本题中形式参数为 p1 和 p2。实际参数初值为 i=2 和 j=3，通过引用方式调用这两个参数，将执行以下计算过程：pl2，p23，p2:p2*p29，p1:p1-p2=2-9=-7，p2:=p2-p19-(-7)16所得结果为 j=16。参数传送采用赋值方式时，从调用点向被调用过程传送的是实际参数的值。这一值成为过程中相应位置上形式参数的初值，此后该形式参数在过程中实际是局部变量，其结果无须返回给实际参数。在这种情况下，形式参数实际上是过程中的局部量，其值的改变不会导致调用点所传送的实际参数的值发生改变，也就是说数据的传送是单向的。本题中实际参数 j 仅起向形式
45、参数 p2 赋初值的作用。过程中关于 p2 的运算对 j 不再起作用，因而过程调用结束后 j 的值仍为 3。文法 G=(VT，V N，P，S)的类型由 G 中的 (21) 决定。若 GO=(a，b，S，X， Y，P，S)，P 中的产生式及其序号如下：1：SXaaY2：XYY|b3：YXbX|a则 GO 为 (22) 型文法，对应于 (23) ，由 GO 推导出句子 aaaa 和 baabbb 时，所用产生式序号组成的序列分别为 (24) 和 (25) 。（分数：5.00）A.VTB.VNC.P D.S解析：A.0B.1C.2 D.3解析：A.图灵机B.下推自动机 C.有限状态自动机D.其他自动
46、机解析：A.13133B.12312C.12322D.12333 解析：A.13133B.12312C.12322 D.12333解析：分析文法 G 是一个四元组GV T,VN，S，P其中 VT是一个非空有限的符号集合，它的每个元素成为终结符号。V N也是一个非空有限的符号集合，它的每个元素称为非终结符号，并且有 VTV N。SV N，称为文法 G 的开始符号。P 是一个非空有限集合，它的元素称为产生式。所谓产生式，其形式为：。 为产生式的左部， 称为产生式的右部，符号“”表示“定义为”，并且 、(V TV N)*，即 、 是由终结符和非终结符组成的符号串。开始符 S 必须至少在某一产生式的左
47、部出现一次。另外可以对形如 ， 的产生式缩写为 |，以方便书写。1956 年，著名的语言学家 Noam Chomsky 根据对产生式所施加的限制的不同，把文法分成了四类，并定义了相应的四类形式语言。0 型文法设 G=(VN，V T，P，S)，如果它的每个产生式 是这样一种结构：(V NV T)*且至少含有一个非终结符，而 (V NV T)*，则 G 是一个 0 型文法。0 型文法也称短语文法。一个非常重要的理论结果是：0型文法的能力相当于图灵机(Turing)。或者说，任何 0 型文法语言都是递归可枚举的，反之，递归可枚举集必定是一个 0 型语言。0 型文法是这几类文法中限制最少的一个。1 型
48、文法1 型文法也叫上下文有关文法，此文法对应于线性有界自动机。它是在 0 型文法的基础上，每一个 都有|。这里的|表示 的长度。注意：虽然要求|，但有一特例： 地满足 1 型文法。如有 A-Ba 则|=2，|=1 符合 1 型文法要求。反之，如 aA-a，则不符合 1 型文法。2 型文法2 型文法也叫上下文无关文法，它对应于下推自动机。2 型文法是在 1 型文法的基础上，再满足：每一个 有 是非终结符。如 A-Ba，符合 2 型文法要求。如 Ab-Bab 虽然符合 1 型文法要求，但不符合 2 型文法要求，因为其 =Ab，而 Ab 不是一个非终结符。3 型文法3 型文法也叫正则文法，它对应于有限状态自动机。它是在 2 型文法的基础上满足： A|B(右线性)或 A|Ba(
