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

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

考试题库2022-08-02  85
问题 对于下图，从顶点1进行深度优先遍历时，不可能得到的遍历序列是( )；若将该图用邻接矩阵存储，则矩阵中的非0元素数目为(请作答此空)。A.7B.8C.14D.16
选项 A.7
B.8
C.14
D.16
答案 B
解析 本题考查数据结构基础知识。对题中所示的图从顶点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，如下图所示。
转载请注明原文地址:https://www.tihaiku.com/congyezige/2425095.html
本试题收录于： 初级程序员题库软件水平考试初中高级分类

初级程序员

软件水平考试初中高级

相关试题推荐
随机试题
最新回复(0)