🏷️ 知识点：图的存储
下列关于图的存储结构的说法中，错误的是（ ）。
A. 使用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中的顶点数有关，与边数无关 B. 邻接表只用于有向图的存储，逆邻接表只用于无向图的存储 C. 若一个有向图的邻接矩阵的主对角线以下元素全为 0，则边只由小编号顶点指向大编号顶点，该图无环且必定存在拓扑序列（不保证唯一） D. 存储无向图的邻接矩阵是对称的，所以只需存储邻接矩阵的下（或上）三角部分
[tag_link]
正确答案：B
结论
错误的是 B。邻接表既可表示有向图，也可表示无向图；逆邻接表同样服务于有向图的入边访问。
推导
邻接矩阵始终按顶点对分配空间，未压缩时为 (O(n^2))，与边数无关。无向图矩阵对称，可只保存一侧三角区；若有向图矩阵主对角线以下全为 0，所有边均从小编号指向大编号，因而不可能成环，按编号升序即可得到一个拓扑序列。
易错点
不要把“邻接表”和“逆邻接表”误认为只适用于某一种图：邻接表通常记录出边，逆邻接表记录入边，二者主要用于有向图的不同访问方向；无向图也可用邻接表表示。
若图的邻接矩阵中主对角线上的元素皆为 0，其余元素全为 1，则该图一定（ ）。
A. 是无向图 B. 是有向图 C. 是完全图 D. 不是带权图
[tag_link]
正确答案：C
结论
该图一定是完全图，答案为 C。
推导
主对角线全为 0 表示没有自环；其余 (n(n-1)) 个位置全为 1，表示任意两个不同顶点之间都存在相应连接。在简单图的邻接矩阵约定下，每一对不同顶点均相邻，故为完全图。
易错点
矩阵是否对称才能进一步判断有向或无向；题干只给出对角线和非对角线取值，不能据此断言图的方向性。矩阵元素为 1 也不排斥“无权表示”，所以“不是带权图”不是必然结论。
在含有 (n) 个顶点和 (e) 条边的简单无向图的邻接矩阵中，零元素的个数为（ ）。
A. (e) B. (2e) C. (n^2-e) D. (n^2-2e)
[tag_link]
正确答案：D
结论
零元素的个数为 (n^2-2e)，答案为 D。
推导
邻接矩阵共有 (n^2) 个位置。简单无向图没有自环，且每条无向边在矩阵中占据对称的两个非零位置，因此非零位置数为 (2e)，零元素数为 (n^2-2e)。
易错点
不能把每条无向边只计一次；矩阵同时记录 ((i,j)) 和 ((j,i))。若题目允许自环或使用其他特殊编码，公式需重新判断，本题明确按简单无向图处理。
带权有向图 (G) 用邻接矩阵存储，约定无边位置为 (\infty)（对角线为 0），则顶点 (v_i) 的入度等于邻接矩阵中（ ）。
A. 第 (i) 行非 (\infty) 的元素个数 B. 第 (i) 列非 (\infty) 的元素个数 C. 第 (i) 行非 (\infty) 且非 0 的元素个数 D. 第 (i) 列非 (\infty) 且非 0 的元素个数
[tag_link]
正确答案：D
结论
答案为 D：扫描第 (i) 列，统计既不是 (\infty) 又不是 0 的元素。
推导
邻接矩阵的第 (j) 行第 (i) 列元素表示边 (v_j\to v_i) 的权值。第 (i) 列中每个有限且非零的权值对应一条进入 (v_i) 的边，因此其个数就是入度；第 (i) 行统计的是出度。
易错点
入度与出度的方向相反：入度看列，出度看行。带权矩阵中不能只判断“非 (\infty)”——对角线的 0 表示无自环，必须同时排除 0。
一个有 n 个顶点的图用邻接矩阵 A 表示，若图为有向图，顶点 v₁的 入 度 是 ( ) ; 若 图 为无向图，顶点v; 的 度 是 ( ) 。
B.
[tag_link]
正确答案：【解答】
从邻接矩阵 看出，该图共有(①)个顶点；若是有向图，则该图共有 拟 (②)条弧；若是无向图，则共有(③)条边。 ① A.9 E. 以上答案均不正确 ② A.5 E. 以上答案均不正确 ③ A.5 E. 以上答案均不正确
B. 3 C. 6 D. 1 B. 4 C. 3 D. 2 B. 4 C. 3 D. 2
[tag_link]
正确答案：【解答】
以下关于图的存储结构的叙述中，正确的是()。
A. 一个图的邻接矩阵表示唯一，邻接表表示唯一 B. 一个图的邻接矩阵表示唯一，邻接表表示不唯一 C. 一个图的邻接矩阵表示不唯一，邻接表表示唯一 D. 一个图的邻接矩阵表示不唯一，邻接表表示不唯一
[tag_link]
正确答案：B
结论
答案为 B：固定顶点编号后，邻接矩阵表示唯一；邻接表受边输入顺序和插入位置影响，不唯一。
推导
矩阵的行列位置由顶点编号确定；邻接表只要求表达同一组邻接关系，链表结点顺序可以不同。
易错点
不要把“表示唯一”误解为存储对象只有一种物理布局；邻接表的顺序变化不改变图。
矩阵A是有向图G的邻接矩阵，若矩阵(A^2)的某元素((A^2)_{ij}=3)，则说明()。
A. 从顶点i 到j 存在3条长度为2的路径 B. 从顶点i 到j存在3条长度不超过2的路径 C. 从顶点i 到j 存在2条长度为3的路径 D. 从顶点i 到j 存在2条长度不超过3的路径
[tag_link]
正确答案：A
结论
答案为 A：从顶点 i 到 j 恰有 3 条长度为 2 的路径。
推导
矩阵乘法中 ((A^2){ij}=\sum_k A{ik}A_{kj})，每个乘积对应经由中间顶点 k 的一条两步路径。
易错点
矩阵幂统计的是“恰好”长度，不是“不超过”长度；长度 3 也不能由 (A^2) 得出。
用邻接表法存储图所用的空间大小()。
A. 与图的顶点数和边数有关 B. 只与图的边数有关 C. 只与图的顶点数有关 D. 与边数的平方有关
[tag_link]
正确答案：A
结论
答案为 A：邻接表空间与顶点数和边数都有关。
推导
顶点表需要 (O(n))；有向图边结点为 (e)，无向图每条边存两次为 (2e)，总空间为 (O(n+e))。
易错点
不能只按边数估算，顶点表即使没有边也要占用空间。
若邻接表中有奇数个边表结点，则()。
A. 图中有奇数个顶点 B. 图中有偶数个顶点 C. 图为无向图 D. 图为有向图
[tag_link]
正确答案：D
结论
答案为 D：边表结点数为奇数时，图必为有向图。
推导
无向图每条边在两个端点的边表中各存一次，总数为 (2e) 必为偶数；有向图按弧存一次，可为奇数。
易错点
奇数只能排除无向图，不能据此推出顶点数奇偶性。
在有向图的邻接表存储结构中，顶点v 在边表中出现的次数是()。
A. 顶点v的度 B. 顶点 v的出度 C. 顶点v的入度 D. 依附于顶点v 的边数
[tag_link]
正确答案：C
结论
答案为 C：v 在所有边表中作为终点出现的次数就是入度。
推导
邻接表按起点组织出边；统计所有边表中目标顶点为 v 的结点，恰好得到指向 v 的弧数。
易错点
只遍历 v 自己的边表得到的是出度，不是入度。
n 个顶点的无向图的邻接表最多有()个边表结点。
A. n² B.n(n-1) C.n(n+1) D.n(n-1)/2
[tag_link]
正确答案：B
结论
答案为 B：最多有 (n(n-1)) 个边表结点。
推导
无向完全图有 (n(n-1)/2) 条边，邻接表中每条边存入两个端点的边表，因此结点数为 (n(n-1))。
易错点
选项 D 是边数而非边表结点数，少乘了 2。
设某无向图中有n 个顶点和e 条边，则建立该图的邻接表的时间复杂度为()。
A. O(n+e) B.O(n²) C.O(ne) D.O(n³)
[tag_link]
正确答案：A
结论
答案为 A：建立邻接表的时间复杂度为 (O(n+e))。
推导
初始化 n 个顶点表结点并处理每条边（无向图处理两次），总操作数是 n 与 e 的线性和。
易错点
不要把邻接表建表误写成矩阵的 (O(n^2))；只有扫描整张矩阵才有该复杂度。
假设有 n 个顶点、e 条边的有向图用邻接表表示，则删除与某个顶点 v 相关的所有边的 时间复杂度为()。
A. O(n) B.O(e) C.O(n+e) D.O(ne)
[tag_link]
正确答案：C
结论
答案为 C：删除与 v 相关的全部出边和入边需要 (O(n+e))。
推导
删除 v 的出边需扫描 v 的边表，删除入边则要扫描其余顶点边表；合计最多访问全部顶点和边。
易错点
仅删除出边可近似为 (O(n))，但题目还要求删除所有入边，不能忽略全表扫描。
已知带权有向图G 的邻接矩阵如下图所示，请画出该带权有向图G。 第 6 章 图209 第 6 章 图
[tag_link]
B
设图G=(V,E) 以邻接表存储，如下图所示。画出其邻接矩阵存储及图G。 453544523 4 5 3 5 4 4 5 2 3
[tag_link]
C