【问题1】（8分）
根据题干说明，填充C代码中的空（1）-（4）。
【问题2】（4分）
根据题干说明和C代码，算法采用的设计策略为（5）。
算法的时间复杂度为（6）,（用O表示）。
【问题3】(3分〉
给定字符序列ACCGGUAGU，根据上述算法求得最大字符对数为（7）。
正确答案及解析
正确答案
解析
【问题1】
（1）max=C[i][j-1]
（2）t=i
（3）isMatch(B[t],B[j])，或isMatch(B[t],B[j])==1，或与其等价的形式
（4）C[1][n]
【问题2】
采用的算法策略：动态规划法
时间复杂度：O(n3)
【问题3】
最大字符对数：2
本题考查的是用动态规划法，以非递归方式实现。
根据题干，配对要求：
（1）满足四种组合之一；
（2）配对的2个字符间距至少有4个字符；
（3）若字符已配对，则其他配对不再考虑，也就是说1个字符不能配对2次，比如ACCCCUCCCCA，只有1组配对AU，U不能再与后面的A形成第2组配对；
（4）不交叉，2组配对字符位置能交叉，比如ACCCCCUUUUG，只有1组配对AU，CG与AU有交叉不能形成配对。
【问题1】
对于问题1代码填空，主要根据题干描述和代码上下文进行推导。
根据代码上下文可知，在整段代码中，缺少对变量max和t赋初值，这两个初值的赋值，应该填在空（1）和空（2）中，一般t作为循环变量，在for中进行赋值。
代码中有三层嵌套for循环。
其中第一层for循环，变量为k，取值范围从5到n-1，从题干描述，我们可以看到对于整个比较过程，要求字符对的位置相差大于4，因此此处的k值是字符对下标的差值；
第二层for循环，变量为i，取值范围从1到n-k，从题干描述，我们可以得出i是字符对较小的下标；
第三层for循环，变量为t，取值范围需要赋初值，并且t＜=j-4（此处有异议，与题干描述中的>4有不符，但不影响本题解题过程），从题干描述和递归式可以看到，t是中间字符下标，用来划分子问题的，并且从递归式我们可以得出，t的最小值应该从i开始，因此空（2）为t=i；
在第二层for循环内部，有j=i+k，根据代码和题干描述，可以得出j是字符对较大的下标，根据i和k的取值，可以看到j的取值范围为从6到n-1，对于空（1）作为max的初始赋值，又根据递归式，可以看到max应该在C[i][j-1]和C[i][t-1]+1+C[t+1][j-1]之间取最大值，在代码中可以看到if会判断max与C[i][t-1]+1+C[t+1][j-1]之间的大小，因此，max之前的赋值应该为C[i][j-1]，才能对二者进行比较，也就是说空（1）应该为max=C[i][j-1]。
空（3）在if判断中作为判断条件，根据递归式的条件和代码上下文，此处缺少字符匹配的判断，题干描述字符下标从1开始，因此，在比较过程中，实际比较的应该为B[t]和B[j]位置的字符，空（3）应该填写isMatch(B[t],B[j)，或isMatch(B[t],B[j])==1，或与其等价的形式。
空（4）作为整个函数的返回值，因此空（4）应该为C[1][n]为最终结果。
【问题2】
本题采取的是动态规划的策略，代码为三层嵌套循环时间复杂度为k*i*t，由于k的取值范围是6~n-1，i的取值范围是1~n-5，t的取值范围是1~n-5，都是与n的取值相关，因此本题的时间复杂度为O(n3)。
【问题3】
对于本题最大字符匹配对数，根据题干描述或代码推导，可以看到，字符序列ACCGGUAGU的最大匹配情况为，(b1,b6)，(b1,b9)或(b2,b8)，(b3,b8)，这两种情况的最大匹配对数都为2，因此本题答案（7）空为2。
包含此试题的试卷
你可能感兴趣的试题
-
- A.V(S2)和P(S4)
- B.P(S2)和V(S4)
- C.P(S2)和P(S4)
- D.V(S2)和V(S4)
- 查看答案
-
- A.V（S1）P（S2）和V（S3）
- B.P（S1）V（S2）和V（S3）
- C.V（S1）V（S2）和V（S3）
- D.P（S1）P（S2）和V（S3）
- 查看答案
-
- A.P（S4）和V（S4）V（S5）
- B.V（S5）和P（S4）P（S5）
- C.V（S3）和V（S4）V（S5）
- D.P（S3）和P（S4）V（P5）
- 查看答案
-
- A.P(S3)和V(S4)V(S5)
- B.V(S3)和P(S4)P(S5)
- C.P(S3)和P(S4)P(S5)
- D.V(S3)和V(S4)V(S5)
- 查看答案
-
- A.P（S2）和P（S4）
- B.P（S2）和V（S4）
- C.V（S2）和P（S4）
- D.V（S2）和V（S4）
- 查看答案