软件设计师——程序设计语言练习_算术表达式a+(b-c)*d的后缀式是

一、单选题

1.以下关于下图所示有限自动机的叙述中，不正确的是（ ）

A、该自动机识别的字符串中a不能连续出现

B、该自动机识别的字符串中b不能连续出现

C、该自动机识别的非空字符串必须以a结尾

D、该自动机识别的字符串可以为空串

正确答案：A

【解析】1既是初态也是终态，从图中可以看出a能连续出现，保持在状态1。

2.下图所示有限自动机的特点是（   ）

 

A、识别的0、1串是以0开头且以1结尾

B、识别的0、1串中1的数目为偶数

C、识别的0、1串中0后面必须是1

D、识别的0、1串中1不能连续出现

正确答案：D

【解析】对于题中自动机的状态图，先忽略状态q0的自环(识别若干个0)，从初态q0到终态q1，该自动机可识别的字符串为1、101、10101、…，显然，该自动机识别的0、1串中1不能连续出现。

从初始态q0输入0仍然到q0或者输入1到达终态q1，从q1还可以输入0重新到达初始态q0，所以这个有限自动机识别的0、1串不一定是以0开头的，1的数目的奇偶性也没办法确定，0后面也可以是0，所以选项A、B、C都是错误的。从q0输入1到达终态q1后，或者串结束，或者输入0再到q0，所以这个串中的1不会连续出现，选项D是正确的。

3.下图所示的有限自动机中，0是初始状态，3是终止状态，该自动机可以识别（   ）

A、abab

B、aaaa

C、bbbb

D、abba

正确答案：B

4.下图所示为两个有限自动机M1和M2 (A是初态、C是终态)，（ ）

 

A、M1和M2都是确定的有限自动机

B、M1和M2都是不确定的有限自动机

C、M1是确定的有限自动机，M2是不确定的有限自动机

D、M1是不确定的有限自动机，M2是确定的有限自动机

正确答案：D

【解析】在本题中给出的图M1中，我们可以看到当在状态A输入0时，它可以转移到它自己，也可以转移到状态B，所以M1是非确定的。而M2中不存在这样的情况，因此是确定的有限自动机。

（1）不确定的有限自动机（NFA）：对每一个可能的输入可以有多个状态转移，从接受到输入，从多个状态转移中不确定的地选择一个。

（2）确定的有限自动机（DFA）：对每一个可能地输入只有一个状态的转移。

二者最大的区别是它们的转移函数不同。

5.下图所示为一个有限自动机（其中，A是初态、C是终态)，该自动机识别的语言可用正规式    表示

A、(0|1)*01

B、1*0*10*1

C、1*(0)*01

D、1*(0|10)*1*

正确答案：A

【解析】

（1）被有限自动机所识别是指从初态开始到终态结束，所输入的字符串能够按顺序地执行下去，若到某个状态不能往下走得到下一个字符，则认为不能识别。

（2）在本题中，选项A能被识别。从初态A出发，不管经过多少个1和0之后，只能是处在A、B、C三种状态中的一种，所以在(0|1)*后，只能是处在A、B、C三种状态中的一种，不管是在那个状态，输入0后，都会处在状态B，然后输入1，都会转换到状态C，因此选项A能被该有限自动机所识别。同样的道理，我们可以知道其它选项的正规式不能被识别。（*代表无限多次的意思）。

（3）题中的自动机，从A出发到达C结束的所有路径必然包含BC这条弧（标记为1），同时到达B的弧上都标记了0，所以其识别的字符串必须以01结尾。

补充正则式：

正规式：由正规文法转换而来，通常正规文法等价于正规式。

*表示可以出现0次或任意多次

x|y表示可能x、也可能是y

ab：只有一种情况，就是 ab
a|b：有两种情况，a或者b
a*：有无数种情况

6.下图所示为一个有限自动机（其中，A是初态、C是终态），该自动机所识别的字符串的特点是（    ）。

A、必须以11结尾的0、1串

B、必须以00结尾的0、1串

C、必须以01结尾的0、1串

D、必须以10结尾的0、1串

正确答案：C

此题和上题一样，问法不一样。

