免费智能真题库 > 历年试卷 > 软件设计师 > 2012年下半年 软件设计师 上午试卷 综合知识
  第60题      
  知识点:   AOV网   排序   拓扑排序
  关键词:   排序   有向图        章/节:   计算机软件知识       

 
拓扑排序是将有向图中所有顶点排成一个线性序列的过程,并且该序列满足:若在AOV网中从顶点vi到vj有一条路径,则顶点vi必然在顶点vj之前。对于下面所示的有向图,(60)是其拓扑序列。
 
 
  A.  1234576
 
  B.  1235467
 
  C.  2135476
 
  D.  2134567
 
 
 

 
  第17题    2012年上半年  
   16%
下图是一个软件项目的活动图,其中顶点表示项目里程碑,连接顶点的边表示活动, 边上的值表示完成活动所需要的时间,则(17)在关键..
  第57题    2016年下半年  
   15%
拓扑序列是有向无环图中所有顶点的一个线性序列,若有向图中存在弧<v,w>或存在从顶点v到w的路径,则在该有向图的任一拓扑..
  第16题    2016年上半年  
   25%
某软件项目的活动图如下图所示,其中顶点表示项目里程碑,连接顶点的边表示包含的活动,边上的数字表示活动的持续时间(天),则..
   知识点讲解    
   · AOV网    · 排序    · 拓扑排序
 
       AOV网
        在有向图中,若一顶点表示活动,用有向边表示活动之间的优先关系,则称这样的有向图为以顶点表示活动的网,简称AOV网。
        在AOV网中不应出现有向环。不存在回路的AOV网称为有向无环图或DAG图。检测的方法是对有向图构造其从顶点开始的拓扑有序序列,若图中所有顶点都在它的拓扑有序序列中,则该AOV网中必定不存在环。
 
       排序
        假设含n个记录的文件内容为{R1R2,…,Rn},其相应的关键字为{k1k2,…,kn}。经过排序确定一种排列{Rj1Rj2,…,Rjn},使得它们的关键字满足如下递增(或递减)关系:kj1≤kj2≤…≤kjn(或kj1kj2≥…≥kjn)。
 
       拓扑排序
               AOV网
               在工程领域,一个大的工程项目通常被划分为许多较小的子工程(称为活动),当这些子工程都完成时,整个工程也就完成了。若以顶点表示活动,用有向边表示活动之间的优先关系,则称这样的有向图为以顶点表示活动的网(Activity On Vertex network,AOV网)。在有向网中,若从顶点νi到顶点νj有一条有向路径,则顶点νiνj的前驱,顶点νjνi的后继。若<νiνj>是网中的一条弧,则顶点νiνj的直接前驱,顶点νjνi的直接后继。AOV网中的弧表示了活动之间的优先关系,也可以说是一种活动进行时的制约关系。
               在AOV网中不应出现有向环,若存在的话,则意味着某项活动必须以自身任务的完成为先决条件,显然这是荒谬的。因此,若要检测一个工程划分后是否可行,首先就应检查对应的AOV网是否存在回路。检测的方法是对其AOV网进行拓扑排序。
               拓扑排序
               拓扑排序是将AOV网中所有顶点排成一个线性序列的过程,并且该序列满足:若在AOV网中从顶点νiνj有一条路径,则在该线性序列中,顶点νi必然在顶点νj之前。
               一般情况下,假设AOV网代表一个工程计划,则AOV网的一个拓扑排序就是一个工程顺利完成的可行方案。对AOV网进行拓扑排序的方法如下:
               (1)在AOV网中选择一个入度为零(没有前驱)的顶点且输出它;
               (2)从网中删除该顶点以及与该顶点有关的所有边;
               (3)重复上述两步,直至网中不存在入度为零的顶点为止。
               按照上述步骤进行拓扑排序的过程如下图所示,得到的拓扑序列为6,1,4,3,2,5。显然,对有向图进行拓扑排序所产生的拓扑序列有可能是多种。
               
               拓扑排序过程
               执行的结果会有两种情况:一种是所有顶点已输出,此时整个拓扑排序完成,说明网中不存在回路;另一种是尚有未输出的顶点,剩余的顶点均有前驱顶点,表明网中存在回路,拓扑排序无法进行下去。
   题号导航      2012年下半年 软件设计师 上午试卷 综合知识   本试卷我的完整做题情况  
1 /
2 /
3 /
4 /
5 /
6 /
7 /
8 /
9 /
10 /
11 /
12 /
13 /
14 /
15 /
 
16 /
17 /
18 /
19 /
20 /
21 /
22 /
23 /
24 /
25 /
26 /
27 /
28 /
29 /
30 /
 
31 /
32 /
33 /
34 /
35 /
36 /
37 /
38 /
39 /
40 /
41 /
42 /
43 /
44 /
45 /
 
46 /
47 /
48 /
49 /
50 /
51 /
52 /
53 /
54 /
55 /
56 /
57 /
58 /
59 /
60 /
 
61 /
62 /
63 /
64 /
65 /
66 /
67 /
68 /
69 /
70 /
71 /
72 /
73 /
74 /
75 /
 
第60题    在手机中做本题