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

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

A.7
B.8
C.14
D.16

参考解析

解析:本题考查数据结构基础知识。
对题中所示的图从顶点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。
若访问完顶点1之后接下来选择访问顶点5,则可得到深度优先遍历序列1523467或1526347或1526734。
因此,不能得到的深度优先遍历序列是1234567。
对于有向图,其邻接矩阵中非零元素的个数即表示图中有向弧的数目,题中的图有8条弧,因此矩阵中的非0元素数目为8,如下图所示。

相关考题:

●具有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)

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

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

● 对连通图进行遍历前设置所有顶点的访问标志为 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

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

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

对于下图,从顶点l进行深度优先遍历时,不可能得到的遍历序列是(42);若将该图用邻接矩阵存储,则矩阵中的非0元素数目为(43)。A.1234567B.1523467C.1234675D.1267435

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

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

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

对于下面的有向图,其邻接矩阵是一个( )的矩阵。采用邻接链表存储时,顶点0的表结点个数为2,顶点3的表结点个数为0,顶点1的表结点个数为(请作答此空)。A.0B.1C.2D.3

对于下面的有向图,其邻接矩阵是一个(请作答此空)的矩阵。采用邻接链表存储时,顶点0的表结点个数为2,顶点3的表结点个数为0,顶点1的表结点个数为( )。A.3×4B.4×3C.6×6D.7×7

对于如下所示的有向图,其邻接矩阵是一个( )的矩阵,采用邻接链表存储时顶点的表结点个数为2,顶点5的表结点个数为0,顶点2和3的表结点个数分别为(请作答此空)A.2.1B.2.2C.3.4D.4.3

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

图G的邻接矩阵如下图所示(顶点依次表示为v0、v1、v2、v3、v4、v5),G是(请作答此空)。对G进行广度优先遍历(从v0开始),可能的遍历序列为( )。A.无向图B.有向图C.完全图D.强连通图

对于如下所示的有向图,其邻接矩阵是一个(请作答此空)的矩阵,采用邻接链表存储时顶点的表结点个数为2,顶点5的表结点个数为0,顶点2和3的表结点个数分别为( )A.5*5B.5*7C.7*5D.7*7

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

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

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

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

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

带权有向图G用邻接矩阵A存储,则顶点i的入度为A中:()。A、第i行非的元素之和B、第i列非的元素之和C、第i行非且非0的元素个数D、第i列非且非0的元素个数

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

用深度优先遍历方法遍历一个有向无环图,并在深度优先遍历算法中按退栈次序打印出相应的顶点,则输出的顶点序列是()。A、逆拓扑有序B、拓扑有序C、无序D、深度优先遍历序列

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

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

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

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