>>>【希赛】2016年下半年软考分数早知道，希赛网解析真题

       软考历年真题是考生备考的法宝，希赛软考网整理了2016年下半年软件设计师考试真题之下午题，供大家参考学习。以下为2016年下半年软件设计师下午真题第二部分。

       试题三（共15分）

       阅读下列说明，回答问题1至问题3，将解答填入答题纸的对应栏内。

       【说明】

       某种出售罐装饮料的自动售货机（Vending Machine）的工作过程描述如下：

       （l）顾客选择所需购买的饮料及数量。

       （2）顾客从投币口向自动售货机中投入硬币（该自动售货机只接收硬币）。硬币器收集投入的硬币并计算其对应的价值。如果所投入的硬币足够购买所需数量的这种饮料且饮料数量足够，则推出饮料，计算找零，顾客取走饮料和找回的硬币；如果投入的硬币不够或者所选购的饮料数量不足，则提示用户继续投入硬币或重新选择饮料及数量。

       （3）一次购买结束之后，将硬币器中的硬币移走（清空硬币器），等待下一次交易。自动售货机还设有一个退币按钮，用于退还顾客所投入的硬币。已经成功购买饮料的

       钱是不会被退回的。

       现采用面向对象方法分析和设计该自动售货机的软件系统，得到如图3-1所示的用例图，其中，用例“购买饮料”的用例规约描述如下。

       参与者：顾客。

       主要事件流：

       1．顾客选择需要购买的饮料和数量，投入硬币；

       2．自动售货机检查顾客是否投入足够的硬币；

       3．自动售货机检查饮料信存仓中所选购的饮料是否足够；

       4．自动售货机推出饮料；

       5．自动售货机返回找零。

       各选事件流：

       2a．若投入的硬币不足，则给出提示并退回到1；

       3a．若所选购的饮料数量不足j,则给出提示并退回到1。

       根据用例“购买饮料”得到自动售货机的4个状态：“空闲”状态、“准备服务”状态、“可购买”状态以及“饮料出售”状态，对应的状态图如图3-2所示。

       所设计的类图如图3-3所示。

       【问题1】（6分）

       根据说明中的描述，使用说明中的术语，给出图3-2中的S1～S4所对应的状态名。

       【问题2】（4分）

       根据说明中的描述，使用说明中的术语，给出图3-2中的E1～E4所对应的事件名。

       【问题3】（5分）

       根据说明中的描述，使用说明中的术语，给出图3-3中CI～C5所对应的类名。

       试题四（共15分）

       阅读下列说明和C代码，回答问题1至问题3，将解答写在答题纸的对应栏内。

       【说明】

       模式匹配是指给定主串t和子串s，在主串t中寻找子串s的过程，其中s称为模式。

       如果匹配成功，返回s在t中的位置，否则返回-1。

       KMP算法用next数组对匹配过程进行了优化。KMP算法的伪代码描述如下：

       1．在串t和串s中，分别设比较的起始下标i=J=O

       2．如果串t和串s都还有字符，则循环执行下列操作：

       （1）如果j=-l或者t[i]-s[j]，则将i和j分别加1，继续比较t和s的下一个字符；

       （2）否则，将j向右滑动到next[j]的位置，即j=next[J]

       3．如果s中所有字符均已比较完毕，则返回匹配的起始位置（从1开始）；否则返回一1．

       其中，next数组根据子串s求解。求解next数组的代码已由get_next函数给出。

       【C代码】

       （1）常量和变量说明

       t，s：长度为悯铂Is的字符串

       next:next数组，长度为Is

       （2）C程序

       #include<stdio．h>

       #nclude<stdliB．h>

       #include<string．h>

       ／*求next[]的值*/

       void get_next（int *next,char *s,int Is）{

       int i=0，j=-1；

       next[0]=-1；/*初始化next[0]*／

       while（i<ls）{/*还有字符*／

       if（j=-1 || s[i]=s[j]）{／*匹配*／

       j++；

       i++；

       if（s[i]一s[jl）

       next[i]-next[j];

       else

       Next[i]=j；

       }

       else

       J=next[j]；

       }

       }

       int kmp（int*next,char*t,char*s,int.lt,int Is）

       {

       inti=0,j=0;

       while（i<lt &&（1）{

       if（j=-1 II 2_）{

       i++;

       j++;

       }else

       （3）:

       }

       if（j>=ls）

       Return（4）

       else.

       return -1；

       【问题1】（8分）

       根据题干说明，填充C代码中的空（1）～（4）.

       【问题2】（2分）

       根据题干说明和C代码，分析出kmp算法的时间复杂度为（5）(主串和子的长度分别为It和Is，用O符号表示）。

       【问题3】（5分）

       根据C代码，字符串“BBABBCAC”的next数组元素值为（6）(直接写素值，之间用逗号隔开）。若主串为“AABBCBBABBCACCD”，子串为“BBABBCAC则函数Kmp的返回值是（7）。

       >>>返回目录：2016年下半年软件设计师考试真题（下午题）

       >>>2016年下半年软件设计师考试下午真题答案与解析

       相关推荐：

       软件设计师考试历年真题答案与解析

       2017年软件设计师考试辅导教材推荐

       软件设计师考试培训视频教程