2024知到网课 算法分析与设计智慧树答案

第一章 单元测试

1、判断题：算法是指解决问题的方法或过程，它包含一系列步骤，用来将输入数据转换成输出结果。
A:对
B:错
正确答案:【对】

2、多选题：使用伪代码描述算法具有（）等优点。
A:简单易懂
B:格式统一规范
C:容易修改
D:易于转化为程序语言代码
正确答案:【简单易懂;容易修改;易于转化为程序语言代码】

3、多选题：算法通常具有（）的性质。
A:输入：有零个或多个输入
B:确定性：组成算法的每条指令清晰、无歧义
C:有限性：算法中每条指令的执行次数有限，执行每条指令的时间也有限
D:输出：至少有一个输出
正确答案:【输入：有零个或多个输入;确定性：组成算法的每条指令清晰、无歧义;有限性：算法中每条指令的执行次数有限，执行每条指令的时间也有限;输出：至少有一个输出】

4、判断题：程序是算法用某种程序设计语言的具体实现，程序需满足算法的所有性质。
A:对
B:错
正确答案:【错】

5、多选题：常用的描述算法的形式有（）。
A:机器语言
B:程序流程图
C:自然语言
D:伪代码
正确答案:【程序流程图;自然语言;伪代码】

6、单选题：函数f(n)=20log3^n的渐进表达式是（）。
A:0(log(n))
B:0（n^2）
C:O(n)
D:0(1)
正确答案:【O(n)】

7、多选题：一个算法的优劣由（）决定。
A:代码长度
B:时间复杂度
C:使用的编程语言
D:空间复杂度
正确答案:【时间复杂度;空间复杂度】

8、判断题：如果存在正的常数C和自然数N0,使得当N≥N0时有f(N)≤Cg(N),则称函数f(N)当N充分大时上有界，且g(N)是它的一个上界，记为f(N)=O(g(N)),即f(N)的阶不高于g(N）的阶。
A:错
B:对
正确答案:【对】

9、单选题：分析以下代码的时间复杂度：int func(int n)
{
int i=1, k=0;
while(i<=n) {
k++;
i=i*2;
}
return k;
}
A:O(logn)
B:O(n)
C:O(n^2)
D:O(n/2)
正确答案:【O(logn)】

10、多选题：对于f(n)=n，下列说法正确的是（）。
A:f(n)=O(n^2)
B:f(n)=O(1/n)
C:f(n)=O(n)
D:f(n)=O(n^3)
正确答案:【f(n)=O(n^2);f(n)=O(n);f(n)=O(n^3)】

第二章 单元测试

1、判断题：递归函数是指在一个函数体中出现直接或间接调用该函数自身的函数。
A:对
B:错
正确答案:【对】

2、单选题：已知f(1)=1，f(n)=f(n-1)+n，那么f(50)的作用是( )。
A:计算1到50的和。
B:计算斐波拉契数列的第50个元素的值。
C:计算1到50的乘积。
D:计算50个1的和。
正确答案:【计算1到50的和。】

3、多选题：递归的优点包括( )。
A:结构清晰
B:容易用数学归纳法来证明算法的正确性
C:运行效率高
D:可读性强
正确答案:【结构清晰;容易用数学归纳法来证明算法的正确性;可读性强】

4、单选题：在经典的汉诺塔问题中，如果有5个圆盘需要从A柱移至C柱，最少需要移动( )步。
A:32
B:31
C:41
D:28
正确答案:【31】

5、多选题：分治法能解决的问题一般具有（）等特征。
A:该问题缩小到一定程度时可以容易地解决
B:最优子结构
C:分解出的子问题的解可以合并为原问题的解
D:子问题相互独立
正确答案:【该问题缩小到一定程度时可以容易地解决;最优子结构;分解出的子问题的解可以合并为原问题的解;子问题相互独立】

6、判断题：在使用分治法设计算法时，最好使子问题的规模大致相同，即将一个问题分成大小相等的多个子问题的处理方法是行之有效的。
A:错
B:对
正确答案:【对】

7、单选题：给定递归公式T(n)=4T(n/2)+O(n),由主定理可以得知T(n)=( )。
A:O(n^2)
B:O(nlogn)
C:O(n)
D:O(logn)
正确答案:【O(n^2)】

8、单选题：已知某楼房共20层，如果采用二分查找，请问最多猜( )次就能猜出任意一个楼层。
A:6
B:5
C:4
D:3
正确答案:【5】

9、多选题：关于快速排序的时间复杂度，( )是正确的。
A:在最坏情况下时间复杂度为O(n^2)
B:在平均情况下时间复杂度为O(nlogn)
C:在最好情况下时间复杂度为O(nlogn)
D:在平均情况下时间复杂度为O(n^2)
正确答案:【在最坏情况下时间复杂度为O(n^2);在平均情况下时间复杂度为O(nlogn);在最好情况下时间复杂度为O(nlogn)】

10、单选题：快速排序是对传统排序算法( )的一种改进。
A:冒泡排序
B:插入排序
C:选择排序
D:归并排序
正确答案:【冒泡排序】

第三章 单元测试

1、多选题：能够使用动态规划算法来求解的问题通常需要具备两个重要的性质，它们分别是( )。
A:递归调用
B:重叠子问题
C:最优子结构
D:贪心选择性质
正确答案:【重叠子问题;最优子结构】

2、多选题：关于备忘录法，以下说法正确的是( )。
A:备忘录法为每个解过的子问题建立备忘录以备需要时查看，又称查表法。
B:备忘录法又称为记忆化搜索，它采用一种自底向上的方式求解问题。
C:备忘录法的控制结构与直接使用递归方法的控制结构相同。
D:备忘录法可以避免相同子问题的重复求解。
正确答案:【备忘录法为每个解过的子问题建立备忘录以备需要时查看，又称查表法。;备忘录法的控制结构与直接使用递归方法的控制结构相同。;备忘录法可以避免相同子问题的重复求解。】

3、单选题：字符序列abcde与字符序列abdge的最长公共子序列长度为( )，最长公共子串长度为( )。
A:4,1
B:3,5
C:4,2
D:4,6
正确答案:【4,2】

4、单选题：使用动态规划算法求两条长度分别为m和n的序列的最长公共子序列，其时间复杂度为( )。
A:O(n*m)
B:O(m^n)
C:O(n^2)
D:O(nlogm)
正确答案:【O(n*m)】

5、单选题：输入数组（-1, 0, 1, -2, 3），它的最大子段和是( )。
A:4
B:2
C:1
D:3
正确答案:【3】

6、单选题：序列（1，7，3，4，9，2，3）的最长递增子序列的长度为( )。
A:2
B:4
C:3
D:1
正确答案:【4】

7、单选题：使用穷举法求解最长递增子序列的时间复杂度为( )。
A:O(nlogn)
B:O(n^2)
C:O(n*2^n)
D:O(n^n)
正确答案:【O(n*2^n)】

8、单选题：使用动态规划算法求最大子段和的时间复杂度为( )。
A:O(n)
B:O(logn)
C:O(nlogn)
D:O(2^n)
正确答案:【O(n)】

9、多选题：某工厂预计明年有A,B,C,D四个新建项目，每个项目的投资额分别为15,10,12,8（万元），投资收益分别为12,8,9,5（万元），投资总额为30万元，选择项目( )可以使总收益最大。（不允许部分投资某个项目）
A:D
B:A
C:B
D:C
正确答案:【D;B;C】