2. 计算机
  3. 阅读下列说明和C代码，回答问题1至问题3，将解答写在答题纸的对应栏内。 【说明】 给定一个字符序列B=b1b2…bn，其中bi∈{A，C，G，U}。B上的二级结构是一组字符对集合S={(bi，bj)}，其中i，j∈{1，2，…，n}，并满足

阅读下列说明和C代码，回答问题1至问题3，将解答写在答题纸的对应栏内。 【说明】 给定一个字符序列B=b1b2…bn，其中bi∈{A，C，G，U}。B上的二级结构是一组字符对集合S={(bi，bj)}，其中i，j∈{1，2，…，n}，并满足

admin2019-10-08  56
问题 阅读下列说明和C代码，回答问题1至问题3，将解答写在答题纸的对应栏内。
    【说明】
    给定一个字符序列B=b1b2…bn，其中bi∈{A，C，G，U}。B上的二级结构是一组字符对集合S={(bi，bj)}，其中i，j∈{1，2，…，n}，并满足以下四个条件：
    (1)S中的每对字符是(A，U)，(U，A)，(C,G)和(GC)四种组合之一；
    (2)S中的每对字符之间至少有四个字符将其隔开，即f＜j-4；
    (3)S中每一个字符(记为bk)的配对存在两种情况：bk不参与任何配对；bk和字符bt配对，其中t＜k-4；
    (4)(不交叉原则)若(bi，bj)和(bk，bt)是S中的两个字符对，且i＜k，则i＜k＜j＜1不成立。
    B的具有最大可能字符对数的二级结构S被称为最优配对方案，求解最优配对方案中的字符对数的方法如下：
    假设用C(i，j)表示字符序列bibi+1…bj，的最优配对方案(即二级结构S)中的字符对数，则C(i，j)可以递归定义为：

下面代码是算法的C语言实现，其中
n：字符序列长度
B[]：字符序列
C[][]：最优配对数量数组
【C代码】
    #include＜stdio．h＞
    #include＜stdlib．h＞
    #define LEN 100
    ／*判断两个字符是否配对*／
    int isMatch(char a，char b)
    {
    if((a==’A’ &&b==’U’)‖(a==’U’&&b==’A’))
    return 1；
    if((a==’C’&&b==’G’)‖(a==’G’&&b==’C’))
    return 1；
    return 0：
    }
    ／*求最大配对数*／
    int RNA_2(char B[LEN]，int n) {
    int i，j，k，t；
    int max；
    int C[LEN][LEN]={0}；
    for(k=5；k＜=n．1；k++)
{
    for(i=1；i＜=n-k；i++)
    {
    j=i+k；
    ______(1)；
    for(______(2)；t＜=j-4；t++)
    {
    if(______(3))&& max＜C[t-1]+1+C[t+1][j-1])
    max=C[t-1]+1+C[t+1][j-1]；
    }
    C[j]=max；
    printf(’’c[％d][％d]=％d--’’，i，j，C[j])；
    }
}
  return ______(4)
}
根据题干说明和C代码，算法采用的设计策略为______(5)。
算法的时间复杂度为______(6)，(用O表示)。
选项
答案(5)动态规划 (6)O(n3)
解析
转载请注明原文地址:https://kaotiyun.com/show/ksxZ777K
本试题收录于： 软件设计师下午应用技术考试题库软考中级分类
0

软件设计师下午应用技术考试

软考中级

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