设有向图G=(V，E)和G′-(V′，E′).如(G′)是G生成树，下面说法中不正确的是()A.G′为G的连通分量 B.G′为G的无环子图 C.G′为G的子图 D.G′为G的极小连通子图且V′=V

题目
设有向图G=(V，E)和G′-(V′，E′).如(G′)是G生成树，下面说法中不正确的是()

A.G′为G的连通分量
B.G′为G的无环子图
C.G′为G的子图
D.G′为G的极小连通子图且V′=V
相似考题

1.McCabe度量法计算公式为：V(G=m-n+p，其中V（G是强连通有向图G中的环数;m是G中的弧数;n是G中的节点数;p是G中分离部分的数目）。此题为判断题(对，错)。

2.有向图G=(V，E)，其中V={a，b，c，d}，E={a，ba，d，b，c，c，d}，则图G为强连通图。()

3.设G1=(V1,E1)和G2=(V2,E2)为两个图,如果V1ÍV2,E1ÍE2则称()。A、G1是G2的子图B、G1是G2的连通分量

4.设V'和E'分别为无向连通图G的点割集和边割集，下面的说法中正确的是Ⅰ．G-E'的连通分支数p(G-E')=2。Ⅱ．G-V'的连通分支数p(G-V')一定等于G-E'的连通分支数p(G-E')。Ⅲ．G-V'的连通分支数p(G-V')≥2。A．Ⅰ和ⅡB．Ⅰ和ⅢC．ⅡD．没有

