算法分析与设计第二章测试_智慧树知到答案2021年

第二章 递归与分治算法：本章主要讲授递归的概述和特点、经典的递归实例（阶乘、Fibonacci数列和汉诺塔问题），分治法的基本思想和复杂度分析，分治算法经典实例之二分查找和快速排序。2.1分治算法之递归概述:学习递归的定义、要素、递归树和特点，以及两个经典的递归实例：求阶乘和Fibonacci数列。
2.2递归算法之汉诺塔问题:学习汉诺塔问题的描述及其求解算法的设计、分析和实现。
2.3分治法的基本思想:学习分治法的总体思想、适用条件和基本步骤。
2.4分治法的复杂度分析:学习分治法时间复杂度递推公式的表示和公式求解（主定理）。
2.5分治算法之二分查找:学习二分查找的定义、算法设计、算法分析和算法实现。
2.6分治算法之快速排序:学习快速排序的概述、算法设计、算法实现和算法分析。

[判断题]递归函数是指在一个函数体中出现直接或间接调用该函数自身的函数。
对
错
答案：对
[单选题]已知f(1)=1，f(n)=f(n-1)+n，那么f(50)的作用是( )。
计算50个1的和。
计算斐波拉契数列的第50个元素的值。
计算1到50的和。
计算1到50的乘积。
答案：计算1到50的和。
[多选题]递归的优点包括( )。
容易用数学归纳法来证明算法的正确性
结构清晰
可读性强
运行效率高
答案：结构清晰
可读性强
容易用数学归纳法来证明算法的正确性
[单选题]在经典的汉诺塔问题中，如果有5个圆盘需要从A柱移至C柱，最少需要移动( )步。
31
28
41
32
答案：31
[多选题]分治法能解决的问题一般具有（ ）等特征。
最优子结构
分解出的子问题的解可以合并为原问题的解
该问题缩小到一定程度时可以容易地解决
子问题相互独立
答案：该问题缩小到一定程度时可以容易地解决
最优子结构
分解出的子问题的解可以合并为原问题的解
子问题相互独立
[判断题]在使用分治法设计算法时，最好使子问题的规模大致相同，即将一个问题分成大小相等的多个子问题的处理方法是行之有效的。
对
错
答案：对
[单选题]给定递归公式T(n)=4T(n/2)+O(n),由主定理可以得知T(n)=( )。
O(logn)
O(n^2)
O(n)
O(nlogn)
答案：O(n^2)
[单选题]已知某楼房共20层，如果采用二分查找，请问最多猜( )次就能猜出任意一个楼层。
5
3
4
6
答案：5
[多选题]关于快速排序的时间复杂度，( )是正确的。
在最坏情况下时间复杂度为O(n^2)
在平均情况下时间复杂度为O(n^2)
在平均情况下时间复杂度为O(nlogn)
在最好情况下时间复杂度为O(nlogn)
答案：在最坏情况下时间复杂度为O(n^2)
在最好情况下时间复杂度为O(nlogn)
在平均情况下时间复杂度为O(nlogn)
[单选题]快速排序是对传统排序算法( )的一种改进。
归并排序
选择排序
冒泡排序
插入排序
答案：冒泡排序