早教吧考试题库频道 --> 计算机类考试 -->软考中级 -->
简单无向图的邻接矩阵是对称的,可以对其进行压缩存储。若无向图G有n个节点,其邻接矩阵为 A[1…n,1…
题目
简单无向图的邻接矩阵是对称的,可以对其进行压缩存储。若无向图G有n个节点,其邻接矩阵为 A[1…n,1…n],且压缩存储在B(1…k)中,则k的值至少为(63)。
A.
B.
C.
D.
参考答案
正确答案:B
解析:具有n个节点的简单无向图的邻接矩阵是对称矩阵。对称矩阵关于主对角线对称,因此只需存储上三角或下三角部分即可。例如,只存储上三角中的元素aij,其特点是j≤i且1≤i≤n,对于上三角中的元素aij,它与对应的aij相等,因此当访问的元素在上三角时,直接去访问和它对应的下三角元素即可。由此可知,原来n×n个存储单元,现在只需要n(n+1)/2个存储单元。另外,由于简单无向图中没有自环,因此主对角线的元素无须存储,因此至少需要n(n-1)/2个存储单元。
解析:具有n个节点的简单无向图的邻接矩阵是对称矩阵。对称矩阵关于主对角线对称,因此只需存储上三角或下三角部分即可。例如,只存储上三角中的元素aij,其特点是j≤i且1≤i≤n,对于上三角中的元素aij,它与对应的aij相等,因此当访问的元素在上三角时,直接去访问和它对应的下三角元素即可。由此可知,原来n×n个存储单元,现在只需要n(n+1)/2个存储单元。另外,由于简单无向图中没有自环,因此主对角线的元素无须存储,因此至少需要n(n-1)/2个存储单元。
看了简单无向图的邻接矩阵是对称的,...的网友还看了以下:
∑(2^n)/(n^n)的收敛性你回答的是:取后一项后前一项的比.(2^n+1)/((n+1)^(n 数学 2020-03-31 …
与地球质量,体积都比较接近的行星是什么如题 其他 2020-04-09 …
关于java直接插入算法的问题当初始序列已经按键值有序,用直接插入算法对其进行排序,需要循环的次数 其他 2020-05-13 …
如图,在平行四边形ABCD中,P1,P2,…,Pn是BD的n等分点,连接AP2并延长交BC于点E, 其他 2020-05-13 …
1.如果n阶行列式中负项的个数为偶数,则n>= 2.如果n阶行列式中等于零的元素个数大于n^2-n 数学 2020-05-16 …
如数表:第1行12345…1415第2行3029282726…1716第3行3132333435… 数学 2020-05-17 …
OMRONPLC交流电源L1,L2/N接口将220VAC接入,按说是一根火线一根零线啊,为什么将L 其他 2020-05-17 …
有若千张边长都是2的三角形纸片,从中取出一些纸片按如图所示的方式拼接起来,可以拼成一个大的平行四边 数学 2020-05-17 …
对于区间[m,n]上有意义的两个函数f(x)与g(x),如果任意x∈[m,n],均有|f(x)-g 其他 2020-05-17 …
考验你的智商!在n边行某一边上任取一点p,连接点p与多边形的每一个顶点,可得多少个三角形?请根据划 数学 2020-05-20 …