数据结构 第4章 串、数组

第4章 数组和广义表

【例4-1】二维数组A的每一个元素是由6个字符组成的串，其行下标i=0，1，…，8，列下标j=1，2，…，10。若A以行为主序存储元素，A[8][5]的物理地址与当A按列为主序存储时的元素（ ）的物理地址相同。设每个字符占一个字节。

A．A[8][5] B．A[3][10] C．A[5][8] D．A[0][9]

解： 二维数A是一个9行10列的矩阵，即A[9][10]。按行存储时，A[8][5]是第85个元素存储的元素。而按列存储时，第85个存储的元素是A[3][10]。即正确答案为B。

【例4-2】若对n阶对称矩阵A以行序为主序方式将其下三角形的元素（包括主对角线上所有元素）依次存放于一维数组B[n（n+1）/2]中，则在B中确定的位置k的关系为（ ）。

A．jii2)1(* B．ijj2)1(* C．jii2)1(* D．ijj2)1(*

解： 如果aij按行存储，那么它的前面有i-1行，其有元素个数为：

1+2+3+…+（i-1）=i（i-1）/2。同时它又是所在行的第j列，因此它排列的顺序还得加上j，一维数组B[n(n+1)/2]中的位置k与其下标的关系是：jii2)1(*。

因此答案为A。

【例4-3】已知n阶下三角矩阵A，按照压缩存储的思想，可以将其主对角线以下所有元素（包括主对角线上元素）依次存放于一维数组B中。请写出从第一列开始以列序为主序分配方式时在B中确定元素aij的存放位置的公式。

解： 如果aij按列存储，那么它的前面有j-1列，共有元素：

n+(n-1)+(n-2)+ …+[n-(j-2)]

=(j-1)*n-2)1)(2(jj

而它又是所在列的第i行，因此在它前的元素个数还得加上i。因此它在一维数组B中的存储顺序为：

(j-1)*n-2)1)(2(jj+i

【例4-4】已知广义表L=((x,y,z),a,(u,t,w))，从L表中取出的原子项ASCII码最大的运算是（ ）。

串、数组和稀疏矩阵 1、串是一种特殊的线性表，请从存储和运算两方面分析它的特殊之处。

2、设字符串S= 'aabaabaabaac'，P= 'aabaac'

(1) 给出S和P的next值

012123456789 012123

(2) 若S作主串，P作模式串，试给出KMP算法的匹配过程。

利用KMP算法的匹配过程：

第一趟匹配：aabaabaabaac

aabaac(i=6,j=6)

第二趟匹配：aabaabaabaac

(aa)baac

第三趟匹配：aabaabaabaac

(成功) (aa)baac

3、假设有二维数组 A6×8，每个元素用相邻的 6 个字节存储，存储器按字节编址。已知 A 的起始存储位置(基地址)

为 1000，计算：

(1) 数组 A 的体积（即存储量）;

(2) 数组 A 的最后一个元素 a57 的第一个字节的地址;

(3) 按行存储时，元素 a14 的第一个字节的地址;

(4) 按列存储时，元素 a47 的第一个字节的地址。 (1）6×8×6 = 288Byte (2）1000+288-6=1282； (3）1000+(1×8+4)×6=1072 (4）1000+(7×6+4)×6=1276 4、一个稀疏矩阵A如图所示 (1) 给出三元组存储示意图； (2) 给出带行指针向量的链式存储示意图； (3) 给出十字链表存储示意图。 （1） （2） （3）

030000020500000000900001A = 4×6

习题四 参考答案

一、选择题

1．下面关于串的叙述中，哪一个是不正确的？（ B ）

A．串是字符的有限序列

B．空串是由空格构成的串

C．模式匹配是串的一种重要运算

D．串既可以采用顺序存储，也可以采用链式存储

2．串的长度是指( A )

A. 串中包含的字符个数 B. 串中包含的不同字符个数

C. 串中除空格以外的字符个数 D. 串中包含的不同字母个数

3．设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（ C ）

A．求子串 B．联接 C．模式匹配 D．求串长

4．设主串的长度为n，模式串的长度为m，则串匹配的KMP算法时间复杂度是( C )。

A. O(m) B. O(n) C. O(n + m) D. O(n×m)

5. 串也是一种线性表，只不过( A )。

A. 数据元素均为字符 B. 数据元素是子串

C. 数据元素数据类型不受限制 D. 表长受到限制

6.设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主进行存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（ B ）。

A. 13 B. 33 C. 18 D. 40

7. 有一个二维数组A[1..6, 0..7] ，每个数组元素用相邻的6个字节存储，存储器按字节编址，那么这个数组占用的存储空间大小是（ D ）个字节。

A. 48 B. 96 C. 252 D. 288

8. 设有数组A[1..8,1..10]，数组的每个元素占3字节，数组从内存首地址BA开始以列序为主序顺序存放，则数组元素 A[5，8]的存储首地址为( B )。

1 第4～5章 串和数组 自测卷 姓名 班级

题号 一 二 三 四 五 总分

题分 20 15 20 15 30 100

得分

一、填空题（每空1分，共20分）

1.

称为空串；

称为空白串。

2.

设S=“A;/document/Mary.doc”，则strlen(s)= , “/”的字符定位的位置为

。

4. 子串的定位运算称为串的模式匹配；

称为目标串，

称为模式。

5. 设目标T=”abccdcdccbaa”，模式P=“cdcc”，则第 次匹配成功。

6. 若n为主串长，m为子串长，则串的古典匹配算法最坏的情况下需要比较字符的总次数为 。

7.

假设有二维数组A6×8，每个元素用相邻的6个字节存储，存储器按字节编址。已知A的起始存储位置（基地址）为1000，则数组A的体积（存储量）为

；末尾元素A57的第一个字节地址为

；若按行存储时，元素A14的第一个字节地址为 ；若按列存储时，元素A47的第一个字节地址为 。

8. 设数组a[1„60, 1„70]的基地址为2048，每个元素占2个存储单元，若以列序为主序顺序存储，则元素a[32,58]的存储地址为

。

9. 三元素组表中的每个结点对应于稀疏矩阵的一个非零元素，它包含有三个数据项，分别表示该元素

的 、

和 。