杭州交通信息网新外大街28号院:邻接矩阵压缩存储问题
来源：百度文库 编辑：杭州交通信息网 时间：2024/05/10 13:56:05
简单无向图的邻接矩阵是对称的，可以对其进行压缩存储。若无向图G有n个节点。若无向图G 有n个节点，其邻接矩阵为A[1..n,1..n], 且压
缩存储在B[1..k] 中，则k 的值至少为____(40)____ 。若按行压缩存储对称矩阵的上三角元素，则当n等于10时，边(V6，V3) 的信息存储在B
[___(41)___] 中。
（40）A.n(n+1)/2 B.n^2/2 C.(n-1)(n+1)/2 D.n(n-1)/2
（41）A.18 B.19 C.20 D.21
为什么选DC,我选的是AD,当然答案是DC,请帮分析一下详细解法,有图更好!
同时还有一题:
在二叉树的顺序存储中，每个结点的存储位置与其父结点、左右子树结点的位置都存在一个简单的映射关系，因此可与三叉链表对应。若某
二叉树共有n个结点，采用三叉链表存储时，每个结点的数据域需要d个字节，每个指针域占用4个字节，若采用顺序存储，则最后一个结点下标
为k（起始下标为1）,那么___(39)___ 时采用顺序存储更节省空间。
（39）A.d<12n/(k-n) B.d>12n/(k-n) C.d<12n/(k+n) D.d>12n/(k+n)
为什么答案是A,希望答案详细些!
缩存储在B[1..k] 中，则k 的值至少为____(40)____ 。若按行压缩存储对称矩阵的上三角元素，则当n等于10时，边(V6，V3) 的信息存储在B
[___(41)___] 中。
（40）A.n(n+1)/2 B.n^2/2 C.(n-1)(n+1)/2 D.n(n-1)/2
（41）A.18 B.19 C.20 D.21
为什么选DC,我选的是AD,当然答案是DC,请帮分析一下详细解法,有图更好!
同时还有一题:
在二叉树的顺序存储中，每个结点的存储位置与其父结点、左右子树结点的位置都存在一个简单的映射关系，因此可与三叉链表对应。若某
二叉树共有n个结点，采用三叉链表存储时，每个结点的数据域需要d个字节，每个指针域占用4个字节，若采用顺序存储，则最后一个结点下标
为k（起始下标为1）,那么___(39)___ 时采用顺序存储更节省空间。
（39）A.d<12n/(k-n) B.d>12n/(k-n) C.d<12n/(k+n) D.d>12n/(k+n)
为什么答案是A,希望答案详细些!