首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。 【说明】 计算两个字符串x和y的最长公共子串(Longest Common Substring)。 假设字符串x和字符串y的长度分别为m和n,用数组c的元素c[i][j
阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。 【说明】 计算两个字符串x和y的最长公共子串(Longest Common Substring)。 假设字符串x和字符串y的长度分别为m和n,用数组c的元素c[i][j
admin
2016-11-11
75
问题
阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。
【说明】
计算两个字符串x和y的最长公共子串(Longest Common Substring)。
假设字符串x和字符串y的长度分别为m和n,用数组c的元素c
[j]记录x中前i个字符和y中前j个字符的最长公共子串的长度。
c
[j]满足最优子结构,其递归定义为:
计算所有c
[j](O≤i≤m,0≤j≤n)的值,值最大的c
[j]即为字符串x和y的最长公共子串的长度。根据该长度即i和j,确定一个最长公共子串。
【C代码】
(1)常量和变量说明
x.y:长度分别为m和n的字符串。
c
[j]:记录x中前i个字符和y中前j个字符的最长公共子串的长度。
max:x和y的最长公共子串的长度。
maxi,maxj:分别表示x和y的某个最长公共子串的最后一个字符在x和y中的位置(序号)。
(2)C程序
#include
#include
int c[50][50];
int maxi;
int maxj;
int 1cs(char *x,int m,char *y,int n) {
int i,j;
int max=0;
maxi=0;
maxj=0;
for(i=0;i<=m;i++) c
[0]=0;
for(i=1;i<=n;i++) C[0]
=0;
for(i=1;i<=m;i++) {
for(j=1;j<=n;j++) {
if(___________(1)) {
c
[j]=C[i—1][j一1]+1;
if(max<c
[j]){
___________(2);
maxi=i;
maxj=j;
}
}
else ___________(3);
}
}
return max;
}
void printLCS(int max,char *x){
int i=0;
if(max==0) return;
for(___________(4);i<maxi;i++)
printf("%c",x
);
}
void main(){
char*x="ABCADAB";
cnar*y="BDCABA";
int max=0;
int m=strlen(x);
int n=strlen(y);
max=lcs(x,m,y,n);
printLCS(max,x);
}
【问题3】
根据题干说明和以上C代码,输入字符串x="ABCADAB",y="BDCABA",则输出为__________(7)。
选项
答案
(7)AB
解析
根据题干和C代码,计算出下表的值。
最大值为2。在计算过程中,我们记录第一个最大值,即表中阴影部分元素,因此得到最长公共子串为AB。
转载请注明原文地址:https://kaotiyun.com/show/OdDZ777K
本试题收录于:
软件设计师下午应用技术考试题库软考中级分类
0
软件设计师下午应用技术考试
软考中级
相关试题推荐
阅读以下说明,回答问题1、问题2、问题3和问题4,将解答填入对应栏内。[说明]ATM(AsynchronousTransferMode)顾名思义就是异步传输模式,是国际电信联盟ITU-T制定的标准。实际上在20世纪80年代中期,人们就已经
如果ping127.0.0.1(本地循环地址),如果该地址无法Ping通,则说明了是什么原因?在DOS状态下输入tracertwww.ciu.net.cn并执行后,经过一段时间等待,系统会反馈出很多IP地址。出现在最上方(第1条记录)的IP地址是什么
阅读以下说明,回答问题。【说明】网络地址转换(NAT)的主要目的是解决IP地址短缺问题以及实现TCP负载均衡等。在如图5-5所示的设计方案中,与Internet连接的路由器采用网络地址转换。【问题】请根据路由器的NAT表和
在RAS上存在着两个RJ45的端口,分别为“Console”与“AUX”,请问这两个端口的用途是什么?(控制在100个字以内)在调用超级终端程序进行设备连接时,应该对设备的连接参数进行正确设置,参数主要包括串口数据传输率、数据位数、停止位数以及是否有奇
阅读以下说明,回答问题1至问题3。【说明】Plug-gw是Linux配置中常带的通用代理程序,可用来代理POP3、HTTP等应用层服务。附图3为某网络结构图,内部网段上有一台POP3服务器和一台FTP服务器。代理服务器中使用ipchains包过滤
阅读以下说明,回答【问题1】~【问题4】,将解答填入答题纸的对应栏内。【说明】设有A、B、C、D四台主机都处在同一个物理网络中,A主机的IP地址是192.155.12.112,B主机的IP地址是192.155.12.120,C主机的IP地址是19
网络负载平衡(NetworkLoadBalancing)的核心是位于网络适配器驱动和(1)之间的WLBS.SYS的筛选器驱动。它采用一种(2),根据传入客户端的(3),以统计方式将其映射到群集主机。当发现到达的数据包时,所有主机同时执行这种映射,以快速
请指出图1-12中(1)空缺处传输的是模拟信号,还是数字信号?图1-12中(2)空缺处是什么设备?该设备在本宽带网络中完成哪些功能?
随机试题
患者,女,17岁。发热、咳嗽、心悸气短、活动明显受限5天,不能平卧、腹胀、尿少、食欲减退2天来院。自幼体弱,有反复呼吸道感染史。查体:体温38℃,血压130/85mmHg,半卧位,口唇明显发绀,颈静脉充盈,可见颈静脉搏动,右下肺叩浊,可闻支气管呼吸音及小水
患者,男,72岁。腰背部疼痛半年前来就诊。查体:肝肋下2cm,脾肋下3cm,多个腰椎骨压痛明显。实验室检查:Hb84g/L,白细胞4.6×109/L,血小板110×109/L,红细胞沉降率120mm/h,尿蛋白定性(-),24小时尿蛋白定量5g
某药店经营者为贪图利益而销售超过有效期的药品,结果造成患者服用后死亡的特别严重后果,依据《中华人民共和国刑法》,给经营者的刑罚是
对竣工时遗留的或试车中发现必须新增的安全、()保护措施,要安排投资和材料限期完成。
市场间价差套利是指针对同一交易所上市的不同种品种同一交割月份的合约进行价差套利。( )
下列各项中,应列入利润表“营业成本”项目的有()。
为避免游客走失,导游应()。
提出“白板说”的教育家是
马克思和列宁设想过的对资产阶级的和平赎买能够在中国实现的原因是
某二叉树中度为2的结点有10个,则该二叉树中有()个叶子结点。
最新回复
(
0
)