不参加最小距离的比较；所以，正确答案选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)；
(C)O(n3)；
(D)上述都不对；
答案：B 解释：
本题考查时间复杂性，和大“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<=5; k++) 5 n2次 (50) sum=sum+1； 5 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; 具体内容请参考课堂视频“高级问题初探: 算法分析与计算复杂性”和第七章课件；