三：串、数组和广义表

1.假设模式串是abababaab，则KMP模式匹配算法中的next[j] = 0 1 1 2 3 4 5 6 2。 T

2.(neuDS_C++)空串与空格串是相同的。 F

3.设主串 T = abaabaabcabaabc，模式串 S = abaabc，采用 KMP 算法进行模式匹配，到匹配成功时为止，在匹配过程中进行的单个字符间的比较次数是：10

4.串是一种特殊的线性表，其特殊性体现在?（数据元素是一个字符）。

5.设有两个串p和q，求q在p中首次出现的位置的运算称为?（模式匹配）。

6.设广义表L=（（a,b,c）），则L的长度和深度分别为（ 1和2）。

长度定义为最外层包含元素的个数。深度定义为所含括弧的重数,其中原子的深度为0,空表的深度为1。大括号里包含一个括号，即一个元素；嵌套两层，深度为2。

7.广义表((a,b,c,d))的表头、表尾是（ ）。

任何一个非空广义表GL均可分解为表头head(GL) = a1和表尾tail(GL) = ( a2,…,an) 两部分。若表头为空表，则此广义表亦为空表。

8.对n阶对称矩阵压缩存储时，需要表长为（  n(n+1)/2 ）的顺序表。

9.有一个n×n的对称矩阵A，将其下三角部分按行存放在一维数组B中，而A[0][0]存放于B[0]中，则第i行的对角元素A[i][i]存放于B中的（ (i+3)i/2 ）处。

相当于求表长，公式同上题。

10.（SWPU-DS）二维数组 A 的每个元素是由 10 个字符组成的串，其行下标 i=0,1,…,8，列下标 j=1,2,…,10。若 A 按行序优先存储，元素 A[8,5] 的起始地址与当 A 按列序优先存储时的元素（A[3,10] ）的起始地址相同。设每个字符占一个字节。

11.（SWPU-DS）对于 C 语言的二维数组 int A[m][n]，每个元素占 2 个字节，数组中元素 a[i,j]的存储位置可由(Loc[i, j]=Loc[0, 0]+ (n×i+j)×2 )式确定。

12.SWPU-DS）数组 A[0..5, 0..6] 的每个元素占 5 个字节，将其按列优先次序存储在起始地址为 1000 的内存单元中，则元素 A[5, 5] 的地址是( 1175)。

13.对矩阵进行压缩存储是为了?（减少存储空间）。

14.稀疏矩阵一般的压缩存储方式有两种，即?（三元组和十字链表）。

15.设二维数组A[1… m,1… n]按行存储在数组B中，则二维数组元素A[i,j]在一维数组B[1…m*n]中的下标为 (n*(i-1)+j-1 )。

16.设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a1，1为第一个元素，其存储地址为1，每个元素占1个地址空间，则a8，5的地址为( 33）。

17.带行表的三元组表是稀疏矩阵的一种 ( 顺序存储结构)。

18.如果最常用的操作是取第i个结点及前驱，最节省时间的存储方式是（顺序表）。