《数据结构》习题集：第4章 串
-
数据结构课后练习题
第
4
章
串
第
4
章
串
一、
选择题
1.
设串
s1=
’
ABCDEFG
’
，
s2=
’
PQRST
’
，函数<
/p>
Concat(x,y)
返回
x
和
y
串的连接串，
< br>Substr(s,i,j)
返回串
s
从序号
i
开始
的
j
个
字符组成的子串，
length(s)
返回串
< br>s
的长度，
则
Concat(
Substr(s1,2,length(s2)),Substr(s1,length(s2),2))
的结果串是（
）。
A
、
BCDEF
B
、
BCDEFG
C
、
BCPQRST
D
、
BCDEFEF
2.
空串和空格是相同的。（
）
A
、正确
B
、错误
3.
若串
S
1=
’
ABCDEFG
’
，
S2=
’
9898
’
，
S3=
’
###
’
，
S4=<
/p>
’
012345
，则执行下列语句后，其
结果为（
）。
replace(s1,Sub
str(s1,4,length(s3)),s3)
；
Concat(s1,Substr(s4,index(s2,
’
8
’
),length(s2)))
A
、
ABC###G0123
B
、
ABCD###2345
C
、
ABC###G2345
D
、
ABC###2345
E
、
ABC###G1234
F
、
ABCD###1234
G
、
ABC###01234
4.
串是一种特殊的线性表，其特殊性体现在（
）。
A
、可以顺序存储
B
、数据元素是一个字符
C
、可以链接存储
D
、数据元素可以是多个字符
5.
设有两个串
p
和
q
，求
q
在
p
中首次出现的位置的运算称为（
）。
A
、连接
B
、模式匹配
C
、求子串
D
、求串长
6.
下面关于串的的叙述中，哪一个是不正确的？（
）
A
．串是字符的有限序列
B
．空串是由空格构成的串
C
．模式匹配是串的一种重要运算
D
．串既可以采用顺序存储，也可以
采用链式存储
7.
串的长度是指（
）
A
．串中所含不同字母的个数
B
．串中所含字符的个数
C
．串中所含不同字符的个数
D
．串中所含非空格字符的个数
二、
判断题
1.
子串定位函数的时间复杂度在最坏的情况下为
O
（
n*m
），因此子串定位
函数没有实际利用价值。
2.
设有两个串
p
和
q
，其中
q
是
p
的子串，把
q
在
p
中首次出现的位置作为子串
q
在
p
中的位置的算法称为
匹配。
3.
KMP
算法的最大特点是指示主串的指针不需要回朔。
三、
填空题
1.
2.
3.
4.
5.
6.
设
s=
’
I_
AM_A_TEACHER
’
，其长度为（
）。
空串是（
），其长度为（
）。
设<
/p>
S1=
’GOOD’
，
< br>S2=’
’
，
S3=’BYE!’
，则
S1
、
S2
和
S3
连接后的结果是（
）。
两个串相等的充分必要条件是（
）。
串的两种最基本的存储方式是（
）。
空格
串是
_________
，其长度等于
_________
。
1/2
北京理工大学珠海学院计算机学院
“数据结构”课程组编制
2011-3-1