2005上半年软件设计师级上午试题分析与解答
试题（28）、（29）
某一确定性有限自动机（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*.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*))
试题（28）、（29）分析
有限自动机也称为有穷状态自动机，是一种数学机器模型，基本形式有非确定有限自动机（NFA）和确定的有限自动机（DFA），并且每一个NFA都有与其等价的DFA。有穷状态自动机的物理模型如下图所示。
一个DFA可以用状态转换图直观的方式。状态转换图是一种有向图。DFA中的每个状态对应转换图中的一个节点，从外部引入弧的节点表示开始节点，双圈节点表示终态；DFA中的每个状态转换对应图中的一条有向弧，若转换关系为f（A，a）=Q，则该有向弧从节点A出发，进入节点Q，字符a是弧上的标记。
有穷状态自动机识别字符串的过程为：初始时，机器处于起始状态（题图中节点0表示初始状态）。读取一个输入符号，并进行相应的状态转移，直到输入串结束或找不到
2 软件设计师历年试题分析与解答
相应的状态转移时为止。
根据题目中给定的自动机，识别3857、1.2E+5、–123.、.576E10的过程分别如下。
分析题中给定的有穷状态自动机，可知该自动机识别以下形式的数值：带小数部分的十进制表示形式和以尾数、指数表示的数值形式。其中，从初态0到达终态5所识别的是带小数点的以十进制数值表示形式的字符串，小数点后可以没有数字，也可以有若干个数字，而小数点之前的整数部分可以不带符号，也可以带负号，其正规式为 “（–d|d）d*.d*”。当数值的表示含有指数部分时，指数部分是不带符号（表示正数）或带负号的整数形式，因此该部分的正规式为“E(–d|d)d*”。 参考答案
（28）B （29）A
试题（30）
对于以下编号为①、②、③的正规式，正确的说法是 （30） 。 ① (aa*|ab)*b ② (a|b)*b ③ ((a|b)*|aa)*b
（30）A．正规式①、②等价 C．正规式②、③等价
B．正规式①、③等价
D．正规式①、②、③互不等价
试题（30）分析
根据正规式r和s的意义，两个正规式等价说明r和s代表的字符串集合相同，因此可用证明集合相等的方法判断。另外，也可构造出与每个正规式对应的自动机进行说明。但是这两个方法实施起来都很繁琐，因此可根据正规式的含义及其代数性质进行判断。 由于题目中给出的正规式①、②和③的共同之处是以字符b结尾，所以只需考虑(aa*|ab)*、(a|b)*和((a|b)*|aa)*之间的等价关系。从直观的角度理解，正规式(aa*|ab)*表示的是包含空串ε以及a开头的且每个b之后必然出现a的字符串的集合，而(a|b)*表示包含空串ε在内的所有a、b构成的字符串集合，并不限制b的出现方式，正规式((a|b)*|aa)*表示的字符串也不具有必须以a开头的特点，因此，正规式①与②、③的等价关系即可
2005上半年软件设计师级上午试题分析与解答 3
排除。
至于(a|b)*和((a|b)*|aa)*，很明显正规式((a|b)*|aa)*中的“aa”是画蛇添足的部分，因为(a|b)*已经包括了含有“aa”子串的所有a、b字符串，因此(a|b)*b和((a|b)*|aa)*b是等价的。 参考答案
（30）C
试题（38）
循环链表的主要优点是（38） 。
（38）A．不再需要头指针了 B．已知某个结点的位置后，能很容易找到它的直接前驱结点 C．在进行删除操作后，能保证链表不断开 D．从表中任一结点出发都能遍历整个链表 试题（38）分析
链表是用连续（或不连续）的存储单元存储数据元素，元素之间的逻辑关系用“指针”指明。链表具体分为几种形式：单向链表中结点包含一个指针，指明其直接前驱（或后继）元素结点；双向链表中结点包含两个指针，分别指明其直接前驱和直接后继元素结点；循环链表是最后结点的指针指回头结点，它可在任何位置上沿指针遍历整个链表。 参考答案
（38）D 试题（39）
表达式a*(b+c)–d的后缀表达形式为 （39） 。 （39）A．abcd*+– B．abc+*d– C．abc*+d–
D．– +*abcd
试题（39）分析
一个表达式可用一棵二叉树表示，其中的叶子结点表示操作数，内部结点表示操作符或中间结果，根结点表示整个表达式的值。对此二叉树分别进行前序、中序和后序遍历恰好为表达式的前缀表示（波兰式）、中缀表示和后缀表示（逆波兰式）。其中表达式的前缀和后缀表示均可以将表达式中的括号省去而不影响计算次序和结果。 参考答案
（39）B 试题（40）
若二叉树的先序遍历序列为ABDECF，中序遍历序列DBEAFC，则其后序遍历序列为 （40） 。
（40）A．DEBAFC B．DEFBCA C．DEBCFA D．DEBFCA 试题（40）分析
对于二叉树遍历序列有一个性质：包含有中序遍历序列的任意两个遍历序列可以唯
4 软件设计师历年试题分析与解答
一确定该二叉树。那么由题中的先序遍历序列和中序遍历序列就可以唯一确定此二叉树如下图所示，再对其进行后序遍历即可。
ABDECF 参考答案
（40）D 试题（41）
无向图中一个顶点的度是指图中 （41） 。 （41）A．通过该顶点的简单路径数 B．通过该顶点的回路数 C．与该顶点相邻接的顶点数 D．与该顶点连通的顶点数 试题（41）分析
图中顶点的度定义为与该顶点相关联的边的数目。在无向图中就是与该顶点相邻接的顶点数。而与该顶点连通的顶点数可能就非常多了。 参考答案
（41）C 试题（42）
利用逐点插入法建立序列（50，72，43，85，75，20，35，45，65，30）对应的二叉排序树以后，查找元素30要进行（42）次元素间的比较。
（42）A．4 B．5 C．6 D．7 试题（42）分析
利用逐点插入法建立二叉排序树是从空树开始，通过查找将每个结点作为一个叶子插入。按上述次序建立的二叉排序树如下图所示。
