第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)
(1)哥尼斯堡七桥问题的路径能够找到吗？ _____。
(A)一定能够找到；
(B)一定不能找到；(C)不确定能不能找到。
(b)
答案：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)(A)图(d)和图(e)都一定不能找到；
(B)图(d)一定能够找到；图(e)一定不能找到；(C)图(d)一定不能找到；图(e)一定能够找到；(D)图(d)和图(e)都一定能够找到；
(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 解释：
本题考查问题及其数学建模的作用
以上说明都正确，对一个具体问题的求解，可先进行数学建模，将具体问题转化成抽象问题，再进行判断是否有解，若有解则计算，若无解则无需计算。
具体内容参考第七章视频之“数学建模与算法策略设计--算法思想”，第七章课件或查阅欧拉回路相关资料。
(10)哥尼斯堡七桥问题，推而广之就是m个顶点n条边的图的“一笔画”问题，我们可以给出一个算法来求解该问题，即“对河流隔开的m块陆地上建造的n座桥梁，若要找到走遍这n座桥且只许走过每座桥一次的路径”。关于该算法的基本思想，下列说法正确的是_____。
(A)以任何一个顶点为起点，按照图的“边”的指示，找到按该边与该顶点相连的下一个顶点，并标记该边为“已访问”，依次循环，直到所有的边都被访问过为止，便可找到给定问题的解；
(B)以任何一个顶点为起点，按照图的未访问过“边”的指示，找到按该边与该顶点相连的下一个顶点，并标记该边为“已访问”，依次循环，直到所有的边都被访问过为止，便可找到给定问题的解；
(C)首先判断该问题是否有解，若无解，则直接退出；若有解，则以任何一个顶点为起点，按照图的未访问过“边”的指示，找到按该边与该顶点相连的下一个顶点，并标记该边为“已访问”，依次循环，直到所有的边都被访问过为止，便可找到给定问题的解；
(D)首先判断该问题是否有解，若无解，则直接退出；若有解，则选择一个奇数度的顶点为起点，按照图的未访问过“边”的指示，找到按该边与该顶点相连的下一个顶点，并标记该边为“已访问”，依次循环，直到所有的边都被访问过为止，便可找到给定问题的解；
(E)上述都不正确。
答案：D 解释：
本题考查问题及其数学建模的作用
选择（D）根据欧拉回路关系可知，要是一个图形可以一笔画，需要满足：1）图形必须是连通的；2）途中的“奇点”（相连的边的个数为奇数的点）个数是0或2。因此，若有奇点，则起点和终点必须是奇点，若无，则任意，因此（A）（B）（C），因此应该选择D。
具体内容参考第七章视频之“数学建模与算法策略设计--算法思想”，第七章课件或查阅欧拉回路相关资料。
3、背包问题的定义是：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中。背包问题的一个例子：应该选择哪些盒子，才能使价格尽可能地大，而保持重量小于或等于15 kg？其示意图如下：
(1)该背包问题的可能解的数量是_____。
(A)5
(B)10
(C)32
(D)64
答案：C 解释：
本题考查问题及其数学建模的作用
由题意可知，只要可放入背包的状态都算是可能解，可以按背包容量由1到15遍历可能性。答案为（C）32个。
具体内容查阅背包问题相关资料。
(2)假定求解该问题的一种贪心策略是：优先选择能装下盒子中价格最高的，依据该算法策略所得到的解的总价值是_____。
(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 解释：
本题考查问题及其数学建模的作用 由题意可知使用贪心算法，从单位价值最高的开始放入，五个物品单位价值从大到小依次为：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 解释：
本题考查问题及其数学建模的作用
由题意可知使用贪心算法，需要让剩余空间最小，那么可以得到的组合是，12kg+2kg+1kg=15kg，重量得到最大利用，总价值是8，所以选择（A）。
具体内容查阅背包问题相关资料。
(5)使用遍历算法策略所得到的解的总价值是_____。
(A)8
(B)15
(C)14
(D)13
答案：B 解释：
本题考查问题及其数学建模的作用
用遍历算法策略，状态转移方程：f[v]=max{f[v],f[v-c[i]]+w[i]}，即f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值，第i件物品的重量是c[i]，价值是w[i]。“将前i件物品放入容量为v的背包中”这个子问题，若只考虑第i件物品的策略（放或不放），那么就可以转化为一个只牵扯前i-1件物品的问题。如果不放第 i件物品，那么问题就转化为“前i-1件物品放入容量为v的背包中”，价值为f[i-1][v]；如果放第i件物品，那么问题就转化为“前i-1件物品放 入剩下的容量为v-c[i]的背包中”，此时能获得的最大价值就是f [i-1][v-c[i]]再加上通过放入第i件物品获得的价值w[i]。按此方法，可得总价值是15，所以选择（B）。
具体内容查阅背包问题相关资料。
(6)假定有N个物品，其价值分别为V1, V2,..., VN，重量分别为W1, W2,..., WN，背包所能承受的总重量为Wmax，为物品i定义一个决策变量xi，其中xi=1表示选择该物品，xi=0表示不选择该物品。下面哪个描述共同构成了该问题的数学模型_____。
(A)问题的目标函数是max xV；
iii1NiiN(B)问题的目标函数是max xW；
i1(C)问题解所应满足的约束是 xWWiii1NNmax；
(D)问题解所应满足的约束是 xVi1iiWmax；
(E)前述(A)和(C)；
答案：E 解释：
本题考查问题及其数学建模的作用 该问题有两个条件：
1）物品不能超过背包所能承受的重量，即（C）选项： xWWiii1Nmax
2）背包内物品价值最大，即（A）选项目标函数为
max xiVii1N
（B）和（D）选项明显错误，将质量和价值比较。
所以选择（E）。
具体内容查阅背包问题相关资料。
4、TSP-旅行商问题，是一个经典问题，如下图所示，描述为“有n个城市，任何两个城市之间的距离都是确定的，现要求一旅行商从某城市出发必须经过每一个城市且只能在每个城市逗留一次，最后回到原出发城市，问如何事先确定好一条最短的路线使其旅行的费用最少”。围绕TSP，回答下列问题。
(1)关于TSP问题的遍历算法和贪心算法，下列说法正确的是_____。
(A)对TSP问题而言，遍历算法和贪心算法求得的解是一样的，所不同的是贪心算法更快一些，而遍历算法更慢一些；
(B)对TSP问题而言，遍历算法和贪心算法求得的解是一样的，所不同的是遍历算法更快一些，而贪心算法更慢一些；
(C)对TSP问题而言，遍历算法和贪心算法求得的解是不一样的，贪心算法是求近似解，执行更快一些，而遍历算法是求精确解，执行更慢一些；(D)对TSP问题而言，遍历算法和贪心算法求得的解是不一样的，贪心算法是求精确解，执行更快一些，而遍历算法是求近似解，执行更慢一些；
答案：C 解释：
本题考查对贪心算法与遍历算法的简单理解
贪心算法：一定要做当前情况下的最好选择，否则将来可能会后悔，故名“贪心”。如果以A城市为起点，选择最近的下一点，为B城市。以B城市为起点，选择最近的下一个城市，可以选择C或D，以选择D为例。以D为起点，选择最近的下一点，为C城市。最后回到A。整个过程的花费为：14。于是，该贪心算法的解为14。而通过遍历可知，该问题的最优解为A-B-C-D-A，花费为13。可见，贪心算法与遍历算法的解不会总是完全相同。而贪心算法只会做当前情况下最优选择，其时间复杂度为n级别。而遍历则会将各种情况考虑在内，其时间复杂度为（n-1）！级别当城市的数量变多时，遍历算法将会出现组合爆炸。故，相比之下，贪心算法的计算速度更快。所以(C)选项是正确的。
详细内容请参考第七章视频“算法，程序与计算系统之灵魂”与第七章课件。
(2)关于TSP，下列说法不正确的是_____。
(A)TSP问题的一个可能解就是n个城市的一个组合，其中任何两个ti，tj都对应不同的城市。若要求得最优解，则必须对所有的组合，即所有可能解进行比较。
(B)TSP问题的难点是当n值很大时，组合数目非常庞大(组合数目为n!)，以致于计算机不能在有限时间内完成所有的组合；
(C)TSP问题的难点是当n值很大时，组合数目非常庞大(组合数目为n!)，虽如此，计算机仍然能够在有限时间内完成所有的组合；
(D)上述思想--对所有组合进行比较的思想，即是所谓的遍历算法策略，它仅仅对n值很小的TSP问题是能行的。
答案：C 解释：
本题考查对TSP组合优化问题的理解
对所有组合进行比较的思想，即所谓的遍历算法策略，其组合数目为n!。2001年解决了德国15112个城市的TSP问题，使用了美国Rice大学和普林斯顿大学之间互连的、速度为500MHz 的Compaq EV6 Alpha 处理器组成的110台计算机，所有计算机花费的时间之和为22.6年。由此可见，当n巨大时，用遍历算法解决TSP问题是不现实的。所以(C)选项错误。
详细内容请参考第七章视频“算法，程序与计算系统之灵魂”与第七章课件。
(3)关于TSP的贪心算法的求解思想，下列说法不正确的是_____。
(A)无需对所有组合(所有可能解)进行比较，而仅需依照某种办法确定其中的一个组合即可，该组合不一定是最优解，但却是一个较优解或次优解；
(B)在确定一个组合时，tk+1是与tk相连接的城市中与tk距离最短的城市，即tk+1是由tk确定的，与tk连接的若干城市中的特性最优的城市；
(C)贪心算法确定的路径，是由局部最优(即tk+1在tk看来是最优的)组合起来的路径，该路径从全局角度也一定是最优的；
(D)对一个具体的TSP问题，每次执行贪心算法，所求得的最终解可能是不同的。
答案：C 解释：
本题考查对TSP贪心算法的理解
（A）(B)选项都是对贪心算法的描述，贪心算法的核心就是：只考虑当前情况下得最优解。故（A）（B）正确。贪心算法得到的解释可行解，但不一定是最优解，故(C)错误。在执行贪心算法的过程中，会遇到下一步有两个最优选项的情况，所以每次执行贪心算法的最终解的结果可能是不同的。故(D)正确。
详细内容请参考第七章视频“算法，程序与计算系统之灵魂”与第七章课件。
(4)下列哪些问题可应用求解TSP的算法，正确的是_____。
(A)电路板上需要钻n个孔，选择一条最短路径使机器移动并完成所有孔的钻孔工作的问题(机器在电路板上钻孔的调度问题)；
(B)n个盘子在三个柱子上的移动问题(梵天塔问题或者说汉诺塔问题)；(C)n座桥，走过每座桥且仅走过一次的问题(图的遍历问题)；
(D)上述(A)(B)(C)都可以。
答案：A 解释：
本题考查对TSP问题抽象的理解
求解TSP问题采用的是贪心算法。(A)选项所描述的问题其实就是TSP问题。（B）选项所描述的问题是梵天塔问题，应该采用的是递归的思想。（C）选项所描述的图的遍历问题，主要有深度优先搜索，和广度优先搜索两种解决方法，不是贪心算法。综上，（A）选项正确。
详细内容请参考第七章视频“算法，程序与计算系统之灵魂”与第七章课件。
(5)关于下列四个数学抽象，说法正确的是_____。
(数学抽象I)城市记为：V={v1,v2,…,vn}，任意两个城市vi,vj∈V之间的距离记为：dvivj，问题的解是寻找所有城市的一个访问顺序T={t1,t2,…,tn}，其中ti∈V，使得min ni=1dtiti+1，这里假定除tn+1=t1外，ti tj(ij时)。
(数学抽象II)电路元件记为：V={v1,v2,…,vn}，任意两个元件vi,vj∈V之间的距离记为：dvivj，问题的解是寻找所有元件之间的一个访问顺序T={t1,t2,…,tn}，其中ti∈V，使得min ni=1dtiti+1，这里假定除tn+1=t1外，ti tj(ij时)。
(数学抽象III)图的结点记为：V={v1,v2,…,vn}，任意两个结点vi,vj∈V的边的权值记为：dvivj，问题的解是寻找所有结点之间的一个访问顺序T={t1,t2,…,tn}，其中ti∈V，使得min ni=1dtiti+1，这里假定除tn+1=t1外，ti tj(ij时)。
(数学抽象IV)图的结点记为：N = {1,2，…，n}，任意两个结点i，j的边的权值记为：dij，问题的解是寻找所有结点之间的一个访问顺序t={t1,t2,…,tn}，其中tiV，使得min min ni=1dtiti+1，这里假定除tn+1=t1外，ti tj(ij时)。
(A)只有数学抽象I是TSP问题，数学抽象II和III不是；
(B)数学抽象I和III可以被认为是TSP问题，数学抽象II和IV不是；(C)数学抽象I、II、III和IV都可以被认为是TSP问题；(D)上述说法都不正确。
答案：C 解释：
本题考查对TSP问题抽象的理解
I就是对最原始的TSP问题的抽象描述。II也是对TSP问题的描述，只是将城市换成了电子元件。III和IV是对同一问题的不同表述罢了，都是TSP问题，只是将城市换为了图。四个数学抽象都可以被认为是TSP问题。故选项（C）正确。
详细内容请参考第七章视频“算法，程序与计算系统之灵魂”与第七章课件。
5、数据结构是算法设计的重要步骤，针对不同问题的算法设计应该选择适当的数据结构，不同的数据结构会使得解决问题的算法的性能有所不同。回答下列问题。(1)关于数据结构，下列说法不正确的是_____。
(A)数据结构是问题域数学模型中各种数据的存储结构；(B)数据结构是将逻辑上有一定语义关系的数据，转换成计算机可以存储和处理的变量，便于算法和程序进行处理；
(C)数据结构是将具有一定语义关系的变量进行命名，以便隐藏数据结构内部的操作细节，便于算法按逻辑语义通过操控该名字来操控该数据结构；
(D)数据结构包含了数据的逻辑结构、存储结构及其操作；
(E)上述说法有不正确的。
答案：E 解释：
本题考查对数据结构的理解
数据结构是数据的逻辑结构、存储结构及其操作的总称，它提供了问题求解/算法的数据操纵机制。(A)(B)(C)(D)的说法都没有问题。所以（E）是不正确的。
详细内容请参考第七章视频“算法，程序与计算系统之灵魂”与第七章课件。
(2)关于数据结构，下列说法不正确的是______________？
(A)数据结构由逻辑结构、存储结构及运算3部分组成；(B)存储结构定义了数据在存储器中的存储方式；(C)向量使用顺序存储结构，并借助元素在存储器中的相对位置来表示数据元素的逻辑关系；
(D)在树结构中，指针用于表达元素之间的逻辑关系——父子关系，每个元素的指针指向其父节点，因此一个元素可以有一个或多个指针。
答案：D 解释：
本题考查对数据结构的理解
数据结构是数据的逻辑结构、存储结构及其操作的总称。（A）正确。数据的存储结构也就是在反映数据逻辑关系的原则下，数据在存储器中的存储方式。（B）正确。向量确实是使用顺序存储结构，并且借助元素在存储器中的相对位置来表示数据元素的逻辑关系的，（C）正确。在树结构中，如果每个元素的指针都指向其父节点，那么每个元素只能有一个指针。因为每个元素只有一个父亲。故（D）错误。
详细内容请参考第七章视频“算法，程序与计算系统之灵魂”与第七章课件。
6.数据通常要存储在存储器中，存储器是按地址访问的存储单元的集合，因此存储器可被认为是按线性方式组织数据。数组是高级语言中经常使用的一种数据结构，其按照不同的下标可访问数组的不同的元素。如下图所示：
(1)关于数组和存储器，下列说法不正确的是_____。
(A)和存储器一样，数组是按线性方式组织数据；
(B)和存储器一样，一维数组是按线性方式组织数据，一个数据元素需要一个存储单元来存储，一个下标即相当于一个存储单元的地址；
(C)和存储器一样，一维数组是按线性方式组织数据，一个数据元素需要一个或多个存储单元来存储，一个下标即相当于一个存储单元的地址；
(D)和存储器一样，一维数组是按线性方式组织数据，一个数据元素需要一个或多个存储单元来存储，一个下标即相当于一个或多个存储单元的地址；
答案：C 解释：
本题考查对存储器和数组的理解。数组是按照线性方式组织数据的。当一个数据元素需要多个存储单元存储时，一个下标代表的就是多个存储单元的地址，所以(C)的说法不准确。其余说法都对。
详细内容请参考第七章视频“算法，程序与计算系统之灵魂”与第七章课件。
(2)请对照上图的左子图和右子图来观察，右子图的二维数组是按左图的形式存储在存储器中。则D[4][2]元素所对应的存储单元的存储地址为_____。
(A)00000000 00000101；
(B)00000000 00001000；
(C)00000000 00001010；
(D)上述都不正确；
答案：B 解释：
本题考查对存储器和数组的理解。
图中，二维数组中，D[4][2]对应的元素是80，而且是第二个80.在存储器中，找到第二个80的位置，其所对应的地址为：00000000 00001000；（B）正确。
详细内容请参考第七章视频“算法，程序与计算系统之灵魂”与第七章课件。
(3)请参照上图的左子图和右子图来观察，右子图的二维数组是按左图的形式存储在存储器中。则D[i][j]元素，与对应存储单元的存储地址的转换关系正确的为_____。
(A)D[i][j]元素的存储地址=数组的起始地址+((i-1)*每行的列数+j-1)*单一元素占用存储单元的数目；
(B)D[i][j]元素的存储地址=数组的起始地址+(i-1)*每行的列数+j-1；此公式在任何情况下都正确；
(C)D[i][j]元素的存储地址=数组的起始地址+((j-1)*每行的列数+i-1)*单一元素占用存储单元的数目；
(D)D[i][j]元素的存储地址=数组的起始地址+(j-1)*每行的列数+i-1；此公式在任何情况下都正确；
答案：A 解释：
本题考查对存储器和二维数组的理解。
记住数组的下标是从0开始编号的。((i-1)*每行的列数+j-1)得到二维数组中，所求的元素的下标偏移量。((i-1)*每行的列数+j-1)*单一元素占用存储单元的数目得到地址的偏移量。再加上数组的起始地址，便可得到所求元素的地址。（A）正确。
详细内容请参考第七章视频“算法，程序与计算系统之灵魂”与第七章课件。
7.“树”是一种典型的数据结构，在很多算法中都应用树来组织相关的数据。树是组织层次型数据的一种存储结构，它将每一个数据称为一个数据元素。见下图I.示意，采用三个数组来存储树型数据，一个数组TreeElement[]存放数据元素本身，一个数组LeftPointer[]存放该数据元素的左侧子元素的存放地址(简称为左指针)，另一个数组RightPointer[]存放该数据元素的右侧子元素的存放地址(简称为右指针)。参照图I.，回答下列问题。
图I.(1)关于“树”这种数据结构，下列说法不正确的是_____。
(A)“树”既需要存储数据元素本身即数据，还需要存储数据元素之间的关系；
(B)“树”可以采用两个数组来组织树型数据，其中一个数组用于存储数据元素本身，另一个数组用于存储与该数据元素发生某种关系的另一个数据元素的存储位置；
(C)“树”可以采用三个数组来组织树型数据，其中一个数组用于存储数据元素本身，另外两个数组用于存储与该数据元素发生某种关系的另外两个数据元素的存储位置；
(D)不仅可以采用(B)(C)的方式组织树型数据，还有其他的方式；
(E)上述说法有不正确的。
答案：E 解释： 本题考查对树结构的理解。
“树”既需要存储数据元素本身即数据，还需要存储数据元素之间的关系。（A）的说法没有问题。用两个数组组织树形数据时，一个数组存放数据元素，另一个数组存储对应的父元素。用三个数组组织树形数据时，一个数组存放数据元素，剩下的两个数据，一个存放对应的左儿子，一个存放对应的右儿子。组织树形数据时，可以把每个元素当做一个节点，通过指针来指向其儿子。故（B）（C）（D）正确。（E）不正确。
详细内容请参考第七章视频“算法，程序与计算系统之灵魂”与第七章课件。
(2)参照上图(I)，下列说法不正确的是_____。
(A)当数据元素不发生变化，而只是数据元素之间的关系发生变化时，可以通过调整数据元素对应的左指针数组或右指针数组中的值来完成；
(B)当数据元素不发生变化，而只是数据元素之间的关系发生变化时，既需要调整数据元素本身，又需要调整其对应的左指针数组或右指针数组中的值来完成；
(C)相同的数据元素，不同的左指针和右指针可以反映数据元素之间不同的关系；
(D)图(a)说明，一个数据元素最多只能有两个子元素，一个是左子元素，一个是右子元素；
(E)上述说法有不正确的。
答案：B 解释：
本题考查对树结构的理解。
“树”既需要存储数据元素本身即数据，还需要存储数据元素之间的关系。当数据元素不发生变化，而只是数据元素之间的关系发生变化时，数据本身是不需要调整的。(B)错误。其余说法均正确。
详细内容请参考第七章视频“算法，程序与计算系统之灵魂”与第七章课件。
(3)上图(I)表示的数据的逻辑关系，下列正确的是_____。
(A)图II.(a)；(B)图II.(b)；
(C)图II.(c)；
(D)图II.(d)；
图II.答案：D 解释：
本题考查对树结构的理解。
第一个元素值为100。其左指针指向的存储单元的内容为地址：00000000 00000010。该地址存储的数据为50。故第一个元素100的左儿子为50。一次类推，可以画出（d）中的树。故（D）正确。
详细内容请参考第七章视频“算法，程序与计算系统之灵魂”与第七章课件。
(4)如想使图(I)，改变为存储下图III所示的逻辑关系，操作正确的是_____。
图III.(A)将00000000 00001000号存储单元的值修改00000000 01101110(即十进制的110)；(B)将00000000 00011010号存储单元的值修改为00000000 00000111；
(C)将00000000 00010001号存储单元的值修改为00000000 00000000(即Null)；
(D)将00000000 00010011号存储单元的值修改为00000000 00001000；(E)上述(A)(B)(C)(D)都需要正确完成；
答案：E 解释：
本题考查对树结构的理解。
想要得到题目要求，则需要改变的是100的右儿子的值。首先，增加110这个元素。这是（A）的操作。很容易知道，110这个元素对应的左指针指向00000000 00010001，将该单元的存储内容改为NULL，增加了110元素的左儿子为空。这是（C）的操作。然后将100元素的右指针指向110，这是（D）的操作。最后，将110的右指针指向150。这是（C）的操作。至此，整个过程完成。所以，（E）正确。
详细内容请参考第七章视频“算法，程序与计算系统之灵魂”与第七章课件。
(5)如想使图(I)，改变为存储下图IV所示的逻辑关系，下列四步操作都是需要的，但有些操作的内容却是不正确的。不正确的是_____。
图IV.(A)将00000000 00001000号存储单元的值修改为00000000 01010101；(B)将00000000 00010010号存储单元的值修改为00000000 00000010；
(C)将00000000 00011010号存储单元的值修改为00000000 00000000(即Null)；
(D)将00000000 00001010号存储单元的值修改为00000000 00001000；
答案：B 解释：
本题考查对树结构的理解。
(A)的操作是在存储表中增加85这个元素。（C）的操作是将85的右儿子设为NULL。（D）的操作是将100的左指针指向85元素的地址。（B）是对00000000 00010010地址进行操作。而改地址在整个过程中，通过其它选项来看，不会有涉及到（B）中的地址。故（B）不正确。
详细内容请参考第七章视频“算法，程序与计算系统之灵魂”与第七章课件。
8.堆栈(stack)是一种特殊的串行形式的数据结构，其特殊支出在于只能允许在链结串行或阵列的一端（称为堆栈顶端指针，top）进行加入数据(push)或输出数据(pop)的运算。其示意图如下所示。
(1)有关堆栈数据结构的说法，不正确的是_____。
(A)堆栈按照先进先出（FIFO, First In First Out）的原理运作；(B)堆栈按照后进先出（LIFO, Last In First Out）的原理运作；(C)堆栈可以使用顺序存储结构作为存储结构；(D)堆栈可以使用链式存储结构作为存储结构。
答案：A 解释：
本题考查对堆栈结构的理解。
在堆栈中，先进栈的元素被保存在堆栈下部。在弹出元素时，栈顶的元素先被弹出。故堆栈运行的原理是后进先出。（A）不正确，（B）正确。堆栈可以使顺序存储结构和链式结构来实现。（C）（D）正确。
详细内容请参考第七章视频“算法，程序与计算系统之灵魂”与第七章课件。
(2)有关堆栈数据结构的基本运算，说法不正确的是_____。
(A)推入是将数据放入堆栈的顶端，堆栈顶端指针top加一；(B)弹出是将堆栈顶端的数据取出，堆栈顶端指针top减一；(C)如果堆栈顶端指针top为0，则堆栈为空；
(D)如果是固定长度的堆栈，当堆栈顶端指针top与长度相等时，堆栈是满的。(E)上述说法有不正确的；
答案：E 解释：
本题考查对堆栈结构的理解。
堆栈只有一个出口，那便是栈顶。推入数据，是在堆栈的顶端推入，数据个数增加了一，栈顶指针加一，（A）正确。弹出数据，也是在堆栈的顶端弹出，数据个数减一，栈顶指针减一，（B）正确。栈顶指针的值代表了堆栈中数据的个数。栈顶指针为0，堆栈为空。栈顶指针为堆栈的固定长度，则堆栈是满的。（C）(D)均正确。故（E）的说法不正确。
详细内容请参考第七章视频“算法，程序与计算系统之灵魂”与第七章课件。
(3)假定当前堆栈顶端指针top=10，欲将栈底的元素取出，其他的元素仍然保持在栈中，则需要进行___ ___次弹出操作，____ ____次推入操作。
(A)1，1
(B)2，1
(C)10，9
(D)10，0
(E)11，8
答案：C 解释：
本题考查对堆栈结构的理解。
堆栈只有栈顶一个数据进出口。栈顶指针的值代表了堆栈中数据的个数。将栈底的元素弹出，则首先必须要使堆栈变空，需要连续十次弹出操作。再将其他9个元素压入堆栈，需要9次推入操作。故（C）选项正确。
详细内容请参考第七章视频“算法，程序与计算系统之灵魂”与第七章课件。
9.程序流程图是表达算法控制结构或者说算法步骤的重要方法。回答下列问题：(1)观察下图I.，没有错误的流程图为_________。
图I.(A)流程图(a)无错误；(B)流程图(b)无错误；
(C)流程图(c)无错误；
(D)没有无错误的流程图；
答案：D 解释：
本题考查流程图的知识点；
图(a)中，在进行“循环控制条件成立？”这一判断时，不应该使用方向，而应该用菱形判断，所以流程图(a)错误；图(b)中，当判断循环控制条件成立为是后，修改部分的返回箭头不应该指向初始化部分，而应该返回判断“循环控制条件成立？”，所以流程图(b)错误；图(c)中，有两处错误，一是在判断“循环控制条件成立？”时，没有标明两个箭头方向是“是”还是“否”，二是同图(b)一样，返回箭头不应该标在初始化部分，所以流程图(c)错误；综上所述，三个图当中都有错误。详细内容请参考第七章视频“算法设计---算法思想的精确表达(II)”与第七章课件。
(2)观察下图II.，该流程图中存在错误，下列说法最完整准确的是_________。
图II.(A)条件判断框不应为矩形，而应为菱形或六角形；(B)条件判断框中引出的箭头应标记Yes(是)或No(否)，表明条件满足或不满足时的程序走向；
(C)仅仅包含错误(A)和(B)；
(D)除错误(A)和(B)外，还包括其他错误；
答案：D 解释：
本题考查流程图的知识点；
条件判断框“循环控制条件成立？”应该为菱形或六角形，不是矩形，所以A正确；同时条件判断框中引出的箭头要标记是或否，表明程序的走向，所以B也正确；根据流程图，在判断控制条件是否成立时，当条件为“是”时，返回部分不应该是初始化部分，而应该是“需循环执行的规则或语句”，所以该图中不止AB两个错误，正确答案选D；
详细内容请参考第七章视频“算法设计---算法思想的精确表达(II)”与第七章课件。
10.阅读下列算法，回答：
Start of the algorithm(算法开始)(1)输入N的值；
(2)设 i 的值为1；
(3)如果 i
(5)计算 i+1，并将结果赋给i；
(6)返回到第3步继续执行；
(7)输出sum的结果。
End of the algorithm(算法结束)
答案：B 解释：
本题考查步骤描述法 ；
在上述步骤中，主要欠缺的是程序的初始化，虽然有将i的初始值设为1，但sum的初始值确忽略了，这样，没办法正确计算sum=1+2+3….+N，应该把sum初始值设为0；
详细内容请参考第七章视频“算法设计---算法思想的精确表达(II)”与第七章课件。
11.阅读下列算法，回答：
Start of the algorithm(算法开始)(1)N=10；
(2)i=2；sum=2；
(3)如果 i
(4)如果i / 2 ==0 则转到第(6)步执行；(5)sum = sum + i；
(6)i = i+1；
(7)返回到第(3)步继续执行；
(8)输出sum的结果。
End of the algorithm(算法结束)上述算法_________。
(A)能够正确地计算sum=1+2+3+4+„+N；
(B)不能正确地计算sum=1+2+3+4+„+N；
答案：B 解释：
本题考查步骤叙述法；由题意，可画出如图所示的流程图： 算法执行的结果为_________。
(A)24；(B)26；(C)55；
(D)45；(E)46；
所以，当i为奇数时，sum=sum+i；i=3，sum=5； i=5，sum=10；i=7，sum=17；i=9，sum=26；综上所述，结果为26，选B；具体内容请参考课堂视频“算法设计---算法思想的精确表达(III)”和第七章课件；
12.TSP算法流程图如下图I.示意，回答下列问题：
图I.(1)最内层循环(L变量控制的循环)的作用是_________。
(A)用于判断某个城市是否是已访问过的城市；(B)用于寻找距当前城市距离最近的城市；(C)用于完整地产生一个路径；
(D)上述都不是；
答案：A 解释：
本题考查学生是否能读懂流程图以及TSP流程；
图中最内层循环，L从1至I-1, 循环判断第K个城市是否是已访问过的城市，如是则不参加最小距离的比较；所以，正确答案选A；
具体内容请参考课堂视频“算法设计---算法思想的精确表达(III)”和第七章课件；
(2)中层循环(K变量控制的循环)的作用是_________。
(A)用于判断某个城市是否是已访问过的城市；(B)用于寻找距当前城市距离最近的城市；(C)用于完整地产生一个路径；
(D)上述都不是；
答案：B 解释：
本题考查学生是否能读懂流程图以及TSP流程；
图中中层循环，K从第2个城市至第N个城市循环, 判断D[K, S[I-1]]是否是最小值，j记录了最小距离的城市号K；所以，正确答案选B；
具体内容请参考课堂视频“算法设计---算法思想的精确表达(III)”和第七章课件；
(3)外层循环(I变量控制的循环)的作用是_________。
(A)用于判断某个城市是否是已访问过的城市；(B)用于寻找距当前城市距离最近的城市；(C)用于完整地产生一个路径；
(D)上述都不是；
答案：C 解释：
本题考查学生是否能读懂流程图以及TSP流程；
图中外层循环，I从2至N循环；I-1个城市已访问过，正在找与第I-1个城市最近距离的城市；已访问过的城市号存储在S[]中；所以，正确答案选C；
具体内容请参考课堂视频“算法设计---算法思想的精确表达(III)”和第七章课件；
13.一般而言，算法设计完成后，需要进行算法的模拟与分析。关于算法的模拟与分析回答下列问题：
(1)通常从哪些方面，进行算法的模拟与分析？_________。
(A)算法的正确性问题，即一个算法求得的解是满足问题约束的正确的解吗？
(B)算法的效果评价问题，即算法输出的是最优解还是可行解，其可行解与最优解的偏差有多大？
(C)算法的时间效率问题(时间复杂性)，即算法执行所需要的时间是多少？(D)算法的空间效率问题(空间复杂性)，即算法执性所需要的空间是多少？
(E)上述全部。
答案：E 解释：
本题考查算法分析和算法复杂性；
当对一个算法进行模拟与分析时，有以下几个方面要判断：（1）问题求解的过程、方法——算法是正确的吗？算法的输出是问题的解吗？（2）算法的输出是最优解还是可行解？如果是可行解，与最优解的偏差多大？（3）算法获得结果的时间有多长?即分为时间复杂性和空间复杂性；所以，答案应选E；
具体内容请参考课堂视频“高级问题初探: 算法分析与计算复杂性”和第七章课件；
(2)算法的时间复杂性，可以表达为关于问题规模n的一个函数T(n)，T(n)可以用大O表示法来处理。问T(n)=O(f(n))是什么意思？正确的是_________。
(A)T(n)是关于f(n)的一个函数；(B)T(n)是与f(n)同数量级的函数；
(C)T(n)是将函数f(n)代入O(x)中所形成的新函数；(D)T(n)是依据f(n)计算出来的；
答案：B 解释：
本题考查时间复杂性，和大“O”记法； 时间复杂性是指如果一个问题的规模是n，解这一问题的某一算法所需要的时间为T(n)，它是n的某一函数，T(n)称为这一算法的“时间复杂性”。“大O记法”：基本参数 n表示问题实例的规模，把复杂性或运行时间表达为n的函数。“O”表示量级(order)，允许使用“=”代替“≈”，如n2+n+1 =Ο(n2)，所以正确答案选B；
具体内容请参考课堂视频“高级问题初探: 算法分析与计算复杂性”和第七章课件；
(3)算法的时间复杂性T(n)，可以通过计算算法基本语句的执行次数来获得。分析下列程序的时间复杂性。
(10)K = 0；
(20)I = 2；(30)While(I
K = K + I；
(50)I = I + 2；} 该程序时间复杂性表达正确的是_________。
(A)O(n)；(B)O(1)；(C)O(n2)；(D)O(n!)；
答案：B 解释：
本题考查时间复杂性，和大“O”记法；具体分析如下： K = 0； 1次 I = 2；
1次
While(I
8次 {
K = K + I； 8次 I = I + 2； 8次 } T(n)=1+1+8 ×3= O(1)，所以答案选B；
具体内容请参考课堂视频“高级问题初探: 算法分析与计算复杂性”和第七章课件；
(4)算法的时间复杂性T(n)，可以通过计算算法基本语句的执行次数来获得。分析下列程序的时间复杂性。
(10)sum=0；
(20)For(i=1;i
sum=sum+1；
该程序时间复杂性表达正确的是_________。
(A)O(n)；(B)O(n2)；(C)O(n3)；
(D)上述都不对；
答案：C 解释：
本题考查时间复杂性，和大“O”记法；具体分析如下：(10)sum=0； 1次(20)For(i=1;i
n2次(40)For(k=1;k
n3次(50)
sum=sum+1； n3次
T(n)= 2 n3 + n2 + n + 1 = O(n3)，所以正确答案选C；
具体内容请参考课堂视频“高级问题初探: 算法分析与计算复杂性”和第七章课件；
(5)算法的时间复杂性T(n)，可以通过计算算法基本语句的执行次数来获得。分析下列程序的时间复杂性。
(10)sum=0；
(20)For(i=1;i
sum=sum+1；
该程序时间复杂性表达正确的是_________。
(A)O(n)；(B)O(n2)；(C)O(n3)；
(D)上述都不对；
答案：B 解释：
本题考查时间复杂性，和大“O”记法；具体分析如下：(10)sum=0； 1次(20)For(i=1;i
n2次(50)
sum=sum+1；n2次
T(n)= 11n2 + n + 1 = O(n2)，所以正确答案选B；
具体内容请参考课堂视频“高级问题初探: 算法分析与计算复杂性”和第七章课件；
(6)阅读下面的程序，其时间复杂度为_________? A.O(1)B.O(n)C.O(n2)
D.O(n*log n)
int index = 5;int condition=1;if(condition==1)then
index++;else
index--；
for i = 1 to 100
for j = 1 to 200
index=index+2;
答案：A 解释：
本题考查时间复杂性，和大“O”记法；具体分析如下：
int index = 5;
1次 int condition=1;
1次 if(condition==1)then 1次
index++;
1次
else
index--；
for i = 1 to 100
100次
for j = 1 to 200
200×100次
index=index+2;
200×100次
所以T(n)=O(1)，正确答案选A；
具体内容请参考课堂视频“高级问题初探: 算法分析与计算复杂性”和第七章课件；(7)为什么要评估算法的复杂性？下列说法不正确的是_________。
(A)当算法的时间复杂性量级为多项式函数时，计算机是能够完成计算的；
(B)当算法的时间复杂性量级为非多项式函数时，如指数函数、阶乘函数时，计算机是不能够完成计算的；
(C)当算法的时间复杂性量级为非多项式函数时，如指数函数、阶乘函数时，对于大规模问题，计算机是不能够完成计算的；
(D)上述说法有不正确的；
答案：B 解释：
本题考查算法分析与计算复杂性；
当算法的时间复杂度的表示函数是一个多项式时，如O(n2)时，则计算机对于大规模问题是可以处理的。当算法的时间复杂度是用指数函数表示时，如O(2n)，当n很大（如10000）时计算机是无法处理的，在计算复杂性中将这一类问题被称为难解性问题。所以对于B的表达，只有当n很大时，属于大规模问题时，计算机才不能完成，表达不精确，所以正确答案为B；
具体内容请参考课堂视频“高级问题初探: 算法分析与计算复杂性”和第七章课件；
(*8)算法的时间复杂性T(n)，可以通过评估算法基本语句的执行次数来获得。分析下列算法的时间复杂性。
Start of the algorithm(算法开始)(1)输入结点的数目n；
(2)当前最短路径Path设为空，当前最短距离Dtemp设为最大值；
注：一个路径是n个结点的一个组合，任何一个结点在路经中不能重复出现
(3)组合一条新路径NewPath并计算该路径的距离D；
(4)如果D
(5)如果所有路径组合完毕，则结束；否则转第(3)步继续执行；
(6)输出Path及Dtemp；
End of the algorithm(算法结束)
该算法的时间复杂性表达正确的是_________。
(A)O(3n)；(B)O(n2)；(C)O(n3)；(D)O(n!)；
(E)上述都不对；
答案：D 解释：
本题考查时间复杂性，和大“O”记法；
由以上步骤可知，由于输入结点的数目为n，总共有n！种组合方式，所以时间复杂性应为O(n!)；正确答案选D;具体内容请参考课堂视频“高级问题初探: 算法分析与计算复杂性”和第七章课件；
(*9)分析下列算法的时间复杂性。
Start of the Algorithm(1)S[1]=1;Sum=0;初始化距离数组D[n][n];
/*I层的循环，即下列步骤为每次找出一个城市，I从2到n，即从找出第2个城市一直到找出第n个城市
(2)I=2;/*K层的循环，即下列步骤为从所有未访问过的城市中查找距离S[I-1]最近的城市j，K依然从2到n寻找
(3)K=2;(4)将Dtemp设为一个大数(比所有两个城市之间的距离都大)/*L层的循环，即下列步骤为判断一个城市是否已被访问过，如果已被访问，则跳过该城市，寻找新的城市，L从1到I-1，因为已经有I-1个城市被访问过。
(5)L=1；
(6)如果S[L]==K，转步骤(10)；
(7)L=L+1；
(8)如果L
(9)如果D[K,S[I-1]]
(11)如果K
(12)S[I]=j;(13)Sum=Sum+Dtemp;(14)I=I+1;(15)如果I
(16)Sum=Sum+D[1, j]；(17)逐个输出S[N]中的全部元素;(18)输出Sum。
End of the Algorithm 该算法的时间复杂性表达正确的是_________。
(A)O(3n)；(B)O(n2)；(C)O(n3)；(D)O(n!)；
(E)上述都不对；
答案：C 解释：
本题考查TSP算法和时间复杂性；
TSP问题贪心算法的复杂性：粗略看是一个关于n的三重循环，即复杂度为n3级别。所以时间复杂度是O(n3)，正确答案选C；
具体内容请参考课堂视频“高级问题初探: 算法分析与计算复杂性”和第七章课件； 14.关于算法类问题的基本求解步骤，回答下列问题：(1)下列说法不正确的是_________。
(A)算法类问题求解首先要进行数学建模，即用数学语言对问题进行抽象；
(B)一个问题，进行了数学建模后，可以通过模型的一些性质的分析判断该问题是否有解；在有解的情况下，再设计算法进行求解，否则则可能做的是无用功！
(C)一个问题，进行了数学建模后，可以依据数学的一些求解方法，设计出让计算机求解的算法。
(D)一个问题，虽然进行了数学建模但可以不依据数学求解方法，设计出让计算机求解的算法；
(E)上述说法有不正确的。
答案：E 解释：
本题考查算法问题求解的基本步骤；
求解一个算法问题，首先要进行数学建模，用数学语言对问题进行抽象，A正确；进行数学建模后，要判断该问题是否有解，所以B也正确；之后要根据数学模型，设计出求解的算法，C正确；对于一个数学模型，我们可以用不同的数学方法设计出不同的解法，所以D也正确；综上所述，正确答案选E；
具体内容请参考第七章所有视频和课件；
(2)对于算法类问题求解，下列说法正确的是_________。
(A)一般而言，算法类问题求解包括数学建模、算法策略设计、算法的数据结构与控制结构设计三个基本步骤；
(B)一般而言，算法类问题求解包括数学建模、算法策略设计、算法的数据结构与控制结构设计、算法的正确性与复杂性分析四个基本步骤；
(C)一般而言，算法类问题求解包括数学建模、算法策略设计、算法的数据结构与控制结构设计、算法的程序实现、算法的正确性与复杂性分析五个基本步骤；
(D)上述说法都正确。
答案：C 解释：
本题考查算法问题求解的基本步骤；
对于算法类问题求解主要包括数学建模、算法策略设计、算法的数据结构与控制结构设计、算法的程序实现、算法的正确性与复杂性分析五个基本步骤，所以C正确；
具体内容请参考课堂视频“算法与算法类问题求解”和第七章课件；
《算法——程序的“灵魂”》观课感听了山东青岛九中李志杰老师的《算法——程序的“灵魂”》，颇有收获。本节内容是第二章的起始章节，介绍了算法的概念和算法的描述方法。是今......
刀豆文库小编为你整合推荐3篇《算法——程序的“灵魂”》观课感，也许这些就是您需要的文章，但愿刀豆文库能带给您一些学习、工作上的帮助。......
智能计算的经典算法解析论文本文是由上传的：智能计算几种经典算法解析。智能计算几种经典算法解析 智能计算几种经典算法解析 智能计算几种经典算法解析论文关键词:智能算法......
刀豆文库小编为你整合推荐3篇智能计算的经典算法解析论文，也许这些就是您需要的文章，但愿刀豆文库能带给您一些学习、工作上的帮助。......
刀豆文库小编为你整合推荐5篇小升初英语练习题与答案解析，也许这些就是您需要的文章，但愿刀豆文库能带给您一些学习、工作上的帮助。......
