问答题
特殊矩阵和稀疏矩阵哪一种压缩存储后失去随机存取的功能?为什么? 【北京邮电大学2001三、1(5分)】
【正确答案】正确答案:特殊矩阵指值相同的元素或零元素在矩阵中的分布有一定规律,因此可以对非零元素分配单元(对值相同元素只分配一个单元),将非零元素存储在向量中,元素的下标i和j和该元素在向量中的下标有一定规律,可以用简单公式表示,仍具有随机存取功能。而稀疏矩阵是指非零元素和矩阵容量相比很小(t<<m*n,且分布没有规律。用十字链表作存储结构自然失去了随机存取的功能。即使用三元组表的顺序存储结构,存取下标为i和j的元素时,要扫描三元组表,下标不同的元素,存取时间也不同,最好情况下存取时间为O(1),最差情况下是O(n),因此也失去了随机存取的功能。
【答案解析】