第四章 串、数组和广义表
一、选择题
1．串的模式匹配是指 (1) 。
(1)：A.判断两个串是否相等
B．对两个串进行大小比较
C．找某字符在主串中第一次出现的位置
D．找某子串在主串中第一次出现的第一个字符位置
2．设二维数组A[m][n]，每个数组元素占用d个存储单元，第一个数组元素的存储地址是如Loc(a[0][0])，求按行优先顺序存放的数组元素a[j]j的存储地址 (2) 。
(2)：A．Loc(a[0][0]+[(i-1)*n+j-1]d
B．Loc(a[0][0])+[in+j]d
C．Loc(a[0][0]+[jm+i]*d
D．Loc(a[0][0])+[(j-1)*m+i-1]*d
3．设二维数组A[m][n]，每个数组元素占d个存储单元，第1个数组元素的存储地址是Loc(a[0][0])，求按列优先顺序存放的数组元素a[j]j的存储地址 (3) 。
(3)：A．Loc(a[0][0]+[(i-1)*n+j-1]d
B．Loc(a[0][0])+[in+j]*d
C．Loc(a[0][0]+[(j-1)*m+i]d
D．Loc(a[0][0])+[jm+i]d
4．已知二维数组A[6][10]，每个数组元素占4个存储单元，若按行优先顺序存放数组元素a[3][5]的存储地址是1000，则a[0][0]的存储地址是 (4) 。
(4)：A．872 B．860 C．868 D．864
5．若将n阶上三角矩阵A，按列优先顺序压缩存放在一维数组F[n(n+1)／2]中，第1个非零元素a11存于F[0]中，则应存放到F[K]中的非零元素aij(1≤i≤n，1≤j≤i的下标i,j与K的对应关系是 (5) 。
(5)：A．i(i+1)/2+j B．i(i-1)/2+j-1
C．j(j+1)／2+j D．j(j-1)／2+i—1
6．若将n阶下三角矩阵A，按列优先顺序压缩存放在一维数组F[n(n+1)／2]中，第一个非零元素a11，存于F[0]中，则应存放到F[K]中的非零元素aij(1≤j≤n，1≤j≤i)的下标i，i与K的对应关系是 (6) 。
(6):A.(2n-j+1)j/2+I-j B.(2n-j+2)(j-1)/2+i-j
C．(2n-i+1)i/2+j-I D．(2n-i+2)i／2+j-i
7．设有10阶矩阵A，其对角线以上的元素aij(1≤j≤10，1<i<j)均取值为-3，其他矩阵元素为正整数，现将矩阵A压缩存放在一维数组F[m]中，则m为 (7) 。
(7)：A．45 B．46 C．55 D.56
8．设广义表L=(a，b，L)其深度是 (8) 。
(8)：A．3 B． C．2 D．都不对
9．广义表B：(d)，则其表尾是 (9) ，表头是 (10) 。
(9)—(10)：A．d B．() C．(d) D．(())
10．下列广义表是线性表的有 （11） 。
(11)：A．Ls=(a，(b，c)) B．Ls=(a，Ls)
C．Ls=(a，b) D．Ls=(a，(()))
11.一个非空广义表的表尾 (12) 。
(12)：A．只能是子表 B．不能是子表
C．只能是原子元素 D．可以是原子元素或子表
12．已知广义表A=((a，(b，c))，(a，(b，c)，d))，则运算head
(head(tail(A)))的结果是 (13) 。
(13)：A．a B．(b，c) C．(a，(b，c)) D．d
二、填空题
1．两个串相等的充分必要条件是 (1) 。
2．空串是 (2) ，其长度等于 (3) 。
3．设有串S=”good”，T=”morning”，求：
(1)concat(S，T)= (4) ；
(2)substr(T，4，3)= (5) ；
(3)index(T，”n”)= (6) ；
(4)replace(S，3，2，”to”)= (7) 。
4．若n为主串长，m为子串长，则用简单模式匹配算法最好情况下，需要比较字符总数是 (8) ，最坏情况下，需要比较字符总数是 (9) 。
5．设二维数组A[8][10]中，每个数组元素占4个存储单元，数组元素a[2][2]按行优先顺序存放的存储地址是1000，则数组元素a[0][0]的存储地址是 (10) 。
6．设有矩阵

压缩存储到一维数组F[m]中，则m为 (11) ，-3应存放到F[k1]中，k1为(12)，元素aij(1≤i≤4，1≤j≤i)按行优先顺序存放到F[k2]中，k2为 (13) ，按列优先顺序存放到F[k3]中，k3为 (14) 。
7．广义表Ls=(a，(b)，((c，(d))))的长度是 (15) ，深度是 (16) ，表头是 (17) ，表尾是 (18) 。
8．稀疏矩阵的压缩存储方法通常有两种，分别是 (19) 和 (20) 。
9．任意一个非空广义表的表头可以是原子元素，也可以是 (21) ，而表尾必定是 (22) 。
三、应用题
1．已知S=”(xyz)+”试利用联接(concat(S，T))，取子串(substr(S，i，j))和置换(replace(S，i，j，T))基本操作将S转化为T=”(x+2)*y”。
2．设串S的长度为n，其中的字符各不相同，求S中互异的非平凡子串(非空且不同于S本身)的个数。
3．设模式串T=”abcaaccbaca”，请给出它的next函数及next函数的修正值nextval之值。
4．特殊矩阵和稀疏矩阵哪一种压缩存储会失去随机存储功能?
5．设n阶对称矩阵A压缩存储于一维数组F[m]中，矩阵元素aij(1≤i≤n，1≤j≤n)，存于Fk中，当用行优先顺序转换时的对应关系是什么?用列优先顺序转换时的对应关系是什么?

参考答案

第四章
一、单项选择题
(1)一(5)DBDBD (6)-(10)BDBBA (11)-(13)CAA
二、填空题
(1)两个串的长度相等且对应位置上的字符相同。
(2)是由零个字符组成的串 (3)0
(4)”goodmorning” (5)”nin” (6)4 (7)”goto” (8)m
(9)m(n-m+1) (10)Loc(a[0][0])=1000-88=912
(11)n(n+1)/2+1 (12) n(n+1)/2 (13)i(i-1)/2+j-1
(14)(2n-j+2)(j-1)/2+i-j (15)3 (16)4 (17)a(18)((b),((c,(d))))
(19)三元组表 （20）十字链表 （21）子表 (22)子表
三、应用题
1．用联接、取子串、置换运算将串S=”(xyz)+*”转化为T=”(x+z)y”。
C1=substr(S,3,1)=”y” C2=substr(S,6,1)=”+”
C3=substr(S,7,1)=”” C4=concat(C3,c11)=”*y”
T=replace(S,3,1,C2)=replace(S,3,1,substr(S,6,1))=”(x+z)+x”
T=replace(T,6,2,concat(C3,C1))=replace(T,6,2,concat(substr(S,7,1)),substr(S,3,1)))=”(x+z)*y”。
若只用取子串和联接操作进行的转换过程是：
C1=concat(substr(S,1,2),substr(S,6,1))=”(x+”
C2=concat(substr(S,7,1),substr(S,3,1))=”*y”
T=concat(concat(concat(substr(S,1,2),substr(S,6,1)),substr(S,4,2)),concat(substr(S,7,1),substr(S,3,1)))
2.串S的长度为n，其中的字符各不相同，所以S=”(x+z)y”中含1个字符的子串有n个，2个字符的子串有n-1个……，含n-2个字符的子串有3个，含n-1个字符的子串有2个，共有非平凡子串的个数是n(n+1)/2-1。
3.串T的next和nextval函数值见下表：

4．特殊矩阵是指具有相同值的矩阵元素或零元素的分布具有一定规律，可以将其压缩存储在一维数组中，矩阵元素aij的下标I和j与其在一维数中存放的下标k之间存在一一对应关系，故不会失去随机存取功能。
稀疏矩阵中零元素的分布没有一定规律，可以将非零元素存于三元组表中，非零元素aij在三元组中的存放位置与i、j没有对应关系，故失去随机存取功能。
5．N阶对称矩阵A中，aij=aji，可以仅存放下三角元素（或上三角元素）。设r=max(i,j)，c=min(i,j),
k=r(r-1)/2+c-1;
例如，4阶对称矩阵A，按行优先顺序存于一维数组F[10]中，

当i=3，j=2时，k=32/2+2-1=4;
当i=2，j=3时，k=4
(2)当对称矩阵A按列优先顺序压缩存放，若仅存放上三角元素，则有：
k=r(r-1)/2+c-1
例如，4阶对称矩阵A，按列优先顺序存于一维数组F[10]中，