2024知到网课 算法分析与设计（山东联盟）智慧树答案

第一章 单元测试

1、判断题：一个问题的同一实例可以有不同的表示形式
A:错
B:对
正确答案:【对】

2、判断题：同一数学模型使用不同的数据结构会有不同的算法，有效性有很大差别。
A:错
B:对
正确答案:【对】

3、判断题：问题的两个要素是输入和实例。
A:对
B:错
正确答案:【错】

4、单选题：算法与程序的区别是（）
A:有穷性
B:确定性
C:输出
D:输入
正确答案:【有穷性】

5、单选题：解决问题的基本步骤是（）。（1）算法设计（2）算法实现（3）数学建模（4）算法分析（5）正确性证明
A:(3)(1)(5)(4)(2)
B:(1)(2)(3)(4)(5)
C:(3)(4)(1)(5)(2)
D:(3)(1)(4)(5)(2)
正确答案:【(3)(1)(5)(4)(2)】

6、单选题：

下面说法关于算法与问题的说法错误的是（）。
A:同一问题可能有几种不同的算法，解题思路和解题速度也会显著不同。
B:算法是一种计算方法，对问题的每个实例计算都能得到正确答案。
C:证明算法不正确，需要证明对任意实例算法都不能正确处理。
D:如果一个算法能应用于问题的任意实例，并保证得到正确解答，称这个算法解答了该问题。
正确答案:【证明算法不正确，需要证明对任意实例算法都不能正确处理。】

7、多选题：下面关于程序和算法的说法正确的是（）。
A:算法是一个过程，计算机每次求解是针对问题的一个实例求解。
B:程序是算法用某种程序设计语言的具体实现。
C:程序总是在有穷步的运算后终止。
D:算法的每一步骤必须要有确切的含义，必须是清楚的、无二义的。
正确答案:【算法是一个过程，计算机每次求解是针对问题的一个实例求解。;程序是算法用某种程序设计语言的具体实现。;算法的每一步骤必须要有确切的含义，必须是清楚的、无二义的。】

8、多选题：最大独立集问题和（）问题等价。
A:稳定匹配问题
B:最小顶点覆盖
C:区间调度问题
D:最大团
正确答案:【最小顶点覆盖;最大团】

9、多选题：给定两张喜欢列表，稳定匹配问题的输出是（  ） 。
A:完美匹配
B:稳定匹配
C:没有不稳定配对
D:最大匹配
正确答案:【完美匹配;稳定匹配;没有不稳定配对;最大匹配】

10、单选题：

问题变换的目的有（）。(1)复杂变简单 (2)未知变已知 (3)隐式变显式 (4)难解变易解 （5）以上都是。
A:（3）

B:（4）

C:（5）
D:（1）

E:（2）

正确答案:【（5）】

11、单选题：

按照霍纳法则，计算p(x) = a_nxⁿ + a_n-1x^n-1 +… + a₁x¹ + a₀   的数量级为____ 。
A:n^2

B:n

C:logn

D:nlogn

正确答案:【n
】

第二章 单元测试

1、判断题：时间复杂度是指算法最坏情况下的运行时间。
A:对
B:错
正确答案:【对】

2、判断题：f(n)=3n³+7n²+4nlogn =O（n²）
A:对
B:错
正确答案:【错】

3、判断题：如果一个算法是多项式时间算法，该算法是有效的,是好算法。
A:对
B:错
正确答案:【对】

4、单选题：算法复杂度分析的两种基本方法为（  ）和（    ）。
A:事后统计  事前分析
B:平摊复杂度 平滑复杂度
C:几何复杂度  平均复杂度
D:结构化方法 面向对象方法
正确答案:【事后统计  事前分析】

5、单选题：

下面程序的时间复杂度为（）

x=1

for i=1 to n  do

for j=1 to i do

for k=1 to j do

x++

A:O(nlogn)
B:O(n)
C:O(n^3)
D:O(n^2)
正确答案:【O(n^3)】

6、单选题：对近似递增序列的线性表从小到大排序，使用哪种方法好？
A:插入排序
B:归并排序
C:快速排序
D:堆排序
正确答案:【插入排序】

7、多选题：顺序查找适合的数据结构是（）
A:散列存储
B:链式存储
C:顺序存储
D:压缩存储
正确答案:【链式存储;顺序存储】

8、单选题：给定n个元素的数组A，n=10^{^3}, 使用折半查找比使用顺序查找大约快___倍。
A:10

B:1000

C:10^(3/2)

D:100

正确答案:【100
】

9、单选题：则f(n)的渐进性态f(n)=Ω(    )

A:n^2

B:1

C:n

D:100

正确答案:【1
】

