违法和不良信息举报 联系客服
免费注册 登录

把大问题分解成子问题，且子问题有大量重合的问题求解，较好的算法是（）。

题目
单选题
把大问题分解成子问题，且子问题有大量重合的问题求解，较好的算法是（）。
A

贪心法

B

分治法

C

动态规划法

D

回朔法

如果没有搜索结果或未解决您的问题，请直接 联系老师 获取答案。
相似问题和答案

第1题：

动态规划是一种在数学和计算机科学中使用的,用于求解包含()的最优化问题的方法。

A、重叠子问题

B、相似子问题

C、互斥子问题

D、有序子问题


参考答案：A

第2题：

对问题进行分割后进行搜索的实质是（）

  • A、对问题进行归纳总结，以寻求一般的概念
  • B、从目标出发的逆向推理，寻找若干子问题的集合
  • C、将多个小问题归纳成一个大问题的求解方法

正确答案:B

第3题：

问题的最优子结构性质是该问题不可用动态规划算法或贪心算法求解的关键特征。()

此题为判断题(对，错)。


正确答案:×

第4题：

动态规划算法的基本思想是将待求解问题分解成若干（），先求解（），然后从这些（）的解得到原问题的解。


正确答案:子问题；子问题；子问题

第5题：

使用分治法求解不需要满足的条件是（）。

  • A、子问题必须是一样的
  • B、子问题不能够重复
  • C、子问题的解可以合并
  • D、原问题和子问题使用相同的方法解

正确答案:A

第6题：

在求解某问题时，经过分析发现该问题具有最优子结构性质，求解过程中子问题被重复求解，则采用（ ）算法设计策略

A.分治
B.动态规划
C.贪心
D.回溯

答案：B
解析：
分治法的设计思想是将一个难以直接解决的大问题分解成一些规模较少的相同问题以便各个击破，分而治之。
动态规划法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划法求解的问题，经分解得到的子问题往往不是独立的。若用分治法来解这类问题，则相同的子问题会被求解多次，以至于最后解决原问题需要耗费指数级时间。
贪心法经常用于解决最优化问题，但他的最优往往是从局部最优来考虑的，每一步都选最优的方案，但这种方案不一定能得到整体上的最优解。回溯法是一种既带有系统性又带有跳跃性的搜索算法。它在包含问题的所有解的解空间树中，按照深度优先的策略，从根节点出发搜索解空间树。
题目描述中提到，需要解决的问题具有最优子结构性质，且求解过程中子问题被重复求解，这种情况下如果采用分治法，效率会很低，所以应采用动态规划法。而“以深度优先的方式搜索解空间”则明显是在采用回溯法。

第7题：

对于0－1背包问题和背包问题的解法，下面（）答案解释正确。

  • A、0－1背包问题和背包问题都可用贪心算法求解
  • B、0－1背包问题可用贪心算法求解，但背包问题则不能用贪心算法求解
  • C、0－1背包问题不能用贪心算法求解，但可以使用动态规划或搜索算法求解，而背包问题则可以用贪心算法求解
  • D、因为0－1背包问题不具有最优子结构性质，所以不能用贪心算法求解

正确答案:C

第8题：

能采用递归描述的算法通常有这样的特征:为求解规模为N的问题,设法将它分解成规模较小的问题,然后从这些小问题的解很容易构造出大问题的解,并且这些规模较小的问题也能采用同样的分解和综合方法,分解成规模更小的问题,并从这些更小问题的解构造出规模较大问题的解。特别地,当规模N=1时,能直接得解。()

此题为判断题(对，错)。


参考答案：正确

第9题：

数据结构与算法里，递归的基本思想描述不正确的是（）。

  • A、把规模大的问题转换为规模小的相似的子问题
  • B、把规模小的问题转换为规模大的问题
  • C、把规模小的问题转换为规模大的相似的子问题
  • D、把规模大的问题转换为规模小的不同类型问题

正确答案:B,C,D

第10题：

分治法的设计思想是将一个难以直接解决的大问题分割成规模较小的子问题，分别解决子问题，最后将子问题的解组合起来形成原问题的解。这要求原问题和子问题（）

  • A、问题规模相同，问题性质相同
  • B、问题规模相同，问题性质不同
  • C、问题规模不同，问题性质相同
  • D、问题规模不同，问题性质不同

正确答案:C

更多相关问题
相关内容