串数组习题
-
第
4
、
5
章
串、数组
习题
一．
选择题
（
1
）一个子串在包含它的主串中的位置是指（
）
。
A.<
/p>
子串的最后那个字符在主串中的位置
B
.
子串的最后那个字符在主串中首次出现的位置
C.
子串的第一个字符在主串中的位置
D.
子串的第一个字符在主串中首次出现的位置
（
2
）串下面关于串的的叙
述中，
（
）是不正确的？
A
．串是字符的有限序列
B
．空串是由空格构成的串
C
．模式匹配是串的一种重要运算
D
．
串既可
以采用顺序存储，
也可以采用链式存储
（
3
）串的长度是指（
）
。
A
．串中所含不同字母的个数
B
．串中所含字符的个数
C
．串中所含不同字符的个数
D
．串中所含非空格字符的个数
（
4
）若
SUBS
TR
（
S
，
i
，
k
）表示求
S
中从第
i
个字符开始的连续
k
个字符组成的子串的
操作，则对于
S=
“
Beijing
＆
Nanjing
”
，
< br>SUBSTR
（
S
，
4
，
5
）
=
（
）
。
A.
“
ij
ing
”
B.
“
ji
ng
＆
”
C.
“
in
gNa
”
D.
“
in
g
＆
N
”
（
5
）
若
INDEX
（
S
，
T
）
表示求
T
在
S
中的位置的操作，
则对于
S=
“
Beijing
＆
N
anjing
”
，
T=
“
jing
”
，
INDEX
（
S
，
T
）
=
（
）
。
A.
2
B.
3
C.4
D.
5
（
6
）
若
REPLACE
< br>（
S
，
S1
，
S2
）
表示用字符串
S2
替换字符串
S
中的子
串
S1
的操作，
则对于
S=
“
Beijing
＆
Nanjing
”
，
S1=
“
Beijing
”
，
S2=
“
Shang
hai
”
，
REPLACE
（
S
，
S1
，
S2
）
=
（
）
。
A.
“
Na
njing
＆
Shanghai
”
B.
“
Nanjing
＆
Nan
jing
”
C.
“
Sh
anghaiNanjing
”
D.
“
Sh
anghai
＆
Nanjing
（
7
）假设以行序为主序存储二维数
组
A=array[1..100,1..100]
，设每个数
据元素占
2
个存储
单元，基地址为
10
，则
LOC[5,5]=
（
）
。
A
．
808
B
．
818
C
．
1010
D
．
1020
（
8
）设有数组
A[i,j]
，数组的每个元素长度为
3
字节，
i
的值为
1
到
8
，
j
的值为
1
到
10
，数
组从内存首地址
BA
开始顺序存放，
当用以列序为主序存放时，元素
A[5,8]
的存储
首地址为
（
）
。
A
．
BA+141
B
．
BA+180
C
．
BA+222
D
．
BA+225
< br>（
9
）
A[N
< br>，
N]
是对称矩阵，将下面三角（包括对角线）以行序存
储到一维数组
T[N(N+1)/2]
中，则对任一上三角元素
a[i][j]
对应
T[k]
的下标
k
是（
）
。
A
．
i(i-1)/2+j
B
．
j(j-1)/2+i
C
．
i(j-i)/2+1
D
．
j(i-1)/2+1
（
10
）设二维数组
A
[1.. m
，
1.. n]
（即
m
行
n
列）按行存
储在数组
B[1.. m*n]
中，则二维数
< br>组元素
A[i,j]
在一维数组
B
中的下标为（
）
。
A
．
(i-1)*n+j
B
．
(i-1)*n+j-1
C
．
i*(j-1)
D
．
j*m+i-1
1
二．简答题
1.
< br>设主串为
s=
“
ababcab
cacbab
”
,
模式为
p=
“
abcac
”
不写出算法
,
只
画出根据书上算法
4.5
进行模式匹配时每一趟的匹配过程。<
/p>
2.
已知一个稀疏矩阵如图所示
0
0
3
0
0
15
12
0
0
0
18
0
9
0
0
24
0
0
0
< br>0
0
0
0
7
0
0
0
0
0
0
0
0
14
0
0
0
0
0
0
0
0
0
（
1
）
给出它的三元组顺序存储表示，并输出。
（
2
）
给出它转置矩阵的三元组顺序存储表示，并输出。
（
3
）
<
/p>
给出对它进行快速转置时，
num
向量中
各分量的值。
（
4
）
给出对它进行快速转置前，
cpot
向量中各分量的值。
（
5
）
给出对它进行快速转置后，
cpot
向量中
各分量的值；
三、
算法设计题
1.
< br>从字符串
S
中找出与字符串
T<
/p>
相同的子串的起始位置，如
S
中不存在<
/p>
T
，则返回
-1
。第
一个字符存储在
s[1]
中。
2.
若
SUB
STR
（
Sub, S
，
pos
，
len
）表示
从串
S
中从第
pos
个字符开始
取连续
k
个字符
组成子串，求得的子串存放在
sub
数组中。例如
S
串为
< br>Nanjing
,
从第
4
个字符取长度为
3
的子串，子串为
jin
。
2