对于下图，从顶点1进行深度优先遍历时，不可能得到的遍历序列是(请作答此空)；若将该图用邻接矩阵存储，则矩阵中的非0元素数目为( )。 A.1234.567 B.1523467 C.1234675 D.1267435

题目
对于下图，从顶点1进行深度优先遍历时，不可能得到的遍历序列是(请作答此空)；若将该图用邻接矩阵存储，则矩阵中的非0元素数目为( )。

A.1234.567
B.1523467
C.1234675
D.1267435
相似考题

1.●具有n个顶点e条边的无向图，若用邻接矩阵作为存储结构，则深度优先或广度优先搜索遍历的时间复杂度为 (48) ；若用邻接表作为存储结构，则深度优先或广度优先搜索遍历时的时间复杂度为 (49) ；深度优先或广度优先搜索遍历的空间复杂度为 (50) 。(48) ,(50) A．O(n2)B．O(n)C．O(n-1)D．O(n+1)(49) A．O(e)B．O(e-1)C．O(e2)D．O(e+10)

2.●设一个包含N 个顶点、E 条边的简单无向图采用邻接矩阵存储结构（矩阵元素 A[i][j]等于1/0 分别表示顶点i与顶点 j 之间有／无边），则该矩阵中的非零元素数目为 (60)。(60)A．NB．EC．2ED．N+E

3.● 对连通图进行遍历前设置所有顶点的访问标志为 false（未被访问） ，遍历图后得到一个遍历序列，初始状态为空。深度优先遍历的含义是：从图中某个未被访问的顶点 v 出发开始遍历，先访问 v 并设置其访问标志为 true（已访问） ，同时将 v 加入遍历序列，再从 v 的未被访问的邻接顶点中选一个顶点，进行深度优先遍历；若 v的所有邻接点都已访问，则回到 v 在遍历序列的直接前驱顶点，再进行深度优先遍历，直至图中所有顶点被访问过。 （40） 是下图的深度优先遍历序列。（40）A. 1 2 3 4 6 5B. 1 2 6 3 4 5C. 1 6 2 5 4 3D. 1 2 3 4 5 6

4.● 邻接矩阵和邻接表是图（网）的两种基本存储结构，对于具有 n个顶点、e条边的图， （59） 。（59）A. 进行深度优先遍历运算所消耗的时间与采用哪一种存储结构无关B. 进行广度优先遍历运算所消耗的时间与采用哪一种存储结构无关C. 采用邻接表表示图时，查找所有顶点的邻接顶点的时间复杂度为O(n*e)D. 采用邻接矩阵表示图时，查找所有顶点的邻接顶点的时间复杂度为O(n2)

