1、第 7 章 算法:程序与计算系统之灵魂1、算法就是一个有穷规则的集合，其中之规则规定了解决某一特定类型问题的一个运算序列。回答下列问题。(1)关于算法的特性，下列说法不正确的是_。(A)算法必须有明确的结束条件，即算法应该能够结束，此即算法的有穷性；(B)算法的步骤必须要确切地定义，不能有歧义性，此即算法的确定性； (C)算法可以有零个或多个输入，也可以有零个或多个输出，此即算法的输入输出性；(D)算法中有待执行的运算和操作必须是相当基本的，可以由机器自动完成，进一步，算法应能在有限时间内完成，此即算法的能行性；(E)上述说法有不正确的；答案：C解释：本题考查对算法基本性质的理解 （C）算法的
2、输出性：算法有一个或多个的输出/ 结果，即与输入有某个特定关系的量。因此（C ）选项错误。其余选项， （A） （B） （D）分别是对算法的有穷性，确定性和能行性的正确描述。具体内容参考第七章视频之“算法与算法类问题的求解”以及第七章课件。(2)关于算法的命题，下列说法不正确的是_。(A)算法规定了任务执行 /问题求解的一系列、有限的步骤。(B)算法所规定的计算/处理步骤是有限的，但算法实际执行的计算/处理步骤可以是无限的。(C)算法可以没有输入，但必须有输出。(D)算法的每一个步骤必须确切地定义，且其运算和操作必须相当基本，可以由机器自动完成。答案：B解释：本题考查对算法基本性质的理解 （B）
3、违反了算法的有穷性：一个算法在执行有穷步规则之后必须结束。因此（B ）选项错误。其余选项， （A） （C） （D）分别是对算法的有穷性，输入输出性和确定性的正确描述。具体内容参考第七章视频之“算法与算法类问题的求解”以及第七章课件。(3)关于算法与程序、计算机语言之间的关系，下列说法不正确的是_。(A)算法是解决问题的步骤，某个问题可能有多个求解算法；(B)算法不能直接由计算机执行，必须将其转换为程序才能够由计算机执行；(C)算法只能由高级（计算机）语言实现，不能通过机器语言实现；(D)求解问题的多个算法不一定获得相同的解。答案：C解释：本题考查对算法基本性质的理解 （C）算法是解决问题的步骤
4、，执行的语言是步骤书写的规范、语法规则、标准的集合是人和计算机都能理解的语言，不仅是高级语言。因此（C）选项错误。其余选项， （A）正确，解决问题的算法可以有多个。 （B）选项，程序是算法的实现方式，正确。 （D）选项，算法有优劣，对于同一个问题，获得的解可能不同。具体内容参考第七章视频之“算法与算法类问题的求解”以及第七章课件。(4)算法是计算系统的灵魂，为什么？不正确的是_。(A)计算系统是执行程序的系统，而程序是用计算机语言表达的算法；(B)一个问题的求解可以通过构造算法来解决， “是否会编程序”本质上章是“能否想出求解该问题的算法” ； (C)一个算法不仅可以解决一个具体问题，它可以在
5、变换输入输出的情况下，求解一个问题系列；(D)问题求解都可以归结到算法的构造与设计，系统和算法的关系是：算法是龙，而系统是睛，画龙要点睛。(E)上述说法有不正确的；答案：D解释：本题考查算法、程序与系统之间的关系（D）选项，算法是计算系统的灵魂，因此系统和算法的关系是：系统是龙，算法是睛，好的算法能起到画龙点睛的效果。 （A ） （B） （C）选项描述正确。具体内容参考第七章视频之“算法与算法类问题的求解”以及第七章课件。2、哥尼斯堡七桥问题，是一个经典问题，如下图(a)所示，描述为“由河流隔开的四块陆地上建造了七座桥，寻找走遍这七座桥且只许走过每座桥一次最后又回到原出发点的路径” 。关于哥尼
6、斯堡七桥问题，著名数学家欧拉对该问题做了一个抽象：“顶点”为陆地， “边”为连接两块陆地的桥梁。这个抽象被称为“图” ，并定义了顶点的“度”为连接一个顶点的边的数量。关于此问题回答下列问题。/本题考查问题及其数学建模的作用(a) (b)(1)哥尼斯堡七桥问题的路径能够找到吗？ _。(A)一定能够找到； (B)一定不能找到； (C)不确定能不能找到。答案：B解释：本题考查问题及其数学建模的作用选择（B） ，根据欧拉回路关系可知，要是一个图形可以一笔画，需要满足：1）图形必须是连通的；2）途中的“奇点” （相连的边的个数为奇数的点）个数是 0 或 2（该题中应为0 个） 。该问题中将四个岛抽象成
7、4 个点，每条桥抽象成边，可知图中奇点个数是 4 个，因此不可能找到。具体内容参考第七章视频之“数学建模与算法策略设计-算法思想” ，第七章课件或查阅欧拉回路相关资料。(2)对河流隔开的 m 块陆地上建造的 n 座桥梁，能否找到走遍这 n 座桥且只许走过每座桥一次最后又回到原出发点的路径呢？ _。 (A)一定能够找到； (B)一定不能找到； (C)不确定能不能找到。答案：C解释：本题考查问题及其数学建模的作用选择（C）根据欧拉回路关系可知，要是一个图形可以一笔画，需要满足：1）图形必须是连通的；2）途中的“奇点” （相连的边的个数为奇数的点）个数是 0 或 2（该题中因为起点和终点是一个，所以
8、奇点个数应为 0 个） 。该问题中将 m 个岛抽象成 m 个点，每条桥抽象成边，但图中奇点个数未知，因此不能做判断。具体内容参考第七章视频之“算法与算法类问题的求解，第七章课件或查阅欧拉回路相关资料。(3)对河流隔开的 m 块陆地上建造的 n 座桥梁，若要找到走遍这 n 座桥且只许走过每座桥一次最后又回到原出发点的路径，则需满足以下条件_。(A)m 个顶点 n 条边的图应是连通的，即由一个顶点出发可沿边到达任何一个其他顶点；(B)每个顶点的度应为偶数； (C)既需要满足(A)又需要满足(B) ；(D)上述条件还不够，还需满足更多条件。答案：C解释：本题考查问题及其数学建模的作用选择（C）根据欧
9、拉回路关系可知，要是一个图形可以一笔画，需要满足：1）图形必须是连通的；2）途中的“奇点” （相连的边的个数为奇数的点）个数是 0 或 2（该题中因为起点和终点是一个，所以奇点个数应为 0 个） 。该问题中将 m 个岛抽象成 m 个点，每条桥抽象成边，因此应该选择 C。具体内容参考第七章视频之“数学建模与算法策略设计-算法思想” ，第七章课件或查阅欧拉回路相关资料。(4)下面所示的图(c) ，能否找到走遍每一座桥，且每座桥仅走过一次、最后又回到原出发点的路径呢？(c)(A)一定能够找到； (B)一定不能找到； (C)不确定能不能找到。答案：B解释：本题考查问题及其数学建模的作用选择（B）根据欧
10、拉回路关系可知，要是一个图形可以一笔画，需要满足：1）图形必须是连通的；2）途中的“奇点” （相连的边的个数为奇数的点）个数是 0 或 2（该题中因为起点和终点是一个，所以奇点个数应为 0 个） 。图中奇点是 C 与 G，个数为 2，不符合要求，因此应该选择 B。具体内容参考第七章视频之“数学建模与算法策略设计-算法思想” ，第七章课件或查阅欧拉回路相关资料。(5)参见图(c)，增加哪些边，使得能够找到走遍每一座桥，且每座桥仅走过一次、最后又回到原出发点的路径呢？(A)BG 边； (B)AG 边； (C)CG 边； (D)AD 边； (E)DE 边。答案：C解释：本题考查问题及其数学建模的作用
11、选择（C）根据欧拉回路关系可知，要是一个图形可以一笔画，需要满足：1）图形必须是连通的；2）途中的“奇点” （相连的边的个数为奇数的点）个数是 0 或 2（该题中因为起点和终点是一个，所以奇点个数应为 0 个） 。图中奇点是 C 与 G，个数为 2，不符合要求，因此在 CG 间增加一条边，将寄点数变成 0 可满足要求，因此应该选择 C。具体内容参考第七章视频之“数学建模与算法策略设计-算法思想” ，第七章课件或查阅欧拉回路相关资料。(6-1)对河流隔开的 m 块陆地上建造的 n 座桥梁，若要找到走遍这 n 座桥且只许走过每座桥一次的路径，则需满足以下条件_。(A)m 个顶点 n 条边的图应是连
12、通的，即由一个顶点出发可沿边到达任何一个其他顶点；(B)每个顶点的度应为偶数； (C)既需要满足(A)又需要满足(B) ；(D)不满足上述条件 (A)(B)(C)的图也能找出满足题目规定要求的路径；答案：D解释：本题考查问题及其数学建模的作用选择（D） ，此题未要求回到原地，即起点和终点可以不是一个，那么可以有 2 个奇数点作为起点和终点。根据欧拉回路关系可知，要是一个图形可以一笔画，需要满足：1）图形必须是连通的；2）途中的“奇点” （相连的边的个数为奇数的点）个数是 0 或 2。不同时满足（A） （B） ，可以有 2 个顶点的度为奇数，也可以满足题目要求，因此应该选择 D。具体内容参考第七
13、章视频之“数学建模与算法策略设计-算法思想” ，第七章课件或查阅欧拉回路相关资料。(6-2)对河流隔开的 m 块陆地上建造的 n 座桥梁，若要找到走遍这 n 座桥且只许走过每座桥一次的路径，则需满足以下条件_。(A)m 个顶点 n 条边的图应是连通的，即由一个顶点出发可沿边到达任何一个其他顶点；(B)每个顶点的度应为偶数，或者，只有两个顶点的度为奇数而其他顶点的度均为偶数；(C)既需要满足(A)又需要满足(B) ；(D)不满足上述条件 (A)(B)(C)的图也能找出满足题目规定要求的路径；答案：C解释：本题考查问题及其数学建模的作用选择（C） ，此题未要求回到原地，即起点和终点可以不是一个，那
14、么可以有 2 个奇数点作为起点和终点。根据欧拉回路关系可知，要是一个图形可以一笔画，需要满足：1）图形必须是连通的；2）途中的“奇点” （相连的边的个数为奇数的点）个数是 0 或 2。因此应该选择 C。具体内容参考第七章视频之“数学建模与算法策略设计-算法思想” ，第七章课件或查阅欧拉回路相关资料。(7)下面所示的图(d) 和图(e)，问能否找到走遍每一座桥，且每座桥仅走过一次的路径呢？ (d) (e)(A)图(d)和图(e)都一定不能找到；(B)图(d) 一定能够找到；图 (e)一定不能找到；(C)图(d) 一定不能找到；图 (e)一定能够找到；(D)图(d)和图(e)都一定能够找到；答案：
15、C解释：本题考查问题及其数学建模的作用选择（C）根据欧拉回路关系可知，要是一个图形可以一笔画，需要满足：1）图形必须是连通的；2）途中的“奇点” （相连的边的个数为奇数的点）个数是 0 或 2。d 图有FGE 三个奇点，一定不能找到，而 e 图有 FG 两个奇点，一定能找到，因此应该选择 C。具体内容参考第七章视频之“数学建模与算法策略设计-算法思想” ，第七章课件或查阅欧拉回路相关资料。(8)参见下图(f)，下列说法正确的是_。(f)(A)对A、B、 C、D、E、F 、 G中的任意两个顶点 X 和 Y，都可以找到一条路径，从X 出发 走遍每一座桥，且每座桥仅走过一次，最后终止于 Y；(B)对
16、两个顶点 A 和 B，可以找到一条路径，从 A 出发 走遍每一座桥，且每座桥仅走过一次，最后终止于 B；(C)对两个顶点 D 和 G，可以找到一条路径，从 D 出发 走遍每一座桥，且每座桥仅走过一次，最后终止于 G； (D)对A、B、 C、D、E、F 、 G中的任意两个顶点 X 和 Y，都找不到一条路径，从 X出发 走遍每一座桥，且每座桥仅走过一次，最后终止于 Y；答案：C解释：本题考查问题及其数学建模的作用选择（C）根据欧拉回路关系可知，要是一个图形可以一笔画，需要满足：1）图形必须是连通的；2）途中的“奇点” （相连的边的个数为奇数的点）个数是 0 或 2。该图奇点为 G 和 D，因此可以
17、找到一条欧拉回路，并且只能以此两点作为起点和终点，因此应该选择 C。具体内容参考第七章视频之“数学建模与算法策略设计-算法思想” ，第七章课件或查阅欧拉回路相关资料。(9)哥尼斯堡七桥问题，给我们的启示是_。(A)一个具体问题应该进行数学抽象，基于数学抽象进行问题求解；(B)一个具体问题的求解，进行数学建模后，通过模型中的性质分析可以判断该问题是否有解，如果有解，则可以进行计算；而如果无解，则无需进行计算；(C)一个具体问题的求解方法，进行数学建模后，可反映出一类问题的求解方法，例如哥尼斯堡七桥问题的求解方法，建立“图”后，可反映任意 n 座桥的求解方法；(D)上述全部；答案：D解释：本题考查
18、问题及其数学建模的作用以上说明都正确，对一个具体问题的求解，可先进行数学建模，将具体问题转化成抽象问题，再进行判断是否有解，若有解则计算，若无解则无需计算。具体内容参考第七章视频之“数学建模与算法策略设计-算法思想” ，第七章课件或查阅欧拉回路相关资料。(10)哥尼斯堡七桥问题，推而广之就是 m 个顶点 n 条边的图的“一笔画”问题，我们可以给出一个算法来求解该问题，即“对河流隔开的 m 块陆地上建造的 n 座桥梁，若要找到走遍这 n 座桥且只许走过每座桥一次的路径” 。 关于该算法的基本思想，下列说法正确的是_。(A)以任何一个顶点为起点，按照图的“边”的指示，找到按该边与该顶点相连的下一个
19、顶点，并标记该边为“已访问” ，依次循环，直到所有的边都被访问过为止，便可找到给定问题的解；(B)以任何一个顶点为起点，按照图的未访问过“边”的指示，找到按该边与该顶点相连的下一个顶点，并标记该边为“已访问” ，依次循环，直到所有的边都被访问过为止，便可找到给定问题的解；(C)首先判断该问题是否有解，若无解，则直接退出；若有解，则以任何一个顶点为起点，按照图的未访问过“边”的指示，找到按该边与该顶点相连的下一个顶点，并标记该边为“已访问” ，依次循环，直到所有的边都被访问过为止，便可找到给定问题的解；(D)首先判断该问题是否有解，若无解，则直接退出；若有解，则选择一个奇数度的顶点为起点，按照图
20、的未访问过“边”的指示，找到按该边与该顶点相连的下一个顶点，并标记该边为“已访问” ，依次循环，直到所有的边都被访问过为止，便可找到给定问题的解；(E)上述都不正确。答案：D解释：本题考查问题及其数学建模的作用选择（D）根据欧拉回路关系可知，要是一个图形可以一笔画，需要满足：1）图形必须是连通的；2）途中的“奇点” （相连的边的个数为奇数的点）个数是 0 或 2。因此，若有奇点，则起点和终点必须是奇点，若无，则任意，因此（A） （B） （C） ，因此应该选择 D。具体内容参考第七章视频之“数学建模与算法策略设计-算法思想” ，第七章课件或查阅欧拉回路相关资料。3、背包问题的定义是：给定一组物品
21、，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中。背包问题的一个例子：应该选择哪些盒子，才能使价格尽可能地大，而保持重量小于或等于 15 kg？其示意图如下：(1)该背包问题的可能解的数量是_。(A) 5 (B) 10 (C) 32 (D) 64答案：C解释：本题考查问题及其数学建模的作用由题意可知，只要可放入背包的状态都算是可能解，可以按背包容量由 1 到 15 遍历可能性。答案为（C）32 个。具体内容查阅背包问题相关资料。(2)假定求解该问题的一种贪心策略是：优先选择能装下盒子中价格最高的，依据
22、该算法策略所得到的解的总价值是_。(A) 16 (B) 15 (C) 14 (D) 13答案：B解释：本题考查问题及其数学建模的作用由题意可知使用贪心算法，从价值最高的开始放入，第一个放入价值$10 的 4kg 物品，接下来价值最大的是$4，但再加上 12kg 已经超过了背包的限度，所以不可放入，接下来放入其余的 3 个可满足重量限制的物品，总价值是 15，所以选择（B） 。具体内容查阅背包问题相关资料。(3)假定求解该问题的一种贪心策略是：优先选择能装下盒子中单位重量价值最高的，依据该算法策略所得到的解的总价值是_。(A) 16 (B) 15 (C) 14 (D) 13答案：B解释：本题考查
23、问题及其数学建模的作用由题意可知使用贪心算法，从单位价值最高的开始放入，五个物品单位价值从大到小依次为：2.5,2,1,1,1/3，依次放入并验证是否超出背包重量限制：$10-4kg, $2-1kg,$1-1kg,$2-2kg，之后放不下$4-12kg 的物品，到此总价值是 15，所以选择（B） 。具体内容查阅背包问题相关资料。(4) 假定求解该问题的一种贪心策略是：最大程度地利用背包的容量（15kg） ，依据该算法策略所得到的解的总价值是_。(A) 8 (B) 15 (C) 14 (D) 13答案：A解释：本题考查问题及其数学建模的作用由题意可知使用贪心算法，需要让剩余空间最小，那么可以得到
24、的组合是，12kg+2kg+1kg=15kg，重量得到最大利用，总价值是 8，所以选择（A ） 。具体内容查阅背包问题相关资料。(5) 使用遍历算法策略所得到的解的总价值是_。(A) 8 (B) 15 (C) 14 (D) 13答案：B解释：本题考查问题及其数学建模的作用用遍历算法策略，状态转移方程：fv=maxfv,fv-ci+wi，即 fiv表示前 i 件物品恰放入一个容量为 v 的背包可以获得的最大价值，第 i 件物品的重量是 ci，价值是 wi。“将前 i 件物品放入容量为 v 的背包中”这个子问题，若只考虑第 i 件物品的策略（放或不放），那么就可以转化为一个只牵扯前 i-1 件物品
25、的问题。如果不放第 i 件物品，那么问题就转化为“前 i-1 件物品放入容量为 v 的背包中” ，价值为 fi-1v；如果放第 i 件物品，那么问题就转化为“ 前 i-1 件物品放 入剩下的容量为 v-ci的背包中” ，此时能获得的最大价值就是 f i-1v-ci再加上通过放入第 i 件物品获得的价值 wi。按此方法，可得总价值是 15，所以选择（B） 。具体内容查阅背包问题相关资料。(6) 假定有 N 个物品，其价值分别为 V1, V2, ., VN，重量分别为 W1, W2, ., WN，背包所能承受的总重量为 Wmax，为物品 i 定义一个决策变量 xi，其中 xi=1 表示选择该物品，
26、xi=0 表示不选择该物品。下面哪个描述共同构成了该问题的数学模型_。(A) 问题的目标函数是 ；N1ixma iV(B) 问题的目标函数是 ；1i iW(C) 问题解所应满足的约束是 ；maxN1i i(D) 问题解所应满足的约束是 ；ax1i Vi(E) 前述 (A)和(C)；答案：E解释：本题考查问题及其数学建模的作用该问题有两个条件：1）物品不能超过背包所能承受的重量，即（C）选项： maxN1i Wi2）背包内物品价值最大，即（A ）选项目标函数为 1iax iV（B）和（D）选项明显错误，将质量和价值比较。所以选择（E） 。具体内容查阅背包问题相关资料。4、TSP-旅行商问题，是一个经典问题，如下图所示，描述为“有 n 个城市，任何两个城市之间的距离都是确定的，现要求一旅行商从某城市出发必须经过每一个城市且只能在每个城市逗留一次，最后回到原出发城市，问如何事先确定好一条最短的路线使其旅行的费用最少” 。围绕 TSP，回答下列问题。(1)关于 TSP 问题的遍历算法和贪心算法，下列说法正确的是_。(A)对 TSP 问题而言，遍历算法和贪心算法求得的解是一样的，所不同的是贪心算法更快一些，而遍历算法更慢一些；
