算法程序与计算系统

《算法程序与计算系统》由会员分享，可在线阅读，更多相关《算法程序与计算系统（26页珍藏版）》请在金锄头文库上搜索。

1、第7 章 算法:程序与计算系统之灵魂1、算法就是一个有穷规则的集合，其中之规则规定了解决某一特定类型问题的一个运算序 列。回答下列问题。(1) 关于算法的特性，下列说法不正确的是。(A) 算法必须有明确的结束条件，即算法应该能够结束，此即算法的有穷性；(B) 算法的步骤必须要确切地定义，不能有歧义性，此即算法的确定性；(C) 算法可以有零个或多个输入，也可以有零个或多个输出，此即算法的输入输出性；(D) 算法中有待执行的运算和操作必须是相当基本的，可以由机器自动完成，进一步， 算法应能在有限时间内完成，此即算法的能行性；(E) 上述说法有不正确的；答案：C 解释：本题考查对算法基本性质的理解(

2、C) 算法的输出性：算法有一个或多个的输出/结果，即与输入有某个特定关系的量。 因此(C)选项错误。其余选项，(A)(B)(D)分别是对算法的有穷性，确定性和能行性的 正确描述。具体内容参考第七章视频之“算法与算法类问题的求解”以及第七章课件。(2) 关于算法的命题，下列说法不正确的是。(A) 算法规定了任务执行/问题求解的一系列、有限的步骤。(B) 算法所规定的计算/处理步骤是有限的，但算法实际执行的计算/处理步骤可以是无限 的。(C) 算法可以没有输入，但必须有输出。(D) 算法的每一个步骤必须确切地定义，且其运算和操作必须相当基本，可以由机器自 动完成。答案： B解释：本题考查对算法基本

3、性质的理解(B) 违反了算法的有穷性：一个算法在执行有穷步规则之后必须结束。因此(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、到原出发点的路径”。 关于哥尼斯堡七桥问题，着名数学家欧拉对该问题做了一个抽象：“顶点”为陆地，“边”为 连接两块陆地的桥梁。这个抽象被称为“图”，并定义了顶点的“度”为连接一个顶点的边 的数量。关于此问题回答下列问题。ABEGABABECECGF15 kgVN,重量分别为W1, W2,WN,背包所能承受的总重量为Wmax，为物品i定义一个决策变量xi, 其中xi=1表示选择该物品，xi=0表示不选择该物品。下面哪个描述共同构成了该问题的数 学模型。(A)问题的目标函数是max x V ； iii=1问题的目标函数是max x W ； iii=1(C) 问题解所应满足的约束是迓x W Wi i

7、 max i=1(D) 问题解所应满足的约束是迓x V Wi i maxi=1(E) 前述(A)和(C)；答案：E解释：本题考查问题及其数学建模的作用该问题有两个条件：区 x W Wi i maxi=11)物品不能超过背包所能承受的重量，即(C)选项:max f x V2)背包内物品价值最大，即(A)选项目标函数为i=1(B) 和(D)选项明显错误，将质量和价值比较。所以选择(E)。具体内容查阅背包问题相关资料。4、TSP-旅行商问题，是一个经典问题，如下图所示，描述为“有n个城市，任何两个城市 之间的距离都是确定的，现要求一旅行商从某城市出发必须经过每一个城市且只能在每个城 市逗留一次，最后

8、回到原出发城市，问如何事先确定好一条最短的路线使其旅行的费用最(A) 对TSP问题而言，遍历算法和贪心算法求得的解是一样的，所不同的是贪心算法更 快一些，而遍历算法更慢一些；(B) 对TSP问题而言，遍历算法和贪心算法求得的解是一样的，所不同的是遍历算法更 快一些，而贪心算法更慢一些；(C) 对TSP问题而言，遍历算法和贪心算法求得的解是不一样的，贪心算法是求近似解, 执行更快一些，而遍历算法是求精确解，执行更慢一些；(D) 对TSP问题而言，遍历算法和贪心算法求得的解是不一样的，贪心算法是求精确解, 执行更快一些，而遍历算法是求近似解，执行更慢一些；答案：C解释：本题考查对贪心算法与遍历算法

9、的简单理解贪心算法：一定要做当前情况下的最好选择，否则将来可能会后悔，故名“贪心”。如 果以A城市为起点，选择最近的下一点，为B城市。以B城市为起点，选择最近的下一个 城市，可以选择C或D,以选择D为例。以D为起点，选择最近的下一点，为C城市。最 后回到A。整个过程的花费为：14。于是，该贪心算法的解为14。而通过遍历可知，该问 题的最优解为A-B-C-D-A,花费为13。可见，贪心算法与遍历算法的解不会总是完全相同。 而贪心算法只会做当前情况下最优选择，其时间复杂度为n3级别。而遍历则会将各种情况 考虑在内，其时间复杂度为(n-1)!级别当城市的数量变多时，遍历算法将会出现组合爆炸。 故，相

10、比之下，贪心算法的计算速度更快。所以C)选项是正确的。详细内容请参考第七章视频“算法，程序与计算系统之灵魂”与第七章课件。关于TSP，下列说法不正确的是。(A)TSP问题的一个可能解就是n个城市的一个组合,其中任何两个ti，都 对应不同的城市。若要求得最优解，则必须对所有的组合，即所有可能解进行比较。(B) TSP问题的难点是当n值很大时，组合数目非常庞大(组合数目为n!),以致于计算机 不能在有限时间内完成所有的组合；(C) TSP问题的难点是当n值很大时，组合数目非常庞大(组合数目为n!)，虽如此，计算 机仍然能够在有限时间内完成所有的组合；(D) 上述思想-对所有组合进行比较的思想，即是

11、所谓的遍历算法策略，它仅仅对n值很 小的 TSP 问题是能行的。答案：C解释：本题考查对TSP组合优化问题的理解对所有组合进行比较的思想，即所谓的遍历算法策略，其组合数目为n!。2001年解决 了德国15112个城市的TSP问题，使用了美国Rice大学和普林斯顿大学之间互连的、速度 为500MHz的Compaq EV6 Alpha处理器组成的110台计算机，所有计算机花费的时间之和 为年。由此可见，当n巨大时，用遍历算法解决TSP问题是不现实的。所以(C)选项错误。详细内容请参考第七章视频“算法，程序与计算系统之灵魂”与第七章课件。(3)关于 TSP 的贪心算法的求解思想，下列说法不正确的是。

12、(A) 无需对所有组合(所有可能解)进行比较，而仅需依照某种办法确定其中的一个组合即 可，该组合不一定是最优解，但却是一个较优解或次优解；(B) 在确定一个组合t2,tn时，tk+1是与tk相连接的城市中与tk距离最短的城市，即 tk+1是由tk确定的，与tk连接的若干城市中的特性最优的城市；(C) 贪心算法确定的路径，是由局部最优(即tk+1在tk看来是最优的)组合起来的路径，该 路径从全局角度也一定是最优的；(D) 对一个具体的TSP问题，每次执行贪心算法，所求得的最终解可能是不同的。答案： C解释：本题考查对 TSP 贪心算法的理解(A) (B)选项都是对贪心算法的描述，贪心算法的核心就

13、是：只考虑当前情况下得最优 解。故(A)(B)正确。贪心算法得到的解释可行解，但不一定是最优解，故C)错误。在执 行贪心算法的过程中，会遇到下一步有两个最优选项的情况，所以每次执行贪心算法的最终 解的结果可能是不同的。故(D)正确。详细内容请参考第七章视频“算法，程序与计算系统之灵魂”与第七章课件。下列哪些问题可应用求解TSP的算法，正确的是。(A) 电路板上需要钻n个孔，选择一条最短路径使机器移动并完成所有孔的钻孔工作的 问题(机器在电路板上钻孔的调度问题)；(B) n 个盘子在三个柱子上的移动问题(梵天塔问题或者说汉诺塔问题)；(C) n 座桥， 走过每座桥且仅走过一次的问题(图的遍历问题

14、)；(D) 上 述(A)( B)(C )都可以。答案：A 解释：本题考查对TSP问题抽象的理解求解TSP问题采用的是贪心算法。（A）选项所描述的问题其实就是TSP问题。（B）选项 所描述的问题是梵天塔问题，应该采用的是递归的思想。（C）选项所描述的图的遍历问题, 主要有深度优先搜索，和广度优先搜索两种解决方法，不是贪心算法。综上，（A）选项正 确。详细内容请参考第七章视频“算法，程序与计算系统之灵魂”与第七章课件。关于下列四个数学抽象，说法正确的是。（数学抽象I）城市记为：- - 5，任意两个城市之间的距离记为：IF 问题的解是寻找所有城市的一个访问顺序T=，:L,.，其中一 i,使得mn：

15、，这里假定除t -外, ti tj（ij时）。（数学抽象II）电路元件记为:V=汀-,任意两个元件丁 P i之间的距离记为： 问题的解是寻找所有元件之间的一个访问顺序T=厂L，其中 ，使得I心，这里假定除-1 -外, ti tj（ij时）。（数学抽象III）图的结点记为：V=5匕-.，任意两个结点&匚的边的权值记为：丫， 问题的解是寻找所有结点之间的一个访问顺序T=厂L，其中-卢-使得，这里假定除t | 1 外，ti tj（ij时）。（数学抽象IV）图的结点记为：N = 1,2,，n,任意两个结点i，j的边的权值记为：d 问题的解是寻找所有结点之间的一个访问顺序t=t,t2,.,tn,其中gV,使得min山丄_| 这里假定除t | 1 外, ti tj（ij时）。（A）只有数学抽象丨是TSP问题，数学抽象II和III不是；（B）数学抽象丨和III可以被认为是TSP问题，数学抽象II和IV不是；（C）数学抽象I、II、III和IV都可以被认为是TSP问题