2. 从业资格
  3. 【问题1】（8分） 根据题干说明，填充C代码中的空（1）-（4）。

【问题1】（8分） 根据题干说明，填充C代码中的空（1）-（4）。

admin2022-08-02  43
问题 【问题1】（8分）根据题干说明，填充C代码中的空（1）-（4）。【问题2】（4分）根据题干说明和C代码，算法采用的设计策略为（5）。算法的时间复杂度为（6）,（用O表示）。【问题3】(3分〉给定字符序列ACCGGUAGU，根据上述算法求得最大字符对数为（7）。
选项
答案
解析 【问题1】
（1）max=C[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[j-1]和C[t-1]+1+C[t+1][j-1]之间取最大值，在代码中可以看到if会判断max与C[t-1]+1+C[t+1][j-1]之间的大小，因此，max之前的赋值应该为C[j-1]，才能对二者进行比较，也就是说空（1）应该为max=C[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。
转载请注明原文地址:https://tihaiku.com/congyezige/2409593.html
本试题收录于： 中级 软件设计师题库软件水平考试初中高级分类

中级 软件设计师

软件水平考试初中高级

相关试题推荐
随机试题
最新回复(0)