1、软件设计师-4 及答案解析(总分：100.00，做题时间：90 分钟)一、单项选择题(总题数：50，分数：100.00)1.如图所示为一个有限自动机(其中，A 是初态，C 是终态)，该自动机所识别的字符串的特点是_。 （分数：1.00）A.必须以 11 结尾的 0、1 串B.必须以 00 结尾的 0、1 串C.必须以 01 结尾的 0、1 串D.必须以 10 结尾的 0、1 串2.编译和解释是实现高级程序设计语言翻译的两种基本形式。以下关于编译与解释的叙述中，正确的是_。（分数：1.00）A.在解释方式下，对源程序不进行词法分析和语法分析，直接进行语义分析B.在解释方式下，无须进行词法、语法和
2、语义分析，而是直接产生源程序的目标代码C.在编译方式下，必须进行词法、语法和语义分析，然后再产生源程序的目标代码D.在编译方式下，必须先形成源程序的中间代码，然后再产生与机器对应的目标代码3.若 C 程序的表达式中引用了未赋初值的变量，则_。（分数：1.00）A.编译时一定会报告错误信息，该程序不能运行B.可以通过编译并运行，但运行时一定会报告异常C.可以通过编译，但链接时一定会报告错误信息而不能运行D.可以通过编译并运行，但运行结果不一定是期望的结果4.以下关于高级程序设计语言翻译的叙述中，正确的是_。（分数：1.00）A.可以先进行语法分析，再进行词法分析B.在语法分析阶段可以发现程序中的
3、所有错误C.语义分析阶段的工作与目标机器的体系结构密切相关D.目标代码生成阶段的工作与目标机器的体系结构密切相关5.如图所示为一个有限自动机(其中，A 是初态，C 是终态)，该自动机可识别_。 （分数：1.00）A.0000B.1111C.0101D.10106.以下关于变量和常量的叙述中，错误的是_。（分数：1.00）A.变量的取值在程序运行过程中可以改变，常量则不行B.变量具有类型属性，常量则没有C.变量具有对应的存储单元，常量则没有D.可以对变量赋值，不能对常量赋值7.某程序设计语言规定在源程序中的数据都必须具有类型，然而，_并不是做出此规定的理由。（分数：1.00）A.为数据合理分配存
4、储单元B.可以定义和使用动态数据结构C.可以规定数据对象的取值范围及能够进行的运算D.对参与表达式求值的数据对象可以进行合法性检查8.函数(过程)调用时，常采用传值与传址两种方式在实参与形参间传递信息。以下叙述中，正确的是_。（分数：1.00）A.在传值方式下，将形参的值传给实参，因此，形参必须是常量或变量B.在传值方式下，将实参的值传给形参，因此，实参必须是常量或变量C.在传址方式下，将形参的地址传给实参，因此，形参必须有地址D.在传址方式下，将实参的地址传给形参，因此，实参必须有地址算术表达式采用逆波兰式表示时不用括号，可以利用_进行求值。与逆波兰式 ab-cd+*对应的中缀表达式是_。（
5、分数：4.00）A.数组B栈C.队列D.散列表A.a-b+c*dB.(a-b)*c+dC.(a-b)*(c+d)D.a-b*c+d函数 t、f 的定义如下所示，其中，a 是整型全局变量。设调用函数 t 前 a 的值为 5，则在函数 t 中以传值调用(call by vahle)方式调用函数 f 时，输出为_；在函数 t 中以引用调用(call by reference)方式调用函数 f 时，输出为_。 （分数：4.00）A.12B.16C.20D.24A.12B.16C.20D.249.编译程序分析源程序的阶段依次是_。（分数：2.00）A.词法分析、语法分析、语义分析B.语法分析、词法分析、
6、语义分析C.语义分析、语法分析、词法分析D.语义分析、词法分析、语法分析10.如图所示的有限自动机中，0 是初始状态，3 是终止状态，该自动机可以识别_。 （分数：2.00）A.ababB.aaaaC.bbbbD.abba11.如图所示为两个有限自动机 M1 和 M2(A 是初态，C 是终态)，_。 （分数：2.00）A.M1 和 M2 都是确定的有限自动机B.M1 和 M2 都是不确定的有限自动机C.M1 是确定的有限自动机，M2 是不确定的有限自动机D.M1 是不确定的有限自动机，M2 是确定的有限自动机12.以下关于可视化程序设计的叙述中，错误的是_。（分数：2.00）A.可视化程序设计
7、使开发应用程序无须编写程序代码B.可视化程序设计基于面向对象的思想，引入了控件和事件驱动C.在可视化程序设计中，构造应用程序界面就像搭积木D.在可视化程序设计中，采用解释方式可随时查看程序的运行效果13.以下关于汇编语言的叙述中，错误的是_。（分数：2.00）A.汇编语言源程序中的指令语句将被翻译成机器代码B.汇编程序先将源程序中的伪指令翻译成机器代码，然后再翻译指令语句C.汇编程序以汇编语言源程序为输入，以机器语言表示的目标程序为输出D.汇编语言的指令语句必须具有操作码字段，可以没有操作数字段14.如图所示为一个有限自动机(其中，A 是初态，C 是终态)，该自动机识别的语言可用正规式_表示。
8、（分数：2.00）A.(0|1)*01B.1*0*10*1C.1*(0)*01D.1*(0|10)*1*15.算术表达式 x-(y+c)*8 的后缀表达式是_。(-、+、*表示算术的减、加、乘运算，运算符的优先级和结合性遵循惯例)（分数：2.00）A.x y c 8-+*B.x y-c+8*C.x y c 8*-+D.x y c+8*-16.传值与传址是函数调用时常采用的信息传递方式，_。（分数：2.00）A.在传值方式下，是将形参的值传给实参B.在传值方式下，形参可以是任意形式的表达式C.在传址方式下，是将实参的地址传给形参D.在传址方式下，实参可以是任意形式的表达式17.若一种程序设计语言
9、规定其程序中的数据必须具有类型，则有利于_。 在翻译程序的过程中为数据合理分配存储单元 对参与表达式计算的数据对象进行检查 定义和应用动态数据结构 规定数据对象的取值范围及能够进行的运算 对数据进行强制类型转换（分数：2.00）A.B.C.D.18.下面 C 程序段中 count+语句执行的次数为_。 for(int i=1; i=11; i*=2) for(int j=1; j=i; j+) count+;（分数：2.00）A.15B.16C.31D.3219.算术表达式(a-b)*c+d 的后缀表达式是_(-、+、*表示算术的减、加、乘运算，运算符的优先级和结合性遵循惯例)。（分数：2.0
10、0）A.abcd-*+B.ab-cd*+C.ab-c*d+D.abc-d*+20.对于一个长度大于 1 且不存在重复元素的序列，令其所有元素依次通过一个初始为空的队列后，再通过一个初始为空的栈。设队列和栈的容量都足够大，一个序列通过队列(栈)的含义是序列的每个元素都入队列(栈)且出队列(栈)一次且仅一次。对于该序列在上述队列和栈上的操作，正确的叙述是_。（分数：2.00）A.出队序列和出栈序列一定相同B.出队序列和出栈序列一定互为逆序C.入队序列与出队序列一定相同，入栈序列与出栈序列不一定相同D.入栈序列与出栈序列一定互为逆序，入队序列与出队序列不一定互为逆序21.若二维数组 arr1M, N
11、的首地址为 base，数组元素按列存储且每个元素占用 K 个存储单元，则元素 arri,j在该数组空间的地址为_。（分数：2.00）A.base+(i-1)*M+j-1)*KB.base+(i-1)*N+j-1)*KC.base+(j-1)*M+i-1)*KD.base+(j-1)*N+i-1)*K22.对于线性表(由 n 个同类元素构成的线性序列)，采用单向循环链表存储的特点之一是_。（分数：2.00）A.从表中任意节点出发都能遍历整个链表B.对表中的任意节点可以进行随机访问C.对于表中的任意一个节点，访问其直接前驱和直接后继节点所用时间相同D.第一个节点必须是头节点23.设下三角矩阵(上三
12、角部分的元素值都为 0)A0n, 0n如图所示，将该三角矩阵的所有非零元素(即行下标不小于列下标的元素)按行优先压缩存储在容量足够大的数组 M中(下标从 1 开始)，则元素Ai,j(0in，ji)存储在数组 M 的_中。 下三角矩阵A B C D （分数：2.00）A.B.C.D.24.设循环队列 Q 的定义中有 rear 和 len 两个域变量，其中 rear 表示队尾元素的指针，len 表示队列的长度，如图所示(队列长度为 3，队头元素为 e)。设队列的存储空间容量为 M，则队头元素的指针为_。 （分数：2.00）A.(Qrear+Qlen-1)B.(Qrear+Qlen-1+M)%MC.
13、(Qrea-Qlen+1)D.(Qrea-Qlen+1+M)%M25.对于二维数组 a1N，1N中的一个元素 ai，j(1i，jN)，存储在 ai，j之前的元素个数_。（分数：2.00）A.与按行存储或按列存储方式无关B.在 i=j 时与按行存储或按列存储方式无关C.在按行存储方式下比按列存储方式下要多D.在按行存储方式下比按列存储方式下要少26.若 n 2 、n 1 、n 0 分别表示一个二叉树中度为 2、度为 1 和叶子节点的数目(节点的度定义为节点的子树数目)，则对于任何一个非空的二叉树，_。（分数：2.00）A.n2 一定大于 n1B.n1 一定大于 n0C.n2 一定大于 n0D.n
14、0 一定大于 n227.一棵满二叉树，其每一层节点个数都达到最大值，对其中的节点从 1 开始顺序编号，即根节点编号为1，其左右子节点编号分别为 2 和 3，再下一层从左到右的编号为 4、5、6、7，以此类推，每一层都从左到右依次编号，直到最后的叶子节点层为止，则用_可判定编号为 m 和 n 的两个节点是否在同一层。 Alog 2 m=log 2 n B C D （分数：2.00）A.B.C.D.28._是由权值集合8，5，6，2构造的哈夫曼树(最优二叉树)。 A B C D （分数：2.00）A.B.C.D.29.在_中，任意一个节点的左右子树的高度之差的绝对值不超过 1。（分数：2.00）A
15、.完全二叉树B.二叉排序树C.线索二叉树D.最优二叉树30.下面关于哈夫曼树的叙述中，正确的是_。（分数：2.00）A.哈夫曼树一定是完全二叉树B.哈夫曼树一定是平衡二叉树C.哈夫曼树中权值最小的两个节点互为兄弟节点D.哈夫曼树中左子节点小于父节点、右子节点大于父节点31.已知一棵度为 3 的树(一个节点的度是指其子树的数目，树的度是指该树中所有节点的度的最大值)中有 5 个度为 1 的节点，4 个度为 2 的节点，2 个度为 3 的节点，那么，该树中的叶子节点数目为_。（分数：2.00）A.10B.9C.8D.732.从存储空间的利用率角度来看，以下关于数据结构中图的存储的叙述，正确的是_。
16、（分数：2.00）A.有向图适合采用邻接矩阵存储，无向图适合采用邻接表存储B.无向图适合采用邻接矩阵存储，有向图适合采用邻接表存储C.完全图适合采用邻接矩阵存储D.完全图适合采用邻接表存储33.无向图中一个顶点的度是指图中与该顶点相邻接的顶点数。若无向图 G 中的顶点数为 n，边数为 e，则所有顶点的度数之和为_。（分数：2.00）A.neB.n+eC.2nD.2e34.设一个包含 N 个顶点、E 条边的简单无向图采用邻接矩阵存储结构(矩阵元素 Aij等于 1/0 分别表示顶点 i 与顶点 j 之间有/无边)，则该矩阵中的非零元素数目为_。（分数：2.00）ANBEC.2ED.N+E35.无向
17、图中一个顶点的度是指图中_。（分数：2.00）A.通过该顶点的简单路径数B.通过该顶点的回路数C.与该顶点相邻的顶点数D.与该顶点连通的顶点数36.单向链表中往往含有一个头节点，该节点不存储数据元素，一般令链表的头指针指向该节点，而该节点指针域的值为第 1 个元素节点的指针。以下关于单链表头节点的叙述中，错误的是_。（分数：2.00）A.若在头节点中存入链表长度值，则求链表长度运算的时间复杂度为 O(1)B.在链表的任何一个元素前后进行插入和删除操作可用一致的方式进行处理C.加入头节点后，代表链表的头指针不因为链表为空而改变D.加入头节点后，在链表中进行查找运算的时间复杂度为 O(1)37.循
18、环链表的主要优点是_。（分数：2.00）A.不再需要头指针了B.已知某个节点的位置后，能很容易找到它的直接前驱节点C.在进行删除操作后，能保证链表不断开D.从表中任一节点出发都能遍历整个链表设栈 S 和队列 Q 的初始状态为空，元素按照 a、b、c、d、e 的次序进入栈 S，当一个元素从栈中出来后立即进入队列 Q。若队列的输出元素序列是 c、d、b、a、e，则元素的出栈顺序是_，栈 S 的容量至少为_。（分数：4.00）A.a、b、c、d、eB.e、d、c、b、aC.c、d、b、a、eD.e、a、b、d、cA.2B.3C.4D.538.输入受限的双端队列是指元素只能从队列的一端输入，但可以从队
19、列的两端输出，如图所示。若有8、1、4、2 依次进入输入受限的双端队列，则得不到输出序列_。 （分数：2.00）A.2、8、1、4B.1、4、8、2C.4、2、1、8D.2、1、4、839.若二叉树的先序遍历序列为 ABDECF，中序遍历序列为 DBEAFC，则其后序遍历序列为_。（分数：2.00）A.DEBAFCB.DEFBCAC.DEBCFAD.DEBFCA40.下面关于二叉排序树的叙述，错误的是_。（分数：2.00）A.对二叉排序树进行中序遍历，必定得到节点关键字的有序序列B.依据关键字无序的序列建立二叉排序树，也可能构造出单支树C.若构造二叉排序树时进行平衡化处理，则根节点的左子树节点
20、数与右子树节点数的差值一定不超过 1D.若构造二叉排序树时进行平衡化处理，则根节点的左子树高度与右子树高度的差值一定不超过 141.下面关于二叉树的叙述，正确的是_。（分数：2.00）A.完全二叉树的高度 h 与其节点数 n 之间存在确定的关系B.在二叉树的顺序存储和链式存储结构中，完全二叉树更适合采用链式存储结构C.完全二叉树中一定不存在度为 1 的节点D.完全二叉树中必定有偶数个叶子节点42.若将某有序树 T 转换为二叉树 T1，则 T 中节点的后(根)序序列就是 T1 中节点的_遍历序列。例如，图(a)所示的有序树转化为二叉树后如图(b)所示。 （分数：2.00）A.先序B.中序C.后序
21、D.层序43.在平衡二叉树中，_。（分数：2.00）A.任意节点的左右子树节点数目相同B.任意节点的左右子树高度相同C.任意节点的左右子树高度之差的绝对值不大于 1D.不存在度为 1 的节点44.在如图所示的平衡二叉树(树中任意节点的左右子树高度之差不超过 1)中，节点 A 的右子树 AR 高度为h，节点 B 的左子树 BL 高度为 h，节点 C 的左子树 CL、右子树 CR 高度都为 h-1。若在 CR 中插入一个节点并使得 CR 的高度增加 1，则该二叉树_。 （分数：2.00）A.以 B 为根的子二叉树变为不平衡B.以 C 为根的子二叉树变为不平衡C.以 A 为根的子二叉树变为不平衡D.
22、仍然是平衡二叉树由权值为 29、12、15、6、23 的 5 个叶子节点构造的哈夫曼树为_，其带权路径长度为_。（分数：4.00）(1).A B C D （分数：2.00）A.B.C.D.A.85B.188C.192D.22245.若某二叉树的后序遍历序列为 KBFDCAE，中序遍历序列为 BK2EFACD，则该二叉树为_。 A B C D （分数：2.00）A.B.C.D.46.拓扑排序是将有向图中所有顶点排成一个线性序列的过程，并且该序列满足：若在 AOV 网中从顶点 V i 到 V j 有一条路径，则顶点 V i 必然在顶点 V j 之前。对于如图所示的有向图，_是其拓扑序列。 （分数：
23、2.00）A.12341576B.1235467C.2135476D.2134567软件设计师-4 答案解析(总分：100.00，做题时间：90 分钟)一、单项选择题(总题数：50，分数：100.00)1.如图所示为一个有限自动机(其中，A 是初态，C 是终态)，该自动机所识别的字符串的特点是_。 （分数：1.00）A.必须以 11 结尾的 0、1 串B.必须以 00 结尾的 0、1 串C.必须以 01 结尾的 0、1 串 D.必须以 10 结尾的 0、1 串解析：被有限自动机所识别是指从初态开始到终态结束，所输入的字符串能够按顺序地执行下去，若到某个状态不能往下走得到下一个字符，则认为不能识
24、别。 在本题中，从初态 A 出发，不管经过多少个 1 和 0 之后，只能是处在 A、B、C 3 种状态中的一种，所以在(011)*后，只能是处在 A、B、C 3 种状态中的一种，不管是在哪个状态，输入 0 后，都会处在状态 B，然后输入 1，都会转换到状态 C，因此与本题有限自动机等价的正规式是(0|1)*01，即该自动机所识别的字符串的特点是必须以 01 结尾的 0、1 串。2.编译和解释是实现高级程序设计语言翻译的两种基本形式。以下关于编译与解释的叙述中，正确的是_。（分数：1.00）A.在解释方式下，对源程序不进行词法分析和语法分析，直接进行语义分析B.在解释方式下，无须进行词法、语法和
25、语义分析，而是直接产生源程序的目标代码C.在编译方式下，必须进行词法、语法和语义分析，然后再产生源程序的目标代码 D.在编译方式下，必须先形成源程序的中间代码，然后再产生与机器对应的目标代码解析：编译和解释是语言处理的两种基本方式。编译过程包括词法分析、语法分析、语义分析、中间代码生成、代码优化和目标代码生成等阶段，以及符号表格管理与出错处理模块。 解释过程在词法、语法和语义分析方面与编译程序的工作原理基本相同，但是在运行用户程序时，它直接执行源程序或源程序的内部形式。 这两种语言处理程序的根本区别是：在编译方式下，机器上运行的是与源码程序等价的目标程序，源程序和编译程序都不再参与目标程序的执
26、行过程；而在解释方式下，解释程序和源程序(或其某种等价表示)要参与到程序的运行过程中，运行程序的控制权在解释程序。 在编译方式下，词法、语法和语义分析是必须要进行的工作，而生产中间代码和代码优化则是可以进行也可以不进行的工作。3.若 C 程序的表达式中引用了未赋初值的变量，则_。（分数：1.00）A.编译时一定会报告错误信息，该程序不能运行B.可以通过编译并运行，但运行时一定会报告异常C.可以通过编译，但链接时一定会报告错误信息而不能运行D.可以通过编译并运行，但运行结果不一定是期望的结果 解析：在 C 程序中，若在某个表达式中引用了未赋初值的变量，那么程序是可以通过编译并运行的，因为程序中并
27、没用语法方面的错误，只是运行的结果可能与我们期望的结果不一致。4.以下关于高级程序设计语言翻译的叙述中，正确的是_。（分数：1.00）A.可以先进行语法分析，再进行词法分析B.在语法分析阶段可以发现程序中的所有错误C.语义分析阶段的工作与目标机器的体系结构密切相关D.目标代码生成阶段的工作与目标机器的体系结构密切相关 解析：在对用高级程序设计语言编写的程序进行执行时，首先是将源代码翻译成目标代码，然后再链接成可执行的二进制代码。因此在翻译阶段，目标代码生成阶段的工作与目标机器的体系结构密切相关。5.如图所示为一个有限自动机(其中，A 是初态，C 是终态)，该自动机可识别_。 （分数：1.00）
28、A.0000B.1111C.0101 D.1010解析：本题主要考查有限自动机。 在本题中，A 是初始状态，C 是终止状态，通过选项中的字符串可以从初始状态到达终止状态，则说明该字符串能被题目中的自动机识别。也可以理解为依次输入选项中的字符串，可以在该自动机中找到相应的路径。 对于选项 A 的字符串 0000，在输入 0 后，从初始状态 A 转移到状态 B，然后接着输入 3 个 0，状态停留在B，而无法到达终态 C，因此选项 A 不能被该自动机识别。 同样的道理，我们可以找到字符串 0101 能被该自动机识别，在输入 0 后，状态跳转到 B，输入 1 则由 B转至 C，再输入 0，又由 C 转
29、至 B，最后输入 1，由 B 转至终态 C。6.以下关于变量和常量的叙述中，错误的是_。（分数：1.00）A.变量的取值在程序运行过程中可以改变，常量则不行B.变量具有类型属性，常量则没有 C.变量具有对应的存储单元，常量则没有D.可以对变量赋值，不能对常量赋值解析：本题主要考查我们对常量与变量的理解。顾名思义，常量是指值一旦确定后就不能再变的量，而变量则是一个在程序执行过程中，可以根据需要修改的量，是一个可改变的量。当然不管是常量还是变量，它们都有其类型属性。7.某程序设计语言规定在源程序中的数据都必须具有类型，然而，_并不是做出此规定的理由。（分数：1.00）A.为数据合理分配存储单元B.
30、可以定义和使用动态数据结构 C.可以规定数据对象的取值范围及能够进行的运算D.对参与表达式求值的数据对象可以进行合法性检查解析：8.函数(过程)调用时，常采用传值与传址两种方式在实参与形参间传递信息。以下叙述中，正确的是_。（分数：1.00）A.在传值方式下，将形参的值传给实参，因此，形参必须是常量或变量B.在传值方式下，将实参的值传给形参，因此，实参必须是常量或变量C.在传址方式下，将形参的地址传给实参，因此，形参必须有地址 D.在传址方式下，将实参的地址传给形参，因此，实参必须有地址解析：形式参数就是过程定义中函数名后括号中所带的参数，实际参数是在调用点表示向被调用过程传递的数据。 在函数
31、调用时，数据传递的方向是从实参到形参。只是采用传值传递方式时，传递的是数值，这个数值只要是确定的即可，可以是常量、变量或表达式等。而采用传址传递方式时，传递的是地址，因此实参必须有地址。算术表达式采用逆波兰式表示时不用括号，可以利用_进行求值。与逆波兰式 ab-cd+*对应的中缀表达式是_。（分数：4.00）A.数组B栈 C.队列D.散列表解析：A.a-b+c*dB.(a-b)*c+dC.(a-b)*(c+d) D.a-b*c+d解析：逆波兰式也叫后缀表达式，即将运算符写在操作数之后的表达式，它不需使用括号，在将算术表达式转换为逆波兰式表示时，需要分配两个栈，一个作为临时存储运算符的栈 S1(
32、含一个结束符号)，一个作为输入逆波兰式的栈 S2(空栈)。 而逆波兰式 ab-cd+*转换为中缀表达式的过程为：ab-cd+*=(ab-)*(cd+)=(a-b)*(cd+)=(a-b)*(c+d)。因此本题答案选 C。函数 t、f 的定义如下所示，其中，a 是整型全局变量。设调用函数 t 前 a 的值为 5，则在函数 t 中以传值调用(call by vahle)方式调用函数 f 时，输出为_；在函数 t 中以引用调用(call by reference)方式调用函数 f 时，输出为_。 （分数：4.00）A.12B.16 C.20D.24解析：A.12B.16C.20D.24 解析：传值调
33、用中，形参取的是实参的值，形参的改变不会导致调用点所传的实参的值发生改变；而引用(传址)调用中，形参取的是实参的地址，即相当于实参存储单元的地址引用，因此改变其值同时就改变了实参的值。 在本题中，首先是采用传值调用，这个时候将变量 a 的值 5 传递给形参 r，即 r 的值为 5，那么 a 的值经过 a=r+1 后变成了 6，而 r 的值经过 r=r*2 后变成了 10，并返回，即在函数 t 中，变量 x 的值被赋值为10，那么在函数 t 中最后输出的是 10+6=16。 采用引用调用时，由于形参 r 指向的是实参 a 的存储空间，即 r 与 a 指向的是同一块存储单元，首先 a 的值为 5，
34、经过 a=r+1 后变成了 6，再经过 r=r*2 后变成了 12，并返回，即在函数 t 中，变量 x 的值被赋值为 12，那么在函数 t 中最后输出的是 12+12=24。9.编译程序分析源程序的阶段依次是_。（分数：2.00）A.词法分析、语法分析、语义分析 B.语法分析、词法分析、语义分析C.语义分析、语法分析、词法分析D.语义分析、词法分析、语法分析解析：编译程序分析源程序的阶段依次为词法分析、语法分析、语义分析。10.如图所示的有限自动机中，0 是初始状态，3 是终止状态，该自动机可以识别_。 （分数：2.00）A.ababB.aaaa C.bbbbD.abba解析：本题主要考查有限
35、自动机。 在题目中，0 是初始状态，3 是终止状态，通过选项中的字符串可以从初始状态到达终止状态，则说明该字符串能被题目中的自动机识别。也可以理解为依次输入选项中的字符串，可以在该自动机中找到相应的路径。 对于选项 A 的字符串 abab，通过 ab 可以达到终止状态，然后输入 a 仍然可以有路径，但再输入 b 时，没有路径与其对应。因此 A 不可被该自动机识别。同样的道理，可以找到字符串 aaaa 能被该自动机识别。11.如图所示为两个有限自动机 M1 和 M2(A 是初态，C 是终态)，_。 （分数：2.00）A.M1 和 M2 都是确定的有限自动机B.M1 和 M2 都是不确定的有限自动
36、机C.M1 是确定的有限自动机，M2 是不确定的有限自动机D.M1 是不确定的有限自动机，M2 是确定的有限自动机 解析：本题主要考查确定有限自动机与不确定有限自动机的判断。 不确定有限自动机与确定有限自动机的最大区别是它们的转移函数不同。确定有限自动机对每一个可能的输入只有一个状态的转移。不确定有限自动机对每一个可能的输入可以有多个状态转移，接收到输入时从这多个状态转移中不确定地选择一个。 在本题中给出的图 M1 中，可以看到当在状态 A 输入 0 时，它可以转移到它自己，也可以转移到状态 B，所以 M1 是不确定的。而 M2 中不存在这样的情况，因此是确定的有限自动机。12.以下关于可视化
37、程序设计的叙述中，错误的是_。（分数：2.00）A.可视化程序设计使开发应用程序无须编写程序代码 B.可视化程序设计基于面向对象的思想，引入了控件和事件驱动C.在可视化程序设计中，构造应用程序界面就像搭积木D.在可视化程序设计中，采用解释方式可随时查看程序的运行效果解析：可视化程序设计主要是让程序设计人员利用软件本身所提供的各种控件，像搭积木似地构造应用程序的各种界面。可视化程序设计最大的优点是设计人员可以不用编写或只需编写很少的程序代码，就能完成应用程序的设计，这样能极大地提高设计人员的工作效率。在可视化程序设计中，可随时查看程序的运行效果。13.以下关于汇编语言的叙述中，错误的是_。（分数
38、：2.00）A.汇编语言源程序中的指令语句将被翻译成机器代码B.汇编程序先将源程序中的伪指令翻译成机器代码，然后再翻译指令语句 C.汇编程序以汇编语言源程序为输入，以机器语言表示的目标程序为输出D.汇编语言的指令语句必须具有操作码字段，可以没有操作数字段解析：面向机器的程序设计语言，使用汇编语言编写的程序，机器不能直接识别，要由一种程序将汇编语言翻译成机器语言，这种起翻译作用的程序叫汇编程序。汇编程序输入的是用汇编语言书写的源程序，输出的是用机器语言表示的目标程序。14.如图所示为一个有限自动机(其中，A 是初态，C 是终态)，该自动机识别的语言可用正规式_表示。（分数：2.00）A.(0|1
39、)*01 B.1*0*10*1C.1*(0)*01D.1*(0|10)*1*解析：被有限自动机所识别是指从初态开始到终态结束的字符串，所输入的字符串能够按顺序地执行下去，若到某个状态不能往下走得到下一个字符，则认为不能识别。 在本题中，选项 A 能被识别。从初态 A 出发，不管经过多少个 1 和 0 之后，只能是处在 A、B、C 3 种状态中的一种，所以在(0|1)*后，只能是处在 A、B、C 3 种状态中的一种，不管是在哪个状态，输入 0 后，都会处在状态 B，然后输入 1，都会转换到状态 C，因此选项 A 能被该有限自动机所识别。 同样的道理，可以知道其他选项的正规式不能被识别。15.算术
40、表达式 x-(y+c)*8 的后缀表达式是_。(-、+、*表示算术的减、加、乘运算，运算符的优先级和结合性遵循惯例)（分数：2.00）A.x y c 8-+*B.x y-c+8*C.x y c 8*-+D.x y c+8*- 解析：后缀表示也称为表达式的逆波兰表示。在这种表示方法中，将运算符号写在运算对象的后面，表达式中的运算符号按照计算次序书写。 对于表达式 x-(y+c)*8，先计算 y 与 c 的和，再乘以 8，最后用 x 减去这个计算结果，因此其后缀表达式为 xyc+8*-。16.传值与传址是函数调用时常采用的信息传递方式，_。（分数：2.00）A.在传值方式下，是将形参的值传给实参B
41、.在传值方式下，形参可以是任意形式的表达式C.在传址方式下，是将实参的地址传给形参 D.在传址方式下，实参可以是任意形式的表达式解析：在函数调用时，系统为形参准备，并把实参的值赋值到形参空间中。在调用结束后，形参空间将被释放，而实参的值保持不变，这就是传值方式。传值方式中实参与形参之间的数据传递是单向的，只能由实参传递给形参，因而即使形参的值在函数执行过程中发生了变化，也不会影响到实参值。在 C 语言中，当参数类型是非指针类型和非数组类型时，均采用传值方式。 传址方式把实参的地址赋值给形参，这样形参就可以根据地址值访问和更改实参的内容，从而实现双向传递。当参数类型是指针类型或数组类型时，均采用
42、传址方式。 区别于参数传值方式和返回值传递方式，传址方式具有以下明显的优势。 (1)参数传值方式是主调函数与被调函数之间的单向数据传递方式，而参数的传址方式则实现了二者之间的双向数据传递。 (2)函数的返回值每次只能把一个数据项从被调函数传递到主调函数，而参数的传址方式却可一次性地传递多个数据项到主调函数。17.若一种程序设计语言规定其程序中的数据必须具有类型，则有利于_。 在翻译程序的过程中为数据合理分配存储单元 对参与表达式计算的数据对象进行检查 定义和应用动态数据结构 规定数据对象的取值范围及能够进行的运算 对数据进行强制类型转换（分数：2.00）A.B. C.D.解析：一种程序设计语言
43、规定其程序中的数据必须具有类型，好处如下。 (1)有利于在翻译程序的过程中为数据合理分配存储单元，因为程序设计语言为不同的数据类型规定了其所占的存储空间，如果数据类型确定，其所占的存储空间也是确定的。 (2)有利于对参与表达式计算的数据对象进行检查，因为知道数据的数据类型，我们就可以根据类型来判断该数据是否可以参与某表达式计算，如自加、自减的操作数不允许是浮点数。只要根据数据的类型就能判断某操作数，是否能进行自加、自减运算。 (3)有利于规定数据对象的取值范围及能够进行的运算，根据数据类型，我们可以知道数据的存储空间，同时也能知道数据的表示范围，如 C 语言中的整型数据，它占两个字节(16 位
44、)，能表示的数据范围就是-2 16 至 2 16 -1。 综上所述，可知本题的正确答案选 B。18.下面 C 程序段中 count+语句执行的次数为_。 for(int i=1; i=11; i*=2) for(int j=1; j=i; j+) count+;（分数：2.00）A.15 B.16C.31D.32解析：本题中给出的是一个双重循环结构，循环体就是 count+。第一层循环的循环次数为 4 次，分别为i=1、2、4、8 的情况。而当 i=1 时，第二层循环 1 次；当 i=2 时，第二层循环 2 次；当 i=4 时，第二层循环 4 次；当 i=8 时，第二层循环 8 次。那么可知循
45、环体一共执行了 1+2+4+8=15 次。19.算术表达式(a-b)*c+d 的后缀表达式是_(-、+、*表示算术的减、加、乘运算，运算符的优先级和结合性遵循惯例)。（分数：2.00）A.abcd-*+B.ab-cd*+C.ab-c*d+ D.abc-d*+解析：本题要求通过中缀表达式，求后缀表达式(也称为逆波兰式)解答这类问题，可以借助于二叉树。因为中缀表达式对应于一棵二叉树的中序遍历，前缀表达式对应于二叉树的前序遍历，后缀表达式对应于二叉树的后序遍历，所以在本题中，需要先把二叉树构造出来。将表达式(a-b)*c+d 构造成二叉树，如图所示。 20.对于一个长度大于 1 且不存在重复元素的序
46、列，令其所有元素依次通过一个初始为空的队列后，再通过一个初始为空的栈。设队列和栈的容量都足够大，一个序列通过队列(栈)的含义是序列的每个元素都入队列(栈)且出队列(栈)一次且仅一次。对于该序列在上述队列和栈上的操作，正确的叙述是_。（分数：2.00）A.出队序列和出栈序列一定相同B.出队序列和出栈序列一定互为逆序C.入队序列与出队序列一定相同，入栈序列与出栈序列不一定相同 D.入栈序列与出栈序列一定互为逆序，入队序列与出队序列不一定互为逆序解析：本题主要考查队列和栈的特性。队列具有先进先出的特点，而栈具有后进先出的特点。因此我们可以知道入队序列与出队序列一定相同，但入栈序列与出栈序列不一定相同
47、。比如 a、b、c 这样一个序列，那么按照 a、b、c 的顺序入队列，那么其出队列的次序一定是 a、b、c。而按照 a、b、c 的顺序入栈，那么可能是 a 入栈后就出栈，然后 b 入栈又出栈，然后 c 入栈出栈。也可能是等 a、b、c 都入栈后再出栈，那么出栈序列就是 c、b、a。21.若二维数组 arr1M, N的首地址为 base，数组元素按列存储且每个元素占用 K 个存储单元，则元素 arri,j在该数组空间的地址为_。（分数：2.00）A.base+(i-1)*M+j-1)*KB.base+(i-1)*N+j-1)*KC.base+(j-1)*M+i-1)*K D.base+(j-1)
48、*N+i-1)*K解析：题目告诉我们是按列存储的，那么在存储元素 arri，j以前，应该存放了 j-1 列，而每一列中有M 个元素(即数组的行数)，那么应该有(j-1)M 个元素，而在第 j 列中，存放元素 arri，j以前，应该有 i-1 个元素被存放，因此，在存放元素 arri，j以前总共有(j-1)M+i-1 个元素被存放，而每个元素占用 K 个存储单元，因此本题答案选 C。22.对于线性表(由 n 个同类元素构成的线性序列)，采用单向循环链表存储的特点之一是_。（分数：2.00）A.从表中任意节点出发都能遍历整个链表 B.对表中的任意节点可以进行随机访问C.对于表中的任意一个节点，访问其直接前驱和直接后继节点所用时间相同D.第一个节点必须是头节点解析：采用单向循环链表存储的特点之一是从表中任
