栈队列数组试题(四)——数组和特殊矩阵

01．对特殊矩阵采用压缩存储的主要目的是( D ).
A.表达变得简单                                             B.对矩阵元素的存取变得简单
C.去掉矩阵中的多余元素                              D.减少不必要的存储空间
解析：特殊矩阵中含有很多相同元素或零元素，所以采用压缩存储，以节省存储空间

02.对n阶对称矩阵压缩存储时，需要表长为(  C  )的顺序表。
A. n/2                       B. n×n/2                        C. n(n+1)/2                        D. n(n-1)/2
解析：对称矩阵只需存储上三角或下三角部分(含对角线)，元素个数为n+(n-1)+(n-2)+...+1=n(n+1)/2

03.有一个nn的对称矩阵A，将其下三角部分按行存放在一维数组B中，而A[0][0]存
放于B[0]中，则第i+1行的对角元素A[i][i]存放于B中的（ A  )处。
A. (i+ 3)i/2                B. (i+1)i/2                      C. (2n- i+1)i/2                     D. (2n- i- 1)i/2
解析：矩阵的最小下标为0，数组下标也是从0开始，矩阵按行优先存在数组中，可以采用特殊代值法，如A[1][1]的下标为2，代入后只有A满足条件

04．在二维数组A中，假设每个数组元素的长度为3个存储单元，行下标i为0~8，列下标
j为0~9,从首地址SA开始连续存放。在这种情况下，元素A[8][5]的起始地址为()
A.SA+141                B. SA+144                      C. SA+222                        D. SA+255
解析:二维数组计算地址(按行优先顺序)的公式为 LOC(i,j)=LOC(0,0)+(i*m+j)*L
LOC(0,0)是SA,是数组存放的首地址；L=3是每个数组元素的长度，m=9-0+1是数组的列数
所以LOC(8,5)=SA+(8*10+5)*3=SA+255;

05．二维数组A按行优先存储，其中每个元素占1个存储单元。若A[1][1]的存储地址为
420，A[3][3]的存储地址为446，则A[5][5]的存储地址为( A ).
A. 472                B.471                C. 458                        D. 457
解析：该二维数组按行优先存储，且A[3][3]的存储地址为446，所以A[3] [1]的存储地址为444，又A[1][1]的存储地址为420,显然A[1][1]和A[3][1]正好相差2行,所以该矩阵的列数为12。而A[5][3]和A[3] [3]正好相差2行，A[5][5]和A[5][3]又相差2个元素，所以A[5][5]的存储地址是446+24*2=472

06．将三角矩阵即数组A[1..100][1..100]按行优先存入一维数组B[1..298]中，数组
中元素A[66] [65]在数组B中的位置k为(  B ).
A.198                        B.195                        C. 197                D.196
解析：对于三对角矩阵，将A[1..n][1..n]压缩至B[1...3n-2]时，ai,j与bk的对应关系为k=2i+j-2,则A[66][65]=2*66+65-2=195

07．若将n阶上三角矩阵A按列优先级压缩存放在一维数组B[ 1...n (n+1)/2+1]中，则存
放到B[ k]中的非零元素ai,j (1≤i,j≤n)的下标i、j与k的对应关系是( C ).
A. i(i+1)/2+j               B. i(i- 1)/2 +j-1                 C. j(j-1)/2+i                D. j(j-1)/2+ i-1
解析:按列优先存储，所以ai,j前面有j-1列，共有1+2+3+...+j-1=j(j-2)/2个元素，元素ai,j在第j列上是第i个元素，数组B的下标是从1开始，因此k=j(j-1)/2+i.

08．若将n阶下三角矩阵A按列优先顺序压缩存放在一维数组B[ 1...n (n+1)/2+1]中，则
存放到B[k]中的非零元素ai,j(1≤i,j≤n)的下标i, j与k的对应关系是(  B ).
A. (j-1)(2n-j+1)/2+i- j                                                B. (j-1)(2n-j+2)/2 +i-j+1
C. (j-1)(2n-j+2)/2+i-j                                                 D. (j-1) (2n-j+1)/2+i-j-1
解析：按列优先存储，所以元素ai,j前有j-1列，共有n+(n-1)+..+(n-j+2)=(j-1)(2n-j+2)/2个元素，元素ai,j是第j列上的第i个元素，数组下标从1开始，k=(j-1)(2n-j+2)/2+i-j+1

