信息系统项目管理工程师备考计算类真题讲解十三

一、最短路径：

1）创建到达矩阵，如果学校设置在每个村落的，到达的距离，如下所示：

学校	A	B	C	D	E	F	G
A	0	1.5	1.2	1.8	4.8	7	8
B	1.5	0	2.7	2.2	5	5.5	7
C	1.2	2.7	0	1.6	4.6	8.2	7.8
D	1.8	2.2	1.6	0	3	6.9	6.2
E	4.8	5	4.6	3	0	3.9	3.2
F	7	5.5	8.2	6.9	3.9	0	1.5
G	8	7	7.8	6.2	3.2	1.5	0

2)对于每行，分别用人数乘上距离，得到如下表：

学校	A	B	C	D	E	F	G
A	0	75	60	90	240	350	400
B	60	0	108	88	200	220	280
C	72	162	0	96	276	492	468
D	36	44	32	0	60	138	124
E	336	350	322	210	0	273	224
F	560	440	656	552	312	0	120
G	800	700	780	620	320	150	0
总共	1864	1771	1958	1656	1408	1623	1616

答案为E

二、图与网络图

分析：对于这种全遍历路径的问题，需要掌握以下几个知识点

1)奇点：如果从这一点出发的线条有奇数个，则此点叫奇点

2）没有奇点或者有2个奇点的图形可以一笔画出。比如：

对于没有奇点的图形，可以从一点一笔回到起点

对于2个奇点的图形，只能从一个奇点回到另一个奇点

3）有4个或4个以上的奇点，不能一笔画出，有2N个奇点，需要N条才能画出

因此图中有2个奇点，所以最长路径为所有路径之和+两个奇点的距离，即：48