【解析】

（1）被有限自动机所识别是指从初态开始到终态结束，所输入的字符串能够按顺序地执行下去，若到某个状态不能往下走得到下一个字符，则认为不能识别。

（2）在本题中，选项A能被识别。从初态A出发，不管经过多少个1和0之后，只能是处在A、B、C三种状态中的一种，所以在(0|1)*后，只能是处在A、B、C三种状态中的一种，不管是在那个状态，输入0后，都会处在状态B，然后输入1，都会转换到状态C，因此选项A能被该有限自动机所识别。同样的道理，我们可以知道其它选项的正规式不能被识别。（*代表无限多次的意思）。

（3）题中的自动机，从A出发到达C结束的所有路径必然包含BC这条弧（标记为1），同时到达B的弧上都标记了0，所以其识别的字符串必须以01结尾。

7.某非确定的有限自动机(NFA)的状态转换图如下图所示（q0既是初态也是终态）。以下关于该NFA的叙述中，正确的是（     ）

A、其可识别的0、1序列的长度为偶数

B、其可识别的0、1序列中0与1的个数相同

C、其可识别的非空0、1序列中开头和结尾字符都是0

D、其可识别的非空0、1序列中结尾字符是1

正确答案：D

【解析】

8.某确定的有限自动机 (DFA) 的状态转换图如下图所示 (A 是初态，D、E 是终态)，则该 DFA 能识别（ ）

A、00110

B、10101

C、11100

D、11001

正确答案：C

【解析】选项中，只有C选项的字符串能被DFA解析。解析路径为：ACEEBDD。

9.某确定的有限自动机（DFA）的状态转换图如下图所示（0是初态，4是终态），则该DFA能识别（   ）

A、aaab

B、abab

C、bbba

D、abba

正确答案：A

【解析】B项从0到1然后走不了了，C项在3状态结束，不对；D项也只到1状态。

10.算术表达式a+(b-c)*d的后缀式是（）

A、b c - d * a +

B、a b c - d * +

C、a b + c - d *

D、a b c d - * +

正确答案：B

【解析】后缀式就是后序遍历，左→右→根，根据算术表达式画出这棵二叉树。

 后缀式是abc-d*+

11.与逆波兰式ab-cd+*对应的中缀表达式是（ ）

A、a-b+c*d

B、(a-b)*c+d

C、(a-b)*(c+d)

D、a-b*c+d

正确答案：C

【解析】

逆波兰式是后缀式，就是后序遍历，左→右→根，根据逆波兰式画出这棵二叉树，中缀表达式就是中序遍历，左→根→右。

 中缀表达式是a-b*c+d

12.算术表达式x-(y+c)*8的后缀式是（）

A、xyc8-+*

B、xy-c+8*

C、xyc8*+-

D、xyc+8*-

正确答案：D

【解析】后缀式就是后序遍历，左→右→根，根据算术表达式画出这棵二叉树。

 后缀式是xyc+8*-

13.算术表达式(a-b)*c+d的逆波兰式是（  ）

A、abcd -*+

B、ab —cd* +

C、ab-c*d+

D、abc-d*+

正确答案：C

【解析】逆波兰式是后缀式，就是后序遍历，左→右→根，根据算术表达式画出这棵二叉树。

 逆波兰式是ab-c*d+

14.与算术表达式“（a+（b-c））*d“ 对应的树是（ ）

A、

B、

C、 

D、 

正确答案：B 

15.若将某有序树 T 转换为二叉树 T1，则 T 中结点的后（根）序序列就是 T1 中结点的（）遍历序列。例如，下图（a）所示的有序树转化为二叉树后如图（b）所示。

A.先序        B.中序        C.后序        D.层序

所属知识点：数据结构与算法基础>数与二叉树的特性

答案解析： 

