设如图5-6所示的是5个城市的航线图，每个结点表示1个城市，2个结点之间边的权值表示2个城市之间直达航线的票价(单位：元)。若某人打算旅游一个城市各一次，并且返回到出发点，则旅行的最低总票价为______元。

admin2018-04-25 33

问题设如图5-6所示的是5个城市的航线图，每个结点表示1个城市，2个结点之间边的权值表示2个城市之间直达航线的票价(单位：元)。若某人打算旅游一个城市各一次，并且返回到出发点，则旅行的最低总票价为______元。

选项 A、875
B、1045
C、1285
D、1525

答案B

解析这是一个求最短哈密尔顿回路的问题。因为该图只有5个结点，比较简单，只需使用观察法就能很快得出正确答案。首先注意的是，在本图中所有的“三角形”线路都满足三角形边长的规则：“任何两边的和大于第三边”，因此凡是有直通的航线，就不要中转。假设从图的最上方那个城市开始，首先选择189，然后选择379(因为279+209＞379)，再选择69，179，最后选择229，则结果为189+379+69+179+229=1045。

转载请注明原文地址:https://kaotiyun.com/show/XxLZ777K

本试题收录于：系统分析师上午综合知识考试题库软考高级分类

系统分析师上午综合知识考试

软考高级

相关试题推荐

随机试题

最新回复(0)

设如图5-6所示的是5个城市的航线图，每个结点表示1个城市，2个结点之间边的权值表示2个城市之间直达航线的票价(单位：元)。若某人打算旅游一个城市各一次，并且返回到出发点，则旅行的最低总票价为______元。

系统分析师上午综合知识考试

软考高级

请将“幻灯片制作方法讲解”视频，插入到当前幻灯片中。

请在演示文稿的所有幻灯片中使用“谈古论今”模板的一种配色方案。

请利用“源数据”对话框向下图表中添加工作表中新增加的长春销售情况。（在工作表最右侧）

请统计津贴分配表中的津贴分配情况中每部门每种职称的津贴总数。

在单元格A1中，利用四则运算求出2007年1月1日到2007年12月15日期间的天数。

请利用编辑栏插入函数。

请将项目符号转换成项目编号，样式为第3种。

下列4项中说法不正确的是

在PowerPoint2003中，关于设计模板的说法正确的是()。

在Internet上传输的信息至少遵循三个协议：网际协议、传输协议和()。

含铁卟啉的化合物有

毕Ⅱ式胃大部切除术后发生胃肠吻合口出血，最主要的表现是

在某案件开庭审理时，原告提出审判员周某是被告的近亲属，要求其回避。以下说法正确的是：

影响混凝土强度的主要因素有()。[2008年真题]

非系统风险包括()等。

我国会计实务中,当长期负债发生时,一般按未来应付的金额(或面值)来计量长期负债,并列示于资产负债表上。()

党的十八大以来，国务院确定的全国第一个生态文明的先行示范区是()。

根据下列资料，回答下列问题。2014年1—3月全国固定资产投资与2015年1—3月全国固定资产投资相比，同比增速之差为：

2005年某省海洋产业总产值达2144．6亿元；海洋产业增加值达302．4亿元，约占全省海洋产业总产值的14．1％。海洋三大产业结构由2000年的31．0：16．7：52．3调整为2005年的21．0：13．2：65．8。以海洋经济为依托的沿海县

DevelopaGoodHabitForthispart,youareallowed30minutestowriteashortessayentitledDevelopaGoodHabitbycommen