2.分治法是我们计算机科学解决问题的一种基本方法。它的基本思想是把一个复杂的问题分成两个或更多的相同或相似的互相独立的（)，再把子问题分成更小的子问题，直到最后的子问题可以简单的直接求解，然后将这些子问题的解合并从而构造出原问题的解。

第1题：

第2题：

已知初始问题的描述，通过一系列变换把此问题最终变为一个子问题集合；这些子问题的解可以直接得到，从而解决了初始问题。这是知识表示法叫（）

• A、状态空间法
• B、问题归约法
• C、谓词逻辑法
• D、语义网络法

正确答案:B

第3题：

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

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

正确答案:A

第4题：

分支定界法在需要分支时必须满足：一是分支后的各子问题必须容易求解；二是各子问题解的集合必须覆盖原问题的解。

正确答案:正确

第5题：

一个直接或间接调用自身的算法称为（）算法。 出自于“平衡子问题”的思想，通常分治法在分割原问题，形成若干子问题时，这些子问题的规模都大致（）。

正确答案:递归；相等

第6题：

在求解规模较大的问题时，可以把它分解成若干个规模较小的子问题，求出各个子问题的解之后，再把这些解合成原问题的解，这种方法是（）。

• A、穷举法
• B、回溯法
• C、分治法
• D、递归法

正确答案:C

第7题：

递归的基本思想描述正确的是（）

• A、把规模大的问题转换为规模小的相似的子问题
• B、把规模小的问题转换为规模大的相似的子问题
• C、把问题转为程序
• D、其它三项都不对

正确答案:A

第8题：

第9题：

第10题：

第11题：

第12题：

第13题：

（）方法是一种将复杂问题变换为比较简单的子问题，子问题再转换为更简单的子问题，最终将问题转换为对本原问题的知识表示方法。

正确答案:问题规约

第14题：

出自于“平衡子问题”的思想，通常分治法在分割原问题，形成若干子问题时，这些子问题的规模都大致（）。

正确答案:相同

第15题：

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

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

第16题：

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

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

正确答案:C

第17题：

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

• A、贪心法
• B、分治法
• C、动态规划法
• D、回朔法

正确答案:C

第18题：

将一个较大规模的问题分解为较小规模的子问题，求解子问题、合并子问题的解得到整个问题的解的算法是（）。

• A、贪心法
• B、分治法
• C、动态规划法
• D、回朔法

正确答案:B

第19题：

递归的基本思想是（）

• A、把规模大的问题转化为规模小的相似的子问题来解决。
• B、把规模小的问题转化为规模大的相似的子问题来解决。
• C、把规模大的问题转化为规模小的不同的子问题来解决。
• D、把规模小的问题转化为规模大的不同的子问题来解决。

正确答案:A

第20题：

第21题：

第22题：

第23题：

第24题：