2. 从业资格
  3. 对于下图，从顶点1进行深度优先遍历时，不可能得到的遍历序列是（ ）；若将该图用

对于下图，从顶点1进行深度优先遍历时，不可能得到的遍历序列是（ ）；若将该图用

免费题库2022-08-02  75
问题 对于下图，从顶点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)