10、判断题：f=O(g) 当且仅当 g =Ω (f)
A:错
B:对
正确答案:【对】

第三章 单元测试

1、判断题：0-1背包问题的枚举算法的时间复杂度为O（2ⁿ）
A:对
B:错
正确答案:【错】

2、判断题：增量构造法生成子集前需要对集合中元素从小到大排列。
A:对
B:错
正确答案:【对】

3、判断题：分块查找一般设分块的长度是n/2.
A:对
B:错
正确答案:【错】

4、判断题：枚举法适用于问题的小规模实例。
A:错
B:对
正确答案:【对】

5、单选题：便于实现集合操作的子集生成算法是（）
A:增量构造法
B:位向量法
C:二进制法
正确答案:【二进制法】

6、单选题：从所有候选答案中去搜索正确的解，这是 （）算法。
A:递推
B:枚举
C:蛮力
正确答案:【枚举】

7、单选题：logn²=(  )(logn+5)
A:o
B:w
C:θ
D:O

正确答案:【θ】

8、单选题：0-1背包问题的枚举算法，如果在百万次每秒的计算机上运行，1年可以计算的问题规模估计是？
A:50
B:40
C:30
D:60
正确答案:【40】

9、多选题：分数拆分问题的枚举算法通过（）方法进行了优化。
A:优化数学模型
B:减少枚举变量的值域
C:优化数据结构
D:减少枚举变量
正确答案:【优化数学模型;减少枚举变量的值域;减少枚举变量】

10、多选题：下面那些算法的时间复杂度为O（）?
A:折半插入排序
B:顺序查找
C:折半查找
D:冒泡排序
E:插入排序
正确答案:【折半插入排序;冒泡排序;插入排序】

11、单选题：A公司处理器速度是B公司的100倍。对于复杂度为n^2的算法，B公司的计算机可以在1小时内处理规模为n的问题，A公司的计算机在1小时能处理的问题规模是（）
A:10n

B:n^2

C:100n

D:n

正确答案:【10n
】

12、判断题：冒泡排序的时间复杂度为Ω(n^2)
A:错
B:对
正确答案:【错】

第四章 单元测试

1、判断题：贪心算法总能找到可行解，但未必是最优解。
A:对
B:错
正确答案:【对】

2、判断题：贪心选择通过一步步选择得到问题的解，每一步的局部最优解都构成全局最优解的一部分。

A:对
B:错
正确答案:【对】

3、判断题：问题的最优子结构性质是该问题可用贪心算法或动态规划算法求解的关键特征。
A:错
B:对
正确答案:【对】

4、判断题：Kruskal算法的贪婪准则是每一次选取不构成环路的最小边。
A:错
B:对
正确答案:【对】

5、单选题：贪心算法基本要素有（   ）和最优子结构性质。
A:重叠子问题性质
B:独立子问题性质
C:贪心选择性质
D:分解合并性质
正确答案:【贪心选择性质】

6、单选题：下面不是证明贪心算法证明方法的有（）。
A:交换论证
B:领先
C:界
D:优化
正确答案:【优化】

7、多选题：最小生成树问题可以使用的算法有（ ）
A:Solim
B:Dijkstra
C:Prim
D:Kruskal
正确答案:【Solim;Prim;Kruskal】

8、多选题：区间问题包含()
A:区间划分
B:区间选点
C:区间覆盖
D:区间调度
正确答案:【区间划分;区间选点;区间覆盖;区间调度】

9、判断题：负权的单源最短路问题可以使用Dijkstra算法求解

A:错
B:对
正确答案:【错】

10、判断题：设C是一个环， f 是C中的最大边，那么最小生成树中肯定包含f。

A:对
B:错
正确答案:【错】

第五章 单元测试

1、判断题：正推是从小规模的问题推解出大规模间题的一种方法。
A:对
B:错
正确答案:【对】

2、判断题：一般来说，递归的效率高于递推。
A:对
B:错
正确答案:【错】

3、单选题：从大规模问题逐步化为小规模问题的算法是（）
A:迭代
B:递归
C:正推
D:倒推
正确答案:【递归】

4、单选题：求解高阶递推方程一般使用（）迭代方法
A:直接迭代
B:差消迭代
C:换元迭代
正确答案:【差消迭代】

5、多选题：递归函数的要素是（）
A:迭代
B:递归方程
C:输入
D:边界条件
正确答案:【递归方程;边界条件】

6、多选题：递归变为非递归的方法有（）
A:循环
B:递推
C:模拟栈
D:尾递归
正确答案:【递推;模拟栈;尾递归】

7、多选题：T(n) = T(n-1) + n ，T(1)=1，则 T(n) =（）
A:O(n^2)

