子问题之间不包含公共的子问题，这个条件涉及到分治法的效率。()

A．分治算法就是把一个问题分成多个相同或相似的子问题，再对简单的子问题求解，最后将子问题的解合并起来就是问题的解

B．一个问题分解出的子问题可以有特例，不和其它子问题一样

C．一个问题分解出的子问题之间可以包含公共的子子问题

D．快速排序使用的不是分治算法，是二分法

A.该问题的规模缩小到一定的程度就可以容易地解决

B.该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质

C.利用该问题分解出的子问题的解不可以合并为该问题的解

D.原问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题

分治法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相（)且与原问题相同。

对于求取两个长度为n的字符串的最长公共子序列问题，利用(41)策略可以有效地避免子串最长公共子序列的重复计算，得到时间复杂度为O(n2)的正确算法。

A．贪心

B．分治

C．分支-限界

D．动态规划

A.贪心

B.分治

C.分支—限界

D.动态规划

式识别中有广泛应用.其中最主要的应用是测量基因序列的相似性.在演化分子生物学的研究中发现,某个重要的DNA序列片段常出现在不同的物种中.在测量基因序列的相似性时,如果需要特别关注一个具体的DNA序列片段,就要考察带有子串排斥约束的最长公共子序列问题.这个问题可以具体表述如下.

给定两个长度分别为n和m的序列x[0...n-1|]和y[0...m-1],以及一个长度为p的约束字符串s[0...p-1].带有子串排斥约束的最长公共子序列问题就是要找出x和y的不包含s为其子串的最长公共子序列.例如,如果给定的序列x和y分别为AATGCCTAGGC和CGATCTGGAC.字符串s=TG时,子序列ATCTGGC是x和y的一个无约束的最长公共子序列,而不包含s为其子串的最长公共子序列是ATCGGC.

算法设计:设计一个算法,找出给定序列x和y的不包含s为其子串的最长公共子序列.

数据输入:由文件input.txt提供输入数据.文件的第1行中给出正整数,分别表示给定序列x和y及约束字符串s的长度.接下来的3行分别给出序列x、y和约束字符串s.

结果输出:将计算出的x和y的不包含s为其子串的最长公共子序列的长度输出到文件output.txt中.

A.分治

B.贪心

C.动态规划

D.分支一限界

对于求取两个长度为n的字符串的最长公共子序列(LCS)问题，利用(24)策略可以有效地避免子串最长公共子序列的重复计算，得到时间复杂度为O(n2)的正确算法。串 ＜1，0，0，1，O，1，0，1＞和＜0，1，0，1，1,0,1，1＞的最长公共子序列的长度为(25)。

A．分治

B．贪心

C．动态规划

D．分支—限界