设用邻接矩阵A表示有向图G的存储结构,则有向图G中顶点i的入度为

题目

设用邻接矩阵A表示有向图G的存储结构,则有向图G中顶点i的入度为()

  • A、第i行非0元素的个数之和
  • B、第i列非0元素的个数之和
  • C、第i行0元素的个数之和
  • D、第i列0元素的个数之和
如果没有搜索结果或未解决您的问题,请直接 联系老师 获取答案。
相似问题和答案

第1题:

用邻接矩阵A表示有向图G的存储结构,则有向图G中顶点i的出度为()。

A.第i行非0元素的个数之和

B.第i列非0元素的个数之和

C.第i行0元素的个数之和

D.第i列0元素的个数之和


正确答案:A

第2题:

● 设一个包含N个顶点、 E条边的简单有向图采用邻接矩阵存储结构 (矩阵元素A[i][j]等于1/0分别表示顶点i与顶点j之间有/无弧),则该矩阵的元素数目为 (60) ,其中非零元素数目为 (61) 。


正确答案:B,C

第3题:

设某有向无环图的顶点个数为n、弧数为e,那么用邻接表存储该图时,实现上述拓扑排序算法的函数TopSort的时间复杂度是(6)。

若有向图采用邻接矩阵表示(例如,图4-1所示有向图的邻接矩阵如图4-3所示),且将函数TopSort中有关邻接表的操作修改为针对邻接矩阵的操作,那么对于有n个顶点、e条弧的有向无环图,实现上述拓扑排序算法的时问复杂度是(7)。


正确答案:(6)O(n+e) (7)O(n2)
(6)O(n+e) (7)O(n2) 解析:邻接表:对有n个顶点和e条弧的有向图而言,在拓扑排序中,若有向图无环,则每个顶点进出队列各一次,共执行e次,搜索算法时间复杂度是由n和e共同决定的,所以总的时间复杂度为O(n+e)。
当用邻接矩阵:对于每个顶点,查找相邻边的时间复杂度是O(n),一共有n个顶点,所以总的时间复杂度是O(n2)。

第4题:

设一个包含N个顶点、E条边的简单无向图采用邻接矩阵存储结构(矩阵元素A[i][j]等于I/O分别表示顶点i与顶点j之间有/无边),则该矩阵中的非零元素数目为( )。

A.N
B.E
C.2E
D.N+E

答案:C
解析:
本题考查数据结构的基础知识。无向图的邻接矩阵是一个对称矩阵,每条边会表示两次,因此矩阵中的非零元素数目为2E。

第5题:

某有向图 G 及其邻接矩阵如下所示。以下关于图的邻接矩阵存储的叙述中,错误的是( )。

A. 有向图的邻接矩阵可以是对称矩阵B. 第 i行的非零元素个数为顶点 i的出度C. 第 i行的非零元素个数为顶点 i的入度D. 有向图的邻接矩阵中非零元素个数为图中弧的数目


正确答案:C

第6题:

●设一个包含N 个顶点、E 条边的简单无向图采用邻接矩阵存储结构(矩阵元素 A[i][j]等于1/0 分别表示顶点i与顶点 j 之间有/无边),则该矩阵中的非零元素数目为 (60)。

(60)

A.N

B.E

C.2E

D.N+E


正确答案:C

第7题:

带权有向图G用邻接矩阵A存储,则顶点i的入度等于A中(41)。

A.第i行非∞且非0的元素个数

B.第i列非∞且非0的元素个数

C.第i列非∞的元素之和

D.第i行非∞的元素之和


正确答案:B
解析:本题考查带权有向图的邻接矩阵存储。带权有向图的邻接矩阵反映顶点间的邻接关系,设G=(V,E)是具有n(n1)个顶点的图,G的邻接矩阵M是一个n行n列的矩阵,并有若(i,j)或i,j>∈E,则M[i][j]=权值;否则,M[i][j]=0。因此,对于有向图,其邻接矩阵的第i行非0元素个数为顶点i的出度,而邻接矩阵的第i列非0元素个数为顶点j的入度。

第8题:

用邻接矩阵A表示有向图G的存储结构,则有向图G中顶点i的入度为()。

A.第i行非0元素的个数之和

B.第i列非0元素的个数之和

C.第i行0元素的个数之和

D.第i列0元素的个数之和


正确答案:B

第9题:

某有向图G的邻接表如下图所示,可看出该图中存在弧,而不存在从顶点Vi出发的弧。关于图G的叙述中,错误的是()。

A.G中存在回路
B.G中每个顶点的入度都为1
C.G的邻接矩阵是对称的
D.G中不存在弧瓜

答案:C
解析:
根据题干邻接表得到的图如下:

第10题:

设一个包含n个顶点、e条弧的简单有向图采用邻接矩阵存储结构(即矩阵元素A[i][j]团等于1或0,分别表示顶点i与顶点j之间有弧或无弧),该矩阵购非零元素数目为( )。

A.e
B.2e
C.n-e
D.n+e

答案:A
解析:
用邻接矩阵存储有向图,图中每一条弧对应矩阵一个非零元素,题目中提到一共有e条弧,所以一共e个非零元素。

miao__miao 2016-05-13
请问矩阵是对称矩阵吗,那a-b和b-a都是1,节点数是不是应该是2e
MegumiIsh 2016-05-14
是不是对称矩阵看图,如果是无向图表示两个顶点直接的关系,那邻接矩阵是对称矩阵。如果是有向图的话又不一样,每一条弧对应矩阵一个非零元素,比如从节点i到节点j有边,则Aij为一个非零元素。如果从节点j到节点i有边,则Aji为一个非零元素。题目中提到一共有e条弧,所以一共e个非零元素。