(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正确； 具体内容请参考课堂视频“算法与算法类问题求解”和第七章课件；