(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; 具体内容请参考课堂视频“高级问题初探: 算法分析与计算复杂性”和第七章课件； (*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<=N，转步骤(5)。 /*K层的循环结束 (12) S[I]=j; (13) Sum=Sum+Dtemp; (14) I=I+1; (15) 如果I<=N，转步骤(3)，否则，转步骤(16); /*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正确； 具体内容请参考课堂视频“算法与算法类问题求解”和第七章课件；