发布时间 : 星期日 文章第7章算法程序与计算系统之灵魂练习题答案解析更新完毕开始阅读
图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<=8)
(40) { 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) 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<=n; i++) (30) For(j=1; j<=n; j++) (40) For(k=1; k<=j; k++) (50) sum=sum+1；
该程序时间复杂性表达正确的是_________。
(A)O(n)； (B)O(n2)； (C)O(n3)；
(D)上述都不对；
答案：C 解释：
本题考查时间复杂性，和大“O”记法；具体分析如下： (10) sum=0； 1次 (20) For(i=1; i<=n; i++) n次 (30) For(j=1; j<=n; j++) n2次 (40) For(k=1; k<=j; 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<=n; i++) (30) For(j=1; j<=n; j++) (40) For(k=1; k<=5; k++) (50) sum=sum+1；
该程序时间复杂性表达正确的是_________。
(A)O(n)； (B)O(n2)；