第7章算法程序与计算系统之灵魂练习题答案解析

第7章算法:程序与计算系统之灵魂1、算法就是一个有穷规则的集合，其中之规则规定了解决某一特定类型问题的一个运算序列。回答下列问题。(1)关于算法的特性，下列说法不正确的是_____。(A)算法必须有明确的结束条件，即算法应该能够结束，此即算法的有穷性；(B)算法的步骤必须要确切地定义，不能有歧义性，此即算法的确定性；(C)算法可以有零个或多个输入，也可以有零个或多个输出，此即算法的输入输出性；(D)算法中有待执行的运算和操作必须是相当基本的，可以由机器自动完成，进一步，算法应能在有限时间内完成，此即算法的能行性；(E)上述说法有不正确的；答案：C解释：本题考查对算法基本性质的理解（C）算法的输出性：算法有一个或多个的输出/结果，即与输入有某个特定关系的量。因此（C）选项错误。其余选项，（A）（B）（D）分别是对算法的有穷性，确定性和能行性的正确描述。具体内容参考第七章视频之“算法与算法类问题的求解”以及第七章课件。(2)关于算法的命题，下列说法不正确的是_____。(A)算法规定了任务执行/问题求解的一系列、有限的步骤。(B)算法所规定的计算/处理步骤是有限的，但算法实际执行的计算/处理步骤可以是无限的。(C)算法可以没有输入，但必须有输出。(D)算法的每一个步骤必须确切地定义，且其运算和操作必须相当基本，可以由机器自动完成。答案：B解释：本题考查对算法基本性质的理解（B）违反了算法的有穷性：一个算法在执行有穷步规则之后必须结束。因此（B）选项错误。其余选项，（A）（C）（D）分别是对算法的有穷性，输入输出性和确定性的正确描述。具体内容参考第七章视频之“算法与算法类问题的求解”以及第七章课件。(3)关于算法与程序、计算机语言之间的关系，下列说法不正确的是_____。(A)算法是解决问题的步骤，某个问题可能有多个求解算法；(B)算法不能直接由计算机执行，必须将其转换为程序才能够由计算机执行；(C)算法只能由高级（计算机）语言实现，不能通过机器语言实现；(D)求解问题的多个算法不一定获得相同的解。答案：C解释：本题考查对算法基本性质的理解（C）算法是解决问题的步骤，执行的语言是步骤书写的规范、语法规则、标准的集合是人和计算机都能理解的语言，不仅是高级语言。因此（C）选项错误。其余选项，（A）正确，解决问题的算法可以有多个。（B）选项，程序是算法的实现方式，正确。（D）选项，算法有优劣，对于同一个问题，获得的解可能不同。具体内容参考第七章视频之“算法与算法类问题的求解”以及第七章课件。(4)算法是计算系统的灵魂，为什么？不正确的是_____。(A)计算系统是执行程序的系统，而程序是用计算机语言表达的算法；(B)一个问题的求解可以通过构造算法来解决，“是否会编程序”本质上章是“能否想出求解该问题的算法”；(C)一个算法不仅可以解决一个具体问题，它可以在变换输入输出的情况下，求解一个问题系列；(D)问题求解都可以归结到算法的构造与设计，系统和算法的关系是：算法是龙，而系统是睛，画龙要点睛。(E)上述说法有不正确的；答案：D解释：本题考查算法、程序与系统之间的关系（D）选项，算法是计算系统的灵魂，因此系统和算法的关系是：系统是龙，算法是睛，好的算法能起到画龙点睛的效果。（A）（B）（C）选项描述正确。具体内容参考第七章视频之“算法与算法类问题的求解”以及第七章课件。2、哥尼斯堡七桥问题，是一个经典问题，如下图(a)所示，描述为“由河流隔开的四块陆地上建造了七座桥，寻找走遍这七座桥且只许走过每座桥一次最后又回到原出发点的路径”。关于哥尼斯堡七桥问题，著名数学家欧拉对该问题做了一个抽象：“顶点”为陆地，“边”为连接两块陆地的桥梁。这个抽象被称为“图”，并定义了顶点的“度”为连接一个顶点的边的数量。关于此问题回答下列问题。//本题考查问题及其数学建模的作用(a)(b)(1)哥尼斯堡七桥问题的路径能够找到吗？_____。(A)一定能够找到；(B)一定不能找到；(C)不确定能不能找到。答案：B解释：本题考查问题及其数学建模的作用选择（B），根据欧拉回路关系可知，要是一个图形可以一笔画，需要满足：1）图形必须是连通的；2）途中的“奇点”（相连的边的个数为奇数的点）个数是0或2（该题中应为0个）。该问题中将四个岛抽象成4个点，每条桥抽象成边，可知图中奇点个数是4个，因此不可能找到。具体内容参考第七章视频之“数学建模与算法策略设计--算法思想”，第七章课件或查阅欧拉回路相关资料。(2)对河流隔开的m块陆地上建造的n座桥梁，能否找到走遍这n座桥且只许走过每座桥一次最后又回到原出发点的路径呢？_____。(A)一定能够找到；(B)一定不能找到；(C)不确定能不能找到。答案：C解释：本题考查问题及其数学建模的作用选择（C）根据欧拉回路关系可知，要是一个图形可以一笔画，需要满足：1）图形必须是连通的；2）途中的“奇点”（相连的边的个数为奇数的点）个数是0或2（该题中因为起点和终点是一个，所以奇点个数应为0个）。该问题中将m个岛抽象成m个点，每条桥抽象成边，但图中奇点个数未知，因此不能做判断。具体内容参考第七章视频之“算法与算法类问题的求解，第七章课件或查阅欧拉回路相关资料。(3)对河流隔开的m块陆地上建造的n座桥梁，若要找到走遍这n座桥且只许走过每座桥一次最后又回到原出发点的路径，则需满足以下条件_____。(A)m个顶点n条边的图应是连通的，即由一个顶点出发可沿边到达任何一个其他顶点；(B)每个顶点的度应为偶数；(C)既需要满足(A)又需要满足(B)；(D)上述条件还不够，还需满足更多条件。答案：C解释：本题考查问题及其数学建模的作用选择（C）根据欧拉回路关系可知，要是一个图形可以一笔画，需要满足：1）图形必须是连通的；2）途中的“奇点”（相连的边的个数为奇数的点）个数是0或2（该题中因为起点和终点是一个，所以奇点个数应为0个）。该问题中将m个岛抽象成m个点，每条桥抽象成边，因此应该选择C。具体内容参考第七章视频之“数学建模与算法策略设计--算法思想”，第七章课件或查阅欧拉回路相关资料。(4)下面所示的图(c)，能否找到走遍每一座桥，且每座桥仅走过一次、最后又回到原出发点的路径呢？(c)(A)一定能够找到；(B)一定不能找到；(C)不确定能不能找到。答案：B解释：本题考查问题及其数学建模的作用选择（B）根据欧拉回路关系可知，要是一个图形可以一笔画，需要满足：1）图形必须是连通的；2）途中的“奇点”（相连的边的个数为奇数的点）个数是0或2（该题中因为起点和终点是一个，所以奇点个数应为0个）。图中奇点是C与G，个数为2，不符合要求，因此应该选择B。具体内容参考第七章视频之“数学建模与算法策略设计--算法思想”，第七章课件或查阅欧拉回路相关资料。(5)参见图(c)，增加哪些边，使得能够找到走遍每一座桥，且每座桥仅走过一次、最后又回到原出发点的路径呢？(A)BG边；(B)AG边；(C)CG边；(D)AD边；(E)DE边。答案：C解释：本题考查问题及其数学建模的作用选择（C）根据欧拉回路关系可知，要是一个图形可以一笔画，需要满足：1）图形必须是连通的；2）途中的“奇点”（相连的边的个数为奇数的点）个数是0或2（该题中因为起点和终点是一个，所以奇点个数应为0个）。图中奇点是C与G，个数为2，不符合要求，因此在CG间增加一条边，将寄点数变成0可满足要求，因此应该选择C。具体内容参考第七章视频之“数学建模与算法策略设计--算法思想”，第七章课件或查阅欧拉回路相关资料。(6-1)对河流隔开的m块陆地上建造的n座桥梁，若要找到走遍这n座桥且只许走过每座桥一次的路径，则需满足以下条件_____。(A)m个顶点n条边的图应是连通的，即由一个顶点出发可沿边到达任何一个其他顶点；(B)每个顶点的度应为偶数；(C)既需要满足(A)又需要满足(B)；(D)不满足上述条件(A)(B)(C)的图也能找出满足题目规定要求的路径；答案：D解释：本题考查问题及其数学建模的作用选择（D），此题未要求回到原地，即起点和终点可以不是一个，那么可以有2个奇数点作为起点和终点。根据欧拉回路关系可知，要是一个图形可以一笔画，需要满足：1）图形必须是连通的；2）途中的“奇点”（相连的边的个数为奇数的点）个数是0或2。不同时满足（A）（B），可以有2个顶点的度为奇数，也可以满足题目要求，因此应该选择D。具体内容参考第七章视频之“数学建模与算法策略设计--算法思想”，第七章课件或查阅欧拉回路相关资料。(6-2)对河流隔开的m块陆地上建造的n座桥梁，若要找到走遍这n座桥且只许走过每座桥一次的路径，则需满足以下条件_____。(A)m个顶点n条边的图应是连通的，即由一个顶点出发可沿边到达任何一个其他顶点；(B)每个顶点的度应为偶数，或者，只有两个顶点的度为奇数而其他顶点的度均为偶数；(C)既需要满足(A)又需要满足(B)；(D)不满足上述条件(A)(B)(C)的图也能找出满足题目规定要求的路径；答案：C解释：本题考查问题及其数学建模的作用选择（C），此题未要求回到原地，即起点和终点可以不是一个，那么可以有2个奇数点作为起点和终点。根据欧拉回路关系可知，要是一个图形可以一笔画，需要满足：1）图形必须是连通的；2）途中的“奇点”（相连的边的个数为奇数的点）个数是0或2。因此应该选择C。具体内容参考第七章视频之“数学建模与算法策略设计--算法思想”，第七章课件或查阅欧拉回路相关资料。(7)下面所示的图(d)和图(e)，问能否找到走遍每一座桥，且每座桥仅走过一次的路径呢？(d)(e)(A)图(d)和图(e)都一定不能找到；(B)图(d)一定能够找到；图(e)一定不能找到；(C)图(d)一定不能找到；图(e)一定能够找到；(D)图(d)和图(e)都一定能够找到；答案：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)对两个顶点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，因此可以找到一条欧拉回路，并且只能以此两点作为起点和终点，因此应该选择C。具体内容参考第七章视频之“数学建模与算法策略设计--算法思想”，第七章课件或查阅欧拉回路相关资料。(9)哥尼斯堡七桥问题，给我们的启示是_____。(A)一个具体问题应该进行数学抽象，基于数学抽象进行问题求解；(B)一个具体问题的求解，进行数学建模后，通过模型中的性质分析可以判断该问题是否有解，如果有解，则可以进行计算；而如果无解，则无需进行计算；(C)一个具体问题的求解方法，进行数学建模后，可反映出一类问题的求解方法，例如哥尼斯堡七桥问题的求解方法，建立“图”后，可反映任意n座桥的求解方法；(D)上述全部；答案：D解释：本题考查问题及其数学建模的作用以上说明都正确，对一个具体问题的求解，可先进行数学建模，将具体问题转化成抽象问题，再进行判断是否有解，若有解则计算，若无解则无需计算。具体内容参考