本题考查数据结构中二叉树基本知识。
对树可进行先根遍历、后根遍历和层序遍历。例如，对题中（a）所示树进行先根遍历的序列为1、2、3、5、6、4、7，后根遍历的序列为2、5、6、3、7、4、1，层序遍历序列为1、2、3、4、5、6、7。
对二叉树可进行先序遍历、中序遍历、后序遍历和层序遍历。对题中（b）所示二叉树进行遍历，先序序列为1、2、3、5、6、4、7，中序序列为2、5、6、3、7、4、1，后序序列为6、5、7、4、3、2、1，层序序列为1、2、3、5、4、6、7。
显然，将树转换为二叉树后，树的先根序列等于对应二叉树的先序序列，树的后根序列等于对应二叉树的中序序列。 

16.与逆波兰式ab+ -c*d-对应的中缀表达式是（）。
A.a-b-c*d        B.-(a+b)*c-d        C.-a+b*c-d        D.(a+b)*(-c-d)

所属知识点：程序设计语言>后缀表达式

答案解析：

本题考查表达式的表示方式。
　　表达式的逆波兰表示也就是后缀表示，在表达式的这种表示方法中，将运算符号写在运算对象的后面，并指明其前面的操作数或中间结果所要执行的运算。对后缀表达式从左到右求值，则每当扫描到一个运算符号时，其操作数是最近刚得到的。因此“ab+-c*d-”表示：先将a与b相加，然后作一元“-”运算，结果再与c相乘，乘运算的结果再与d相减，因此中缀表达式的形式为“-（a+b）*c-d”。

逆波兰式是后缀式，就是后序遍历，左→右→根；中缀表达式是中序遍历，也是算术表达式，左→根→右，根据中缀表达式画出ABCD四个选项的二叉树。

A.

B. 

C. 

D.  

17.以编译方式翻译C/C++源程序的过程中，类型检查在( )阶段处理。

A.词法分析 B.语义分析 C.语法分析 D.目标代码生成

所属知识点：程序设计语言>编译器工作过程

答案解析：

词法分析阶段处理的错误：非法字符、单词拼写错误等。

语法分析阶段处理的错误：标点符号错误、表达式中缺少操作数、括号不匹配等有关语言结构上的错误。

静态语义分析阶段（即语义分析阶段）处理的错误：运算符与运算对象类型不合法等错误。本题选择语义错误。

目标代码生成（执行阶段）处理的错误：动态语义错误，包括陷入死循环、变量取零时做除数、引用数组元素下标越界等错误等。

18.某确定性有限自动机（DFA）的状态转换图如下图所示，令 d=0|1|2|...|9，则以下字符串中，能被该DFA 接受的是（）。

A.3857

B.1.2E+5

C.-123.67

D.0.576E10

所属知识点：程序设计语言>编译与解释答案解析：本题程序语言翻译基础知识。
　　翻译高级语言源程序的第一步工作是进行词法分析，即将源程序中的单词（记号）识别出来，该过程可用有限自动机描述。
　　自动机M识别一个字符串的过程是从开始状态出发，根据字符串中的字符依次进行状态转移，若能到达终态且字符串结束，则该字符串可被自动机M识别。考查题目中的选项，3857的识别过程是状态0→状态1→状态1→状态1，状态1不是终态；字符串1.2E+5中的“+”不能识别。字符串0.576E10的识别过程是状态0一状态1→状态5→状态6→状态6，在状态6下不能识别E。字符串_123.67的识别过程是状态0→状态4→状态1→状态1→状态1→状态5→状态6→状态6，因此该字符串可被题中的自动机识别。

19.下面C程序段中count++语句执行的次数为（ ）。

for(int i=1；i<=11；i*=2)
    for(intj=1；j<=i；j++)
        count++；

A.15        B.16        C.31        D.32

所属知识点：程序设计语言>其它

答案解析：本题中给出的是一个双重循环结构，循环体就是count++。第一层循环的循环次数为4次，分别为i=1，2，4，8的情况。而当i=1时，第二层循环循环1次；当i=2时，第二层循环2次；当i=4时，第二层循环4次；当i=8时，第二层循环8次。那么可知循环体一共执行了1+2+4+8=15次。

20.下图是一有限自动机的状态转换图，该自动机所识别语言的特点是（），等价的正规式为（）。

（1）A.由符号a.b构成且包含偶数个a的串

B.由符号a.b构成且开头和结尾符号都为a的串

C.由符号a.b构成的任意串

