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

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

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

(43)
选项 A、7
B、8
C、14
D、16
答案B
解析 本题考查数据结构基础知识。
    对题中所示的图从顶点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://kaotiyun.com/show/d5VZ777K
本试题收录于： 程序员上午基础知识考试题库软考初级分类
0

程序员上午基础知识考试

软考初级

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