itgle.com

某图的邻接矩阵如下，该图为（请作答此空）；若采用邻接表表示该图，则邻接表中用来表示边（或弧）的表结点总数为（ ）个。 A.无向图 B.有向图 C.完全图 D.二部图

题目
某图的邻接矩阵如下，该图为（请作答此空）；若采用邻接表表示该图，则邻接表中用来表示边（或弧）的表结点总数为（ ）个。

A.无向图
B.有向图
C.完全图
D.二部图
相似考题

1.● 从存储空间的利用率角度来看，以下关于数据结构中图的存储的叙述，正确的是（60）。（60）A．有向图适合采用邻接矩阵存储，无向图适合采用邻接表存储B．无向图适合采用邻接矩阵存储，有向图适合采用邻接表存储C．完全图适合采用邻接矩阵存储D．完全图适合采用邻接表存储

2.已知一个有向图图的邻接矩阵表示,删除所有从第j个结点出发的边的方法是将邻接矩阵上第j行元素置为0。()此题为判断题(对，错)。

3.对于一个具有n个顶点和e条边的无向图,若采用邻接表表示,则所有顶点邻接表中的结点总数为( )。A、 2*nB、 2*eC、 nD、 e

4.n个顶点、e条边的无向图采用邻接表存储方法,该邻接表中共有()个边结点。A、eB、2eC、nD、2n

