首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列说明和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},并满足
admin
2019-10-08
47
问题
阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。
【说明】
给定一个字符序列B=b
1
b
2
…b
n
,其中b
i
∈{A,C,G,U}。B上的二级结构是一组字符对集合S={(b
i
,b
j
)},其中i,j∈{1,2,…,n},并满足以下四个条件:
(1)S中的每对字符是(A,U),(U,A),(C,G)和(GC)四种组合之一;
(2)S中的每对字符之间至少有四个字符将其隔开,即f<j-4;
(3)S中每一个字符(记为b
k
)的配对存在两种情况:b
k
不参与任何配对;b
k
和字符b
t
配对,其中t<k-4;
(4)(不交叉原则)若(b
i
,b
j
)和(b
k
,b
t
)是S中的两个字符对,且i<k,则i<k<j<1不成立。
B的具有最大可能字符对数的二级结构S被称为最优配对方案,求解最优配对方案中的字符对数的方法如下:
假设用C(i,j)表示字符序列b
i
b
i+1
…b
j
,的最优配对方案(即二级结构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(n
3
)
解析
转载请注明原文地址:https://kaotiyun.com/show/ksxZ777K
本试题收录于:
软件设计师下午应用技术考试题库软考中级分类
0
软件设计师下午应用技术考试
软考中级
相关试题推荐
为了便于用户下载相关资料,特安装一台FTP服务器,其服务器端软件是Serv-U,假如要增加一个名为CIU10009的用户,对应目录为D盘,且要求加密,在图6-4中怎么设置?假如想将某用户在设咸FTP服务器管理员,其用户名称不变,请问在“Privileg
指出上述解决方案存在什么问题?需要增加什么设备?如何连接?若在该局域网实现VLAN,路由器将起什么作用?
阅读以下基于WindowsServer2003操作系统部署NAT服务器的技术说明,根据要求回答问题1至问题5。【说明】某企业内部局域网通过ISP提供的ADSL宽带线路与Internet相连,ISP分配的公网IP地址为202.217.6.32/
通常,在该图书馆架构无线局域网(WLAN)的设计流程需要经过以下6个阶段:A.设备软硬件安装、调试B.确定无线局域网物理结构C.确定无线局域网逻辑结构D.进行需求分析和现场调研E.验收测试和维护F.进行设备产
通常,在该图书馆架构无线局域网(WLAN)的设计流程需要经过以下6个阶段:A.设备软硬件安装、调试B.确定无线局域网物理结构C.确定无线局域网逻辑结构D.进行需求分析和现场调研E.验收测试和维护F.进行设备产
某大学机房网络要配置一台DHCP服务器,实验室的计算机自动分配IP地址。学生通过DHCP服务器上Internet,请回答以下问题。
请分别说出(1)与(2)的设备名称。假设有一个50M的文件从终端用户上传至服务器,需要的最短时间是多少?
设计该宽带路由器的多任务嵌入式实时操作系统时,由于多个任务均可能要求占用CPU这个关键资源,因此CPU的任务管理是一个非常重要的设计内容。在该实时操作系统中,任务作为占用资源的基本单位,总共有5个状态:休眠状态、就绪状态、运行状态、等待或挂起状态和中断服务
阅读以下关于HFC宽带接入Internet网的技术说明,根据要求回答问题1至问题4。【说明】混合光纤同轴电缆网(HFC网)应用数字和模拟传输技术,综合接入Internet、电话、模拟和数字广播电视、数字交互业务等多种业务,将计算机网络、有线电视网
随机试题
AUnlikeAmericanswhoseemBtoprefercoffee,theEnglishCdrinksDagreatdealoftea.
电路如图7-29所示,开关S闭合前,L和C均未储能;S闭合后瞬间,电感两端的电压uC(0+)为()V。
政府对金融市场实施()。
合理的组织设计不宜使管理层次太多,否则会出现()等不足。
【背景资料】某机电安装公司中标了某铸造厂以保本价为目标的机电安装工程。合同额1980万元,工程材料费占工程造价的60%,工程设备由业主提供,按照合同规定,若当地主管部门有明确的调价规定可以执行。该公司注重项目成本各阶段的控制,给项目经理部下达目标
平均收益(AR),指厂商销售每一个单位产品平均得到的收入,即单位产品的价格。当某厂商的平均收益(AR)曲线从水平线变为向右下方倾斜的曲线时说明()。
从众
孔颖达,字仲达,冀州衡水人。八岁就学,诵记日千余言,暗记《三礼义宗》。及长,明服氏《春秋传》、郑氏《尚书》、《诗》、《礼记》、王氏《易》,善属文,通步历。尝造同郡刘焯,焯名重海内,初不之礼,及请质所疑,遂大畏服。隋大业初,举明经高第,授河内郡博士
曾经有许多人认为,暴饮暴食是肥胖的原因,但是一项新的调查研究否定了这种看法。研究者发现,无所事事才是肥胖的根本原因。以下各项如果为真,最能支持上述新发现的是:
Carforsale(SUV)ExampleAgeofcar:justunder10yearsoldColour:【L1】________Mileage:【L2】________Previousownerwasa【L3】
最新回复
(
0
)