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

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

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

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

4、程序是算法用某种程序设计语言的具体实现，程序需满足算法的所有性质。
答案：错

5、常用的描述算法的形式有（ ）。
A、自然语言
B、机器语言
C、伪代码
D、程序流程图
答案：机器语言

6、函数f(n)=20log3^n的渐进表达式是（ ）。
A、O(n)
B、0（n^2）
C、0(1)
D、0(log(n))
答案：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）的阶。
答案：对

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

10、对于f(n)=n，下列说确的是（ ）。
听录音，选出正确的字母填在题前括号内。
(    ) 1. z d p r 
(    ) 2. f g e c  
(    ) 3. o m n b 
(    ) 4. g k  i  b    
(    ) 5. u m w v 
(    ) 6. R A Q S    
(    ) 7. L N G J    
(    ) 8. B R T N                                              
(    ) 9. Z U Y W       
(    ) 10. J T I L  
答案：1. d    2. e   3. n   4. g   5. v   6. Q   7. J   8. R   9. Y   10. I

1、递归函数是指在一个函数体中出现直接或间接调用该函数自身的函数。
答案：对

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

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

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

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

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

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

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

9、关于快速排序的时间复杂度，( )是正确的。
A、在最坏情况下时间复杂度为O(n^2)
B、在最好情况下时间复杂度为O(nlogn)
C、在平均情况下时间复杂度为O(n^2)
D、在平均情况下时间复杂度为O(nlogn)
答案：在最坏情况下时间复杂度为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,2
B、4,6
C、4,1
D、3,5
答案：4,2

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

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

6、序列（1，7，3，4，9，2，3）的最长递增子序列的长度为( )。
A、1
B、2
C、3
D、4
答案：4

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

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

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

10、在使用动态规划算法求解0-1背包问题时，若m[i][j]=m[i+1][j-w[i]]+v[i]，说明第i个物品在剩余背包容量为j时可以装入，并且装入比不装入的背包总价值更大，装入后，背包剩余容量减少w[i]，价值增加v[i]。
答案：正确