数据结构考研分类复习真题 第五章 答案[23]

设用munu和tu表示稀疏矩阵行数列数和非零元素个数则转置矩阵的行数列数和非零元素的个数分别是numu和tu转置可按转置矩阵的三元组表中的元素顺序进行即按稀疏矩阵的列序从第列到第nu列每列中按行值递增顺序找出非零元素逐个放入转置矩阵的三元组表中转时行列值互换元素值复制按这种方法第列到第个非零元素一定是转置后矩阵的三元组表中的第个元素第列非零元素在第列非零元素的前面这种方法时间复杂度是O(n*P)其中p是非零元素个数当p和m*n同量级时时间复杂度为O(n)

另一种转置方法称作快速转置使时间复杂度降为O(m*n)它是按稀疏矩阵三元组表中元素的顺序进行按顺序取出一个元素放到转置矩阵三元组表的相应位置这就要求出每列非零元素个数和每列第一个非零元素在转置矩阵三元组表中的位置设置了两个附加向量

广义表中的元素可以是原子也可以是子表即广义表是原子或子表的有限序列满足线性结构的特性在非空线性结构中只有一个称为第一个的元素只有一个成为最后一个的元素第一元素有后继而没有前驱最后一个元素有前驱而没有后继其余每个元素有唯一前驱和唯一后继从这个意义上说广义表属于线性结构

数组是具有相同性质的数据元素的集合同时每个元素又有唯一下标限定可以说数组是值和下标偶对的有限集合n维数组中的每个元素处于n个关系之中每个关系都是线性的且n维数组可以看作其元素是n维数组的一个线性表而广义表与线性表的关系见上面题的解释

．线性表中的元素可以是各种各样的但必须具有相同性质属于同一数据对象广义表中的元素可以是原子也可以是子表其它请参见

（）（cd） （）（b） （）b （）（f） （）（）

[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []