第 2 章：程序语言.pdf

您现在的位置：希赛网 云阅读 软件设计师考试试题分类精解（第3版）例题1第 2 章：程序语言作者：希赛教育软考学院 来源：希赛网 2014年02月07日例题12.2 试题精解例题1（2005年5月试题28-29）某一确定性有限自动机（DFA）的状态转换如图2-1所示，令d=0|1|2|9,则以下字符串中，不能被该DFA接受的是（28）,与该DFA等价的正则式是（29）.（其中，e 表示空字符）3857 1.2E+5 -123 576E10图2-1 状态转换图（28）A.，B.，C.，D.，（29）A.（-d|d）d*E（-d|d）d*|（-d|d）d*.d*（e|E（-d|d）d*）B.（-d|d）dd*（。|e）d*|（e|E（-d|d）d*）C.（-|d）dd*E（-|d）d*|（-d|d）dd*.d*（e|E（-|d）d*）D.（-d|d）dd*E（-d|d）d*|（-d|d|）dd*.d*（e|E（-dd*|dd*）试题分析题目第一问是判断备选答案中有哪些字符串不能被DFA接受。我们现在逐个对其进行判别，这样有利于对DFA功能的理解和后面的解题。首先看3857,这个字符串中的元素全部是数字，在DFA的初态0输入一个数字，进入状态1;在状态1输入数字，还是回到状态1.如果还想往后走，必须要输入字符.或是字符E,但3857中不存在这样的字符，因而无法到达终态，所以不能被DFA接受。接着看1.2E+5,这个不用判断就知道不行，因为+在此DFA中无法识别。再看-123.,此串能从始点顺利到达终点，所以可以被DFA接受。最后我们看.576E10,第一个字符.在初始状态无法被识别，所以此串不能被DFA识别。接下来是把DFA转化为正则式。我们用排除法来解答，首先可以排除B和D,很明显（-d|d）dd*所表达的串会比DFA所描述的串多一个d.再看C选项（-|d）dd*E（-|d）d*|（-d|d）dd*.d*（e|E（-|d）d*）。其中（-|d）dd*E（-|d）d*表示的路径是不经过节点5的路径。后面的（-d|d）dd*.d*（e|E（-|d）d*）是指经过节点5的路径。这里的（-d|d）dd*也是多出一个d,所以C也可以排除，答案就只能是A了。试题答案B A版权方授权希赛网发布，侵权必究上一节本书简介下一节第 2 章：程序语言作者：希赛教育软考学院 来源：希赛网 2014年02月07日例题2上一节本书简介下一节第 2 章：程序语言作者：希赛教育软考学院 来源：希赛网 2014年02月07日例题3例题2（2005年5月试题30）对于以下编号为，的正则式，正确的说法是_.（aa*|ab）*b（a|b）*b（a|b）*|aa）*b（30）A.正则式，等价B.正则式，等价C.正则式，等价D.正则式，互不等价试题分析由正则式产生的字串为a*b或ab*b,产生的字串为a*b或b*b,产生的字串为a*b或b*b.试题答案C版权方授权希赛网发布，侵权必究例题3（2005年11月试题27）编译程序进行词法分析时不能_。A.过滤源程序中的注释 B.扫描源程序并识别记号C.指出出错行号 D.查出拼错的保留字（关键字）试题分析在词法分析阶段，其任务是从左到右逐个字符地读入源程序，对构成源程序的字符流进行扫描和分解，从而识别出一个个单词（也称单词符号或符号）。这里所谓的单词是指逻辑上紧密相连的一组字符，这些字符组合在一起才表示某一含义。比如标识符是由字母开头，后跟字母或数字组成的一种单词。保留字（关键字或基本字）也是一种单词，此外还有算符等。在词法分析阶段，空白（由单词间的空格、制表或回车换行字符引起的空白）和注释都被滤掉了。在识别保留字时，词法分析程序将每个标识符对照一张保留字表进行查询，若查到则为保留字，反之则认为是用户定义的标识符。可见，词法分析阶段是查不出拼错的保留字的。在词法分析阶段，如果不符合词法规则，比如标识符不是以字母开头，就会进行错误处理，指出出错行号。试题答案D上一节本书简介下一节第 2 章：程序语言作者：希赛教育软考学院 来源：希赛网 2014年02月07日例题4版权方授权希赛网发布，侵权必究例题4（2005年11月试题28,29）某一确定有限自动机（DFA）的状态转换图如图2-2所示，该DFA接受的字符串集是（28）,与之等价的正规式是（29）。图2-2 状态转换图（28）A.以1开头的二进制代码串组成的集合B.以1结尾的二进制代码串组成的集合C.包含偶数个0的二进制代码串组成的集合D.包含奇数个0的二进制代码串组成的集合（29）A.1*0（0|1）*B.（0|1*0）*1*）*C.1*（0|1）0）*D.（1*（01*0）*）*试题分析在状态转换图中，末端没有状态连接的所指向的节点为初态节点，而终态用双环圈表示，显然，该题中q0既是初态又是终态，那么该DFA显然能识别空串。当处于q0时输入0便转换到q1,而当处于q1时输入0又回到q0,并且在q0或q1状态连续输入n?0个1时仍回到原状态，因此，该DFA识别的串是包含偶数个0的二进制代码串，即在偶数个0之间或前后可插入任意个1的串，如e、00、010、10101、1011011、1001101101.对于正规式，首先来了解几个符号的含义。*号，在正规式中，它表示任意自我连接，比如，a*表示n?0个a，（ab）*表示n?0个ab相连ababab；|表示或；表示连接，通常省略，如ab=ab.如果某有穷自动机所能识别的字符串集跟某正规式对应的正规集相等，则称两者等价。将有穷自动机M转化为与其等价的正规式R的步骤如下。首先，在M的转换图上加进两个状态x和y,从x用标有e的弧连接到M的所有初态节点，从M的所有终态节点用标有e的弧连接到y,从而形成一个新的有穷自动机，记为M.它只有一个初态x和一个终态y,显然L（M）=L（M），L（M）表示M所能接受的字符串集。然后，逐步消去所有节点，直到只剩下x和y为止，在消节过程中逐步用正规式来标记弧。其消节的规则见图2-3.上一节本书简介下一节第 2 章：程序语言作者：希赛教育软考学院 来源：希赛网 2014年02月07日例题5图2-3 状态转换图消节点规则最后，从x到y的弧上标记的正规式即为所构造的正规式R.以该题为例，其转化过程见图2-4.图2-4 状态转换图转正规式示意图注意到，（R1|R2）*=（R1*R2*）*,所以，（1|01*0）*=（1*（01*0）*）*,因此（29）空选D.另外，可以根据（28）题的结果来排除（29）空的A、B、C三个选项，因为这三个选项的正规式所能表达的串中不但含有偶数个0,而且可含有奇数个0,范围扩大了，所以不等价。试题答案C D版权方授权希赛网发布，侵权必究例题5（2006年5月试题19）开发专家系统时，通过描述事实和规则由模式匹配得出结论，这种情况下适用的开发语言是_。A.面向对象语言 B.函数式语言 C.过程式语言 D.逻辑式语言试题分析本题考查程序语言基本知识。函数式程序设计的数据结构本质上是表，而函数又可以作为值出现在表中，因此函数式程序的控制结构取决于函数，以及函数的定义和调用。函数式语言主要用于符号数据处理，如微分和积分演算、数理逻辑、游戏推演及人工智能等其他领域。用逻辑式程序设计语言编写程序不需要描述具体的解题过程，只需要给出一些必要的事实和规则。这些规则是解决问题的方法的规范说明，根据这些事实和规则，计算机利用谓词逻辑，通过演绎得到求解问题的执行序列。这种语言主要用在人工智能领域，也应用在自然语言处理、数据库查上一节本书简介下一节第 2 章：程序语言作者：希赛教育软考学院 来源：希赛网 2014年02月07日例题6上一节本书简介下一节第 2 章：程序语言作者：希赛教育软考学院 来源：希赛网 2014年02月07日例题7询、算法描述等方面，尤其适合于作为专家系统的开发工具。试题答案D版权方授权希赛网发布，侵权必究例题6（2006年5月试题20）高级程序设计语言中用于描述程序中的运算步骤、控制结构及数据传输的是_。A.语句 B.语义 C.语用 D.语法试题分析在高级程序设计语言中，语句用于描述程序中的运算步骤、控制结构及数据传输。语法是语言的外观，给出语言的语法意味着给出语句、声明和其他语言结构的书写规则。语义则表示不同的语法结构的含义。在程序语言的手册中，语言的描述都是围绕语法结构展开的。通常，先给出各种语句结构的语法，然后给出对应该结构的语义以描述内在含义。语用是关于程序与使用者之间的关系。试题答案A版权方授权希赛网发布，侵权必究例题7（2006年5月试题44）对于下面的文法GS,_ 是其句子（从S出发开始推导）。GS:SM|（S,M）MP|MP Pa|b|c|x|x|zA.（a,F）B.（fac,bb），g）C.（abc）D.（c,（da）试题分析在备选答案中，只有（fac,bb），g）能被推导出来，所以答案为B.试题答案B版权方授权希赛网发布，侵权必究上一节本书简介下一节第 2 章：程序语言作者：希赛教育软考学院 来源：希赛网 2014年02月07日例题8上一节本书简介下一节第 2 章：程序语言作者：希赛教育软考学院 来源：希赛网 2014年02月07日例题9例题8（2006年5月试题46）下面的C程序代码段在运行中会出现_ 错误。int i=0;while（i10）；i=i+l;A.语法 B.类型不匹配C.变量定义D.动态语义试题分析对于上面的程序段，大致一看，可能发现不了错误。所以，这类错误也是大家编程时需要注意的，错误仅仅是while语句后面多了一个分号;,然而这种错误是编译程序无法发现的，因为这个程序段并没有语法错误，它是一个可执行的程序段。只是程序中出现了死循环，无法停止，这种错误属于语义错误。正确的写法应是：int i=0;while（i或标以-,终态结点用双圈表示或标以+,若 f（ki,a）=kj,则从状态结点ki到状态结点kj画标记为a的弧；被DFA所接受是指从初态开始来终态，所输入的字符串能够按顺序的执行下去，若到某个状态不能往下走得到下一个字符，则认为不可接受。本题的状态图的状态间的字符有-、d、E、下面来逐个分析四个选项：A 选项不能被接受。由于3857都是数字，所以从初态0出发不经过状态4,而是直接到状态1,因为0和1之间产生字符为d,又在状态1处有d*,所以表面可以接受dddd形式的字符串；但是，状态1之后的产生字符是E和,不再是数字d,若输入全数字则到不了终态6.所以输入3857是不能接受的。B 选项不能被接受。从初态0152,就不能再往下走了，因为状态2后的产生字符是-、d,不是+,也无法到达终态6.C 选项能被接受。从初态04156,由于状态1和6处的可以反复多个字符，所以本选项正确。D 选项不能被接受。从初态0156,虽然从初态到终态，但无法接受字符E了，所以错误。试题答案C版权方授权希赛网发布，侵权必究例题28（2008年12月试题20）编译程序对高级语言源程序进行翻译时，需要在该程序的地址空间中为变量指定地址，这种地址称为_.上一节本书简介下一节第 2 章：程序语言作者：希赛教育软考学院 来源：希赛网 2014年02月08日例题28A.逻辑地址 B.物理地址 C.接口地址 D.线性地址试题分析本题考查逻辑地址与物理地址的区别，接口地址和线性地址可以首先排除。逻辑地址（Logical Address）是指由程序产生的与段相关的偏移地址部分。例如，在进行C语言指针编程中，可以读取指针变量本身值（&操作），实际上这个值就是逻辑地址，它是相对于你当前进程数据段的地址，不和绝对物理地址相干。而本题中将高级语言程序编译以后产生的仍然是一种程序（低级语言程序，如汇编语言），只有当程序调入到内存执行时，逻辑地址才会转化成物理地址。所以物理地址（Physical Address）是指出现在CPU外部地址总线上的寻址物理内存的地址信号，是地址变换的最终结果地址。试题答案A版权方授权希赛网发布，侵权必究例题29（2008年12月试题21）程序设计语言一般都提供多种循环语句，例如实现先判断循环条件再执行循环体的while语句和先执行循环体再判断循环条件的do-while语句。关于这两种循环语句，在不改变循环体的条件下，_是正确的。A.while语句的功能可由do-while语句实现B.do-while语句的功能可由while语句实现C.若已知循环体的次数，则只能使用while语句D.循环条件相同时，do-while语句的执行效率更高试题分析以下是两种循环语句的结构：while 循环条件循环体loopdo循环体while 循环条件其区别在于while循环会先进行条件判断，如果条件成立，再执行循环体；而do-while循环会先执行循环体，再进行条件判断，如果条件成立则再次执行循环体。所以do-while循环的循环体至少会被执行一次（也就是循环体执行：1N次），而while循环的循环体可以不执行，也可以执行N次（也就是循环体执行：0N次）。这样我们可以看出do-while循环的功能是可由while语句实现的。试题答案上一节本书简介下一节第 2 章：程序语言作者：希赛教育软考学院 来源：希赛网 2014年02月08日例题29上一节本书简介下一节第 2 章：程序语言作者：希赛教育软考学院 来源：希赛网 2014年02月08日例题30B版权方授权希赛网发布，侵权必究例题30（2008年12月试题42）_是指在运行时把过程调用和响应调用所需要执行的代码加以结合。A.绑定 B.静态绑定 C.动态绑定 D.继承试题分析绑定（binding）是指将对象置于运行状态，允许调用它所支持的操作。对象可在运行时进行绑定，也可在编译时进行绑定，前者称为后期绑定或动态绑定，后者称为静态绑定。所以本题选C.试题答案C版权方授权希赛网发布，侵权必究例题31（2008年12月试题48）给定文法GS及其非终结符A,FIRST（A）定义为：从A出发能推导出的终结符号的集合（S 是文法的起始符号，为非终结符）。对于文法GS:SL|aLL,S|S其中，GS包含的四个终结符号分别为：a ,则FIRST（S）的成员包括_.A.a B.a、C.a、和 D.a、和，试题分析由于有：SaSL所以FIRST（S）=a,试题答案上一节本书简介下一节第 2 章：程序语言作者：希赛教育软考学院 来源：希赛网 2014年02月08日例题31上一节本书简介下一节第 2 章：程序语言作者：希赛教育软考学院 来源：希赛网 2014年02月08日例题32B版权方授权希赛网发布，侵权必究例题32（2008年12月试题49）高级语言源程序的编译过程分若干个阶段，分配寄存器属于_阶段的工作。A.词法分析 B.语法分析 C.语义分析 D.代码生成试题分析高级语言源程序的编译过程通常分为：词法分析、语法分析、语义分析中间代码生成、优化、目标代码生成五个阶段。词法分析：输入源程序，对构成源程序的字符串进行扫描和分解，识别出一个个单词（也称单词符号，或简称符号）在词法分析阶段工作所依循的是语言的词法规则。描述词法规则的有效工具是正规式和有限自动机。语法分析：在词法分析的基础上，根据语言的语法规则，把单词符号分解成各类语法单位（语法范畴），如短语、句子、子句、程序段等。语义分析与中间代码生成：这一阶段通常包括两方面的工作首先对各种语法范畴进行静态语义检查，如果正确则进行另一方面的工作，即进行中间代码的翻译。通常使用属性文法描述语义规则。所谓中间代码是一种含义明确，便于处理的记号系统。中间代码除四元式外，还有三元式、间接三元式、逆波兰记号、树形表示等。优化：优化的任务在于对前段产生的中间代码进行加工，以期在最后阶段产生更为高效（省时间和空间）的代码。优化所依循的原则是程序的等价变换规则，其方法有：公共子表达式的提取、循环优化、删除无用代码等。目标代码生成：把中间代码（或经优化处理后）变换成特定机器上的低级语言代码。它有赖于硬件系统结构和机器指令含义。分配寄存器涉及物理层面，编译过程中只有目标代码生成涉及到物理层面，所以该题选D.试题答案D版权方授权希赛网发布，侵权必究第 2 章：程序语言作者：希赛教育软考学院例题31上一节本书简介下一节第 3 章：操作系统作者：希赛教育软考学院 来源：希赛网 2014年02月08日例题1例题33（2008年12月试题50）设某上下文无关文法如下：S11|1001|S0|SS,则该文法所产生的所有二进制字符串都具有的特点是_.A.能被3整除 B.0、1出现的次数相等C.0和1的出现次数都为偶数 D.能被2整除试题分析本题要求考生分析文法的特点，由于答案选项有限，所以解题最简单的方法便是以此文法生成几个二进制字符串。然后再判断选项是否符合。如生成串：11、1001、110、10010,对于这些串，只有A答案符合，所以正确答案为A.试题答案A版权方授权希赛网发布，侵权必究3.2 试题精解例题1（2004年5月试题2326）若有一个仓库，可以存放P1,P2两种产品，但是每次只能存放一种产品。要求：w=P1的数量-P2的数量-iwk（i,k为正整数）若用P-V操作实现P1和P2产品的入库过程，至少需要（23）个同步信号量及（24）个互斥信号量，其中，同步信号量的初值分别为（25）,互斥信号量的初值分别为（26）.（23）A.0B.1C.2D.3（24）A.0B.1C.2D.3（25）A.0B.i,k,0C.i,kD.i-1,k-1（26）A.1B.1,1C.1,1,1D.i,k试题分析同步是指进程间共同完成一项任务时直接发生相互作用的关系，即具有伙伴关系的进程在执行时间次序上必须遵循的规律。互斥是指进程因竞争同一资源而相互制约。同步和互斥可以这样来理解：互斥是指在使用临界资源的时候，多个进程不能同时使用临界资源，如果进程A在使用，B需要等待，待A用完之后，才能让B用。这种信号量的初值一般为1,表示只有一个资源可用，如果已经有一个进程占用了这个资源，其他进程要使用，则须等待。同步是指进程间共同完成一项任务时直接发生相互作用的关系，即具有伙伴关系的进程在执行时间次序上必须遵循的规律。通俗一点说就是要步伐一致，即保证差距不是很远。例如：A和B两人约定去C家里