工学

填空题对于有向图，顶点V的度分为（）。

题目
填空题
对于有向图，顶点V的度分为（）。
如果没有搜索结果，请直接 联系老师 获取答案。
如果没有搜索结果，请直接 联系老师 获取答案。
相似问题和答案

第1题：

对有向图,下面()种说法是正确的。

A.每个顶点的入度等于出度

B.每个顶点的度等于其入度与出度之和

C.每个顶点的入度为0

D.每个顶点的出度为0


参考答案：B

第2题：

在有向图的邻接表表示中,顶点v在边单链表中出现的次数是()。

A.顶点v的度

B.顶点v的出度

C.顶点v的入度

D.依附于顶点v的边数


参考答案：C

第3题：

设一个图G={V,{A}},V={a,b,c,d,e,f},A={,,,,,,}。那么顶点e的入度是_____;出度是_____;通过顶点f的简单回路有_____条;就连通性而言,该图是_____图;它的强连通分量有_____个;其生成树可能的最大深度是_____。


参考答案：2;1;2;强连通分量;1;5

第4题：

拓扑序列是有向无环图中所有顶点的一个线性序列，若有向图中存在弧或存在从顶点v到w的路径，则在该有向图的任一拓扑序列中，V一定在w之前。下面有向图的拓扑序列是( )

A.41235

B.43125

C.42135

D.41=325


正确答案：A

第5题：

设某有向无环图的顶点个数为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)。

第6题：

设无向图中有6条边,有一个3度顶点和一个5度顶点,其余顶点度为2,则该图的顶点数是()

A、3

B、4

C、5

D、6


参考答案：B

第7题：

在有向图的邻接表表示中,顶点v的边单链表中的结点个数等于()。

A.顶点v的度

B.顶点v的出度

C.顶点v的入度

D.依附于顶点v的边数


参考答案：B

第8题：

对n个顶点的有向图,若所有顶点的出度之和为s,则所有顶点的入度之和为()。

A.s

B.s-1

C.s+1

D.n


参考答案：A

第9题：

一个有8个顶点的有向图，所有顶点的入度出度之和与所有顶点的出度之和的差是()

A.16

B.4

C.0

D.2


正确答案：C

第10题：

如果一个有向图(25)，则是一棵有向树。

A．恰有一个顶点的人度为0，其余顶点的人度为1

B．恰有一个顶点的人度为1，其余顶点的人度为0

C．恰有一个顶点的人度为1，其余顶点的人度为2

D．恰有一个顶点的人度为1，其余顶点的度大于1


正确答案：A
解析：本题考察了对有向树概念的理解。

更多相关问题
相关内容