软件水平考试

【单选题】设有向图G=(V，E、，其中V=V₁，V₂，V₃，V₄，V₅，V₆，V₇，V₈)，E=V₁，V₂＞，＜V₁，V₃＞，＜V₂，V₄＞，＜V₂，V₆＞，＜V₃，V₅＞，＜V₄，V₈＞，＜V₅，V₄＞，＜V₆，V₃＞，＜V₆，V₇＞， (V₇，V₅＞，＜V₈，V₇＞)，那么该图的邻接表可以是 (10) ，按照该邻接表从V₁，出发，图G的深度优先遍历序列为 (11) ，广度优先遍历序列为 (12) 。
A．V₁ V₂ V₆ V₃ V₅ V₄ V₈ V₇
B．V₁ V₃ V₂ V₄ V₆ V₅ V₈ V₇
C．V₁ V₂ V₃ V₄ V₆ V₅ V₈ V₇
D．V₁ V₂ V₃ V₄ V₆ V₅ V₇ V₈

网考网参考答案：C
网考网解析：
(10)～(12)根据边集E可以得到图G如图13-29所示。 [*] [*] 在有向无权图的邻接表中，对图中每个顶点V i 建立一个单链表，第i个单链表中的表结点表示从顶点V i 出发的边。每个表结点由两个域组成：邻接点域，用以指示与V i 邻接的点在图中的位置；链域。用以指向从顶点V i 出发的下一条边对应的结点。每个链表上附设一个表头结点，它设有两个域：链域，指向链表中的第一个结点；数据域，存储顶点的名称或其它信息，如图13-30所示。 [*] 图的深度优先遍历的基本思想是：从图G的某个顶点V 0 出发，访问、V 0 ，然后选择一个与V 0 相邻且未被访问过的顶点V i 访问，再从V i 出发选择一个与V i 相邻且未被访问的顶点V j 进行访问，依此继续。如果当前被访问的顶点的所有邻接顶点都已被访问过，则退回到已被访问的顶点序列中最后一个拥有未被访问的相邻顶点的顶点W，从W出发按同样方法进行访问，直到图中所有与V 0 相通的顶点都被访问。此时，若图中尚有顶点未被访问，则另选图中一个未曾访问的顶点做起始点，重复上述过程，直到图中所有顶点都被访问过。值得强调的是。这里可能有回退的过程。 在未给定图的邻接表时，由于一个顶点可能有多个邻接点，导致有不同的选择，从而最后得到不同的遍历顺序。而当给定一个图的邻接表之后，不管是深度优先遍历还是广度优先遍历，遍历结果都只有一种。 在对G从V 1 开始进行深度优先遍历时，先访问V 1 ，之后因为以V 1 为表头接点的单链表的第一个表结点的邻接点域里存的是1，这是V 2 所在的下标，于是访问V 2 ，接着因为以V 2 为表头结点的单链表的第一个表结点的邻接点域里存的是5，这是V 6 的下标，于是访问V 6 。类似地，接下来依次访问V 3 、V 5 、V 4 、V 8 、V 7 。 图的广度优先遍历的基本思想是：首先访问初始点V i ，并将其标记为已经访问过，接着访问V i 的所有未被访问过的邻接点V i1 、V i2 、V i3 ... 、V it ，并标记为已访问过，然后再按照V i1 、V i2 、V i3 、... 、V it 的次序(注意，一定得按照这个对应的次序)访问每一个顶点的所有未被访问过的邻接点，并将其标记为已访问过。依此类推，直到图中所有和初始点V i 有路径相通的顶点都被访问过为止。此时，若图中尚有顶点未被访问，则另选图中一个未曾访问的顶点做起始点，重复上述过程，直到图中所有顶点都被访问过。换句话说，广度优先遍历图的过程是以V i 为起始点，由近至远，依次访问跟V i 有路径相通且路径长度为 1、2、…的顶点。 从V 1 出发对G进行广度优先遍历，先访问V 1 ，接着因为以V 1 为表头结点的单链表可知接下来依次访问V 2 、V 3 、V 4 ，然后访问V 2 的邻接点V 6 ，接着访问V 3 的邻接点V 5 ，再接着访问V 4 的邻接点V 8 ，最后访问V 8 的邻接点V 7 。 document.getElementById("warp").style.display="none"; document.getElementById("content").style.display="block"; 查看试题解析出处>>