参考答案和解析
答案：A
解析：
B项、D项都是生成树的特点，而A项为概念错误：G′为连通图而非连通分量，图的连通分量是指无向图中的极大连通子图。
更多“设有向图G=(V，E)和G′-(V′，E′).如(G′)是G生成树，下面说法中不正确的是()”相关问题

  • 第1题：

    图 G 的最小支撑树中从 V1 到 Vn 的通路一定是图 G 从 V1 到 Vn 的最短路。 ()

    此题为判断题(对，错)。


    正确答案:错误

  • 第2题：

    以下控制流图的圈复杂度V(g)和基本圈复杂度EV(g)是___(63)___

    (63)A．V(g)=5 EV(g)=1 B．V(g)=6 EV(g)=6

    C．V(g)=5 EV(g)=5 D．V(g)=6 EV(g)=1


    正确答案：D

  • 第3题：

    设有一个无向图G=(V，E)和G′=(V′,E′)，如果G′为G的生成树，则下面不正确的说法是(40)。

    A．G′为G的子图

    B．G′为G的极小连通子图且V′=V

    C．G′为G的一个无环子图

    D．G′为G的边通分量


    正确答案：D
    解析：本题考查无向图与其生成树的关系。对于无向图而言，如果无向图G是一个连通图，在对其进行遍历时，一次可以遍历所有顶点，得到的极小连通子图是一棵生成树，树中包含了图的所有顶点，但不一定包含所有的边；如果无向图G是一个非连通图，在对其进行遍历时，得到的是森林，这个森林是由图的连通分量的生成树组成的，森林中也不一定包含图中所有的边。因此，G'不一定为G的边通分量。

  • 第4题：

    以下控制流图的圈复杂度V（g）和基本圈复杂度EV（g）是（ ）。


    A.V（g）=5 EV（g）=1
    B.V（g）=6 EV（g）=6
    C.V（g）=5 EV（g）=5
    D.V（g）=6 EV（g）=1

    答案：D
    解析：
    本题考查从控制流图计算圈复杂度V(g)和基本圈复杂度EV(g)的方法。V(G)=(区域数)=6，Essential Complexity (ev(G))基本圈复杂度，是用来衡量程序非结构化程度的，非结构成分降低了程序的质量，增加了代码的维护难度，使程序难于理解。因此，基本复杂度高意味着非结构化程度高，难以模块化和维护。将圈复杂度图中的结构化部分简化成一个点，计算简化以后流程图的圈复杂度就是基本复杂度。当基本复杂度为1，这个模块是充分结构化的；当基本复杂度大于1而小于圈复杂度，这个模块是部分结构化的；当基本复杂度等于圈复杂度，这个模块是完全非结构化的。按照结构化原则简化后，原来的控制流图转变成顺序执行的流图，因此EV(g)=1。

  • 第5题：

    计算以下控制流程图的环路复杂性V（G），正确答案是（ ）。

    A.V（G）=2
    B.V（G）=4
    C.V（G）=9
    D.V（G）=11

    答案：B
    解析：
    本题考查环路复杂性的计算方法。V(G)=edge-node+2=11-9+2=4，其中edge为控制流程图的边数，node为控制流程图的节点数。

  • 第6题：

    设无向图G=（V，E）和G’=（V’，E’），如果G’是G的生成树，则下面的说法中错误的是（）。

    • A、G’为G的子图
    • B、G’为G的连通分量
    • C、G’为G的极小连通子图且V=V’
    • D、G’是G的一个无环子图

    正确答案:B

  • 第7题：

    互在任一图G中，当点集V确定后，树图是G中边数最少的连通图。


    正确答案:正确

  • 第8题：

    设G1=（V1，E1）和G2=（V2，E2）为两个图，如果V1V2，E1E2则称（）。

    • A、G1是G2的子图
    • B、G2是G1的子图
    • C、G1是G2的连通分量
    • D、G2是G1的连通分量

    正确答案:A

  • 第9题：

    判断题
    在任一图G中，当点集V确定后，树图是G中边数最少的连通图。（）
    A

    对

    B

    错


    正确答案： 错
    解析： 暂无解析

  • 第10题：

    单选题
    设无向图G=（V，E）和G’=（V’，E’），如果G’是G的生成树，则下面的说法中错误的是（）。
    A

    G’为G的子图

    B

    G’为G的连通分量

    C

    G’为G的极小连通子图且V=V’

    D

    G’是G的一个无环子图


    正确答案： D
    解析： 暂无解析

  • 第11题：

    单选题
    以下说法不正确的是（）。
    A

    连通图G一定存在生成树

    B

    连通图G的生成树中一定包含G的所有顶点

    C

    连通图G的生成树中不一定包含G的所有边

    D

    连通图G的生成树可以是不连通的


    正确答案： B
    解析： 暂无解析

  • 第12题：

    判断题
    互在任一图G中，当点集V确定后，树图是G中边数最少的连通图。
    A

    对

    B

    错


    正确答案： 对
    解析： 暂无解析

  • 第13题：

    ● 计算以下控制流程图的环路复杂性 V(G)，正确答案是（44） 。

    （44）

    A．V(G)=2

    B．V(G)=4

    C．V(G)=9

    D．V(G)=11


    正确答案：B

  • 第14题：

    计算以下控制流程图的环路复杂度V（G）,正确答案是（44）。

    A.V（G）=2

    B.V（G）=4

    C.V（G）=9

    D.V（G）=11


    正确答案：B
    解析：

  • 第15题：

    设无向图G=(V，E)和G′=(V′，E′)，如果G′是G的生成树，则下面的说法中错误的是()。

    A.G′为G的极小连通子图且V=V′
    B.G′是G的一个无环子图
    C.G′为G的子图
    D.G′为G的连通分量

    答案：D
    解析：
    连通分量是无向图的极大连通子图，其中极大的含义是将依附于连通分量中顶点的所有边都加上，所以，连通分量中可能存在回路。

  • 第16题：

    图G的邻接矩阵如下图所示（顶点依次表示为v0、v1、v2、v3、v4、v5），G是（请作答此空）。对G进行广度优先遍历（从v0开始），可能的遍历序列为（ ）。


    A.无向图
    B.有向图
    C.完全图
    D.强连通图

    答案：B
    解析：

  • 第17题：

    以下说法不正确的是（）。

    A连通图G一定存在生成树

    B连通图G的生成树中一定包含G的所有顶点

    C连通图G的生成树中不一定包含G的所有边

    D连通图G的生成树可以是不连通的


    D
    略

  • 第18题：

    在公式V（G）=E–N+2中：E为程序图G中边的总数；N为程序图中结点的总数。V（G）又称为图G的环形（）。


    正确答案:复杂度

  • 第19题：

    在任一图G中，当点集V确定后，树图是G中边数最少的连通图。（）


    正确答案:正确

  • 第20题：

    以下有关联通图的说法不正确的是（）。

    • A、连通图G一定存在生成树
    • B、连通图G的生成树中一定包含G的所有顶点
    • C、连通图G的生成制中不一定包含G的所有边
    • D、连通图G的生成树可以是不连同的

    正确答案:D

  • 第21题：

    填空题
    在公式V（G）=E–N+2中：E为程序图G中边的总数；N为程序图中结点的总数。V（G）又称为图G的环形（）。

    正确答案： 复杂度
    解析： 暂无解析

  • 第22题：

    单选题
    以下有关联通图的说法不正确的是（）。
    A

    连通图G一定存在生成树

    B

    连通图G的生成树中一定包含G的所有顶点

    C

    连通图G的生成制中不一定包含G的所有边

    D

    连通图G的生成树可以是不连同的


    正确答案： B
    解析： 暂无解析

  • 第23题：

    单选题
    设G1=（V1，E1）和G2=（V2，E2）为两个图，如果V1V2，E1E2则称（）。
    A

    G1是G2的子图

    B

    G2是G1的子图

    C

    G1是G2的连通分量

    D

    G2是G1的连通分量


    正确答案： A
    解析： 暂无解析

相关内容