数据结构 | 每日一练（98）

数据结构

合抱之木,生于毫末;九层之台,起于累土;千里之行,始于足下

——老子

1

每日一练

判断题

1．KMP 算法的特点是在模式匹配时指示主串的指针不会变小。（ ）

2．设模式串的长度为 m,目标串的长度为 n，当 n≈m 且处理只匹配一次的模式时，朴素的匹配（即子串定位函数）算法所花的时间代价可能会更为节省。（ ）

3．串是一种数据对象和操作都特殊的线性表。（ ）

填空题

1．空格串是指__(1)__，其长度等于___(2)__。

2．组成串的数据元素只能是________。

3．一个字符串中________称为该串的子串 。

4．INDEX（‘DATASTRUCTURE’， ‘STR’）=________。

5．设正文串长度为 n，模式串长度为 m，则串匹配的 KMP 算法的时间复杂度为________。

正确答案

PS：||代表注释

1.√ 2.√ 3.√

1．(1) 由空格字符（ASCII值32）所组成的字符串 (2)空格个数

2．字符

3．任意个连续的字符组成的子序列

4．5

5.O(m+n)