2. 考研
  3. 有如图3—4所示的带权有向图G，试回答以下问题。 若用三元组存储邻接矩阵的数据，每个三元组占3个字节，求共需多大空间？若用邻接矩阵存储时每个元素占1个字节，试比较哪种存储更省空间。

有如图3—4所示的带权有向图G，试回答以下问题。 若用三元组存储邻接矩阵的数据，每个三元组占3个字节，求共需多大空间？若用邻接矩阵存储时每个元素占1个字节，试比较哪种存储更省空间。

admin2017-04-28  34
问题 有如图3—4所示的带权有向图G，试回答以下问题。

若用三元组存储邻接矩阵的数据，每个三元组占3个字节，求共需多大空间？若用邻接矩阵存储时每个元素占1个字节，试比较哪种存储更省空间。
选项
答案稀疏矩阵的压缩一般采用三元组的方式，参考下面的补充知识点。 补充知识点：稀疏矩阵采用三元组压缩。 三元组压缩就是存储矩阵非零元素中的行、列、值3个元素。将表示稀疏矩阵的非零元素的三元组按行优先（或列优先）的顺序排列（跳过零元素），并依次存放在向量中，将这种稀疏矩阵的顺序存储结构称为三元组表。 例如矩阵M: [*] 则三元组表为（假设下标都从1开始）： {(1， 3， 9)， (1， 5，一7)， (3， 4， 8)， (4， 1， 5)， (4， 6， 2)， (5， 5， 16)} 回到题目，从题干给出的图可以看出，该图一共有13条边，也就是需要13个三元组来存储，而每个三元组占3个字节，所以共占用空间3×13B=39B。如果采用邻接矩阵，则需要一个8×8的矩阵，共64个元素，每个元素占1个字节，共需64B。综上所述，三元组更节省空间。
解析
转载请注明原文地址:https://kaotiyun.com/show/kPRi777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

相关试题推荐
随机试题
最新回复(0)