chapter04数组和矩阵_2

数组和矩阵

1、(2分)【单选题】某串的长度小于一个常数，则采用( )存储方式最节省空间

A、链式

B、顺序

C、堆结构

D、无法确定

参考答案：B

解析：串的顺序和链式存储结构

2、(2分)【单选题】与线性表相比，串的插入和删除操作的特点是( )。

A、通常以串整体作为操作对象

B、需要更多的辅助空间

C、算法的时间复杂度较高

D、涉及移动的元素更多

参考答案：A

解析：串的基本运算

3、(2分)【单选题】在稀疏矩阵的三元组表示法中，每个三元组表示( )。

A、矩阵中非零元素的值

B、矩阵中数据元素的行号和列号

C、矩阵中数据元素的行号、列号和值

D、矩阵中非零数据元素的行号、列号和值

参考答案：D

解析：二维数组的存储结构及求址方法

4、(2分)【单选题】已知二维数组A8X10，按行存储时，元素a12的地址为1000，每个元素占2个字节，则元素a00的地址为( )

A、972

B、974

C、976

D、978

参考答案：C

解析：二维数组的存储结构及求址方法

5、(2分)【单选题】数组通常具有的两种基本操作是( )

A、建立和删除

B、索引和修改

C、查找和修改

D、查找和索引

参考答案：C

解析：二维数组的存储结构及求址方法

6、(2分)【单选题】在长度为n的字符串S的第i个位置插入另外一个字符串，i的合法值应该是( )。

A、i＞0

B、i≤n

C、1≤i≤n

D、1≤i≤n+1

参考答案：D

解析：串的基本运算

7、(2分)【单选题】两个字符串相等的条件是( )。

A、两串的长度相等

B、两串包含的字符相同

C、两串的长度相等，并且两串包含的字符相同

D、两串的长度相等，并且对应位置上的字符相同

参考答案：D

解析：串的基本运算

8、(2分)【单选题】设有串s=“software”，则其子串的数目是( )。

A、36

B、37

C、8

D、9

参考答案：B

解析：串的基本运算

第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. 数组在内存中占用一段连续的存储空间，数组元素的逻辑顺序和物理顺序一致

3. 数组中的元素本身可以是具有某种结构的数据，如整型，字符型，自定义结构体类型多维数组可以被看做是一维数组，n维数组(n>=2)可以看做是一维数组，它的每个数组元素都是一个n-1维的数组

二维数组中每一个数组元素最多可以有两个直接前驱和两个直接后继(边界元素除外)——>在n维数组中，每个数组元素最多可以有n个直接前驱和n个直接后继，所以多维数组是一种非线性结构

清晰定义：数组是一个具有固定格式和数量的数据有序集，每个数据元素由唯一的数组下标标识，因此，在数组上不适合做插入、删除数据元素的操作 数组中两个主要操作：

取值操作：给定数组下标，读取其对应的数据元素；

赋值操作：给定数组下标，存储或修改与其对应的数据元素；

数组的基本操作(书上P75面)

数组的物理结构(是数组在计算机中的存储表示):

实质是讨论数组在内存中的映像。通常，数组在内存中被映像为向量，即用向量作为数组的一种存储结构。

因为内存的地址空间是一维的，用一维的连续存储空间存放多维数组，就必须通过某种次序将数组中的元素排成一个线性序列，然后将这个线性序列顺序存放在计算机中。当数组的行列固定后，通过一个映像函数，则可根据数组元素下表得到它的存储地址:

1. 对于一维数组按下标顺序分配地址即可ai=a0+(n-1)d

2. 对于二维数组分配地址时，需要把它的元素映像存储在一维存储器中，如(BASIC,Pascal,C等)采用以行为主(先行后列)的方式顺序存放，即一行分配结束之后，再分配下一行，物理地址:aij=a00+(i*n+j)d

3. “以行为主序”的分配规律：最右边的下标先从小到大变化，循环一遍后，右边第二个下标再变，……，按照此规律从右往左，最后变化的是数组元素最左边的下标

本章概览

当前讲授

一、知识结构

二、本章重难点

本要求考生熟悉数组在按行优先顺序的存储结构中元素地址的计算方法；熟悉特殊矩阵在压缩存储时的下标变换方法；理解稀疏矩阵的三元组表存储表示方法及有关算法；熟悉广义表的有关概念，理解广义表的括号表示和图形表示；掌握广义表的求表头和表尾的运算。

本章重点是多维数组的存储方式、矩阵的压缩存储、广义表的表头和表尾的求解；难点是压缩存储特殊矩阵和稀疏矩阵的各种运算及应用。

第一节 多维数组和运算

当前讲授

一、多维数组的定义

1、一维数组

是一种元素个数固定的线性表。

2、多维数组

是一种复杂的数据结构，可以看成是线性表的推广，一个n维数组可视为其数据元素为n-1维数组的线性表。

二、数组的顺序存储

通常采用顺序存储结构来存放数组。对二维数组可有两种存储方法：一种是以行序为主序的存储方式，另一种是以列序为主序的存储方式。在C语言中，采用以行为主序存储。

（1）对于C语言的二维数组A[m][n]，下标从0开始，假设一个数组元素占d个存储单元，则二维数组中任一元素a[i][j]的存储位置可由下式确定：

loc(A[i][j])=loc(A[0][0])+(i *n + j) * d

【真题选解】

（例题·单选题）二维数组A[4][5]按行优先顺序存储，若每个元素占2个存储单元，且第一个元素A[0][0]的存储地址为1000，则数组元素A[3][2]的存储地址为( )

A．1012

B．1017 C．1034

D．1036

隐藏答案

【答案】C

【解析】loc(A[3][2])=loc(A[0][0])+(3 *5 + 2) *

2=1000+34=1034

（2）对于C语言的三维数组A[m][n][p]，下标从0开始，假设一个数组元素占d个存储单元，则三维数组中任一元素a[i][j][k]的存储位置可由下式确定：

loc(A[i][j][k])=loc(A[0][0][0]+(i *n *p+ j*p+k) * d