对于下图,从顶点1进行深度优先遍历时,不可能得到的遍历序列是( );若将该图用

免费题库2022-08-02  66

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

选项 A.1234567
B.1523467
C.1234675
D.1267435

答案 A

解析 本题考查数据结构基础知识。
    对题中所示的图从顶点1出发进行深度优先遍历,访问1之后接下来既可以访问顶点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。
转载请注明原文地址:https://tihaiku.com/congyezige/2427310.html

最新回复(0)