1、 已知文法GS:SA0|Bl，AS1|1，BS0|0；该文法属于乔姆斯基定义的_(12)_文法，它不能产生串_(13)_。(12) A. 0 型B. 1 型C. 2 型D. 3 型(13) A. 0011 B. 1010 C. 1001 D. 0101语言L=ambn|m0，n1的正规表达式是_(14)_。(14) A. a*bb* B. aa*bb* C. aa*b* D. a*b*一个文法G=(N，T，P，S)，其中N 是非终结符号的集合，T 是终结符号的集合，P 是产生式集合，S 是开始符号，令集合V=NT，那么G 所描述的语言是_(15)_的集合。(15) A由S 推导出的所有符号串B
2、由S 推导出的所有终结符号串CV 中所有符号组成的符号串DV 的闭包中的所有符号串 下图为一确定有限自动机的状态转换图，与该自动机等价的正规表达式是_（12）_，图中的_（13）_是可以合并的状态。（12）A.(a|b)*bb(a*b*)* B.(a|b)*bba*|b*C.(a*b*)bb(a|b)* D.(a*|b*)*bb(a*|b*)（13）A.0 和1 B.2 和3 C.1 和2 D.0 和3正确答案：A解析：在状态转换图中，每一个结点代表一个状态，其中双圈是终结状态。该题实际上是一个简化确定有限自动机(DFA)的过程，一个确定有限自动机可以通过消除多余状态和合并等价状态而转换成一个
3、最小的与之等价的有限自动机。首先介绍 2 个概念：最小状态 DFA 和等价状态。最小状态 DFA 必须满足以下 2 个条件。(1)没有多余状态(死状态) ：多余状态从该自动机的开始状态出发，任何输入串都不能到达的那个状态。(2)没有 2 个状态是互相等价(不可区别)。2 个状态 s 和 t 如果同时满足下列 2 个条件，就称 s 和 t 是等价的。(1)一致性：同是终态或同是非终态。(2)蔓延性：从 s 出发读人某个 a 和从 t 出发读入某个 a 到达的状态等价。本题的简化过程如下：首先，将图中状态分为终态和非终态 2 个子集即(0,1,2,3) ，再进行子集划分，观察第一个子集0,1 ，输
4、入 b 后，状态 0 转换为状态 1，而状态 1 转换为状态 2。因此1和2中的状态是可区别的。由于状态 2,3 输入字符 a 得到相同的结果 3，输入字符 b 得到相同结果 2，所以子集 2,3是不可区别的。从而得到新的划分：(0，1，2，3)，因此，(2)空的正确答案为 B。重复子集划分步骤，发现新的状态无法再次划分。所以，本题中 2，3 状态可以消除 3 状态，得到新的状态转换图如图 3-2 所示。由图 3-2 可知终态 2 可以转换为正规表达式 (a|b)*，同时必须输入连续 2 个 b 字符，才能完成 0 状态到终态 2 的转换，所以结果正规表达式必为形如“.bb(a|b)*”的字符
5、串。又因为 0 和 1 之间由 b 和 a 轮回输入，可以表示为(ba)*，同时，状态 0 上输入 a 又回到自身，可以表示为 a*。因此，(1)空的正确答案应该为(a*b*)*bb(a|b)* ，根据正规式之间的代数性质，(a*b*)*bb(a|b)*与(a|b)*bb(a*b*)*等价。 编译的优化工作对于下面程序段构造的控制流程图有_（15）_个基本块。A:=0j:=100i:=1loop1: B:=j+1C:=B+IA:=A+Cif i=100 goto loop2i:=i+1 Goto loop1loop2: write Ahalt(15)A.1 B.2 C.3 D. 4正确答案：D
6、解析：基本块划分的3个步骤：(1)满足下列3个条件之一的任一语句可充当入口。 程序的第一个语句； 能由条件转移语句或无条件转移语句转移到的语句； 紧跟在条件转移语句后面的语句。(2)根据(1)求出的每一入口语句，构造其所属的基本块。 由该人口语句到另一入口语句(不包括该入口语句)之间的语句序列； 由该人口语句到一转移语句(包括该转移语句)之间的语句序列； 由该人口语句到一停转移语句(包括该转移语句)之间的语句序列。(3)凡是未被纳入某一基本块中的语句，都是程序中控制流程无法到达的语句，从而也是不会被执行到的语句，可以从程序中删除。在本题中，根据程序求解。(1)确定入口。A：=100 入口 j：
7、 =100i：=1loop1： B：=j+1 入口C：=B+IA：=A+Cif i=100 goto loop2i：=i+1 入口goto 100p1100p2： write A 入 口halt 停语句(2)确定基本块。基本块 1 A：=00 入口j：=100i：=1基本块 2 loop1： B：=j+1 入口C： =B+IA：=A+Cif i=100 goto 100p2基本块 3 i：=i+1 入口goto loop1基本块 4 loop2： write A 入口halt 停语句(3)确定可删除语句。没有无法到达的语句。 文法GS:SxSx|y 所描述的语言是_（16）_ (n0)。(16
8、)A.(xyx)n B.xyxn C.xynx D.xnyxn正确答案：D解析：正规文法到正规式的转换规则如下：在本题中，推导过程如下：S-xSxxyxx 2Sx2-x 2yx2-x3Sx3-x 3yx3-.-x nSxn-x nyxn得出生成式的规律是：两个x串中间只有一个y，同时两边的 x串等长。某一非确定性有限自动机(NFA)的状态转换图如下图所示，与该NFA 等价的正规式是_(28)_，与该NFA 等价的DFA 是_(29)_。A(28) A0*|(0|1)0 B(0|10)* C0*(011)0)* D0*(10)*正确答案：B解析：根据分析题目中给出的状态转换图可知，该NFA可识别
9、空串以及任意数目0组成的串，但若出现1，则其后至少要有1 个0才能到达终态，因此，该自动机识别的串等价于正规式(0|10)*。某一确定性有限自动机（DFA）的状态转换图如下图所示，令d=0|1|2|9, 则以下字符串中，不能被该DFA 接受的是_(28)_，与该DFA 等价的正规式是_(29)_。(其中，表示空字符) 3857 1.2E+5 -123 . .576E10（28）A B C D（29）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
10、*(|E(-|d)d*)D(-d|d)dd*E(-d|d)d*|(-d|d|)dd*.d*(|E(-dd*|dd*)正确答案：B解析：有限自动机也称为有穷状态自动机，是一种数学机器模型，基本形式有非确定有限自动机(NFA)和确定的有限自动机(DFA)，并且每一个NFA都有与其等价的DPA。有穷状态自动机的物理模型如下图所示。*一个DFA可以用状态转换图直观的方式。状态转换图是一种有向图。DFA中的每个状态对应转换图中的一个节点，从外部引入弧的节点表示开始节点，双圈节点表示终态；DFA中的每个状态转换对应图中的一条有向弧，若转换关系为/(A,a)=Q，则该有向弧从节点A 出发，进入节点Q，字符a
11、是弧上的标记。有穷状态自动机识别字符串的过程为：初始时，机器处于起始状态(题图中节点。表示初始状态)。读取一个输入符号，并进行相应的状态转移，直到输入串结束或找不到相应的状态转移时为止。根据题目终给定的自动机，识别3857、1.2E+5、-123.、.576E10的过程分别如下。*分析题中给定的有穷状态自动机，可知该自动机识别以下形式的数值：带小数部分的十进制表示形式和以尾数、指数表示的数值形式。其中，从初态0到达终态5所识别的是带小数点的以十进制数值表示形式的字符串，小数点后可以没有数字，也可以有若干个数字，而小数点之前的整数部分可以不带符号，也可以带负号，其正规式为“(-d|d)d*.d*
12、。当数值的表示含有指数部分时，指数部分是不带符号(表示正数)或带负号的整数形式，因此该部分的正规式为“E(-d|d)d*”。对于以下编号为、的正规式，正确的说法是_(30)_。 (aa*|ab) *b (a|b) *b (a|b) *|aa) *b（30）A.正规式、等价B.正规式、等价C.正规式、等价D.正规式、互不等价正确答案：C解析：由于正规式产生的字符串为a*b或ab*b，产生的字符串为 a*b或b*b，产生的字符串为a*b或b*b，故等价。 开发专家系统时，通过描述事实和规则由模式匹配得出结论，这种情况下适用的开发语言是（19）。（19）A面向对象语言B函数式语言C过程式语言D逻辑式
13、语言正确答案：D本题考查程序语言基本知识。函数式程序设计的数据结构本质上是表，而函数又可以作为值出现在表中，因此函数式程序的控制结构取决于函数，以及函数的定义和调用。函数式语言主要用于符号数据处理，如微分和积分演算、数理逻辑、游戏推演以及人工智能等其他领域。用逻辑式程序设计语言编写程序不需要描述具体的解题过程，只需要给出一些必要的事实和规则。这些规则是解决问题的方法的规范说明，根据这些事实和规则，计算机利用谓词逻辑，通过演绎推理得到求解问题的执行序列。这种语言主要用在人工智能领域，也应用在自然语言处理、数据库查询、算法描述等方面，尤其适合于作为专家系统的开发工具 高级程序设计语言中用于描述程序
14、中的运算步骤、控制结构及数据传输的是（20） 。（20）A语句B语义C语用D语法正确答案：A解析：本题考查程序语言的基本成分。程序设计语言的语法是语言的外观。给出语言的语法意味着给出语句、声明和其他语言结构的书写规则。语义则表示不同的语法结构的含义。在程序语言的手册中，语言的描述都是围绕着语法结构展开的。通常，先给出各种语句结构的语法，然后给出对应该结构的语义以描述内在含义。语用是关于程序与使用者之间的关系。在高级程序设计语言中，语句用于描述程序中的运算步骤、控制结构及数据传输。 对于下面的文法GS， （44） 是其句子（从S 出发开始推导）。GS:SM|(S,M) MP|MP Pa|b|c|
15、x|x|z（44）A(a,F) B(fac,bb),g) C(abc) D(c,(da)选B.S=(S,M)=(S,M),M)=(M,M),M)=(MP,M),M)=(MPP,M),M)=(PPP,M),M)=(fPP,M),M)=(faP,M),M）=(fac,M),M)=(fac,MP),M)=(fac,PP),M)=(fac,bb),M)=(fac,bb),g). 与逆波兰式ab+ -c*d-对应的中缀表达式是（45） 。（45）Aa-b-c*d B-(a+b)*c-d C-a+b*c-d D(a+b)*(-c-d) 下面的C 程序代码段在运行中会出现（46） 错误。int i=0;wh
16、ile(i10);i=i+l;（46）A语法B类型不匹配C变量定义D动态语义 “通过指明一系列可执行的运算及运算的次序来描述计算过程”是（19）语言的特点。（19）A逻辑式B函数式C交互式D命令式（或过程式）正确答案：D 解析：过程式(或命令式) 语言是基于动作的语言，在这种语言中，计算被看成是动作的序列。因此，通过指明一列可执行的运算及运算的次序来描述计算过程是命令式语言的特点。逻辑式语言是一类以形式逻辑为基础的语言。函数式语言以-演算为基础。 “X（AB） (C - D/E)”的后缀式表示为（20）。（20）AXAB+CDE/-= BXAB-C-DE/=CXAB+CDE-/= DXAB-C
17、D-E/= 下图是一有限自动机的状态转换图，该自动机所识别语言的特点是（45），等价的正规式为（46）。（45）A由符号a、b 构成且包含偶数个a 的串B由符号a、b 构成且开头和结尾符号都为a 的串C由符号a、b 构成的任意串D由符号a、b 构成且b 的前后必须为a 的串（46）A(ab)*(aa)* Ba(ab)*a C(ab)* Da(ba)*a正确答案：B解析：本题考查有限自动机的基本运算。在有限自动机的状态转换图中，每一个结点代表一个状态，其中双圈是终态结点。对于字符串，若存在一条从初态结点到某一终止状态结点的路径，且这条路径上所有弧的标记符连接成的字符串等于，则称可由DFA M识别
18、( 接收或读出) 。若一个 DFA M的初态结点同时又是终态结点，则空字 可由该DFA识别( 或接收 )。 DFA M所能识别的语言 L(M)=|是从M的初态到终态的路径上的弧上标记所形成的串。分析题中给出的自动机：从初态 0出发，识别一个符号a 后进入状态1，在状态1可识别出任意个a或(和) 任意个b ，再识别出一个 a而到达终态2。显然，该自动机识别的语言特点是“由a开头由a结尾，期间的a、b 任意排列”。用正规式表示为“a(a|b)*a”。 表达式“(a+b)* (c-d)”的后缀表示为（48）。（48）A. ab+cd-* B. abcd+-* C. ab+*cd- D. abcd*+
19、- 函数t()、f()的定义如下所示，若调用函数t 时传递给x 的值为3，并且调用函数f()时，第一个参数采用传值（call by value）方式，第二个参数采用传引用（call by reference）方式，则函数t 的返回值为（49） 。（49）A. 35 B. 24 C. 22 D. 11 程序设计语言中（50） 。（50）A. while 循环语句的执行效率比do-while 循环语句的执行效率高B. while 循环语句的循环体执行次数比循环条件的判断次数多1，而do-while 语句的循环体执行次数比循环条件的判断次数少1C. while 语句的循环体执行次数比循环条件的判断次
20、数少1，而do-while 语句的循环体执行次数比循环条件的判断次数多1D. while 语句的循环体执行次数比循环条件的判断次数少1，而do-while 语句的循环体执行次数等于循环条件的判断次数 给定C 语言的数据结构struct T int w;union T char c; int i; double d; U;假设char 类型变量的存储区大小是1 字节，int 类型变量的存储区大小是4 字节，double 类型变量的存储区大小是8 字节，则在不考虑字对齐方式的情况下，为存储一个struct T 类型变量所需要的存储区域至少应为（15） 字节。（15）A. 4 B. 8 C. 12
21、D. 17正确答案：C解析：在不考虑字对齐规则的情况下，C语言中一个结构体变量的存储区大小就是其所有成员所需存储区大小之和，一个联合体变量的存储区大小就是其各成员所需存储区大小中的最大者。因此题目中给定的联合体union T变量需要的存储区大小就是存储一个 double类型变量的大小(即8 字节)，struct T类型变量的存储区最小应为int 类型成员w存储区大小(4 字节)与union T类型成员U的存储区大小之和，即 12字节。 在过程式程序设计（）、数据抽象程序设计（）、面向对象程序设计（）、泛型（通用）程序设计（）中，C+ 语言支持（16） ，C 语言支持（17） 。（16）A. B
22、. C. D. （17）A. B. C. D. C 语言是一种（18） 语言。（18）A. 编译型B. 解释型C. 编译、解释混合型D. 脚本正确答案：A编译型语言指用该语言编写的程序在执行前，需要由相应的编译器将源程序翻译为目标代码程序，然后在目标机器上运行目标代码程序。解释型语言指用该语言编写的程序无需编译为目标代码，即可执行。对于解释型语言，都有相应的解释器，负责检查源程序的语法，进行语义分析，通常采用边翻译边执行的方式。对于C语言而言，一个C源程序必须由编译器将其翻译为目标代码，才能在目标机上运行，因此，它是编译型语言。 若程序运行时系统报告除数为0，这属于（20）错误。（20）A.
23、语法B. 语用C. 语义D. 语境 集合L =amb m m 0 （21）。（21）A.可用正规式“a *b *”表示B.不能用正规式表示，但可用非确定的有限自动机识别C.可用正规式“a mb m ”表示D.不能用正规式表示，但可用上下文无关文法表示 表达式“X = A + B (C D )/ E”的后缀表示形式可以为（22） （运算符优先级相同时，遵循左结合的原则）。（22）A. XAB + CDE/= B. XA+BC DE/= C. XABCDE/+= D. XABCDE+/= 在软件开发中， （29） 不能用来描述项目开发的进度安排。在其他三种图中，可用（30） 动态地反映项目开发进展情况。（29）A. 甘特图B. PERT 图C. PERT/CPM 图D. 鱼骨图
