2018年下半年软件设计师试题及答案上午题 (1) 下载本文

内容发布更新时间 : 2024/6/16 2:39:04星期一 下面是文章的全部内容请认真阅读。

48. 在以阶段划分的编译器中,( )阶段的主要作用是分析程序中的句子结构是否正确。 A.词法分析 B.语法分析 C.语义分析 D.代码生成

参考答案B 试题解析:

1、词法分析阶段:识别出一个个的单词,删掉无用的信息,报告分析时的错误。

2、语法分析阶段:语法分析器以单词符号作为输入,分析单词符号是否形成符合语法规则的语法单位,如表达式、赋值、循环等,按语法规则分析检查每条语句是否有正确的逻辑结构。语法分析构造一棵语法树。

3、语义分析阶段:主要检查源程序是否存在语义错误,并收集类型信息供后面的代码生成阶段使用,如:赋值语句的右端和左端的类型不匹配。表达式的除数是否为零等。

49. 下图所示为一个不确定有限自动机(NFA)的状态转换图。该NFA可识别字符串( )。

A.0110

参考答案A 试题解析:

由答案可知以0开始以0结尾,所以只有A符合。

50.函数f和g的定义如下图所示。执行函数f时若采用引用(call by reference)方式调用函数g(a),则函数f的返回值为( )。

B.0101

C.1100

D.1010

A.14 参考答案D 试题解析:

代入可知m=2*5;x=10-1; return x+m=19 19+9=28

51. 数据库系统中的视图、存储文件和基本表分别对应数据库系统结构中的( )。 A.模式、内模式和外模式 B.外模式、模式和内模式

B.18

C.24

D.28

C.模式、外模式和内模式 D.外模式、内模式和模式 参考答案D 试题解析:

本题考察的是数据库体系结构:三层模式。对于题干给出的视图、存储文件、基本表分别对应:视图-外模式,存储文件-内模式,基本表-模式。因此本题选择D选项

52. 在分布式数据库中,( )是指用户或应用程序不需要知道逻辑上访问的表具体如何分块存储。 A.逻辑透明 B.位置透明 C.分片透明 D.复制透明 参考答案C 试题解析:

本题考查的是分布式数据库相关知识。

1.逻辑透明性(局部映像透明性):它是最低层次的透明性,该透明性提供数据到局部数据库的映像,即用户不必关心局部DBMS支持哪种数据模型、使用哪种数据操纵语言,数据模型和操纵语言的转换是由系统完成的。因此,局部映像透明性对异构型和同构异质的分布式数据库系统时非常重要的。2.位置透明性:用户不必知道所操作的数据放在何处,即数据分配到哪个或哪些站点存储对用户是透明的。因此,数据分片模式的改变,如把数据从一个站点转移到另一个站点将不会影响应用程序,因而应用程序不必改写。

3.分片透明性:用户不必关心数据是如何分片,他们对数据的操作在全局关系上进行的,即关心如何分片对用户是透明的,因此,当分片改变时应用程序可以不变。

4.复制透明性:用户不用关心数据库在网络中的各个节点的复制情况,被复制的数据的更新都由系统自动完成。

53.54 设有关系模式R(A1,A2,A3,A4,A5,A6),函数依赖集F={A1→A3,A1 A2→A4,A5 A6→A1,A3 A5→A6,A2 A5→A6}。关系模式R的一个主键是( ), 从函数依赖集F可以推出关系模式R( )。 A.A1A4

A.不存在传递依赖,故R为1NF B.不存在传递依赖,故R为2NF C.存在传递依赖,故R为3NF

D.每个非主属性完全函数依赖于主键,故R为2NF 参考答案B.D 试题解析:

把每个选项代入求它的闭包,A2A5能推出所有属性的为主键。

第二空,根据第一空可知R的一个主键为A2A5,由函数依赖集F可知,存在A2A5→A6,A5A6→A1,A1→A3,这里存在传递函数依赖,故A、B选项均不正确,C选项本身不正确,存在非主属性对候选键的传递函数依赖,是不满足3NF的。因此本题选择D选项。