D.由符号a.b构成且b的前后必须为a的串

（2）A.(a∣b)*(aa)*        B.a(a∣b)*a        C.(a∣b)*        D.a(ba)*a

所属知识点：无

答案解析：本题考查有限自动机的基本运算。
　　在有限自动机的状态转换图中，每一个结点代表一个状态，其中双圈是终态结点。
　　对于字符串ω，若存在一条从初态结点到某一终止状态结点的路径，且这条路径上所有弧的标记符连接成的字符串等于ω，则称ω可由DFA M识别（接收或读出）。若一个DFA M的初态结点同时又是终态结点，则空字ε可由该DFA识别（或接收）。DFA M所能识别的语言L（M）={ω|ω）是从M的初态到终态的路径上的弧上标记所形成的串}。
　　分析题中给出的自动机：从初态0出发，识别一个符号a后进入状态1，在状态1可识别出任意个a或（和）任意个b，再识别出一个a而到达终态2。显然，该自动机识别的语言特点是“由a开头由a结尾，期间的a、b任意排列”。用正规式表示为“a（a|b）*a”。

21.某有限自动机的状态转换图如下图所示，与该自动机等价的正规式是（ ）。

A. (0|1)*        B.(0|10)*        C.0*(10)*        D.0*(1|0)*

所属知识点：程序设计语言>有限自动机

答案解析：本题考查程序语言基础知识。
从题中的自动机可分析出，初态q0同时是终态，从q0到q0的弧（标记0）表明该 自动机识别零个或多个0构成的串，路径q0→q1→q0的循环表明“10”的多次重复，因此该自动机识别的字符串是“0|10”的无穷多次，表示为(0|10)*。

21.计算机执行程序时，内存分为静态数据区、代码区、栈区和堆区。其中（ ）一般在进行函数调用和返回时由系统进行控制和管理，（ ）由用户在程序中根据需要申请和释放。

（1）A.静态数据区        B.代码区        C.栈区        D.堆区

（2）A.静态数据区        B.代码区        C.栈区        D.堆区

所属知识点：程序设计语言>其它

答案解析：解析1本题考查程序语言基础知识。
程序在不同的系统中运行时，虽然对其代码和数据所占用的内存空间会有不同的布局和安排，但是一般都包括正文段（包含代码和只读数据）、数据区、堆和栈等。例如，在Linux系统中进程的内存布局示意图如下图所示。

栈是局部变量以及每次函数调用时所需保存的信息的存储区域，其空间的分配和释放由操作系统进行管理。每次函数调用时，其返回地址以及调用者的环境信息(例如某些寄存器)都存放在栈中。然后，在栈中为新被调用的函数的自动和临时变量分配存储空间。栈空间向低地址方向增长。
堆是一块动态存储区域，由程序员在程序中进行分配和释放，若程序语句没有释放， 则程序结束时由操作系统回收。堆空间地址的增长方向是从低地址向高地址。在C程序中，通过调用标准库函数malloc/calloc/realloc等向系统动态地申请堆存储空间来存储相应规模的数据，之后用free函数释放所申请到的存储空间。

22.将编译器的工作过程划分为词法分析、语义分析、中间代码生成、代码优化和目标代码生成时，语法分析阶段的输入是（ ）。若程序中的括号不配对，则会在（ ）阶段检查出该错误。问题（1）A.记号流        B.字符流        C.源程序        D.分析树

（2）A.词法分析        B.语法分析        C.语义分析        D.目标代码生成

所属知识点：程序设计语言>编译器工作过程

答案解析：A选项记号流，词法分析的输出是记号流，也就是语法分析的输入，第一空选择A选项。
B选项字符流，在Java中，根据处理的数据单位不同，分为字节流和字符流。字符流是由字符组成的，例如 File Reader、File Writer、Buffered Reader、Buffered Writer、Input Stream Reader、Output Stream Writer 等。与本题无关。
C选项源程序，词法分析的任务是把源程序的字符串转换成单词符号序列。
D选项分析树，如果没有语法错误，语法分析后就能正确的构造出其语法树。
括号不匹配是典型的语法错误，会在语法分析阶段检测出来。