第4章-串(习题)
-
第四章
串
一、选择题
1
．下面关于串的的叙述中，哪一个是不正确的？（
）（
2
分）
A
．串是字符的有限序列
B
．空串是由空格构成的串
C
．模式匹配是串的一种重要运算
D
．串既可以采用顺序存储，也可以采用链式存储
2
若串
S
1
=
‘
ABC
DEFG
’
, S2=
‘
9898
’
,S3=
‘<
/p>
###
’
,S4=
‘
012345
’
,
执行
concat(replace(S1,sub
str(S1,length(S2),length(S3)),S3),substr(S4,index(
S2,
‘
8
’
),length(S2)))
其结果为（
）（
7
分）
A
．
ABC###G0123
B
．
ABCD###2345
C
．
ABC###G2345
D
．
ABC###2345
E
．
ABC###G1234
F
．
ABCD###1234
G
．
ABC###01234
3
．设有两个串
p
和
q
，其中
q
是
p
的子串，求
q
在
p
中首次出现的位置的算法称为（
）
A
．求子串
B
．联接
C
．匹配
D
．求串长（
2
分）
4<
/p>
．已知串
S=
‘
aaab
’
,
其
Next
数组值为（
）。（
2
分）
A
．
0123
B
．
1123
C
．
1231
D
．
1211
5
．串
<
/p>
‘
ababaaababaa
’
的
next
数组为（
）。
A
．
B
．
C
．
D
．
5
<
/p>
6
．字符串‘
ababaabab
’
的
nextval
为（
）
<
/p>
A
．
(0,1,0,1,04,1,0,
1) B
．
(0,1,0,1,0,2,1,0,1)
C
．
(0,1,0,
1,0,0,0,1,1)
D
．
(0,1,0,1,0,1,0,1,1
)
（
2
分）
7
．模式串
t=
‘
abcaabbcabcaabdab
< br>’，该模式串的
next
数组的值为（
），
nextval
数组的
值为
（
）。
A
．
0 1 1 1 2 2 1 1
1 2 3 4 5 6 7 1 2 B
．
0 1 1 1
2 1 2 1 1 2 3 4 5 6 1 1 2
C
．
0 1 1 1 0 0 1 3
1 0 1 1 0 0 7 0 1 D
．
0 1 1 1
2 2 3 1 1 2 3 4 5 6 7 1 2
E
．
0 1 1 0 0 1 1 1
0 1 1 0 0 1 7 0 1 F
．
0 1 1 0
2 1 3 1 0 1 1 0 2 1 7 0 1
（
2
分）
8
．若串
S
=
’
software
’
,
其子串的数目是（
）。（
2
分）
A
．
8
B
．
37
C
．
36
D
．
9
9
．设
S
为一个长度为
n
的字符串，其中的字符各不相同，则
S
中的互异的非平凡子串（非
空且不同于
S
本身）的个数为（
）。
A
．
2n-1
B
．
n2
C
．
(n2/2)+(n/2)
D
．
(n2/2)+(n/2)-1 E.
(n2/2)-(n/2)-1 F.
其他情况
10
．串的长度是指（
）（
3
分）
A
．串中所含不同字母的个数
B
．串中所含字符的个数
C
．串中所含不同字符的个数
D
．串中所含非空格字符的个数
二、判断题
1
．
KMP
算法的特点是在模式匹配时指示主串的指针不会变小。（
）
（
1
分）
2<
/p>
．设模式串的长度为
m,
目标串的长度为
n
，当
n
≈<
/p>
m
且处理只匹配一次的模式时，朴素的匹
配（即子串定位函数）算法所花的时间代价可能会更为节省。（
）
(1
分
)
3
．串是一种数据对象和操作都特殊的线性表。（
< br>
）
(1
分
)
二、填空题
1
．空格串是指
__(1)__
，其
长度等于
___(2)__
。（
2
分）
2<
/p>
．组成串的数据元素只能是
________
。
（
1
分）
3<
/p>
．一个字符串中
________
称为该
串的子串
。（
1
分）
4<
/p>
．
INDEX
（‘
DATASTRUCTURE
’，
‘
STR
’）
=________
。
(2
分
)
5
．设正文串长度为
n
，模式串长度为
m
，则串匹配的
K
MP
算法的时间复杂度为
________
< br>。
6
．模式串
P=
‘
abaabcac<
/p>
’的
next
函数值序列为
________
。（
2
分）
7<
/p>
．字符串’
ababaaab
’的
nextval
函数值为
________
。（
2
分）
8
．设
T
和
P
是两个给定的串，在
T
中寻找等于
P
的子串的过程称为
__(1)__
，又称
P
为
__(2)__
。（
16/
6
分）
9
．
串是一种特殊的线性表，
其特殊性
表现在
__(1)__
；
串的两种最基
本的存储方式是
__(2)__
、
__
(3)__
；两个串相等的充分必要条件是
__(4)__
。
（
4
分）
10
．两个字符串相等的充分必要条件是
_______
。（
2
分）
11
．知
U
=
‘
xyxyxyxxyxy
’；
t=
‘
xxy
’；
ASSIGN
（
S
，
U
）；
ASSIGN
（
V
，
SUBSTR
（
S
，
INDEX
（
s
，
t
），
LEN<
/p>
（
t
）
+1
））；
ASSIGN
（
m
，‘
ww
’）
求
REPLACE
（
S
，
V
，
m
）
=
________
。
(5
分
)
12
．实现字符串拷贝的函数
strcpy
为：
void
strcpy(char *s , char *t) /*copy t to
s*/
{ while
(________)
} (3
分
)
13
．下列程序判断字符串
s
是否对称，对称则返回
1
，否则返回
0
；如
f(
返回
1
，
f(
返回
0
；
int
f((1)________)
{int
i=0,j=0;
while
(s[j])(2)________;
for(j--;
i
return((3)_______)
} (3
分
)
14
．下列算法实现求采用顺序结构存储的串
s
和串
t
的一个最长公共子串。
程序（
a
）
PROCEDURE maxcomstr(VAR s,t :
orderstring; VAR index,length :
integer);
VAR
i,j,k,length1:integer; con:boolean;
BEGIN
index :=0;
length :=0; i :=1;
WHILE(i<=) DO
[j:=1;
WHILE
(j<=) DO
[ IF (s[i]=t[j])
THEN
[ k:=1; length1:=1;
con:=true;
WHILE con
DO
IF (1)__THEN
[length1:=length1+1;k:=k+1;] ELSE(2) _;
IF (length1>length) THEN [index:=i;
length:=length1; ]
(3)____;
]
ELSE
(4)____;
]
(5) ___;
]
END;
程序
(b)
void maxcomstr(orderstring *s,*t; int
index, length)
{int
i,j,k,length1,con;
index=0;length=0;i=1;
while (i<=)
{j=1;
while(j<=)
{ if
(s[i]= =t[j])
{
k=1;length1=1;con=1;
while(con)
if (1)
_ { length1=length1+1;k=k+1; } else (2)
__;
if (length1>length) {
index=i; length=length1; }
(3)____;
}
else (4)
___;
}
(5) __
} }
（
10
分）
15
．完善算法：求
KMP
算法中
next
数组。
PROC get
_next(t:string,VAR next:ARRAY[1..] OF
integer);
BEGIN
j:=1; k:=(1)__; next[1]:=0;
WHILE j< DO
IF
k=0 OR [j]=[k] THEN BEGIN j:=j+1; k:=k+1;
next[j]:=k;END
ELSE
k:=(2)___;
END;
（
4
分）
16
．
下面函数
index
用于求
t
是否为
s
的子串，
若是返回
t
第一次出现在
s
中的序号
(
从
1
开
始计
)
，否则返回
0
。
例如
:s=
‘
abcdefcdek
’，
t=
‘
cde
’
,
则
indse(s,t)=3,
index(s,
’
aaa
’
)=0
。已知
t
，
s
的
串长分别是
mt,ms
FUNC index(s,t,ms,mt);
i:=1;j:=1;
<
br>其中 <
br>字符 <
br> <
br>; endch= <
br>并返回“ “
<
br>
WHILE
(i
IF
s[i]=t[j] THEN [ (1)__; (2)__]
ELSE [ (3)___; (4)_ ]
IF j>mt THEN return (5)____; ELSE
return (6)__
ENDF;
（
6
分）
17
．阅读下列程序说明和
pascal
程序
,
把应填入其中的（
）处的字句写在答题纸上。
程序说明
：本程序用于判别输入的字符串是否为如下形式的字符串
:W&M$$
,
子字符串
M
是子字符串
W
的字符反向排列
,
在此假定
W
不含
有字符
&
和字符
$$,
&
用作
W
与
M
的分隔符
,
字符
$$
用作字符串的输入结束符。
例如
,
对输入字符串
ab&ba$$
、
11&12$$
、
ab&dd$$
、
&$$,
程序将
分别输出
Ok.(
是
)
,No.(
不是
)
。
程序
PROGRAM
accept(input,output);
CONST
midch=
’
&
’
’
$$
’
;
VAR an:boolean;
ch:char;
PROCEDURE match(VAR
answer: boolean);
VAR
ch1,ch2:char; f:boolean;
BEGIN
read(ch1);
IF
ch1<>endch
THEN IF
(1)__
THEN BEGIN
match(f);
IF f THEN BEGIN read(ch2); answer:=(2)_
END ELSE answer:=false
END
ELSE
(3)___
ELSE
(4)___
END;
BEGIN
writeln(
‘
Enter
String:
’
);
match(an);
IF an
THEN BEGIN
(5)__ IF (6)_
THEN writeln(
‘
Ok.
’
) ELSE writeln(
‘
No.
’
)
END
ELSE writeln(
‘
No.
’
)
END.
（
15
分）
18
．试利用下列栈和串的基本操作
完成下述填空题。
initstack(s)
置
s
为空栈；
push(s,x)
元素
x
入栈
;
pop(s)
出栈操作
;
gettop(s)
返回栈顶元素；
sempty(s)
判栈空函数；
setnull(st)
置串
st
为空串；
length(st)
返回串
st
的长度；
equal(s1,s2)
判串
s1
和
s2
是否相等的函数；
concat(s1,s2)
返回联接
s1
和
s2
之后的串；
sub(s,i,1)
返回
s
中第
i
个字符；
empty(st)
判串空函数
FUNC
invert(pre:string; VAR
exp:string):boolean;
{
若给定的表达式的前缀式
pre
正确，本过程求得和它相应的表达式
exp
true
”，
否则
exp
为空串，
并返回
false
”
。
已知原表达式中不包含括弧，
opset
为运算符的集合。
}
VAR s:stack; i,n:integer; succ:boolean;
ch: char;
BEGIN
i:=1; n:=length(pre);
succ:=true;
(1)__;
(2)__;
WHILE (i
BEGIN ch:=sub
（
pre,i,l
）
;
IF (3)_ THEN (4)__
ELSE IF (5)__THEN (6)_
ELSE BEGIN
exp:=concat((7)___,(8)____);
exp:=concat((9)___,(10)___);
(11)__;
END;
i:=i+1
END;
-
-