练习题

一、选择题

1.以下有关串的描述中，（ ）是不正确的。

A.串是字符的有限序列

B.子串是串中任意连续字符组成的子序列

C.串可以采用顺序存储或链式存储

D.空串是由一个或多个空格组成的串

2.串的长度是指（ ）。

A.串中包含的字符个数　B.串中包含的不同字符个数

C.串中除空格以外的字符个数　D.串中包含的不同字母个数

3.若串中字符经常发生变化，则采用（ ）存储方式最合适。

A.定长顺序　B.堆　C.链式　D.散列

4.串也是一种线性表，只不过（ ）。

A.数据元素是子串　B.数据元素均为字符

C.数据元素数据类型不受限制　D.表长受到限制

5.设有两个串S和T，求T在S中首次出现的位置的运算是（ ）运算。

A.求子串　B.串插入　C.串连接　D.模式匹配

6.已知两个串S＝“abcczym”和T＝“abccyzm”，则StrCmp操作的结果是（ ）。

A.－1　B.0　C.1　D.64

7.在KMP算法中，若模式串T中存在tj＝tk（k＝next［j］），且si≠tj时，则下一次不必与tk进行比较，而直接和（ ）进行比较。

A.t　kB.tnext［k］　C.tnext［j］　D.tj

8.模式串“abccabab”的next值为（ ）。

A.－1 0 0 0 0 1 2 1　B.－1 0 0 1 0 1 2 1

C.－1 0 1 0 0 2 1 2　D.－1 0 1 2 0 0 0 1

9.模式串“cbcacbcab”的nextval值为（ ）。

A.－1 0 1 1 0 0－1 1 4　B.－1 0－1 1－1 0－1 1 4

C.－1 0 0 0－1 0 0 1 4　D.－1 0 0 1 2 0 0 1 4

10.Brute－Force算法在最坏情况下的时间复杂度为（ ）。

A.O（n＋m）　B.O（n－m）　C.O（n×m）　D.O（n÷m）

二、填空题

1.一个串的任意连续字符组成的子序列称为串的_________________，该串称为_________________。

2.串长度为0的串称为_________________，只包含空格的串称为_________________。

3.若两个串的长度相等且对应位置上的字符也相等，则称两个串_________________。

4.模式串T＝“abcacbababcabcccbbaa”的next［j］函数值为_________________，nextval［j］函数值为_________________。

5.寻找子串在主串中的位置，称为_________________。其中，主串又称为_________________，子串又称为_________________。