【MOOC】算法设计与分析-武汉理工大学 中国大学慕课MOOC答案

【MOOC】算法设计与分析-武汉理工大学中国大学慕课MOOC答案“算法设计基础”算法实现题“算法设计基础”单元测验1、【多选题】下列关于算法的说法中正确的有（）。本题答案：【算法必须在有限步操作之后停止#算法的每一步操作必须是明确的，不能有歧义或含义模糊#算法执行后一定产生确定的结果】2、【多选题】以下哪些是算法的基本特点（）。本题答案：【有穷性#确定性#可行性】“算法分析基础”测试题1、【单选题】以下关于渐近记号的性质，正确的有（）本题答案：【】2、【单选题】以下关于记号的定义，正确的是（）本题答案：【存在正常数和使得对所有有：】3、【单选题】若一个算法的递归方程为，则其时间复杂度为（）本题答案：【】4、【单选题】表示当输入规模为时的算法效率，以下算法效率最优的是（）本题答案：【】“分治法”算法实现题“分治法”单元测试1、【单选题】分治法的设计思想是将一个难以直接解决的大问题分割成规模较小的子问题，分别解决子问题，最后将子问题的解组合起来形成原问题的解。这要求原问题和子问题（）。本题答案：【问题规模不同，问题性质相同】2、【单选题】在寻找n个元素中第k小元素问题中，如快速排序算法思想，运用分治算法对n个元素进行划分，如何选择划分基准？下面（）答案解释最合理。本题答案：【以上皆可行。但不同方法，算法复杂度上界可能不同】3、【单选题】减少子问题个数，就是减少时间复杂度函数T(n)=aT(n/b)+f(n)中的（）值。本题答案：【a】4、【单选题】使用分治法求解不需要满足的条件是（）。本题答案：【子问题不能够重复】5、【多选题】改进分治算法的方法有（）。本题答案：【减少子问题的个数#减少合并的时间#改进分治的均衡度】6、【填空题】阅读以下代码:intFun(intn){if(n=1)return1;intFirst=Fun(n-1);intSecond=Fun(n-2);intiSum=First+Second;returniSum;}调用该函数，假设输入参数n值为5，当程序第二次执行语句iSum=First+Second时，iSum的值为（）。本题答案：【3】“动态规划法”算法实现题“回溯法”算法实现题“分枝限界法”算法实现题“贪心法”算法实现题算法设计与分析考试题1、【单选题】分治法的设计思想是将一个难以直接解决的大问题分割成规模较小的子问题，分别解决子问题，最后将子问题的解组合起来形成原问题的解。这要求原问题和子问题（）。本题答案：【问题规模不同，问题性质相同】2、【单选题】下面问题（）不能使用贪心法解决。本题答案：【n皇后问题】3、【单选题】对于0－1背包问题和背包问题的解法，下面（）答案解释正确。本题答案：【0－1背包问题不能用贪心算法求最优解，但可以使用动态规划或搜索算法求解，而背包问题则可以用贪心算法求解】4、【单选题】常见的两种分支限界法为（）。本题答案：【队列式（FIFO）分支限界法与优先队列式分支限界法】5、【单选题】T(n)表示当输入规模为n时的算法效率，以下算法效率最优的是（）。本题答案：【】6、【单选题】算法分析中，记号Θ表示（）。本题答案：【渐近紧界】7、【单选题】采用最大效益优先搜索方式的算法是（）。本题答案：【分支限界法】8、【单选题】在寻找n个元素中第k小元素问题中，如快速排序算法思想，运用分治算法对n个元素进行划分，如何选择划分基准？下面（）答案解释最合理。本题答案：【以上皆可行。但不同方法，算法复杂度上界可能不同】9、【单选题】回溯法在问题的解空间树中，按（）策略，从根结点出发搜索解空间树。本题答案：【深度优先】10、【单选题】优先队列式分支限界法选取扩展结点的原则是（）。本题答案：【结点的优先级】11、【单选题】归并排序算法是利用（）实现的算法本题答案：【分治策略】12、【单选题】（）是回溯法中为避免无效搜索采取的策略。本题答案：【剪枝函数】13、【单选题】找n个元素的中位数的分治算法的时间复杂度为()。本题答案：【】14、【单选题】回溯法的算法框架按照问题的解空间一般分为子集树算法框架与（）算法框架。本题答案：【排列树】15、【单选题】矩阵连乘问题的算法可由（）设计实现本题答案：【动态规划算法】16、【多选题】算法是由若干条指令组成的有穷序列，而且满足以下性质（）。本题答案：【输入：有0个或多个输入#输出：至少有一个输出#确定性：指令清晰，无歧义#有限性：指令执行次数有限，而且执行时间有限】17、【多选题】求解递归方程使用的方法有（）。本题答案：【迭代法#代入法#主定理#递归树】18、【多选题】分治法所能解决的问题一般具有（）特征。本题答案：【问题可以分解为规模较小的子问题#子问题可合并为原问题的解#小规模子问题可解】19、【多选题】回溯法的效率依赖于下列哪些因素（）。本题答案：【满足显式约束的值的个数#计算限界函数的时间#计算约束函数的时间】20、【多选题】改进分治算法的方法有（）。本题答案：【改进分治的均衡度#减少合并的时间#减少子问题的个数】21、【判断题】无论在何种情况下，分治法总能产生效率最高的算法。本题答案：【错误】22、【判断题】一个算法是正确的，那么它就是有效的。本题答案：【错误】23、【判断题】重叠子问题保证了动态