2014年下半年（上午）《软件设计师》真题

试卷预览

1 单选题 1分

DHCP客户端可从DHCP服务器获得（　　）。

查看答案 开始考试

正确答案：B

本题解析：

本试题考查DHCP协议的工作原理。

DHCP客户端可从DHCP服务器获得本机IP地址、DNS服务器的地址、DHCP服务器的地址、默认网关的地址等，但没有Web服务器、邮件服务器地址。

2 单选题 1分

在字符串的KMP模式匹配算法中，需先求解模式串的next函数值，其定义如下式所示，j表示模式串中字符的序号（从1开始）。若模式串p为“abaac”，则其next函数值为（　　）。

查看答案 开始考试

正确答案：B

本题解析：

＜k＜k＜k＜j的数k，由（3）式，next[2]=1；

＜k＜j的数k=2，同时需要满足'p1p2lpk-1'="pj-k+1pj-k+2Lpj-1"。

＜k＜j的数k=2或3：

＜k＜j的数k=2、3或4：

本题考查字符串的模式匹配运算知识。

KMP是进行字符串模式匹配运算效率较高的算法。根据对next函数的定义，模式串前两个字符的next值为0、1。对于第3个字符“a”，其在模式串中的前缀为“ab”，从该子串找不出前缀和后缀相同的部分，因此，根据定义，该位置字符的next值为1。

对于第4个字符“a”，其在模式串中的前缀为“aba”，该子串只有长度为1的前缀“a”和后缀“a”相同，根据定义，该位置字符的next值为2。

对于第5个字符“a”，其在模式串中的前缀为“abaa0”，该子串只有长度为1的前缀“a”和后缀“a”相同，根据定义，该位置字符的next值为2。

综上可得，模式串“abaac”的next函数值为01122。

一、对于公式：

1、由（1）式，当j=1时，next[1]=0；