更多“对于下图，从顶点1进行深度优先遍历时，不可能得到的遍历序列是(请作答此空)；若将该图用邻接矩阵存储，则矩阵中的非0元素数目为( )。 A.1234.567 B.1523467 C.1234675 D.1267435”相关问题

  • 第1题：

    ● 设一个包含N个顶点、 E条边的简单有向图采用邻接矩阵存储结构 （矩阵元素A[i][j]等于1/0分别表示顶点i与顶点j之间有/无弧），则该矩阵的元素数目为 （60） ，其中非零元素数目为 （61） 。


    正确答案：B,C

  • 第2题：

    对于下图，从顶点l进行深度优先遍历时，不可能得到的遍历序列是(42)；若将该图用邻接矩阵存储，则矩阵中的非0元素数目为(43)。

    A.1234567

    B.1523467

    C.1234675

    D.1267435


    正确答案：A
    本题考查数据结构基础知识。对题中所示的图从顶点1出发进行深度优先遍历，访问l之后接下来既可以访问顶点2，也可以访问顶点5。若先访问顶点2，则接下来可以访问顶点3或6，此时得到的已访问顶点顺序是123或126。若选择先访问顶点3，则接下来就访问顶点4，便得到已访问的顶点顺序1234，由于从顶点4出发不存在继续前进的路径，所以需要先回溯至顶点3再回溯至顶点2。由于顶点2存在尚没有得到访问的邻接顶点6，所以接下来访问的顶点是6，然后是顶点7，从而得到已访问顶点的遍历序列123467。最后还需回溯至顶点1．再去访问顶点5，这样就完成了所有顶点的访问，从而得到深度优先遍历序列1234675。若访问完顶点2后接下来选择访问顶点6，则可得到遍历序列1263475或1267435，若访问完顶点l之后接下来选择访问顶点5，则可得到深度优先遍历序列1523467或1526347或1526734。因此，不能得到的深度优先遍历序列是1234567。对于有向图，其邻接矩阵中非零元素的个数即表示图中有向弧的数目，题中的图有8条弧，因此矩阵中的非O元素数目为8，如下图所示。

  • 第3题：

    下图的邻接矩阵表示为( )(行列均以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。

  • 第4题：

    对于下面的有向图，其邻接矩阵是一个（请作答此空）的矩阵。采用邻接链表存储时，顶点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

  • 第5题：

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


    A.v0、v1、v2、v3、v4、v5
    B.v0、v2、v4、 v5、v1、v3
    C.v0、v1、v3、v5、v2、v4
    D.v0、v2、v4、v3、v5、v1

    答案：A
    解析：

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

    已知如图所示的一个图，若从顶点a出发，按深度优先搜索法进行遍历，则可能得到的一种顶点序列为（）。

    Aabecdf

    Bacfebd

    Caedfcb

    Daebcfd


    C
    略

  • 第8题：

    若具有n个顶点、e条边且不带权的无向图采用邻接矩阵存储，则邻接矩阵中的零元素的数目是（）


    正确答案:n2-2e

  • 第9题：

    带权有向图G用邻接矩阵A存储，则顶点i的入度为A中：（）。

    • A、第i行非的元素之和
    • B、第i列非的元素之和
    • C、第i行非且非0的元素个数
    • D、第i列非且非0的元素个数

    正确答案:D

  • 第10题：

    用深度优先遍历方法遍历一个有向无环图，并在深度优先遍历算法中按退栈次序打印出相应的顶点，则输出的顶点序列是（）。

    • A、逆拓扑有序
    • B、拓扑有序
    • C、无序
    • D、深度优先遍历序列

    正确答案:A

  • 第11题：

    填空题
    若具有n个顶点且不带权的连通图采用邻接矩阵存储，则该邻接矩阵中至少有（）个非零元素。

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

  • 第12题：

    填空题
    若具有n个顶点、e条边且不带权的无向图采用邻接矩阵存储，则邻接矩阵中的零元素的数目是（）

    正确答案： n2-2e
    解析： 暂无解析

  • 第13题：

    具有n个顶点e条边的无向图，若用邻接矩阵作为存储结构，则深度优先或广度优先搜索遍历的时间复杂度为(48)；若用邻接表作为存储结构，则深度优先或广度优先搜索遍历时的时间复杂度为(49)；深度优先或广度优先搜索遍历的空间复杂度为(50)。

    A．O(n2)

    B．O(n)

    C．O(n-1)

    D．O(n+1)


    正确答案：A

  • 第14题：

    下图的邻接矩阵表示为(请作答此空)(行列均以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。

  • 第15题：

    对于下面的有向图，其邻接矩阵是一个（ ）的矩阵。采用邻接链表存储时，顶点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

  • 第16题：

    对于如下所示的有向图，其邻接矩阵是一个（ ）的矩阵，采用邻接链表存储时顶点的表结点个数为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。

  • 第17题：

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


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

    答案：B
    解析：

  • 第18题：

    如图若从顶点a出发按深度优先搜索法进行遍历，则可能得到的顶点序列为（）。

    Aacfgedb

    Baedbgfc

    Cacfebdg

    Daecbdgf


    B
    略

  • 第19题：

    若具有n个顶点且不带权的连通图采用邻接矩阵存储，则该邻接矩阵中至少有（）个非零元素。


    正确答案:2(n-1)

  • 第20题：

    如果无向图G有n个顶点、e条边且用邻接矩阵进行存储，那么深度优先遍历图G的时间复杂度为（）。


    正确答案: O(N2)

  • 第21题：

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


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

  • 第22题：

    填空题
    如果无向图G有n个顶点、e条边且用邻接矩阵进行存储，那么深度优先遍历图G的时间复杂度为（）。

    正确答案： O(N2)
    解析： 暂无解析

  • 第23题：

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

    正确答案： O(n2) O(n+e)
    解析： 暂无解析

相关内容