大学计算机计算思维导论（哈尔滨工业大学）2023章节测试答案超星尔雅

14

分析下列算法的时间复杂性。

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<I，转步骤(6)；

/*L层的循环结束

(9) 如果D[K,S[I-1]]<Dtemp，j=K，Dtemp＝D[K,S[I-1]]；

(10) K=K+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

该算法的时间复杂性表达正确的是_________。B

A、O(3n)

B、O(n2)

C、O(n3)

D、O(n!)

15

对于算法类问题求解，下列说法正确的是_________。

我的答案：一般而言，算法类问题求解包括数学建模、算法策略设计、算法的数据结构与控制结构设计、算法的程序实现、算法的正确性与复杂性分析五个基本步骤

A、一般而言，算法类问题求解包括数学建模、算法策略设计、算法的数据结构与控制结构设计三个基本步骤

B、一般而言，算法类问题求解包括数学建模、算法策略设计、算法的数据结构与控制结构设计、算法的正确性与复杂性分析四个基本步骤

C、一般而言，算法类问题求解包括数学建模、算法策略设计、算法的数据结构与控制结构设计、算法的程序实现、算法的正确性与复杂性分析五个基本步骤

D、上述说法都正确

16

关于算法的命题，下列说法正确的是_____。ACD

A、算法规定了任务执行/问题求解的一系列、有限的步骤

B、算法所规定的计算/处理步骤是有限的，但算法实际执行的计算/处理步骤可以是无限的

C、算法可以没有输入，但必须有输出

D、算法的每一个步骤必须确切地定义，且其运算和操作必须相当基本，可以由机器自动完成

17

关于算法与程序、计算机语言之间的关系，下列说法正确的是_____。ABD

A、算法是解决问题的步骤，某个问题可能有多个求解算法

B、算法不能直接由计算机执行，必须将其转换为程序才能够由计算机执行

C、算法只能由高级（计算机）语言实现，不能通过机器语言实现

D、求解问题的多个算法不一定获得相同的解

18

哥尼斯堡七桥问题，推而广之就是m个顶点n条边的图的“一笔画”问题，我们可以给出一个算法来求解该问题，即“对河流隔开的m块陆地上建造的n座桥梁，若要找到走遍这n座桥且只许走过每座桥一次的路径”。 关于该算法的基本思想，下列说法不正确的是_____。ABC

★《布宫号》提醒您：民俗信仰仅供参考，请勿过度迷信！