第4章 串(习题)
-
第
4
章
串
习题
一、
选择题
1
、如下陈述中正确的是（
）
A
．串是一种特殊的线性表
B
．串的长度必须大于零
C
．串中元素只能是字母
D
．空串就是空白串
2
、设有两个串
p
和
q
，其中
q
是
p
的子串，求
q
在
p<
/p>
中首次出现的位置的算法称为（
）
A
．求子串
B
．联接
C
．匹配
D
．求串长
3
、串”
ababaaababaa
”的
next
数组为（
）
。
A
．
B
．
C
．
D
．
5
4
、
串是
_____________
。
A.
不少于一个字母的序列
B.
任意个字母的序列
C.
不少于一个字符的序列
D.
有限个字符的序列
5
、串的长度是指（
）
A
．串中所含不同字母的个数
B
．串中所含字符的个数
C
．串中所含不同字符的个数
D
．串中所含非空格字符的个数
二、填空题
1
、设正文串长度为
n
，模式串长度为
m
，则串匹配的
KMP
算法的时间复杂
度为
________
。
。
2
、一个字符串中
_
_______
称为该串的子串
。
3
、串
是一种特殊的线性表，其特殊性表现在
__
__
；串的两种最基本的存储方式是
____
、
__
__
；两个串相等的充分必要条件是
____
。
4
、
INDEX
（
‘
MY
STUDENT
’
，
‘
STU
’
）
=________
。
5<
/p>
、设正文串长度为
n
，模式串长度为
m
，则串匹配的
KMP
算法的时间复杂度为
________
。
< br>
6
、设串
S
的长度为
n,
则
S
的子串个数为
________
7
、字符串”
mnmnmmmn
”的
< br>nextval
函数值为
________
。
8
、设
T
和
P
是两个给定的串，在
T
中寻找等于
P
的子串的过程称为
__ __
，又称
P
为
_
__
。
9
、下列程序判断字符串
s
是否对称，对称则返回
1
，否则返回
0
；如
f(
返回
1
，
f(
返回
0
；
int f(_______)
{int
i=0,j=0;
while (s[j])________;
目标串的长度为
for(j--; i
return(_______);
}
三、
判断题
1
、
KMP
算
法的特点是在模式匹配时指示主串的指针不会变小。
2
、
设模式串的长度为
m,
n
，
当
n
≈
m
且处理只匹配一次
的模式时，
朴素的匹
配（即子串定位函数）算法所花的时间代价
可能会更为节省。
3
、
next
函数值序列的产生仅与模式串有关。