免费智能真题库 > 历年试卷 > 软件设计师 > 2016年下半年 软件设计师 下午试卷 案例
  第4题      
  知识点：   常量   数组   常量和变量

 
阅读下列说明和C代码，回答问题1至问题3，将解答写在答题纸的对应栏内。
【说明】
模式匹配是指给定主串t和子串s，在主串t中寻找子串s的过程，其中s称为模式。如果匹配成功，返回s在t中的位置，否则返回-1。
KMP算法用next数组对匹配过程进行了优化。KMP算法的伪代码描述如下：
1．在串t和串s中，分别设比较的起始下标i=j=0。
2．如果串t和串s都还有字符，则循环执行下列操作：
（1）如果j=-1或者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）常量和变量说明

（2）C程序
 
问题：4.1   根据题干说明，填充C代码中的空（1）～（4）.
 
问题：4.2   根据题干说明和C代码，分析出kmp算法的时间复杂度为（5）（主串和子串的长度分别为lt和ls，用O符号表示）。
 
问题：4.3   根据C代码，字符串“BBABBCAC”的next数组元素值为（6）（直接写素值，之间用逗号隔开）。若主串为“AABBCBBABBCACCD”，子串为“BBABBCAC”，则函数Kmp的返回值是（7）。
 
 
 

   知识点讲解    
   · 常量    · 数组    · 常量和变量
 
       常量
        与C语言不同，使用final关键字，C++语言则是const，如final float pi=3.14f、 final byte c=12。浮点常数后面要加"f"，如12.7f、 1.02f。
 
       数组
               数组的定义及基本运算
               n维数组是一种"同构"的数据结构，其每个元素类型相同、结构一致。数组是定长线性表在维数上的扩张，即线性表中的元素又是一个线性表。
               数组结构的特点是：数据元素数目固定；数据元素具有相同的类型；数据元素的下标关系具有上下界的约束且下标有序。
               对数组进行的基本运算有以下两种。
               （1）给定一组下标，存取相应的数据元素。
               （2）给定一组下标，修改相应的数据元素中某个数据项的值。
               数组的顺序存储
               一旦定义了数组，结构中的数据元素个数和元素之间的关系就不再发生变动，因此数组适合于采用顺序存储结构。
               由于计算机的内存结构是一维线性的，因此存储多维数组时必须按照某种方式进行降维处理，即将数组元素排成一个线性序列，这就产生了次序约定问题。对二维数组有两种存储方式：一种是以列为主序的存储方式；另一种是以行为主序的存储方式。
               设每个数据元素占用L个单元，m、n为数组的行数和列数，那么以行为主序优先存储的地址计算公式为
               Loc(aij)=Loc(a11)+((i-1)n+(j-1))L
               同样的，以列为主序优先存储的地址计算公式为
               Loc(aij)=Loc(a11)+((j-1)m+(i-1))L
 
       常量和变量
        按照程序运行时数据的值能否改变，将程序中的数据分为常量和变量。程序中的数据对象可以具有左值和（或）右值，左值指存储单元（或地址、容器），右值是值（或内容）。变量具有左值和右值，在程序运行过程中其右值可以改变；常量只有右值，在程序运行过程中其右值不能改变。
   题号导航      2016年下半年 软件设计师 下午试卷 案例   本试卷我的完整做题情况  
1 /
2 /
3 /
4 /
5 /
6 /
 
第4题    在手机中做本题