参考答案和解析
正确答案:B
更多“6个顶点的连通图的最小生成树,其边数为()A、6B、5C、7D、4”相关问题
  • 第1题:

    M个顶点的连通图的最小支撑树有()条边。


    参考答案:M-1

  • 第2题:

    具有6个顶点的连通图的广度优先生成树,其边数为(53)。

    A.6

    B.5

    C.7

    D.4


    正确答案:B
    解析:连通图的生成树具有两个特点:①所有顶点是连通的;②不构成回路。n个顶点要连通必须要有n-1条边,再多一条边必形成回路。所以,具有6个顶点的连通图的广度优先生成树,其边数为5。

  • 第3题:

    从赋权连通图中生成最小树,以下叙述()不正确。

    • A、任一连通图生成的各个最小树,其总长度必相等
    • B、任一连通图生成的各个最小树,其边数必相等
    • C、任一连通图中具有最小权的边必包含在生成的最小树上
    • D、最小树中可能包括连通图中的最大权边

    正确答案:A,B,D

  • 第4题:

    关于图的生成树,下列说法不正确的是()。

    • A、它又称为图的支撑树。
    • B、图有生成树的充要条件是该图为连通图。
    • C、图的生成树是唯一的。
    • D、顶点数为n的图的生成树有n-1条边。

    正确答案:C

  • 第5题:

    对于含有n个顶点e条边的连通图,利用Prim算法求最小生成树的时间复杂度为(),利用Kruskal算法求最小生成树的时间复杂度为()。


    正确答案:O(n2);O(elog2e)

  • 第6题:

    一个连通图的生成树是该图的()连通子图。若这个连通图有n个顶点,则它的生成树有()条边。


    正确答案:极小(最小);n-1

  • 第7题:

    数据结构里,有4个顶点的无向图,最多有()条边。

    • A、6
    • B、5
    • C、7
    • D、4

    正确答案:A

  • 第8题:

    对于一个具有n个顶点和e条边的连通图,其生成树中的顶点数和边数分别为()和()。


    正确答案:n;n-1

  • 第9题:

    单选题
    最小生成树指的是()。
    A

    由连通网所得到的边数最少的生成树

    B

    由连通网所得到的顶点数相对较少的生成树

    C

    连通网中所有生成树中权值之和为最小的生成树

    D

    连通网的极小连通子图


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

  • 第10题:

    填空题
    一个连通图的生成树是该图的()连通子图。若这个连通图有n个顶点,则它的生成树有()条边。

    正确答案: 极小(最小),n-1
    解析: 暂无解析

  • 第11题:

    单选题
    由一个具有n个顶点的连通图生成的最小生成树中,具有()条边。
    A

     n

    B

     n-1

    C

     n+1

    D

     2×n


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

  • 第12题:

    填空题
    对于含有n个顶点e条边的连通图,利用Prim算法求最小生成树的时间复杂度为(),利用Kruskal算法求最小生成树的时间复杂度为()。

    正确答案: O(n2),O(elog2e)
    解析: 暂无解析

  • 第13题:

    n个顶点的连通图的生成树有()条边。

    A.n

    B.n-1

    C.n+1

    D.不确定


    参考答案:B

  • 第14题:

    对于含有n个顶点的带权连通图,它的最小生成树是指()。

    A.图中任意一个由n-l条权值最小的边构成的子图
    B.图中任意一个由n-1条权值之和最小的边构成的子图
    C.图中任意一个由n-1条权值之和最小的边构成的连通子图
    D.图中任意一个由n个顶点构成的边的权值之和最小的连通子图

    答案:D
    解析:
    一个连通图的生成树(连通无回路图)是一个极小连通子图。它含有图中全部n个项点,但只有构成一棵树的(n-1)条边。如果小于(n-1)条边,则是非连通图;如果多于(n-1)条边,则一定有回路,因为这条边使得它依附的那两个顶点之间有了第二条路径。但是,有(n-1)条边的图不一定都是生成树。带权连通无向图的所有生成树中具有边上的权值之和最小的树称为图的最小生成树。总之,含有n个顶点的带权连通图,它的最小生成树是指图中任意一个由n个顶点构成的边的权值之和最小的连通子图。

  • 第15题:

    从连通图中生成树,以下叙述()正确。

    • A、任一连通图必有支撑树
    • B、任一连通图生成的支撑树必唯一
    • C、在支撑树中再增加一条边后必含圈
    • D、任一连通图生成的各个支撑树其边数必相同

    正确答案:A,C,D

  • 第16题:

    若图G的最小生成树不唯一,则G的边数一定多于n-1,并且权值最小的边有多条(其中n为G的顶点数)。


    正确答案:正确

  • 第17题:

    最小生成树指的是()。

    • A、由连通网所得到的边数最少的生成树
    • B、由连通网所得到的顶点数相对较少的生成树
    • C、连通网中所有生成树中权值之和为最小的生成树
    • D、连通网的极小连通子图

    正确答案:C

  • 第18题:

    由一个具有n个顶点的连通图生成的最小生成树中,具有()条边。

    • A、 n
    • B、 n-1
    • C、 n+1
    • D、 2×n

    正确答案:B

  • 第19题:

    对于含有N个顶点E条边的无向连通图,利用Kruskal算法生成最小代价生成树的时间复杂度为()。


    正确答案:o(elg0)

  • 第20题:

    多选题
    从连通图中生成树,以下叙述()正确。
    A

    任一连通图必有支撑树

    B

    任一连通图生成的支撑树必唯一

    C

    在支撑树中再增加一条边后必含圈

    D

    任一连通图生成的各个支撑树其边数必相同


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

  • 第21题:

    单选题
    6个顶点的连通图的最小生成树,其边数为()
    A

    6

    B

    5

    C

    7

    D

    4


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

  • 第22题:

    填空题
    对于含有N个顶点E条边的无向连通图,利用Kruskal算法生成最小代价生成树的时间复杂度为()。

    正确答案: o(elg0)
    解析: 暂无解析

  • 第23题:

    单选题
    关于图的生成树,下列说法不正确的是()。
    A

    它又称为图的支撑树。

    B

    图有生成树的充要条件是该图为连通图。

    C

    图的生成树是唯一的。

    D

    顶点数为n的图的生成树有n-1条边。


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