设图G有n个结点，m条边，且G中每个结点的度数不是k，就是k+1，则G中度数为k的节点数是 。A．n/2B．n(n+1)C．nk-2mD．n(k+1)-2m

题目

设图G有n个结点，m条边，且G中每个结点的度数不是k，就是k+1，则G中度数为k的节点数是 。

A．n/2

B．n(n+1)

C．nk-2m

D．n(k+1)-2m

相似考题

1.设G=(n,m)且G中每个结点的度数不是k就是k＋1,则G中度数为k的结点的个数是()。A、n/2B、n(n+1)C、nkD、n(k+1)-2m

2.设G是一右线性文法，并设G中的非终结符号的个数为k，则所要构造的状态转换图共有几个结点()。A、k-1B、kC、k+1D、k+2

3.如果图G是无向图,且其结点度数均为偶数,则图G存在一条欧拉回路。()此题为判断题(对，错)。

4.设G是n个顶点的无向简单图,则下列说法不正确的是()A、若G是树，则其边数等于n-1B、若G是欧拉图，则G中必有割边C、若G中有欧拉路，则G是连通图，且有零个或两个奇度数顶点D、若G中任意一对顶点的度数之和大于等于n-1，则G中有汉密尔顿路

参考答案和解析
n(k+1)-2m
更多“设图G有n个结点，m条边，且G中每个结点的度数不是k，就是k+1，则G中度数为k的节点数是 。”相关问题

  • 第1题：

    设G是一个连通平面图,且有6个结点11条边,则G有7个面。()

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


    答案：对

  • 第2题：

    设一棵有n个叶结点的二叉树,除叶结点外每个结点度数都为2,则该树共有()个结点。

    A.2n-1

    B.2n+2

    C.2n+1

    D.2n


    参考答案：A

  • 第3题：

    设根结点的层次为0，则高度为k的二叉树的最小结点数为

    A．2k

    B．2*(k+1)

    C．k+1

    D．2(k+1)-1


    正确答案：C
    解析：二叉树是结点的有限集合，这个有限集合或者为空集，或者由一个根结点及两棵不相交的、分别称作左子树和右子树的二叉树组成。由定义知二叉树的一个非叶结点至少有一棵子树，至多有两棵于树。该题题意是求最小的结点数，所以只考虑极端的情形。此时每一层上都有一个结点。所以总共有k+1个结点。

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

    设无向图G中有n个顶点e条边，则其对应的邻接表中的表头结点和表结点的个数分别为()。

    A.e，n
    B.n.e
    C.2n，e
    D.n.2e

    答案：D
    解析：
    使用邻接表存储图，图有多少结点，邻接表就有多少个表头，无向图的表结点个数为2e。

  • 第6题：

    某树共有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。

  • 第7题：

    设E为程序图G中边的总数；N为程序图中结点的总数，则该程序图的环形复杂度为 （）。


    正确答案:E–N+2

  • 第8题：

    设在一棵度数为3的树中，度数为3的结点数有2个，度数为2的结点数有1个，度数为1的结点数有2个，那么度数为0的结点数有（）个。

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

    正确答案:C

  • 第9题：

    设无向图G中顶点数为n，则图G至少有（）条边，至多有（）条边；若G为有向图，则至少有（）条边，至多有（）条边。


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

  • 第10题：

    填空题
    设无向图G中顶点数为n，则图G至少有（）条边，至多有（）条边；若G为有向图，则至少有（）条边，至多有（）条边。

    正确答案： 0,n（n-1）/2,0,n（n-1）
    解析： 图的顶点集合是有穷非空的，而边集可以是空集；边数达到最多的图称为完全图，在完全图中，任意两个顶点之间都存在边。

  • 第11题：

    填空题
    设E为程序图G中边的总数；N为程序图中结点的总数，则该程序图的环形复杂度为 （）。

    正确答案： E–N+2
    解析： 暂无解析

  • 第12题：

    填空题
    设一棵有n个叶结点的二叉树，除叶结点外每个结点度数都为2，则该树共有（）个结点。

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

  • 第13题：

    设图G是有5个结点的连通图,结点度数总和为10,则可从G中删去6条边后使之变成树。()

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


    答案：错

  • 第14题：

    设结点A有3个兄弟结点且结点B为结点A的双亲结点,则结点B的度数数为()

    :A3

    B4

    C5

    D1


    参考答案：B

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

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

    设，|V|=n(n＞1)，当且仅当(59)，G=＜V，E＞是强连通图。

    A．G中至少有一条路

    B．G中至少有一条回路

    C．G中有通过每个结点至少一次的路

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


    正确答案：D
    解析：本题考查的是图论中的基本知识点。在简单有向图G中，任何一对结点问两者之间是相互可达的，则称这个图是强连通的。如图：A→B只有A到达B，有一次路，但是该图不是强连通的。所以，C错。

  • 第17题：

    设某棵二叉树中只有度数为0和度数为2的结点且度数为0的结点数为n.则这棵二叉中共有()个结点。

    A.2n+1
    B.n+1
    C.2n-1
    D.2n

    答案：C
    解析：
    在二叉树中度为2的结点个数为度为零的结点数减一，所以二叉树共有2n-1个结点。

  • 第18题：

    设无向图G有n个顶点m条边，则其邻接表中表结点数是（）

    • A、n
    • B、2n
    • C、m
    • D、2m

    正确答案:D

  • 第19题：

    设无向图G中有n个顶点e条边，则其对应的邻接表中的表头结点和表结点的个数分别为（）

    • A、n，e
    • B、e，n
    • C、2n，e
    • D、n，2e

    正确答案:D

  • 第20题：

    设一棵有n个叶结点的二叉树，除叶结点外每个结点度数都为2，则该树共有（）个结点。


    正确答案:2n-1

  • 第21题：

    设某棵二叉树中只有度数为0和度数为2的结点且度数为0的结点数为n，则这棵二叉中共有（）个结点。

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

    正确答案:C

  • 第22题：

    单选题
    设无向图G中有n个顶点e条边，则其对应的邻接表中的表头结点和表结点的个数分别为（）
    A

    n，e

    B

    e，n

    C

    2n，e

    D

    n，2e


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

  • 第23题：

    单选题
    设某棵二叉树中只有度数为0和度数为2的结点且度数为0的结点数为n，则这棵二叉中共有(  )个结点。
    A

    2n

    B

    n+1

    C

    2n-1

    D

    2n+1


    正确答案： D
    解析：

  • 第24题：

    单选题
    设无向图G有n个顶点m条边，则其邻接表中表结点数是（）
    A

    n

    B

    2n

    C

    m

    D

    2m


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

相关内容