适用于压缩存储稀疏矩阵的两种存储结构是()
A.三元组表和十字链表
B.三元组表和邻接矩阵
C.十字链表和二叉链表
D.邻接矩阵和十字链表
解答:
关于图的存储结构,我...
用户登录可进行刷题及查看答案
关于图的存储结构,我们学过邻接矩阵、邻接表、十字链表和邻接多重表。
这边要求压缩稀疏矩阵,所以建议使用 O(|V|+|E|) 的存储结构存储, O(|V|^2) 空间复杂度的邻接矩阵排除,剩选项A和C,十字链表空间复杂度为 O(|V|+|E|) ,正确。剩下的两个概念三元组表和二叉链表在图的存储结构中我们并没有接触过,但是我们可以排除二叉链表,二叉链表就是有两个指针的链表啊,不就是二叉树吗?树是图的一种特例,图的存储结构能存储树,但树的存储结构不能存储图,排除选项C,只剩选项A了。
三元组表的结点存储了行row、列col、值value三种信息,即两个顶点和边权,是主要用来存储稀疏矩阵的一种数据结构。也就是三元组表存储系数矩阵的空间复杂度为 O(|V|+|E|) ,正确。
二叉链表又名左孩子右兄弟表示法,可用于表示树或森林。
本题选A。
登录后提交答案
暂无评论,来抢沙发