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

B、在确定一个组合<t1, t2, …, tn>时，tk+1是与tk相连接的城市中与tk距离最短的城市，即tk+1是由tk确定的，与tk连接的若干城市中的特性最优的城市

C、贪心算法确定的路径，是由局部最优(即tk+1在tk看来是最优的)组合起来的路径，该路径从全局角度也一定是最优的

D、对一个具体的TSP问题，每次执行贪心算法，所求得的最终解可能是不同的

9

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

我的答案：电路板上需要钻n个孔，选择一条最短路径使机器移动并完成所有孔的钻孔工作的问题(机器在电路板上钻孔的调度问题)

A、电路板上需要钻n个孔，选择一条最短路径使机器移动并完成所有孔的钻孔工作的问题(机器在电路板上钻孔的调度问题)

B、n个盘子在三个柱子上的移动问题(梵天塔问题或者说汉诺塔问题)

C、 n座桥， 走过每座桥且仅走过一次的问题(图的遍历问题)

D、都可以

10

关于数据结构，下列说法不正确的是______________？

我的答案：C

A、数据结构由逻辑结构、存储结构及运算3部分组成

B、存储结构定义了数据在存储器中的存储方式

C、向量使用顺序存储结构，并借助元素在存储器中的相对位置来表示数据元素的逻辑关系

D、在树结构中，指针用于表达元素之间的逻辑关系——父子关系，每个元素的指针指向其父节点，因此一个元素可以有一个或多个指针

11

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

我的答案：高级语言中二维数组可以由两个下标变量确定一个元素，其存储时仍旧是以线性方式进行存储，这种转换可以由编译器来完成

A、存储器是按线性方式组织数据，而二维数组是按“表”方式组织数据“表”方式存储数据

B、高级语言中二维数组可以由两个下标变量确定一个元素，其存储时仍旧是以“表”方式进行存储

C、高级语言中二维数组可以由两个下标变量确定一个元素，其存储时仍旧是以线性方式进行存储，这种转换可以由编译器来完成

D、以上都正确

12

算法的时间复杂性，可以表达为关于问题规模n的一个函数T(n)，T(n)可以用大O表示法来处理。问T(n)=O(f(n))是什么意思？正确的是_________。

我的答案：C.T(n)是与f(n)同数量级的函数

A、T(n)是关于f(n)的一个函数

B、T(n)是与f(n)同数量级的函数

C、T(n)是将函数f(n)代入O(x)中所形成的新函数

D、T(n)是依据f(n)计算出来的

13

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

我的答案：当算法的时间复杂性量级为非多项式函数时，如指数函数、阶乘函数时，计算机是不能够完成计算的

A、当算法的时间复杂性量级为多项式函数时，计算机是能够完成计算的

B、当算法的时间复杂性量级为非多项式函数时，如指数函数、阶乘函数时，计算机是不能够完成计算的

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

D、上述说法都不正确

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