55.56给定关系R(A, B,C,D)和S(C,D,E),若关系R与S进行自然连接运算,则运算后的元组属性列数为( );关系代数表达

B.A2A5

C.A3A4

D.A4A5

式A.4

B.5

与( )等价。 C.6

D.7

参考答案B.D 试题解析:

对于自然连接只要把重复的列去掉就可以所以为5. 第二空和选项等价的为D选项

57.栈的特点是后进先出,若用单链表作为栈的存储结构,并用头指针作为栈顶指针,则( )。 A.入栈和出栈操作都不需要遍历链表 B.入栈和出栈操作都需要遍历链表 C.入栈操作需要遍历链表而出栈操作不需要 D.入栈操作不需要遍历链表而出栈操作需要 参考答案A 试题解析:

本题用单链表作为栈的存储结构,因为栈的操作是先进后出,因此无论是入栈还是出栈,都只对栈顶元素操作,而在单链表中用头指针作为栈顶指针,此时无论是出栈还是入栈,都只需要对头指针指向的栈顶指针操作即可,不需要遍历链表。

58. 已知某二叉树的先序遍历序列为A B C D E F、中序遍历序列为B A D C F E,则可以确定该二叉树( )。 A.是单支树(即非叶子结点都只有一个孩子) B.高度为4(即结点分布在4层上) C.根结点的左子树为空 D.根结点的右子树为空 参考答案B 试题解析:

根据先序遍历和中序遍历序列可以构造出二叉树高度为4的所以选择B

59. 可以构造出下图所示二叉排序树(二叉检索树、二叉查找树)的关键码序列是( )。

A.10 13 17 19 23 27 31 40 65 91 B.23 40 91 17 19 10 31 65 27 13 C.23 19 40 27 17 13 10 91 65 31 D.27 31 40 65 91 13 10 17 23 19 参考答案B 试题解析:

根据排序二叉树的构造过程,可知A选项的根节点为10,D选项的根节点为27,因此可以排除。对于C选项,构造根节点的子

结点,可知19为其左孩子结点,与图不符。本题只有B选项可以构造出图示的排序二叉树。

60.61 图G的邻接矩阵如下图所示(顶点依次表示为v0、v1、v2、v3、v4、v5),G是( )。对G进行广度优先遍历(从v0开始),可能的遍历序列为( )。

A.无向图

A.v0、v1、v2、v3、v4、v5 B.v0、v2、v4、 v5、v1、v3 C.v0、v1、v3、v5、v2、v4 D.v0、v2、v4、v3、v5、v1 参考答案B.A 试题解析:

B.有向图

C.完全图

D.强连通图

62~65 在一条笔直公路的一边有许多房子,现要安装消防栓,每个消防栓的覆盖范围远大于房子的面积,如下图所示。现求解能覆盖所有房子的最少消防栓数和安装方案(问题求解过程中,可将房子和消防栓均视为直线上的点)。

该问题求解算法的基本思路为:从左端的第一栋房子开始,在其右侧m米处安装一个消防栓,去掉被该消防栓覆盖的所有房子。在剩余的房子中重复上述操作,直到所有房子被覆盖。算法采用的设计策略为( );对应的时间复杂度为( )。

假设公路起点A的坐标为0,消防栓的覆盖范围(半径)为20米,10栋房子的坐标为(10,20,,30,35,60,80,160,210,260,300),单位为米。根据上述算法,共需要安装( )个消防栓。以下关于该求解算法的叙述中,正确的是( )。 A.分治

B.动态规划 C.贪心 D.回溯

A.4

B.5

C.6

D.7

参考答案:A.B.B.C 试题解析: (一)

对于第一空,本题使用的是分治法。

1、 分治法特征:对于一个规模为n的问题,若该问题可以容易地解决(比如说规模n较小)则直接解决;否则将其