09．稀疏矩阵采用压缩存储后的缺点主要是( B )。
A．无法判断矩阵的行列数                                      B.丧失随机存取的特性
C．无法由行、列值查找某个矩阵元素                    D.使矩阵元素之间的逻辑关系更复杂
解析:稀疏矩阵通常采用三元组来压缩存储，存储矩阵元素的行列下标和相应的值，因此不能根据矩阵元素的行列下标快速定位矩阵元素，失去了随机存取的特性。

10.下列关于矩阵的说法中，正确的是(B ).
I、在n ( n>3）阶三对角矩阵中，每行都有3个非零元
Ⅱ、稀疏矩阵的特点是矩阵中的元素较少
A.仅Ⅰ                      B.仅Ⅱ                     C.Ⅰ和Ⅱ                   D.无正确项
解析：三对角矩阵中，第1行和最后一行只有2个非零元，其余各行均有3个非零元，稀疏矩阵的特点是矩阵中非零元的个数较少

11.【2016统考真题】有一个100阶的三对角矩阵M，其元素mi,j ( 1≤i, j≤100）按行优先
依次压缩存入下标从0开始的一维数组N中。元素m30,30在N中的下标是(  B ).
A. 86                        B. 87                        C. 88                        D.89
解析：三对角矩阵第一行有两个元素，剩下的在元素m30,30所在行之前的28行(注意下标1<=i,j<=100)中，每行都有3个元素，而m30,30之前只有一个元素m30,29,所以m30,30在数组N中的下标是2+28*3+2-1=87

12.【2017统考真题】适用于压缩存储稀疏矩阵的两种存储结构是(  A  )
A.三元组表和十字链表                                              B.三元组表和邻接矩阵
C.十字链表和二叉链表                                              D.邻接矩阵和十字链表
解析：三元组表的结点存储了行（row)、列（col)、值(value）三种信息，是主要用来存储稀疏矩阵的一种数据结构。十字链表将行单链表和列单链表结合起来存储稀疏矩阵。邻接矩阵空间复杂度达O(n^2)，不适合于存储稀疏矩阵。二叉链表又名左孩子右兄弟表示法，可用于表示树或森林。

13.【2018统考真题】设有一个12×12阶对称矩阵M,将其上三角部分的元素mi,j( 1≤i≤j≤12 )
按行优先存入C语言的一维数组N中，元素m6,6在N中的下标是( A ).
A. 50                          B. 51                        C. 55                        D. 66
解析：M的下标从0开始，第一个元素m1,1对应存入N0，第一行12个元素，第二行11个，第三行10个，第四行9个，第五行8个，所以m6,6是第12+11+10+9+8+1=51个元素，下标为50

14.【2020统考真题】将一个10×10阶对称矩阵M的上三角部分的元素mi,j ( 1≤i≤j≤10)
按列优先存入C语言的一维数组N中，元素m7,2在N中的下标是（C  )。
A. 15                          B.16                         C.22                        D.23
解析：M的下标从0开始，按列优先存储，第一列1个元素，第二列2个，，，第6列6个，所以m7,2是第1+2+3+4+5+6+2=23个元素 所以下标为22

15.【2021统考真题】二维数组A按行优先方式存储，每个元素占用1个存储单元。若元素
A[0][0]的存储地址是100，A[3][3]的存储地址是220，则元素A[5][5]的存储地址是( B )。
A. 295                         B.300                       C. 301                     D.306
解析：二维数组按行优先存储，每个元素占1个存储单元，有A[0][0]和A[3][3]的存储地址可知A[3][3]是第121个元素，假设二维数组每行有n个元素，则n*3+4=121，n=39,所以元素A[5][5]的存储地址为100+39*5+6-1=300

16.【2023统考真题】若采用三元组表存储结构存储稀疏矩阵M，则除三元组表外，下列数
据中还需要保存的是( A ).
I. M的行数                                        Ⅱ. M中包含非零元素的行数
Ⅲ. M的列数                                      IV. M中包含非零元素的列数
A．仅Ⅰ、Ⅲ               B．仅I、IV              C.仅II、IV                 D. Ⅰ、Ⅱ、Ⅲ、IV
解析：用三元组表存储结构存储稀疏矩阵M时，每个非零元素都由三元组（行标、列标、关键字值）组成。但是，仅通过三元组表中的元素无法判断稀疏矩阵M的大小，因此还要保存M的行数和列数。此外，还可以保存M的非零元素个数。如果两个稀疏矩阵的三元组表是相同的，若不保存行数和列数，则无法判断两个稀疏矩阵的大小。