软件水平考试（高级）信息系统项目管理师上午综合知识（运筹学）历年真题试卷汇编1
中文选择题
1.假设市场上某种商品有两种品牌A和B，当前的市场占有率各为50％。根据历史经验估计，这种商品当月与下月市场占有率的变化可用转移矩阵P来描述：
(C)
A. A的份额增加了10％，B的份额减少了10％
B. A的份额减少了10％，B的份额增加了10％
C. A的份额增加了14％，B的份额减少了14％
D. A的份额减少了14％，B的份额增加了14％
解析：看到这道题，你是否回想起了上大学时的线性代数?
市场占有率变化的计算过程如下所示。
2.下图标出了某地区的运输网。
各结点之间的运输能力如下表：
(B)
A. 26
B. 23
C. 22
D. 21
解析：这题考的是最大流量问题。
首先把运输能力数据标在图上(注意：结点之间的双向运输能力都是相同的，所以省略了箭头，这是最简单的流量问题)。
接下来寻找从结点①到结点⑥的运输能力最大的那条路径(注意：每条路径上的最大流量应是其各段流量的最小值)，路径①③⑤⑥运输能力最大，为10万吨。
将总运输能力暂时记为10万吨，然后将路径①③⑤⑥上各段线路上的流量扣除10万吨，剩余流量为0的线段则将其删除(比如①一③)。此时的运输网变成了下图。
继续寻找从①到⑥的运输能力最大的那条路径，此时路径①②⑤⑥的运输能力最大，为6万吨。
将总运输能力暂时记为10+6=16万吨，然后将路径①②⑤⑥上各段线路上的流量扣除6万吨，剩余流量为0的线段则将其删除。此时的运输网变成了下图。
3.煤气公司想要在某地区高层住宅楼之间铺设煤气管道并与主管道相连，位置如下图所示，结点代表各住宅楼和主管道位置，线上数字代表两节点间距离(单位：百米)。则煤气公司铺设的管道总长最短为( )米。
(B)
A. 1 800
B. 2 200
C. 2 000
D. 2 100
解析：这是一个典型的无向连通图的最小生成树问题(Minimum Spanning Tree)。
算法如下：
任取一点，例如①，将其纳入已完成部分。点①与其他各点中的最小距离为①⑤=3，从而将边①⑤以及点⑤纳入已完成部分。
点①、⑤与其他各点②、③、④、⑥这两个集合之间的最短距离为①④=⑤⑥=5，任选其一，比如①④，从而将边①④与点④纳入已完成部分。
点①、④、⑤与点②、③、⑥两个集合的最短距离为③④=4，从而将边③④与点③纳入已完成部分。
点①、③、④、⑤与点②、⑥两个集合之间的最短距离为⑤⑥=5，从而将边⑤⑥与点⑥纳入已完成部分。
点①、③、④、⑤、⑥与点②两个集合之间的最短距离为②⑥=5，从而将边②⑥与点②纳入已完成部分。
此时，所有6个点都已经接通，其边为AE、AB．AF、FD．CD，总长度为22(百米)．如下图所示：
4.某学院10名博士生(B1—B10)选修6门课程(A—F)的情况如下表(用√表示选修)。
(D)
A. AE，BD，CF
B. AC，BF，DE
C. AF，BC，DE
D. AE，BC，DF
解析：这题考的是排课表问题(Time—table Problem)。
这道题最简单的解法就是把四个选项挨个检查一遍，看是否符合规则。
比如A选项的BD将导致博士生Bl在一天参加两门考试，不能选。
比如B选项的AC将导致博士生B2在一天参加两门考试，不能选。
比如C选项的AF将导致博士生B3在一天参加两门考试，不能选。
图示建模法也是一种常用的解法，具体如下：
将6门课程作为6个结点。
如果两门课程不可以在同一天安排考试，就在它们之间划一条连线。
一个博士生选修的各门课程之间都应画出连线，例如，博士生B1选修了A、B、D三门课程，则A、B、D之间都应有连线，表示这三门课中的任何两门都不能安排在同一天。
5.有八种物品A、B、C、D、E、F、G、H要装箱运输，虽然量不大，仅装1箱也装不满，但出于安全考虑，有些物品不能同装一箱。在下表中，符号X表示相应的两种物品不能同装一箱。运输这八种物品至少需要装( )箱。
(B)
A. 2
B. 3
C. 4
D. 5
解析：将不能放在一起的物品连线，得出下图。
从图中选取连线最多的节点G(共5条连线)，将其放入第一箱，图中与G之间没有连线的节点为A、B(能够与G放在一起的物品)，且AB之间没有连线，于是第一箱为ABG。
将ABG去除后，形成新图，如下所示：
<
本文档预览：3600字符，共16458字符，源文件无水印，下载后包含无答案版和有答案版，查看完整word版点下载
