itgle.com
简述分治策略的基本思想。
题目
简述分治策略的基本思想。
相似考题
更多“简述分治策略的基本思想。”相关问题
-
第1题：
最优性原理的基本思想是，一个最优策略的子策略总是（）的。
正确答案:最优 -
第2题：
Strassen矩阵乘法是利用（）实现的算法。
- A、分治策略
- B、动态规划法
- C、贪心法
- D、回溯法
正确答案:A -
第3题：
简述归并排序算法和快速排序算法的分治方法。
正确答案: 1）归并排序的分治是将数组从中间分开，分别对前后来那个部分进行排序，将排序后的两个数组合并成整个数组的排序。这样分治为递归过程，直到一个元素时返回。
2）快速排序的分治是选取分割元素，以分割元素为界，将数组分成两部分，一部分小于分割元素，一部分大于分割元素，分别对两部分排序。 -
第4题：
哈夫曼编码可利用（）算法实现。
- A、分治策略
- B、动态规划法
- C、贪心法
- D、回溯法
正确答案:C -
第5题：
简述在cache失效率的策略中，编译优化分块策略的基本思想。
正确答案: 编译器把对数组的整行或整列访问改为按块进行，使得块内的访问具有较好的局部性，从而降低失效率。 -
第6题：
算法设计中的分治策略、贪心策略、动态规划策略、回溯策略以及分支定界策略的基本思想是什么？
正确答案: 分治策略的基本思想是把一个规模为n的问题划分为若干个规模较小、且与原问题相似的子问题，然后分别求解这些子问题，最后把各子结果合并得到整个问题的解。分解的子问题通常与原问题相似，所以可以递归地使用分治策略来求解。
贪心策略的基本思想是把一个整体最优问题分解为一系列的最优选择问题，决策一旦做出，就不能再更改。它是通过若干次的贪心选择而得出最优解（或较优解）的一种解题策略。
动态规划策略与贪心策略类似，将一个问题划分为重复的子问题，通过对相同子问题的求解来解决较大问题，即将一个问题的解决方案视为一系列决策的结果。不同的是，在贪心策略中，每采用一次贪心准则便做出一个不可撤回的决策，可能得不到问题的最优解。而在动态规划中，处理要按照某种规则进行选择，还要考察每个最优决策序列中是否包含一个最优子序列，目的是得到问题的最优解。
回溯策略也叫试探法，它的基本思想是：在一些问题求解进程中，先选择某一种可能情况向前探索，当发现所选用的试探性操作不是最佳选择，需退回一步，重新选择继续进行试探，直到找到问题的解或者证明问题无解。
分支定界策略也经常被称为分支限界策略，它的基本思想是：首先确定目标值的上下界，然后一边搜索一边剪掉空间树的某些不可能产生最优解的分支，提高搜索效率。 -
第7题：
孙中山“权能分治”理论的基本思想是把国家的大权分为“政权”和“能权”。
正确答案:错误 -
第8题：
简单描述分治法的基本思想。
正确答案:分治法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同；对这k个子问题分别求解。如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止；将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。 -
第9题：
问答题具有什么特征的问题适合用分治策略求解？正确答案： 三个特征：
（1）原问题可以分解成规模较小、相互独立和类型相同的子问题；
（2）子问题的规模缩小到一定的程度，就不需要再分解，可以容易地求解；
（3）所有子问题的解能够合并成原问题的解。解析： 暂无解析 -
第10题：
问答题算法设计中的分治策略、贪心策略、动态规划策略、回溯策略以及分支定界策略的基本思想是什么？正确答案： 分治策略的基本思想是把一个规模为n的问题划分为若干个规模较小、且与原问题相似的子问题，然后分别求解这些子问题，最后把各子结果合并得到整个问题的解。分解的子问题通常与原问题相似，所以可以递归地使用分治策略来求解。
贪心策略的基本思想是把一个整体最优问题分解为一系列的最优选择问题，决策一旦做出，就不能再更改。它是通过若干次的贪心选择而得出最优解（或较优解）的一种解题策略。
动态规划策略与贪心策略类似，将一个问题划分为重复的子问题，通过对相同子问题的求解来解决较大问题，即将一个问题的解决方案视为一系列决策的结果。不同的是，在贪心策略中，每采用一次贪心准则便做出一个不可撤回的决策，可能得不到问题的最优解。而在动态规划中，处理要按照某种规则进行选择，还要考察每个最优决策序列中是否包含一个最优子序列，目的是得到问题的最优解。
回溯策略也叫试探法，它的基本思想是：在一些问题求解进程中，先选择某一种可能情况向前探索，当发现所选用的试探性操作不是最佳选择，需退回一步，重新选择继续进行试探，直到找到问题的解或者证明问题无解。
分支定界策略也经常被称为分支限界策略，它的基本思想是：首先确定目标值的上下界，然后一边搜索一边剪掉空间树的某些不可能产生最优解的分支，提高搜索效率。解析： 暂无解析 -
第11题：
问答题简单描述分治法的基本思想。正确答案： 分治法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同；对这k个子问题分别求解。如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止；将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。解析： 暂无解析 -
第12题：
问答题因特网的当前地址分配策略是无类别域间选路。简述无类别域间选路的基本思想。正确答案： 无类别域间选路基本思想是取消地址的分类结构，取而代之的是允许以可变长分界的方式分配网络数。它支持路由聚合，可先知Internet主干路由器中必要路由信息的增长。“无类别”的意思是选路决策是基于整个32位IP地址的掩码操作。而不管其地址是A类，B类或是C类，这样能够将路由表的许多表项归并成更少的数目。解析： 暂无解析 -
第13题：
实现大整数的乘法是利用的算法（）
- A、贪心法
- B、动态规划法
- C、分治策略
- D、回溯法
正确答案:C -
第14题：
简述分治法的基本步骤。
正确答案: 分治法在每一层递归上都有三个步骤：
（1）分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；
（2）解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题；
（3）合并：将各个子问题的解合并为原问题的解。 -
第15题：
实现最长公共子序列利用的算法是（）。
- A、分治策略
- B、动态规划法
- C、贪心法
- D、回溯法
正确答案:B -
第16题：
因特网的当前地址分配策略是无类别域间选路。简述无类别域间选路的基本思想。
正确答案:无类别域间选路基本思想是取消地址的分类结构，取而代之的是允许以可变长分界的方式分配网络数。它支持路由聚合，可先知Internet主干路由器中必要路由信息的增长。“无类别”的意思是选路决策是基于整个32位IP地址的掩码操作。而不管其地址是A类，B类或是C类，这样能够将路由表的许多表项归并成更少的数目。 -
第17题：
具有什么特征的问题适合用分治策略求解？
正确答案: 三个特征：
（1）原问题可以分解成规模较小、相互独立和类型相同的子问题；
（2）子问题的规模缩小到一定的程度，就不需要再分解，可以容易地求解；
（3）所有子问题的解能够合并成原问题的解。 -
第18题：
简述分治法与动态规划法的异同。
正确答案: 分治法与动态规划法的相同点是：
将待求解的问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。
两者的不同点是：
适合于用动态规划法求解的问题，经分解得到的子问题往往不是互相独立的。而用分治法求解的问题，经分解得到的子问题往往是互相独立的。 -
第19题：
基于半联接的查询优化策略的基本思想是什么？
正确答案: 数据在网络中传输时，如果以整个关系传输，则传输数据量大，是一种冗余的做法，而实际上，在联接时并非每个数据都参与操作或有用。因此，考虑到不参与操作的值或无用的值不必经网络来回传输，则可以减少传输的数据量。 -
第20题：
填空题最优性原理的基本思想是，一个最优策略的子策略总是（）的。正确答案： 最优解析： 暂无解析 -
第21题：
问答题简述孙中山“权能分治”理论的基本内容。正确答案： 孙中山认为，理想的民主政治应是“政权”与“治权”分开，即人民对国家的管理权应与政府的治理权分开。关于“政权”，应掌握在人民手中，具体包括选举、罢免、创制、复决四个方面的权力。关于“治权”，应包括行政权、立法权、司法权、考试权、监察权等五个方面的职权。至于“政权”与“治权”的关系，孙中山指出，应该是“用人民的四个政权来管理政府的五个治权”。有了这种政权和治权，才可以造成万能政府，为人民谋幸福。解析： 暂无解析 -
第22题：
问答题简述分治法的基本步骤。正确答案： 分治法在每一层递归上都有三个步骤：
（1）分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；
（2）解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题；
（3）合并：将各个子问题的解合并为原问题的解。解析： 暂无解析 -
第23题：
判断题孙中山“权能分治”理论的基本思想是把国家的大权分为“政权”和“能权”。A对
B错
正确答案： 错解析： 暂无解析 -
第24题：
问答题简述在cache失效率的策略中，编译优化分块策略的基本思想。正确答案： 编译器把对数组的整行或整列访问改为按块进行，使得块内的访问具有较好的局部性，从而降低失效率。解析： 暂无解析