2016下半年软件设计师考试真题及答案-下午卷

（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 #nclude #include ／*求next【】的值*/

void get_next（ int *next, char *s, int int i=0，j=-1；

next[0]=-1；/*初始化next[0]*／ while（i< ils）{/*还有字符*／ if（j=-1l ls[i]=s[j]）{／*匹配*／ j++； i++；

if（ s[i]一s[jl） next [i]- next[j]; else Next[i]=j； } else

J= next[j]；

11

Is） { } }

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

inti= 0,j =0 ;

while （i

（3） : }

if （j>= ls）

Retum （4） else . retum-1； 【问题1】（8分）

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

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

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

12

（3）：get_next(next, s, ls);

j=next[j]; （4）：i+1-ls; 问题2：

问题3：（6）：[-1,-1,1,-1,-1,2,0,0]，（7）6。 试题分析：

本题问题1根据KMP算法的伪代码描述进行推导。

根据伪代码中第2步可以推导（1）是判断字符串s是否还有字符，即j

根据伪代码第2.1步可以推导（2）是判断字符串t和字符串s当前位置的字符是否相同，即t[i]==s[j]。

根据伪代码第2.2步可以推导（3）是当第2.1步判断条件不满足时，改变j所指向的字符位置。即调用函数get_next(next, s, ls)，且j=next[j]。

根据伪代码第3步可以推导（4）是返回匹配的起始位置。由于当前i所指向字符串中匹配子串的最后一个字符的位置，且已知子串的长度为ls。（4）的代码为i+1-ls。 本题问题2是计算KMP算法的复杂度。

本题问题3中已知字符串“BBABBCAC”，则根据get_next()函数可以求得next数组的元素值为[-1,-1,1,-1,-1,2,0,0]。并计算得到起始位置为6。

试题五（共15分）

阅读下列说明和C++-代码，将应填入 （n） 处的字句写在答题纸的对应栏内。 【说明】

某发票（lnvoice）由抬头（Head）部分、正文部分和脚注（Foot）部分构成。现采用装饰（ Decorator）模式实现打印发票的功能，得到如图5-1所示的类图。

13

【C++代码】

#include using namespace std； class invoice{ public：

（1） {

cout《 \is the content of the invoice!\《 endl; } };

class Decorator : public invoice { Invoice *ticket; public:

Decorator（lnvoice *t） { ticket = t; } void printinvoice（）{ if（ticket != NULL） （2）； } };

class HeadDecorator : public Decorator{

14

public:

HeadDecorator（lnvoice*t）: Decorator（t） { } void printinvoice0 { cout

《 \is the header of the invoice! \endl; （3） ； } }；

class FootDecorator : public Decorator{ public:

FootDecorator（invoice *t）: Decorator（t） { } void printlnvoice（） {

（4） ；

cout《 \is the footnote 《 endl; } };

int main（void） { Invoice t;

FootDecorator f（&t）; HeadDecorator h（&f）; H.printlnvoice（）;

cout< < “_____”< < endl;

or a（NULL）;

HeadDecorator b（ （5） ）; B．printinvoice（）;

15

of the invoice!\ FootDecorat