niusouti.com
参考答案和解析
G1是G的连通分量
更多“设无向图G=(V,E)和G'=(V',E'),如果G'是G的生成树,则下列说法中错误的是_____。”相关问题
  • 第1题:

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


    参考答案:错误

  • 第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题:

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

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

    答案:A
    解析:
    B项、D项都是生成树的特点,而A项为概念错误:G′为连通图而非连通分量,图的连通分量是指无向图中的极大连通子图。

  • 第5题:

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


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

    答案:B
    解析:

  • 第6题:

    若已知有向图G=(V,E),其中,顶点的集合为V={v1,v2,v3,v4,v5},弧的集合为E={, },则G的拓扑序列有哪些?(写出结论即可)


    正确答案:G的拓扑序列有3个,分别是v1,v2,v3,v4,v5;v1,v3,v2,v4,v5和v1,v3,v4,v2,v5。

  • 第7题:

    在公式V(G)=E–N+2中:E为程序图G中边的总数;N为程序图中结点的总数。V(G)又称为图G的环形()。


    正确答案:复杂度

  • 第8题:

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


    正确答案:正确

  • 第9题:

    以下有关联通图的说法不正确的是()。

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

    正确答案:D

  • 第10题:

    填空题
    在公式V(G)=E–N+2中:E为程序图G中边的总数;N为程序图中结点的总数。V(G)又称为图G的环形()。

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

  • 第11题:

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

    连通图G一定存在生成树

    B

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

    C

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

    D

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


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

  • 第12题:

    单选题
    设G1=(V1,E1)和G2=(V2,E2)为两个图,如果V1V2,E1E2则称()。
    A

    G1是G2的子图

    B

    G2是G1的子图

    C

    G1是G2的连通分量

    D

    G2是G1的连通分量


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

  • 第13题:

    设G1=(V1,E1)和G2=(V2,E2)为两个图,如果V1ÍV2,E1ÍE2则称()。

    A、G1是G2的子图

    B、G1是G2的连通分量


    参考答案:A

  • 第14题:

    设|V|=n(n>1),当且仅当______,G=是强连通图。A.G中至少有一条路B.G中至少有一条回路C.G中有

    设|V|=n(n>1),当且仅当______,G=<V,E>是强连通图。

    A.G中至少有一条路

    B.G中至少有一条回路

    C.G中有通过每个节点至少一次的路

    D.G中有通过每个节点至少一次的回路

    A.

    B.

    C.

    D.


    正确答案:D
    解析:在简单有向图G中,任何一对节点间两者之间是相互可达的,则称这个图是强连通的。设|V|=n(n>1),当且仅当G中有通过每个节点至少一次的回路,G=V,E>是强连通图。
      对于选项C,例如图“A→B”,即只有A到达B,有一次路,但是该图不是强连通的。因此选项C的说法不能成为强连通图的充要条件。

  • 第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题:

    以下控制流图的圈复杂度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。

  • 第17题:

    以下说法不正确的是()。

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

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

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

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


    D

  • 第18题:

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

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

    正确答案:B

  • 第19题:

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


    正确答案:正确

  • 第20题:

    设G1=(V1,E1)和G2=(V2,E2)为两个图,如果V1V2,E1E2则称()。

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

    正确答案:A

  • 第21题:

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

    B


    正确答案:
    解析: 暂无解析

  • 第22题:

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

    G’为G的子图

    B

    G’为G的连通分量

    C

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

    D

    G’是G的一个无环子图


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

  • 第23题:

    单选题
    以下说法不正确的是()。
    A

    连通图G一定存在生成树

    B

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

    C

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

    D

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


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

  • 第24题:

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

    B


    正确答案:
    解析: 暂无解析