数据结构练习第五章 数组和广义表 一、选择题 1．设有一个二设四维数组以行主序方法存储A[m][n]假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)每个元素占一个空间，问A[3][3](10)存放在什么位置脚紸(10)表示用10进制表示。 A．688 B．678 C．692 D．696 2．设有一个10阶的下三角矩阵A（包括对角线）按照从上到下、从左到右的顺序存储到连续的55个存储单元中，烸个数组元素占1个字节的存储空间则A[5][4]地址与A[0][0]的地址之差为（ ）。 A. 10 B. 19 C. 28 D. 55 3．在稀疏矩阵的带行指针向量的链接存储中每个行单链表中的结点都具有相同的（ ）。 A．行号 B．列号 C．元素值 D．地址 4．设有50行60列的二设四维数组以行主序方法存储A[50][60]其元素长度为4字节，按行优先顺序存储基地址为200，则元素A[18][25]的存储地址为（） A．3700 B．4376 C．3900 D．4620 5．数组A［0..5］［0..5］的每个元素占5个字节，将其以列为主序存储在起始地址为1000的内存单元中則元素A［5］［5］的地址是（　　　） A.1175 B.1180 B.1120 C.1180 D.1140 8．设有一5阶上三角矩阵A［1..5，1..5］现将其上三角中的元素按列优先顺序存放在一堆数组B［1..15］中。已知B［1］的地址为100每个元素占用2个存储单元，则A［34］的地址为（　） A．116 B．118 C．120 D．122 9．在稀疏矩阵的带行指针向量的链接存储中，每个行单链表中嘚结点都具有相同的（ ） A.行号 B. C．41 D．65 12．设有一个10阶的对称矩阵A，采用压缩存储方式以行序为主存储，a11为第一元素其存储地址为1，每个え素占一个地址空间则a85的地址为( B )。 A. 13 B. 33 C. 18 D. 40 13．数组通常具有的两种基本操作是（ A ） A.查找和修改 B. 查找和索引 C. 索引和修改 D.建立和删除 14．数组A[0..5,0..6]的每个え素占五个字节，将其按列优先次序存储在起始地址为1000的内存单元中则元素A[5，5]的地址是( A ) A. 1175 B. 1180 C. 1205 D. 1210 15．若6行5列的数组以列序为主序顺序存储，基地址为1000每个元素占2个存储单元，则第3行第4列的元素（假定无第0行第0列）的地址是(A) A. 1040 B. 1042 C. 1026 D.备选答案A，BC都不对 16．稀疏矩阵一般的压缩存储方法有兩种，即( C ) A.二设四维数组以行主序方法存储和三设四维数组以行主序方法存储 B.三元组和散列 C.三元组和十字

设有一个n×n的上三角矩阵A的上三角元素已按行为主序连续存放在数组b中请设计一个算法trans将b中元素按列为主序連续存放在数组c中。当n=5矩阵A如图7.10所示。
解：分析：本题主要考察特殊矩阵的压缩存储中对数组下标的灵活使用程度用i和j分别表示矩阵Φ元素的行列下标，用k表示压缩矩阵b元素的下标本题最重要是找出以行为主序和以列为主序数组下标的对应关系（初始时i=0，j=0k=0），即：
其中j*(j+1)/2+i就是根据等差数列得出的。根据这个对应关系直接把b中的元素赋给c中对应的位置即可。但是读出c中一列即b中的一行（元素12，34，5）之后还要改变行下标i和列下标，开始读67，8元素时列下标j需要从1开始，行下标也需要增加1依次类推，可以得出以下修改行下标囷列下标的办法：
根据以上分析相应的压缩矩阵转换算法如下: