第1题
对于求取两个长度为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.分支—限界
第2题
对于求取两个长度为n的字符串的最长公共子序列问题,利用(41)策略可以有效地避免子串最长公共子序列的重复计算,得到时间复杂度为O(n2)的正确算法。
A.贪心
B.分治
C.分支-限界
D.动态规划
第3题
问题描述:给定2个长度分别为n和m的序列x[0...n-1]和y[0...m-1],以及d个约束字符串多子串排斥约束的最长公共子序列问题就是要找出x和y的不含为其子串的最长公共子序列
算法设计:设计一个算法,找出给定序列x和y的不含为其子串的最长公共子序列.
数据输入:重文件input.txt提供输入数据.文件的第1行中给出正整数d,表示约束字符串个数.接下来的2行分别给出序列x和y.最后d行的每行给出一个约束字符串.
结果输出:将计算出的x和y的不含为其子串的最长公共子序列输出到文件output.txt中.文件的第1行输出最长公共子序列.第2行输出最长公共子序列的长度.
第4题
算法设计:设计一个算法,找出给定序列x和y的包含s为其子串的最长公共子序列.
数据输入:由文件input.txt提供输入数据.文件的第1行中给出正整数,分别表示给定序列x、y和约束字符串s的长度.接下来的3行分别给出序列x、y和约束字符串s.
结果输出:将计算出的x和y的包含s为其子串的最长公共子序列的长度输出到文件output.txt中.
第5题
给定两个长度分别为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中.
第7题
给定1个长度为n的字符串x,最长回文子串问题就是要找出X中长度最长的回文了串.例如,如果给定的字符串X=bbacababa,则子串bacab是X的一个最长的回文子串,它的长度是5.
算法设计:设计一个算法,找出给定字符串X的最长回文子串.
数据输入:由文件input.txt提供输入数据.文件的第1行中给出字符串X.
结果输出:将计算出的字符串X的最长回文子串输出到文件output.txt中.文件的第1行是最长回文子串的长度.文件的第2行是最长回文子串.
第9题
在最长公共子串问题的递推式中,表示____
A、和是否相等
B、和中以或结尾的最长公共子串的长度
C、和中的最长公共子串的长度
D、和中以和结尾的最长公共子串的长度
为了保护您的账号安全,请在“上学吧”公众号进行验证,点击“官网服务”-“账号验证”后输入验证码“”完成验证,验证成功后方可继续查看答案!