若一个具有n个结点、k条边的非连通无向图是一个森林(n＞k)，则该森林中必有(34)棵树。A．kB．nC．n-kD．n+k

题目

若一个具有n个结点、k条边的非连通无向图是一个森林(n＞k)，则该森林中必有(34)棵树。

A．k

B．n

C．n-k

D．n+k

相似考题

1.一个有n个顶点的无向图若是连通图,则至少有________条边。A、n-1B、nC、n+1D、(n+1)/2

2.一棵二叉树中有2n－2条边(结点间的连线),其中每一个非叶结点的度数都为2,则该树共有_______个非叶结点。

3.一个具有n(n＞0)个顶点的连通无向图至少有(49)条边。A．n+lB．nC．D．n-1

4.●对于一个具有n个结点和e条边的无向图，若采用邻接表表示，则所有边链表中边结点的总数为 (39) 。(39) A．2eB．e/4C．e／2D．n+2e

更多“若一个具有n个结点、k条边的非连通无向图是一个森林(n>k),则该森林中必有(34)棵树。A.kB.nC.n－kD.n ”相关问题

  • 第1题：

    下面哪一种图不一定是树?()。

    A、无回路的连通图

    B、有n个结点n-1条边的连通图

    C、每对结点间都有通路的图

    D、连通但删去一条边则不连通的图


    参考答案：C

  • 第2题：

    若一棵有n个结点的二叉树,其中所有分支结点的度均为k,该树中的叶子结点个数是()。

    A.n(k-1)/k

    B.n-k

    C.(n+1)/k

    D.(nk-n+1)/k


    参考答案：D

  • 第3题：

    下列叙述中正确的是（ ）。A．连通分量是无向图中的极小连通子图 B．生成树是连通图的一个极大连通子图 C．若一个含有n个顶点的有向图是强连通图，则该图中至少有n条弧 D．若一个含有n个顶点的无向图是连通图，则该图中至少有n条边


    正确答案：C
    有向图是一个二元组，其中 　　1.V是非空集合，称为顶点集。 　　2.E是V×V的子集，称为边集。 　　直观来说，若图中的每条边都是有方向的，则称为有向图。有向图中的边是由两个顶点组成的有序对，有序对通常用尖括号表示，如表示一条有向边，其中vi是边的始点，vj是边的终点。和代表两条不同的有向边。如果在有向图中任意两个顶点都是连通的，则称图为连通图。因此如果有向图是连通图，则该图中至少有n条弧。 一个无向图(undirected graph)是一个二元组，其中： 　　1.E是非空集合，称为顶点集。 　　2.V是E中元素构成的无序二元组的集合，称为边集。 　　直观来说，若一个图中每条边都是无方向的，则称为无向图。

  • 第4题：

    一棵共有n个结点的树，其中所有分支结点的度均为众，则该树中叶子结点的个数为(50)。

    A．[n×(k-1)+1]K

    B．n×(k-1)k

    C．[n×(k+1)+1)k

    D．n×(k+1)k


    正确答案：A
    解析：设叶子结点个数为n0，则有分支数n-1=(n-n0)×k，所以n0=(n×(k-1)+1]/k。

  • 第5题：

    若一个具有n个结点、k条边的非连通无向图是一个森林(n＞k)，则该森林中必有( )。棵树。

    A．k

    B．n

    C．n-k

    D．n+k


    正确答案：C
    解析：假设有x棵树，任一棵树的结点数ni与边数ki都满足ni=ki+1，所以对x棵树有 n=k+x，则x=n-k。

  • 第6题：

    对于一个具有n个结点e条边的无向图，若采用邻接表表示，则所有边链表中边结点的总数为______。

    A．e/2

    B．e

    C．2e

    D．n+e


    正确答案：C
    解析：本题考查无向图的邻接表表示方法。邻接表可以表示出各个结点之间的关系，即无向图中的边，又由于图中有e条边，而每条边要连接两个结点，所以链表中的边结点总数为2e。

  • 第7题：

    对于一个具有N个结点和E条边的无向图，若采用邻接表示，则表头向量的大小是( )

    A．N

    B．N+1

    C．N-E

    D．N-1


    正确答案：A

  • 第8题：

    在n个结点的元向图中，若边数在于n-1，则该图必是连通图。


    正确答案:错误

  • 第9题：

    一个连通图的生成树是该图的（）连通子图。若这个连通图有n个顶点，则它的生成树有（）条边。


    正确答案:极小（最小）；n-1

  • 第10题：

    一个具有n个顶点k条边的无向图是一个森林（n>k），则该森林中必有（）棵树。

    • A、k
    • B、n
    • C、n-k
    • D、1

    正确答案:C

  • 第11题：

    单选题
    一个具有n个顶点k条边的无向图是一个森林（n>k），则该森林中必有（）棵树。
    A

    k

    B

    n

    C

    n-k

    D

    1


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

  • 第12题：

    判断题
    在n个结点的元向图中，若边数在于n-1，则该图必是连通图。
    A

    对

    B

    错


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

  • 第13题：

    在n个结点的无向图中,若边数大于n-1,则该图必是连通图。()


    正确答案:错

  • 第14题：

    对于一个具有n个结点和e条边的无向图，若采用邻接表表示，则顶点表的大小为(20)，所有边链表中边结点的总数为(21)。

    A．n

    B．n+1

    C．n-1

    D．n+e


    正确答案：A
    解析：此题考的是无向图。

  • 第15题：

    某树共有n个结点,其中所有分支结点的度为k(即每个非叶子结点的子树数目),则该树中叶子结点的个数为()

    A、(n(k+1)-1)/k

    B、(n(k+1)+1)/k

    C、(n(k-1)+1)/k

    D、(n(k-1)-1)/k


    正确答案：C

  • 第16题：

    若一个具有n个节点、k条边的非连通无向图是一个森林(n＞k)，则该森林中必有(19)棵树。

    A．k

    B．n

    C．n-k

    D．n+k


    正确答案：C
    解析：设该森林共有m棵树，每棵树有ni(1≤i≤m)个节点，依据树的性质有n=n1+n2+…+nmk=(n1-1)+(n2-1)+…+(nm-1)上面两式相减得n-k=1+1+…+1=m而m就是树的个数，所以该森林共有n-k棵树。

  • 第17题：

    一个具有n(n＞0)个顶点的连通无向图至少有______条边。

    A．n+1

    B．n

    C．n/2

    D．n-1


    正确答案：D
    解析：在无向图中如果任意两点是可达的，则我们称其为连通无向图。要把这n个顶点连通，可以让一个顶点向其它所有顶点连一条边，这样需要n-1条边，如图3-75所示。此外，我们还可以让这n个结点首尾相接，这样也需要n-1条边，如图3-76所示。所以至少需要n-1条边。

  • 第18题：

    若一个具有n个结点、k条边的非连通无向图是一个森林(n，k)，则该森林中必有(58)棵树。

    A．k

    B．n

    C．n-k

    D．n+k


    正确答案：C
    解析：假设该森林中有s棵树：T1，T2...，TS，且每个Ti有ni个结点，ki条边(i=1,2,...，S)，由树的等价条件可知：ki=ni-1，则k＝k1+k2+...+ks：(n1-1)+(n2-1)+...+(ns-1)=n-s，故s=n-k，所以该森林中必有n-k棵树。友情提示：该题如果清楚树的等价条件，可以很容易的解出。若不清楚，则无法下手。不过考生也可以画出一个具体的非连通无向图的森林，如：5个结点3条边2棵树的森林，也可帮助判断。抽象问题具体化是作选择题的一个重要方法。

  • 第19题：

    某树共有n个结点，其中所有分支结点的度为k（即每个非叶子结点的子树数目），则该树中叶子结点的个数为（）

    A.（n（k+1）-1）/k
    B.（n（k+1）+1）/k?
    C.（n（k-1）+1）/k
    D.（n（k-1）-1）/k?

    答案：C
    解析：
    任意画一棵树，再带入四个选项，符合要求的是选项C。

  • 第20题：

    如果G1是一个具有n个顶点的连通无向图，那么G1最多有（）条边，G1最少有（）条边。如果G2是一个具有n个顶点的强连通有向图，那么G2最多有（）条边，G2最少有（）条边。


    正确答案:n（n-1）/2；n-1；n（n-1）；n

  • 第21题：

    一个连通图的生成树是一个（），它包含图中所有顶点，但只有足以构成一棵树的n-1条边。


    正确答案:极小连通子图

  • 第22题：

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

    正确答案： 极小（最小）,n-1
    解析： 暂无解析

  • 第23题：

    填空题
    一棵二叉树中有2n-2条边（结点间的连线），其中每一个非叶结点的度数都为2，则该树共有（）个非叶结点。

    正确答案： n-1
    解析： 暂无解析

相关内容