免费智能真题库 > 历年试卷 > 程序员 > 2018年下半年 程序员 上午试卷 综合知识
  第64题      
  知识点:   拓扑排序   排列   排序   培训
  关键词:   排序        章/节:   常用算法       

 
某企业在职培训需要开设九门课程(编号为A~1,但是每次只能开设1门。有些课程之间有先修关系(见下图):“甲→乙”表示课程甲必须先于课程乙开设(不要求一定紧接)。将这九门课程按拓扑排序,意味着顺序排列后的课程将全部保持所要求的先修关系。( )属于拓扑排序
 
 
  A.  G-A-I-E-F-D-B-H-C
 
  B.  A-G-I-D-B-E-C-F-H
 
  C.  A-G-I-E-B-C-D-F-H
 
  D.  G-A-I-E-B-D-C-F-H
 
 
 

   知识点讲解    
   · 拓扑排序    · 排列    · 排序    · 培训
 
       拓扑排序
        顶点活动的网(也称AOV-网)是用顶点表示活动、用弧表示活动优先关系的有向图。在网中,如果从顶点i到顶点j有一条有向路径,则称i是j的前驱,j是i的后继。若是网中的一条弧,则i是j的直接前驱,j是i的直接后继。
        在AOV-网中,不应存在环,因某项活动不应以它自己为先决条件,故对给定的AOV-网,可采用对有向图构造其顶点的拓扑有序序列来监测其是否存在环。拓扑有序序列是AOV-网中的顶点所构成的有序序列T=(l,…,I,…,n),且满足以下条件:
        .AOV-网的优先关系与序列所反映的先后关系一致;
        .在AOV-网中无优先关系的顶点也被赋予了一定的先后关系。
        则称序列T为AOV-网的一个拓扑有序序列,对AOV-网构造它的拓扑有序序列的过程叫作拓扑排序。
        若网中的所有顶点都在它的拓扑有序序列中,则该AOV-网中必定不存在环。
        拓扑有序序列的构造方法如下。
        (1)在有向图中选择一个没有前驱(即入度为0)的顶点并输出。
        (2)从图中删除该顶点和所有以它为尾弧的顶点。
        (3)重复执行上述步骤(1)和(2),直到全部顶点都已输出或图中已没有无前驱的顶点。
        拓扑排序方法是关键路径求解问题等的基础,同时可应用于课程计划的制订等。从拓扑排序构造的方法可见拓扑排序本质上就是图的遍历过程。
 
       排列
        设S为具有n个不同元素的n元集,从S中选取r个元素且考虑其顺序称为S的一个r排列,不同排列的总数记为,有时也用P(nr)表示。如果r=n,则称这个排列为S的全排列。从排列的定义可知,如果两个排列相同,不仅这两个排列的元素必须完全相同,而且排列的顺序也必须完全相同。
        
        例子1:用0~9这十个数字,可以组成多少个没有重复数字的三位数?
        解法1:由于百位数上的数字不能为0,因此可先考虑排百位上的数字,再排十位和个位上的数字。百位数上的数字只能从除0以外的1~9数字中任选一个,有种;十位和个位上的数字,可以从余下的9个数字中任选两个,有种。根据乘法原理,所求的三位数的个数是
        解法2:可先考虑从0~9这十个数字中任取三个数字的排列数(),再减去其中以0开头的排列数()。因此,所求的三位数的个数是
        解法3:符合条件的三位数可以分为三类:每一位数字都不是0的三位数有个;个位数是0的三位数有个;十位数是0的三位数有个。根据加法原理,符合条件的三位数个数是
 
       排序
        假设含n个记录的文件内容为{R1R2,…,Rn},其相应的关键字为{k1k2,…,kn}。经过排序确定一种排列{Rj1Rj2,…,Rjn},使得它们的关键字满足如下递增(或递减)关系:kj1≤kj2≤…≤kjn(或kj1kj2≥…≥kjn)。
 
       培训
        培训包括旨在提高项目团队成员能力的全部活动。
        培训可以是正式或非正式的。培训方式包括课堂培训、在线培训、计算机辅助培训、在岗培训(由其他项目团队成员提供)、辅导及训练。
        应按人力资源管理计划中的安排来实施预定的培训。也应根据管理项目团队过程中的观察、交谈和项目绩效评估的结果,来开展必要的计划外培训,培训成本通常应该包括在项目预算中,或者由执行组织承担(如果增加的技能有利于未来的项目)。培训可以由内部或外部培训师来执行。
   题号导航      2018年下半年 程序员 上午试卷 综合知识   本试卷我的完整做题情况  
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 /
 
第64题    在手机中做本题