超星 - 算法-程序与计算系统之灵魂

单选题

下列哪些问题可应用求解TSP的算法，正确的是_____。

A. 电路板上需要钻n个孔，选择一条最短路径使机器移动并完成所有孔的钻孔工作的问题(机器在电路板上钻孔的调度问题)
B. n个盘子在三个柱子上的移动问题(梵天塔问题或者说汉诺塔问题)
C. n座桥，走过每座桥且仅走过一次的问题(图的遍历问题)
D. 都可以

查看答案

单选题

关于数组和存储器，下列说法正确的是_____。-

A. 存储器是按线性方式组织数据，而二维数组是按“表”方式组织数据“表”方式存储数据
B. 高级语言中二维数组可以由两个下标变量确定一个元素，其存储时仍旧是以“表”方式进行存储
C. 高级语言中二维数组可以由两个下标变量确定一个元素，其存储时仍旧是以线性方式进行存储，这种转换可以由编译器来完成
D. 以上都正确

查看答案

单选题

为什么要评估算法的复杂性？下列说法不正确的是_________。

A. 当算法的时间复杂性量级为多项式函数时，计算机是能够完成计算的
B. 当算法的时间复杂性量级为非多项式函数时，如指数函数、阶乘函数时，计算机是不能够完成计算的
C. 当算法的时间复杂性量级为非多项式函数时，如指数函数、阶乘函数时，对于大规模问题，计算机是不能够完成计算的
D. 上述说法都不正确

查看答案

单选题

分析下列算法的时间复杂性。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
A. O(3n)
B. O(n2)
C. O(n3)
D. O(n!)
查看答案

单选题

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

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

查看答案

多选题

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

A. 算法规定了任务执行/问题求解的一系列、有限的步骤
B. 算法所规定的计算/处理步骤是有限的，但算法实际执行的计算/处理步骤可以是无限的
C. 算法可以没有输入，但必须有输出
D. 算法的每一个步骤必须确切地定义，且其运算和操作必须相当基本，可以由机器自动完成

查看答案

多选题

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

A. 算法是解决问题的步骤，某个问题可能有多个求解算法
B. 算法不能直接由计算机执行，必须将其转换为程序才能够由计算机执行
C. 算法只能由高级（计算机）语言实现，不能通过机器语言实现
D. 求解问题的多个算法不一定获得相同的解

查看答案

多选题

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

A. 以任何一个顶点为起点，按照图的“边”的指示，找到按该边与该顶点相连的下一个顶点，并标记该边为“已访问”，依次循环，直到所有的边都被访问过为止，便可找到给定问题的解
B. 以任何一个顶点为起点，按照图的未访问过“边”的指示，找到按该边与该顶点相连的下一个顶点，并标记该边为“已访问”，依次循环，直到所有的边都被访问过为止，便可找到给定问题的解
C. 首先判断该问题是否有解，若无解，则直接退出；若有解，则以任何一个顶点为起点，按照图的未访问过“边”的指示，找到按该边与该顶点相连的下一个顶点，并标记该边为“已访问”，依次循环，直到所有的边都被访问过为止，便可找到给定问题的解
D. 首先判断该问题是否有解，若无解，则直接退出；若有解，则选择一个奇数度的顶点为起点，按照图的未访问过“边”的指示，找到按该边与该顶点相连的下一个顶点，并标记该边为“已访问”，依次循环，直到所有的边都被访问过为止，便可找到给定问题的解

查看答案

多选题

关于TSP，下列说法正确的是_____。

A. TSP问题的一个可能解就是n个城市的一个组合<t1, t2, …, tn>，其中任何两个ti，tj都对应不同的城市。若要求得最优解，则必须对所有的组合，即所有可能解进行比较
B. TSP问题的难点是当n值很大时，组合数目非常庞大(组合数目为n!)，以致于计算机不能在有限时间内完成所有的组合
C. TSP问题的难点是当n值很大时，组合数目非常庞大(组合数目为n!)，虽如此，计算机仍然能够在有限时间内完成所有的组合
D. 上述思想--对所有组合进行比较的思想，即是所谓的遍历算法策略，它仅仅对n值很小的TSP问题是能行的

查看答案

多选题

关于数据结构，下列说法正确的是_____。

A. 数据结构是问题域数学模型中各种数据的存储结构
B. 数据结构是将逻辑上有一定语义关系的数据，转换成计算机可以存储和处理的变量，便于算法和程序进行处理
C. 数据结构是将具有一定语义关系的变量进行命名，以便隐藏数据结构内部的操作细节，便于算法按逻辑语义通过操控该名字来操控该数据结构
D. 数据结构包含了数据的逻辑结构、存储结构及其操作

查看答案