算法分析与设计（山东联盟）期末答案2023秋

1.三种时间复杂度是指()。
A:最好时间复杂度 B:概率时间复杂度 C:平均时间复杂度 D:最坏时间复杂度
答案:平均时间复杂度###最好时间复杂度###最坏时间复杂度
2.算法的性质有（）
A:有限性 B:确定性 C:输入 D:输出
答案:输入; 输出; 确定性; 有限性
3.算法复杂度主要是分析()。
A:空间复杂度 B:计算复杂度 C:时间复杂度 D:程序复杂度
答案:空间复杂度
4.回溯法求解过程中遇到不可行解就回溯到父节点。
A:错误 B:正确
答案:正确
5.公共子序列在原序列中不一定是连续的。
A:正确 B:错误
答案:正确
6.分治法所能解决的问题一般具有利用该问题分解出的子问题的解可以合并为该问题的解的特征。
A:正确 B:错误
答案:正确
7.动态规划算法求解问题时，分解出来的子问题相互独立。
A:错误 B:正确
答案:错误
8.从分治法的一般设计模式可以看出，用它设计出的程序一般是递归算法
A:错 B:对
答案:对
9.可以使用邻接矩阵来作为m着色问题的主要数据结构。
A:正确 B:错误
答案:正确
10.最小生成树是唯一的。
A:错误 B:正确
答案:错误
11.在背包问题中，当xi=0时，表示物品i被装入背包。
A:错误 B:正确

12.两个n*n的矩阵相乘的时间复杂度是O(n2)
A:错 B:对 13.求 21+1/n 的渐进表达式是θ(1)
A:对 B:错 14.回溯法中限界函数的目的是剪去得不到最优解的子树。
A:对 B:错 15.现实计算机上无法产生真正的随机数。
A:对 B:错 16.用动态规划法求解的问题都可以分解为相互重叠的子问题。
A:对 B:错 17.采用动态规划算法时，子问题的重叠关系表现在对给定问题求解的递推关系中。
A:正确 B:错误 18.分支限界法在最坏情况下，时间复杂度为指数阶。
A:正确 B:错误 19.Prim算法更适合构造稠密图的最小生成树，Dijkstra算法更适合构造稀疏图的最小生成树。( )
A:错误 B:正确 20.分支限界法与回溯法都是在问题的解空间树T上搜索问题的解，二者（）。
A:求解目标相同，搜索方式不同 B:求解目标不同，搜索方式也不同 C:求解目标不同，搜索方式相同 D:求解目标相同，搜索方式也相同 21.求单源点最短路径的Dijkstra算法是按（ ）的顺序求源点到各顶点的最短路径的。
A:路径长度递减 B:路径长度递增 C:顶点编号递增 D:顶点编号递减 22.背包问题的贪心算法所需的计算时间为（ ）
A:O(nlogn) B:O(n) C:O(2n) D:O(n2n) 23.算法分析中，记号O表示（ ）
A:渐进上界 B:渐进下界 C:非紧上界 D:紧渐进界 24.不是分支界限法搜索方式的是( )
A:最小耗费优先 B:最大效益优先 C:深度优先 D:广度优先 25.实现棋盘覆盖算法利用的算法是（ ）。
A:贪心法 B:回溯法 C:动态规划法 D:分治法 26.背包问题的贪心算法所需的计算时间为
A:O（nlogn） B:O（2n） C:O（n） D:O（n2n） 27.采用最大效益优先搜索方式的算法是（ ）。
A:动态规划 B:贪心法 C:分支限界法 D:回溯法 28.算法分析中，记号Ω表示（ ）
A:渐进上界 B:紧渐进界 C:非紧上界 D:渐进下界 29.回溯法的效率不依赖于下列哪些因素（ ）
A:满足显约束的值的个数 B:确定解空间的时间 C:计算约束函数的时间 D:计算限界函数的时间 30.原问题的最优解包含其子问题的最优解，这是（）性质
A:无后效性 B:贪心选择 C:重叠子问题 D:最优子结构 31.备忘录与动态规划算法的不同点是（）
A:最优子结构 B:子问题重叠 C:自顶向下计算 D:递推关系 32.软件的灵魂是()。
A:编程语言 B:数据结构 C:算法 D:数据 33.5个物品，其重量分别是{2, 2, 6, 5, 4}，价值分别为{6, 3, 5, 4, 6}，背包的容量为10，采用0-1背包算法，则最终被装入背包的分别为第几个物品。（ ）
A:1、3、5 B:1、2、4 C:1、2、5 D:1、2、3 34.多机调度问题属于（ ）。
A:NP问题 B:NPC问题 C:P问题 D:PN问题 35.下列算法中不能解决0/1背包问题的是（ ）
A:分支限界法 B:回溯法 C:动态规划 D:贪心法 36.描述渐进上界的符号是()。
A:ω B:Ω C:A D:O 37.使用回溯法求解背包问题是，限界函数可以设计为()。
A:v+(W+w)*(vi+1/wi+1) B:v+(W-w)*(vi+1/wi+1) C:v-Wi*vi D:v+w 38.下列说法正确的是
A:如果一个NP完全问题有多项式时间算法，那么NP中的每一个问题都可以有多项式时间算法 B:优化问题可多项式变换到判定问题 C:任何基于比较的排序算法至少需要O(n log n)次比较 D:任何时候复杂性渐近阶比较低的算法比复杂性的渐近阶比较高的算法有效