免费智能真题库 > 历年试卷 > 软件设计师 > 2012年上半年 软件设计师 上午试卷 综合知识
  第58题      
  知识点:   
  关键词:   函数   模式匹配   匹配算法   字符串   算法        章/节:   计算机软件知识       

 
在字符的KMP模式匹配算法中,需要求解模式p的next函数值,其定义如下所示。若模式p为“aaabaaa”,则其next函数值为(58)。

 
 
  A.  0123123
 
  B.  0123210
 
  C.  0123432
 
  D.  0123456
 
 
 

 
  第1题    2018年上半年  
   49%
对有n个结点、e条边且采用数组表示法(即邻接矩阵存储)的无向图进行深度优先遍历,时间复杂度为(1)。
  第62题    2009年下半年  
   56%
字符串采用链表存储方式时,每个结点存储多个字符有助于提高存储密度。若采用结点大小相同的链表存储串,在串比较、求子串、串连..
  第58题    2016年上半年  
   40%
设有二叉排序树(或二叉查找树)如下图所示,建立该二叉树的关键码序列不可能是(58)。
   知识点讲解    
   · 
 
       串
               串的定义及基本运算
               串是仅由字符构成的有限序列,是取值范围受限的线性表。一般记为S='a1a2an',其中S是串名,a1a2an是串值。
               下面介绍串的几个基本概念。
               (1)空串:长度为零的串,空串不包含任何字符。
               (2)空格串:由一个或多个空格组成的串。
               (3)子串:由串中任意长度的连续字符构成的序列。含有子串的串称为主串。子串在主串中的位置指子串首次出现时,该子串的第一个字符在主串中的位置。空串是任意串的子串。
               (4)串相等:指两个串长度相等且对应位置上的字符也相同。
               (5)串比较:两个串比较大小时以字符的ASCII码值作为依据。比较操作从两个串的第一个字符开始进行,字符的ASCII码值大者所在的串为大;若其中一个串先结束,则以串长较大者为大。
               对串进行的基本操作有以下几种。
               (1)赋值操作StrAssign(s,t):将串t的值赋给串s。
               (2)连接操作Concat(s,t):将串t接续在串s的尾部,形成一个新串。
               (3)求串长StrLength(s):返回串s的长度。
               (4)串比较StrCompare(s,t):比较两个串的大小。
               (5)求子串SubString(s,start,len):返回串s中从start开始的、长度为len的字符序列。
               串的存储结构
               1)串的静态存储:定长存储结构
               串的顺序存储结构是用一组地址连续的存储单元来存储串值的字符序列。由于串中的元素为字符,所以可通过程序语言提供的字符数组定义串的存储空间,也可以根据串长的需要动态申请字符串的空间。
               2)串的链式存储:块链
               串也可采用链表方式作为存储结构,当用链表存储串中的字符时,每个节点中可以存储一个字符,也可以存储多个字符,要考虑存储密度的问题。在链式存储结构中,节点大小的选择和顺序存储方法中数组空间大小的选择一样重要,它直接影响对串处理的效率。
               串的模式匹配
               子串的定位操作通常称为串的模式匹配,它是各种串处理系统中最重要的运算之一。子串也称为模式串。
               1)朴素的模式匹配算法
               朴素的模式匹配算法也称为布鲁特一福斯算法,其基本思想是:从主串的第一个字符起与模式串的第一个字符比较,若相等则继续逐个字符进行后续的比较,否则从主串的第二个字符起与模式串的第一个字符重新比较,直至模式串中的每个字符依次和主串中的一个连续的字符序列相等,则称匹配成功,否则称匹配失败。
               该算法在最好情况下匹配算法的时间复杂度为O(n+m),而在最坏情况下的时间复杂度为O(n×m)。
               2)改进的模式匹配算法
               改进的模式匹配算法又称为KMP算法,其改进之处在于:每当匹配过程中出现相比较的字符不相等时,不需要回溯主串的指针,而是利用已经得到的"部分匹配"的结果,将模式串向后"滑动"尽可能远的距离,再继续进行比较。
               此算法的时间复杂度为O(n+m)。
   题号导航      2012年上半年 软件设计师 上午试卷 综合知识   本试卷我的完整做题情况  
1 /
2 /
3 /
4 /
5 /
6 /
7 /
8 /
9 /
10 /
11 /
12 /
13 /
14 /
15 /
 
16 /
17 /
18 /
19 /
20 /
21 /
22 /
23 /
24 /
25 /
26 /
27 /
28 /
29 /
30 /
 
31 /
32 /
33 /
34 /
35 /
36 /
37 /
38 /
39 /
40 /
41 /
42 /
43 /
44 /
45 /
 
46 /
47 /
48 /
49 /
50 /
51 /
52 /
53 /
54 /
55 /
56 /
57 /
58 /
59 /
60 /
 
61 /
62 /
63 /
64 /
65 /
66 /
67 /
68 /
69 /
70 /
71 /
72 /
73 /
74 /
75 /
 
第58题    在手机中做本题