2024知到网课 算法分析与设计(黑龙江工程学院)智慧树答案

第一章 单元测试

1、判断题：算法就是一组有穷的规则，它们规定了解决某一特定类型问题的一系列运算。
A:错
B:对
正确答案:【对】

2、判断题：计算机的资源最重要的是内存和运算资源。因而，算法的复杂性有时间和空间之分。
A:错
B:对
正确答案:【对】

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

4、单选题：下面关于算法的说法中正确的是（  ）。
（1）求解某一问题的算法是唯一的。
（2）算法中每条指令的执行次数是有限的，执行每条指令的时间也是有限的。
（3）算法的每一条指令是清晰无歧义的。
（4）算法可以用某种程序设计语言具体实现，所以算法和程序是等价的。
A:（2）（3）

B:（1）（3）

C:（2）（4）

D:（1）（2）

正确答案:【（2）（3）
】

5、单选题：描述算法的基本方法有（  ） 。
（1）自然语言
（2）流程图
（3）伪代码
（4）程序设计语言
A:（1）(2)（3）(4)

B:（1）（2）（3）

C:（2）（3）(4)

D:（1）（3）(4)

正确答案:【（1）(2)（3）(4)
】

6、单选题：算法分析是（  ）。
A:将算法用某种程序设计语言恰当地表示出来

B:证明算法对所有可能的合法出入都能算出正确的答案

C:对算法需要多少计算时间和存储空间作定量分析

D:在抽象数据数据集合上执行程序，以确定是否产生错误结果

正确答案:【对算法需要多少计算时间和存储空间作定量分析
】

7、单选题：下面算法段所需计算时间的下界为（  ）。    其中odd(n)，判断n是否为奇数，若是则返回值为真，否则为假。        while(n>1)        if(odd(n))             n=3*n+1;        else            n=n/2;

A:logn
B:n³
C:n²
D:3ⁿ
正确答案:【logn】

8、单选题：下面函数中增长率最低的是（  ）。
A:logn
B:n²
C:2ⁿ
D:n

正确答案:【logn】

9、多选题：下面属于算法的特性有(  )。
A:确定性：组成算法的每条指令是清晰，无歧义的。

B:输入：有0个或多个外部量作为算法的输入。

C:有限性：算法中每条指令的执行次数是有限的，执行每条指令的时间也是有限的。

D:输出：算法产生至少一个量作为输出。

正确答案:【确定性：组成算法的每条指令是清晰，无歧义的。
;输入：有0个或多个外部量作为算法的输入。
;有限性：算法中每条指令的执行次数是有限的，执行每条指令的时间也是有限的。
;输出：算法产生至少一个量作为输出。
】

10、单选题：10.下面算法的时间复杂度为（  ）。    int sum(int n)    {        if(n == 1)            return 1;        else            return n + sum(n-1);    }

A:O(1)
B:O(logn)
C:

O(n²)

D:O(n)
正确答案:【O(n)】

第二章 单元测试

1、判断题：直接或间接调用自身的算法称为递归算法。（）
A:错
B:对
正确答案:【对】

2、判断题：递归算法的基本原则包括基准情形、不断推进、设计法则和合成效益法则。（）
A:错
B:对
正确答案:【对】

3、判断题：使用分治法解决的一个问题时，需要将一个大的问题分解成若干个子问题，这些子问题可以和原问题相同，也可以不同。（）
A:对
B:错
正确答案:【错】

4、判断题：适合于用分治法求解的问题，经分解得到的子问题可以不是互相独立的。（）
A:对
B:错
正确答案:【错】

5、单选题：设当n＞1时，T（n）=2T（n/2）+O（n），则此分治法的时间复杂度为（）。
A:Θ(n²)
B:Θ（n）

C:Θ（nlogn）

D:Θ（logn）

正确答案:【Θ（nlogn）
】

6、单选题：设当n＞1时，T（n）=27T（n/3）+O（n2），则此分治法的时间复杂度为（）。
A:Θ（n²logn）
B:Θ（n）

C:Θ(n³)
D:Θ（n²）
正确答案:【Θ(n³)】

7、单选题：二分查找有序表（2，8，13，24，33，41，52，58，63，100 ），若查找表中元素51，则其依次和表中元素（）进行比较，查找结果是失败。
A:33，9，41，52

B:56，41，52

C:33，56，41，52

D:56，52

正确答案:【33，56，41，52
】

8、单选题：对于棋盘覆盖问题的分治算法，使用主定理进行算法分析时，k、m、d的值分别为（）。
A:k=2，m=4，d=1

B:k=4，m=2，d=0

C:k=4，m=2，d=1

D:k=2，m=4，d=0

正确答案:【k=4，m=2，d=0
】

9、单选题：下列选项中，不可能是快速排序第2趟排序结果的是（）。
A:{2，7，5，6，4，3，9}

B:{2，3，5，4，6，7，9}

C:{3，2，5，4，7，6，9}

D:{4，3，2，5，7，6，9}

正确答案:【{3，2，5，4，7，6，9}
】

10、单选题：采用递归方式对顺序表进行快速排序，下列关于递归次数的叙述中，正确的是（）。
A:递归次数与初始初始数据的排列次序无关

B:递归次数与每次划分后得到的分区处理顺序无关

C:每次划分后，先处理较短的分区可以减少递归次数

D:每次划分后，先处理较长的分区可以减少递归次数

正确答案:【递归次数与每次划分后得到的分区处理顺序无关
】

第三章 单元测试

1、判断题：动态规划算法是以空间换时间的时空权衡技术（）。
A:错
B:对
正确答案:【对】

2、判断题：动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。（）
A:对
B:错
正确答案:【对】

3、判断题：适合于用动态规划法求解的问题，经分解得到的子问题不是互相独立的。（）
A:对
B:错
正确答案:【对】

4、判断题：0-1背包问题实例的动态规划表中某一行值的序列总是非递减的（）。
A:对
B:错
正确答案:【对】

5、判断题：求解某一问题的算法是唯一的。
A:对
B:错
正确答案:【错】

6、单选题：下列算法通常以自底向上的方式求解的是（）。
A:回溯法

B:贪心法

C:备忘录法

D:动态规划算法

正确答案:【动态规划算法
】

7、单选题：下列是动态规划基本要素的是（）
A:子问题重叠性质

B:构造最优解