本章的基本内容是：串类型的定义、各种存储结构及其基本运算的实现以及串的模式匹配算法，数组、稀疏矩阵的定义、各种存储结构及其基本运算的实现。
串是一种数据类型受到限制的特殊线性表，它规定表中的每一个元素类型只能为字符。一个串所包含字符的个数称为串的长度，长度为零的串称为空串。应注意的是空格也是合法的字符，只有空格的串称为空格串，不是空串。
串的存储结构主要有顺序存储结构和链式存储结构两种。顺序存储结构的缺点是不便于进行串的插入、删除运算。对于插入、删除运算较多的情况适合采用链式存储结构。
串的匹配运算是一个比较复杂的串操作，它就是判断某串是否是另一已知串的子串，如是其子串，则给出该串的起始点。该算法在文本编辑程序中经常用到，提出该问题的有效算法能大大提高编辑程序的响应性能。
1．选择题
（1）串是一种特殊的线性表，其特殊性表现在 。
A．可以顺序存储 B．数据元素是一个字符
C．可以链接存储 D．数据元素可以是多个字符
（2）设有两个串P和Q，求Q在P中首次出现的位置的操作称为 。
A．连接 B．模式匹配
C．求子串 D．求串长
（3）设串S1="ABCEEFG"，S2="PQRST"，函数StringConcat(X,Y)返回X和Y的连接串，SubString(S,I,J)返回串S中序号I的字符开始的J个字符组成的子串，StringLength(5)返回串S的长度，则StringConcat(SubString(S1.2,StringLength(S2),Substring(S1,StringLength (S2),2))的结果串是 。
A．BCDEF B．BCDEFG
C．BCDQRSTD D．BCDEFEF
（4）数组通常具有两种基本操作是 。
A．建立和删除 B．索引和修改
C．查找和修改 D．查找和索引
（5）二维数组A[10..20,5..10]采用行序为主序方式存储，每个数据元素占4个存储单元，且A[10,5]的存储地址是1000，则A[18,9]的存储地址是 。
A．1208 B．1212
C．1268 D．1364
（6）三维数组A[0..4,0..5,0..6]，采用行序为主序方式存储，每个数据元素占2个存储单元，且第一个元素的存储地址是120，则A[3,4,5]的存储地址是 。
A．438 B．358
C．360 D．362
（7）二维数组A中，每个元素的长度为4个字节，行下标从0～4，列下表从0～5，A按行优先存储元素A[3,5]的地址与A按列优先存储时元素 的地址相同。
A．A[2,4] B．A[3,4]
C．A[3,5] D．A[4,4]
（8）对矩阵压缩存储是为了 。
A．方便运算 B．节省时间
C．方便存储 D．提高运算速度
（9）稀疏矩阵的压缩存储方法通常有两种，即 。
A．二元数组和三元数组 B．三元数组和散列
C．三元组和十字链表 D．散列和十字链表
2．填空题
（1）两个串相等的充分必要条件是 。
（2）空串是 ，其长度等于 。
（3）空格串是 ，其长度等于 。
（4）广义表的深度是指 。
（5）已知二维数组A[m][n]采用行序为主方式存储，每个元素占k个存储单元，并且第一个元素的存储地址是LOC(A[0][0])，则A[i][j]的地址是 。
（6）二维数组A[10][20]采用列序为主方式存储，每个元素占一个存储单元，并且A[0][0]的存储地址是200，则A[6][10]的地址是 。
（7）二维数组A[10..20][5..20]采用行序为主方式存储，每个元素占4个存储单元，并且A[10][5]的存储地址是1000，则A[18][9]的地址是 。
（8）有一个10阶对称矩阵A，采用压缩存储方式（以行为主存储，且LOC(A[0][0])=1），则A[8][5]的地址是 。
3．问答题
（1）若串s="software"，其子串的数目是多少？
（2）设串S的长度为n，其中的字符各不相同，求S中互异的非空且不同于S本身的子串的个数。
（3）设模式串T="abcaacabaca"，请给出它的next函数值。
（4）按行优先顺序和按列优先顺序列出四维数组A[2][2][2][2]所有元素在内存中的存储次序。
（5）画出广义表(a,(b,(c,())),(d,e))的存储结构图。
（6）已知广义表(a,(b,(a,b)),((a,b),(a,b)))，试完成以下要求：
①画出该广义表的存储结构图。
②计算该广义表的表头和表尾。
③计算该广义表的深度。
（7）已知广义表A=(((a)),(b),c,(a),(((d,e))))，画出它的存储结构图，给出表的长度与深度，并用求表头、表尾的方式求出原子e。
4．上机操作题
（1）采用顺序结构存储串，设计一个算法strcmp(s,t)实现串比较运算，串比较以词典方式进行，当s>t时返回1，s=t时返回0，s小于t时返回-1。
（2）设计一个算法判断顺序存放的字符串是否为回文（即正读与倒读相同）。
（3）在顺序串s中，将第i个字符开始的连续j个字符构成的子串用串t替换，产生新的串，请编写一个实现上述功能的算法。
（4）设串采用顺序存储表示，请编写一个算法，求子串T在主串S中出现的次数。
（5）编写程序段，将An×n的上三角形，以列为主，存储于一个B(1…n(n+1)/2)的数组中。再编写程序段，从B数组中取出A(i, j)。
（6）设计一个算法MaxAtom(*g)，求出一个广义表g中最大的原子。例如，MaxAtom(a, (b),d,c)返回的结果为d。
（7）设计一个算法，利用head()和tail()算法将一个广义表逆置，例如，广义表 (b,(b,b,c), ((a,b),x))逆置后的结果为((x,(b,a)),(c,b,b),b)。