🏷️ 知识点：三元组表

适用于压缩存储稀疏矩阵的两种存储结构是（）

特殊矩阵

A. 三元组表和十字链表 B. 三元组表和邻接矩阵 C. 十字链表和二叉链表 D. 邻接矩阵和十字链表

[tag_link]

正确答案：A

三元组表 的结点存储了行 row、列 col、值 value 三种信息，是主要用来存储稀疏矩阵的一种 数据结构。十字链表将行单链表和列单链表结合起来存储稀疏矩阵。邻接矩阵空间复杂度达O(n2), 不适用于存储稀疏矩阵。二叉链表又名左孩子右兄弟表示法，可用于表示树或森林。因此 A 正确。

若采用三元组表存储结构存储系数矩阵 M。则除三元组外，下列数据中还需要保存的是（ ）。

I. M 的行数

II. M 中包含非零元素的行数

III. M 的列数

IV. M 中包含非零元素的列数

特殊矩阵 三元组表

A. 仅 I 和 III B. 仅 I 和 IV C. 仅 II 和 IV D. I, II, III, IV

[tag_link]

正确答案：A

存储稀疏矩阵 M， 三元组表 的表项存储了行 row、列 col、值 value 三种信息，除此之外，我们还需要知道矩阵 M 的规模 rows × cols，即 M 的行数 rows 和 M 的列数 cols，这个信息应该直接给出。当我们需要某个位置的元素，可以先根据 M 的行数和列数判断是否越界，如果没有越界，在三元组进行查找，如果三元组没有保存对应位置的值代表矩阵中该位置的值为 0。本题答案选 A。