参考答案和解析
答案：B
解析：
图的邻接矩阵是一个方阵，所有行标和列标都与图中的顶点一一对应，这样对于矩阵中的一个元素 [i，j]，其值为1 表示 i、j 对应的顶点间有边(或弧)，其值为 0则表示 i、j对应的顶点间不存在边(或弧)。显然，图中总共有9条边。在无向图中，边 (i，j)与(j，i)是指同一条边，其取值是相同的；在有向图中， 与是两条不同的弧。而在本题中，矩阵中的(i，j)与(j，i)是不同的，因此这个是有向图。
更多“某图的邻接矩阵如下，该图为（请作答此空）；若采用邻接表表示该图，则邻接表中用来表示边（或弧）的表结点总数为（ ）个。 ”相关问题

  • 第1题：

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

    A．n

    B．n+1

    C．n-1

    D．n+e


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

  • 第2题：

    图的存储结构主要有邻接表和(1)，若用邻接表来存储一个图，则需要保存一个(2)存储的结点表和若干个(3)存储的关系表(又称边表)。

    A．转移矩阵

    B．邻接矩阵

    C．状态矩阵

    D．优先矩阵


    正确答案：B

  • 第3题：

    某图的邻接矩阵如下，该图为（ ）；若采用邻接表表示该图，则邻接表中用来表示边（或弧）的表结点总数为（请作答此空）个。

    A.9
    B.18
    C.21
    D.49

    答案：A
    解析：
    图的邻接矩阵是一个方阵，所有行标和列标都与图中的顶点一一对应，这样对于矩阵中的一个元素 [i，j]，其值为1 表示 i、j 对应的顶点间有边(或弧)，其值为 0则表示 i、j对应的顶点间不存在边(或弧)。显然，图中总共有9条边。在无向图中，边 (i，j)与(j，i)是指同一条边，其取值是相同的；在有向图中， 与是两条不同的弧。而在本题中，矩阵中的(i，j)与(j，i)是不同的，因此这个是有向图。

  • 第4题：

    下图的邻接矩阵表示为( )(行列均以A、B、C、D、E为序)；若某无向图具有10个顶点，则其完全图应包含(请作答此空)条边。

    A.10
    B.20
    C.45
    D.90

    答案：C
    解析：
    本题考查数据结构基础知识。
    图的邻接矩阵是一个方阵，所有行标和列标都与图中的顶点一一对应，这样对于矩阵中的一个元素[i,j]，其值为1表示i、j对应的顶点间有边(或弧)，其值为0则表示i、j对应的顶点间不存在边(或弧)。显然，第一个空的选项符合以上说明。
    完全图是指图中任意一对顶点间都存在边(或弧)，在无向图中，边(i,j)与(j,i)是指同一条边，在有向图中，＜i,j＞与＜j,i＞是两条不同的弧。
    若完全无向图具有10个顶点，则边的数目为10*9/2=45。

  • 第5题：

    对于下面的有向图，其邻接矩阵是一个（请作答此空）的矩阵。采用邻接链表存储时，顶点0的表结点个数为2，顶点3的表结点个数为0，顶点1的表结点个数为（ ）。

    A.3×4
    B.4×3
    C.6×6
    D.7×7

    答案：C
    解析：
    本题考查数据结构邻接矩阵的基础知识。邻接矩阵：表示顶点之间相邻关系的矩阵。设G=(V,E)是一个图，其中V={v1,v2,…,vn} 。G的邻接矩阵是一个具有下列性质的n阶方阵：①对无向图而言，邻接矩阵一定是对称的，而且主对角线一定为零（在此仅讨论无向简单图），副对角线不一定为0，有向图则不一定如此。②在无向图中，任一顶点i的度为第i列（或第i行）所有非零元素的个数，在有向图中顶点i的出度为第i行所有非零元素的个数，而入度为第i列所有非零元素的个数。③用邻接矩阵法表示图共需要n^2个空间，由于无向图的邻接矩阵一定具有对称关系，所以扣除对角线为零外，仅需要存储上三角形或下三角形的数据即可，因此仅需要n（n-1）/2个空间。因此有向图有7个结点，则是一个7×7 的矩阵。顶点1分别可以指向2和5，所以表的结点个数为2。第一空正确答案为：D，第二空正确答案为：C

  • 第6题：

    对于如下所示的有向图，其邻接矩阵是一个（请作答此空）的矩阵，采用邻接链表存储时顶点的表结点个数为2，顶点5的表结点个数为0，顶点2和3的表结点个数分别为（ ）

    A.5*5
    B.5*7
    C.7*5
    D.7*7

    答案：A
    解析：
    有向图的邻接矩阵如下。可以看出有4个结点的邻接矩阵是一个4*4 的矩阵。

    同理，题干是5个结点的有向图若采用邻接矩阵存储是一个5*5 的矩阵

  • 第7题：

    n个顶点e条边的图采用邻接矩阵存储，广度优先遍历算法的时间复杂度为（）；若采用邻接表存储，该算法的时间复杂度为（）。


    正确答案:O(n2) O(n+e)

  • 第8题：

    在图G的邻接表表示中，每个顶点邻接表中所含的结点数，对于无向图来说等于该顶点的（），对于有向图来说等于该顶点的（）


    正确答案:度数；出度数

  • 第9题：

    假定一个图具有n个顶点和e条边，则采用邻接矩阵、邻接表和边集数组表示时，其相应的空间复杂度分别为（）、（）和（）。


    正确答案:O（n2）；O（n）+O（e）；O（e）+O（n）

  • 第10题：

    单选题
    在图的表示法中，表示形式唯一的是（）。
    A

    邻接矩阵表示法

    B

    邻接表表示法

    C

    逆邻接表表示法

    D

    邻接表和逆邻接表表示法


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

  • 第11题：

    填空题
    在有向图的邻接表和逆邻接表表示中，每个顶点邻接表分别链接着该顶点的所有（）和（）结点。

    正确答案： 出边,入边
    解析： 暂无解析

  • 第12题：

    单选题
    设某有向图的邻接表中有n个表头结点和m个表结点，则该图中有（）条有向边。
    A

    n

    B

    n-1

    C

    m

    D

    m-1


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

  • 第13题：

    设某有向无环图的顶点个数为n、弧数为e，那么用邻接表存储该图时，实现上述拓扑排序算法的函数TopSort的时间复杂度是(6)。

    若有向图采用邻接矩阵表示(例如，图4-1所示有向图的邻接矩阵如图4-3所示)，且将函数TopSort中有关邻接表的操作修改为针对邻接矩阵的操作，那么对于有n个顶点、e条弧的有向无环图，实现上述拓扑排序算法的时问复杂度是(7)。


    正确答案：(6)O(n+e) (7)O(n2)
    (6)O(n+e) (7)O(n2) 解析：邻接表：对有n个顶点和e条弧的有向图而言，在拓扑排序中，若有向图无环，则每个顶点进出队列各一次，共执行e次，搜索算法时间复杂度是由n和e共同决定的，所以总的时间复杂度为O(n+e)。
    当用邻接矩阵：对于每个顶点，查找相邻边的时间复杂度是O(n)，一共有n个顶点，所以总的时间复杂度是O(n2)。

  • 第14题：

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

    A．e/2

    B．e

    C．2e

    D．n+e


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

  • 第15题：

    下图的邻接矩阵表示为(请作答此空)(行列均以A、B、C、D、E为序)；若某无向图具有10个顶点，则其完全图应包含( )条边。




    答案：C
    解析：
    本题考查数据结构基础知识。
    图的邻接矩阵是一个方阵，所有行标和列标都与图中的顶点一一对应，这样对于矩阵中的一个元素[i,j]，其值为1表示i、j对应的顶点间有边(或弧)，其值为0则表示i、j对应的顶点间不存在边(或弧)。显然，第一个空的选项符合以上说明。
    完全图是指图中任意一对顶点间都存在边(或弧)，在无向图中，边(i,j)与(j,i)是指同一条边，在有向图中，＜i,j＞与＜j,i＞是两条不同的弧。
    若完全无向图具有10个顶点，则边的数目为10*9/2=45。

  • 第16题：

    对于下面的有向图，其邻接矩阵是一个（ ）的矩阵。采用邻接链表存储时，顶点0的表结点个数为2，顶点3的表结点个数为0，顶点1的表结点个数为（请作答此空）。

    A.0
    B.1
    C.2
    D.3

    答案：C
    解析：
    本题考查数据结构邻接矩阵的基础知识。邻接矩阵：表示顶点之间相邻关系的矩阵。设G=(V,E)是一个图，其中V={v1,v2,…,vn} 。G的邻接矩阵是一个具有下列性质的n阶方阵：①对无向图而言，邻接矩阵一定是对称的，而且主对角线一定为零（在此仅讨论无向简单图），副对角线不一定为0，有向图则不一定如此。②在无向图中，任一顶点i的度为第i列（或第i行）所有非零元素的个数，在有向图中顶点i的出度为第i行所有非零元素的个数，而入度为第i列所有非零元素的个数。③用邻接矩阵法表示图共需要n^2个空间，由于无向图的邻接矩阵一定具有对称关系，所以扣除对角线为零外，仅需要存储上三角形或下三角形的数据即可，因此仅需要n（n-1）/2个空间。因此有向图有7个结点，则是一个7×7 的矩阵。顶点1分别可以指向2和5，所以表的结点个数为2。第一空正确答案为：D，第二空正确答案为：C

  • 第17题：

    对于如下所示的有向图，其邻接矩阵是一个（ ）的矩阵，采用邻接链表存储时顶点的表结点个数为2，顶点5的表结点个数为0，顶点2和3的表结点个数分别为（请作答此空）

    A.2.1
    B.2.2
    C.3.4
    D.4.3

    答案：B
    解析：
    如果是采用邻接表的方式存储，那么对于顶点V0来说，结点个数是2。

    同理，题干是5个结点的有向图若采用邻接矩阵存储是一个5*5 的矩阵，若采用邻接表的方式存储，顶点2和3的表结点个数分别为2、2。

  • 第18题：

    在有向图的邻接表和逆邻接表表示中，每个顶点邻接表分别链接着该顶点的所有（）和（）结点。


    正确答案:出边；入边

  • 第19题：

    在图的表示法中，表示形式唯一的是（）。

    • A、邻接矩阵表示法
    • B、邻接表表示法
    • C、逆邻接表表示法
    • D、邻接表和逆邻接表表示法

    正确答案:A

  • 第20题：

    设某有向图的邻接表中有n个表头结点和m个表结点，则该图中有（）条有向边。

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

    正确答案:C

  • 第21题：

    若邻接表中的有奇数个表结点，则一定（）

    • A、图中有奇数个顶点
    • B、图中有偶数个顶点
    • C、图为无向图
    • D、图为有向图

    正确答案:D

  • 第22题：

    填空题
    在图G的邻接表表示中，每个顶点邻接表中所含的结点数，对于无向图来说等于该顶点的（）；对于有向图来说等于该顶点的（）。

    正确答案： 度,出度
    解析： 暂无解析

  • 第23题：

    填空题
    假定一个图具有n个顶点和e条边，则采用邻接矩阵、邻接表和边集数组表示时，其相应的空间复杂度分别为（）、（）和（）。

    正确答案： O（n2）,O（n）+O（e）,O（e）+O（n）
    解析： 暂无解析

相关内容