大学计算机计算思维导论（哈尔滨工业大学）2023章节测试答案超星尔雅

对河流隔开的m块陆地上建造的n座桥梁，若要找到走遍这n座桥且只许走过每座桥一次最后又回到原出发点的路径，则需满足以下条件_____。

我的答案：既需要满足(A)又需要满足(B)

A、m个顶点n条边的图应是连通的，即由一个顶点出发可沿边到达任何一个其他顶点

B、每个顶点的度应为偶数

C、既需要满足(A)又需要满足(B)

D、上述条件还不够，还需满足更多条件

4

哥尼斯堡七桥问题的路径能够找到吗？ _____。

我的答案：一定不能找到

A、一定能找到

B、一定不能找到

C、可能有多条路径

D、不确定能否找到

5

对河流隔开的m块陆地上建造的n座桥梁，若要找到走遍这n座桥且只许走过每座桥一次的路径，则需满足以下条件_____。

我的答案：不满足上述条件(A)(B)(C)的图也能找出满足题目规定要求的路径

A、m个顶点n条边的图应是连通的，即由一个顶点出发可沿边到达任何一个其他顶点

B、每个顶点的度应为偶数

C、既需要满足(A)又需要满足(B)

D、不满足上述条件(A)(B)(C)的图也能找出满足题目规定要求的路径

6

哥尼斯堡七桥问题，给我们的启示是_____。

我的答案：以上全部

A、一个具体问题应该进行数学抽象，基于数学抽象进行问题求解

B、一个具体问题的求解，进行数学建模后，通过模型中的性质分析可以判断该问题是否有解，如果有解，则可以进行计算；而如果无解，则无需进行计算

C、一个具体问题的求解方法，进行数学建模后，可反映出一类问题的求解方法，例如哥尼斯堡七桥问题的求解方法，建立“图”后，可反映任意n座桥的求解方法

D、以上全部

7

TSP-旅行商问题，是一个经典问题，描述为“有n个城市，任何两个城市之间的距离都是确定的，现要求一旅行商从某城市出发必须经过每一个城市且只能在每个城市逗留一次，最后回到原出发城市，问如何事先确定好一条最短的路线使其旅行的费用最少”。

我的答案：对TSP问题而言，遍历算法和贪心算法求得的解是不一样的，贪心算法是求近似解，执行更快一些，而遍历算法是求精确解，执行更慢一些

关于TSP问题的遍历算法和贪心算法，下列说法正确的是_____。

A、对TSP问题而言，遍历算法和贪心算法求得的解是一样的，所不同的是贪心算法更快一些，而遍历算法更慢一些

B、对TSP问题而言，遍历算法和贪心算法求得的解是一样的，所不同的是遍历算法更快一些，而贪心算法更慢一些

C、对TSP问题而言，遍历算法和贪心算法求得的解是不一样的，贪心算法是求近似解，执行更快一些，而遍历算法是求精确解，执行更慢一些

D、对TSP问题而言，遍历算法和贪心算法求得的解是不一样的，贪心算法是求精确解，执行更快一些，而遍历算法是求近似解，执行更慢一些

8

关于TSP的贪心算法的求解思想，下列说法不正确的是_____。

我的答案：贪心算法确定的路径，是由局部最优(即tk+1在tk看来是最优的)组合起来的路径，该路径从全局角度也一定是最优的

A、无需对所有组合(所有可能解)进行比较，而仅需依照某种办法确定其中的一个组合即可，该组合不一定是最优解，但却是一个较优解或次优解

★《布宫号》提醒您：民俗信仰仅供参考，请勿过度迷信！