B:Ω(n^2)
C:θ(n^2)
D:n(n+1)/2
正确答案:【O(n^2)
;Ω(n^2);θ(n^2);n(n+1)/2】

8、多选题：递归一般用于解决问题有（）
A:数据的定义是按递归定义的
B:问题解法按递归实现
C:数据的结构形式是按递归定义的
D:迭代问题
正确答案:【数据的定义是按递归定义的;问题解法按递归实现;数据的结构形式是按递归定义的】

9、单选题：

主方法可以求解满足T(n)=aT(n/b) + f (n) 形式的递推方程， 则下列关于方程中的约束中不准确的是？设
A:对于系数b，必须满足b>1
B:若对于常数e>0，f(n)=O(y)，则T(n)=Θ(x)
C:对于系数a，必须满足a>=1
D:若f(n)=O(x)，则T(n)=Θ(xlogn)
正确答案:【若f(n)=O(x)，则T(n)=Θ(xlogn)】

10、单选题：，则 T(n) =（）

A:Θ(n^2)
B:O(n)
C:Ω(n^3)
D:O(nlogn)
正确答案:【Θ(n^2)】

11、判断题：循环用于重复性的工作。循环体的特点是：“以不变应万变”。
A:错
B:对
正确答案:【对】

第六章 单元测试

1、判断题：分治法分解的子问题与原问题形式相同。
A:对
B:错
正确答案:【对】

2、判断题：N个元素排序的时间复杂度不可能是线性时间。
A:错
B:对
正确答案:【错】

3、判断题：三分法的判定树是三叉树。
A:对
B:错
正确答案:【对】

4、判断题：减治法减一个常量就是每次迭代减去一个相同的常数因子(一般为2)
A:错
B:对
正确答案:【错】

5、单选题：设有5000个无序的元素，希望用最快的速度挑选出其中前10个最大的元素，最好选用(   )法。
A:合并排序
B:快速排序
C:基数排序
D:冒泡排序
正确答案:【冒泡排序】

6、单选题：堆排序的时间复杂度是O（）。
A:O（nlogn）
B:O（2ⁿ）
C:O（n）
D:O（n²）
正确答案:【O（nlogn）】

7、单选题：改进分治算法的方法有（ ）和改进划分的对称性。
A:加速原理
B:减少子问题数
C:备忘录
D:拟阵原理
正确答案:【减少子问题数】

8、多选题：通过减少子问题个数，降低分治算法时间复杂度的有（）
A:Strassen矩阵乘法
B:最接近点对
C:线性时间选择
D:大整数乘法
正确答案:【Strassen矩阵乘法;大整数乘法】

9、多选题：分治法在每一层递归上有三个步骤（）
A:解决

B:分解
C:选择
D:合并
正确答案:【解决
;分解;合并】

10、单选题：

使用分治法求解不需要满足的条件是（）。
A:原问题和子问题使用相同的方法求解
B:子问题必须是一样的
C:子问题的解可以合并
D:子问题不能够重复
正确答案:【子问题必须是一样的】

11、判断题：最小堆中每个元素调整的次数不超过树高。
A:对
B:错
正确答案:【对】

12、判断题：分治算法的思想是将难以直接解决的大问题，分割成一些规模较小的子问题，以便各个击破，分而治之。

A:对
B:错
正确答案:【对】

13、判断题：任何排序算法至少需要O(n log n)次比较。
A:错
B:对
正确答案:【错】

14、单选题：找n个元素的中位数的分治算法的时间复杂度为O().
A:n

B:n^2
C:nlogn

D:logn
正确答案:【n
】

第七章 单元测试

1、判断题：动态规划算法把原问题分为交叉的子问题，解决子问题，记录子问题的解，合并为原问题的解。
A:错
B:对
正确答案:【对】

2、判断题：0/1背包问题的动态规划算法是多项式时间算法。
A:对
B:错
正确答案:【错】

3、判断题：对于稀疏图，Floyd算法的效率要高于执行n次Dijkstra算法，也要高于执行n次SPFA算法。
A:对
B:错
正确答案:【错】

4、判断题：Dijkstra算法在求解过程中，源点到集合S内各顶点的最短路径一旦求出，则之后不变了，修改的仅仅是源点到还没选择的顶点的最短路径长度。
A:对
B:错
正确答案:【对】

5、单选题：含负权的最短路问题一般使用（）求解。
A:贪心算法
B:网络流算法
C:动态规划
D:分治算法
正确答案:【动态规划】

6、单选题：动态规划算法的基本要素有（ ）和最优子结构性质。
A:分解合并性质
B:独立子问题性质
C:贪心选择性质
D:重叠子问题性质
正确答案:【重叠子问题性质】