2、当j=1时，由（2）式，max{k|1＜k＜k3、取值范围，j、k都为正整数，且1＜=j＜=5

【可根据下面的具体过程理解公式】

二、本题计算如下：

1、j=1，由（1）式，next[1]=0；

2、j=2，找不到满足1＜k＜j的数k，由（3）式，next[2]=1；

3、j=3，满足1＜k＜j的数k=2，同时需要满足'p1p2lpk-1'="pj-k+1pj-k+2Lpj-1"。

'p1p2Lpk-1'='p1p2Lp1'=p1，为第一个字母a；'pj-k+1pj-k+2Lpj-1'='p2p3Lp2'=p2，为第二个字母b，a!=b，此时，找不到k不满足条件，由（3）式，next[3]=1。

4、j=4，满足1＜k＜j的数k=2或3：

（1）当k=2，'p1p2Lpk-1'='p1p2Lp1'=p1，为第一个字母a，'pj-k+1pj-k+2Lpj-1'='p3p4Lp3'=p3，为第三个字母a，满足'p1p2Lpk-1'='pj-k+1pj-k+2Lpj-1'。

（2）当k=3，'p1p2Lpk-1'='p1p2Lp2'=p1p2，为第一二字母ab，'pj-k+1pj-k+2Lpj-1'='p2p3Lp3'=p2p3，为第二三个字母ba，不满足'p1p2Lpk-1'='pj-k+1pj-k+2Lpj-1'。

综上可得，当j=4时，满足条件的最大k值为2，next[4]=2。

5、j=5，满足1＜k＜j的数k=2、3或4：

（1）当k=2，'p1p2Lpk-1'='p1p2Lp1'=p1，为第一个字母a，'pj-k+1pj-k+2Lpj-1'='p4p5Lp4'=p4，为第四个字母a，满足'p1p2Lpk-1'='pj-k+1pj-k+2Lpj-1'。

（2）当k=3，'p1p2Lpk-1'='p1p2Lp2'=p1p2，为第一二字母ab，'pj-k+1pj-k+2Lpj-1'='p3p4Lp4'=p3p4，为第三四个字母aa，不满足'p1p2Lpk-1'='pj-k+1pj-k+2Lpj-1'。

（3）当k=4，'p1p2Lpk-1'='p1p2Lp3'=p1p2p3，为第一二三字母aba，'pj-k+1pj-k+2Lpj-1'='p2p3Lp4'=p2p3p4，为第二三四个字母baa，不满足'p1p2Lpk-1'='pj-k+1pj-k+2Lpj-1'。

综上可得，当j=5时，满足条件的最大k值为2，next[5]=2。

根据上面的分析过程，可以得出next[]函数值为01122。

3 单选题 1分

某个二叉查找树（即二叉排序树）中进行查找时，效率最差的情形是该二叉查找树是（　　）。

查看答案 开始考试

正确答案：C

本题解析：

单枝树时该二叉查找树效率最低。

4 单选题 1分

给定关系模式R（U，F），U={A，B，C，D，E，H}，函数依赖集F={A→B,A→C,C→D，AE→H}。关系模式R的候选关键字为（　　）。

查看答案 开始考试

正确答案：C

本题解析：

关系中的某一属性或属性组的值能唯一的标识一个元组，而其任何真子集都不能再标识，则称该属性组为候选码。

R的候选关键字为AE。

5 单选题 1分

对于大多数通用程序设计语言，用（　　）描述其语法即可。

查看答案 开始考试

正确答案：B

本题解析：

上下文无关文法：形式语言理论中一种重要的变换文法，用来描述上下文无关语言，在乔姆斯基分层中称为2型文法。由于程序设计语言的语法基本上都是上下文无关文法，因此应用十分广泛。

6 单选题 1分

UML图中，一张交互图显示一个交互。由一组对象及其之间的关系组成，包含它们之间可能传递的消息。（　　）不是交互图。

查看答案 开始考试

正确答案：B

本题解析：

交互图由一组对象和它们之间的关系构成，其中包括：需要什么对象，对象相互之间发送什么消息，什么角色启动消息以及消息按什么顺序发送。交互图的分类：交互图主要分为这两种：顺序图和协作图。对象图不是交互图的一种。

顺序图（sequencediagram，序列图）。顺序图是一种交互图（interactiondiagram），交互图展现了一种交互，它由一组对象或参与者以及它们之间可能发送的消息构成。交互图专注于系统的动态视图。顺序图是强调消息的时间次序的交互图。

对象图（objectdiagram）。对象图描述一组对象及它们之间的关系。对象图描述了在类图中所建立的事物实例的静态快照。和类图一样，这些图给出系统的静态设计视图或静态进程视图，但它们是从真实案例或原型案例的角度建立的。

通信图（communicationdiagram）。通信图也是一种交互图，它强调收发消息的对象或参与者的结构组织。顺序图和通信图表达了类似的基本概念，但它们所强调的概念不同，顺序图强调的是时序，通信图强调的是对象之间的组织结构（关系）。在UML1.X版本中，通信图称为协作图（collaborationdiagram）。

7 单选题 1分

以下关于软件维护和可维护性的叙述中，不正确的是（　　）。

查看答案 开始考试

正确答案：D

本题解析：

在软件开发的各个阶段都需考虑软件的可维护性。

8 单选题 1分

以下关于CMM的叙述中，不正确的是（　　）。

查看答案 开始考试

正确答案：B

本题解析：

CMM（CapabilityMaturityModel）是能力成熟度模型的缩写，CMM是国际公认的对软件公司进行成熟度等级认证的重要标准。CMM共分五级。在每一级中，定义了达到该级过程管理水平所应解决的关键问题和关键过程。每一较低级别是达到较高级别的基础。其中五级是最高级，即优化级，达到该级的软件公司过程可自发地不断改进，防止同类问题二次出现；四级称为已管理级，达到该级的软件公司已实现过程的定量化；三级为已定义级，即过程实现标准化；二级为可重复级，达到该级的软件公司过程已制度化，有纪律，可重复；一级为初始级，过程无序，进度、预算、功能和质量等方面不可预测。

9 单选题 1分

假设段页式存储管理系统中的地址结构如下图所示，则系统（　　）。

查看答案 开始考试

正确答案：D

本题解析：

该题在2013年下半年考过类似的题目，从图中可见，页内地址的长度为12位，212=4096，即4K，页号长度为21-12+1=10，210=1024，段号长度为31-22+1=10，210=1024。故正确答案为D。

10 单选题 1分

假设系统采用PV操作实现进程同步与互斥。若n个进程共享两台打印机，那么信号量S的取值范围为（　　）。

查看答案 开始考试

正确答案：D

本题解析：

有两台打印机，故信号量初值为2。前两个进程请求能够满足。当有进程运行时，其他进程访问信号量，信号量就会减一，n个进程同时请求两台打印机时为n-2。