首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列说明和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
55
问题
阅读下列说明和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
软件设计师下午应用技术考试
软考中级
相关试题推荐
根据你的网络工程经验,请用250字以内的文字简要描述该21层教学综合大楼网络层次结构设计的要点。(不要求画图)该21层教学综合大楼网络规则方案不仅要体现所设计的网络能满足现有及未来几年信息系统的应用需求,还需具有较高的平均无故障时间和尽可能低的平均故障
阅读以下说明,将(n)的含义填入对应栏内。[说明]电子邮件是Internet中应用最广泛的服务,因此安装和配置一个高效与满足实际需求的电子邮件系统是每一个系统管理员的奋斗的目标之一,Linux的出现为构建低成本的、高效的电子邮件服务器提供了
阅读以下说明,回答问题。【说明】网络地址转换(NAT)的主要目的是解决IP地址短缺问题以及实现TCP负载均衡等。在如图5-5所示的设计方案中,与Internet连接的路由器采用网络地址转换。【问题】请根据路由器的NAT表和
简述本题中POP3服务的实现过程。要求:(1)仅屏蔽来自200.117.112.0网络的FTP数据信息;(2)仅屏蔽来自192.168.11.12主机对Internet的FTP数据信息请求。请填写完整相关信息,将(1)~(4)处
阅读以下基于Windows2003操作系统服务器实施负载平衡策略的技术说明,根据要求回答问题1至问题5。【说明】随着各行业信息化建设的不断深入,对网络应用服务器的处理能力、高可用性提出了更高的要求。尤其是高度信息化的企业中,关键性网络服务已经成
请指出图1-12中(1)空缺处传输的是模拟信号,还是数字信号?在图1-12所示的网络拓扑图中,欲使内部网具有构造虚拟网的功能,图中(5)空缺处的交换机应具有哪些功能?
请指出图1-12中(1)空缺处传输的是模拟信号,还是数字信号?图1-12中(2)空缺处是什么设备?该设备在本宽带网络中完成哪些功能?
在RAS上存在着两个RJ45的端口,分别为Console与AUX,请问这两个端口的用途是什么?(控制在100个字以内)在第4步中,进入虚拟操作台后,在IOS环境下输入了如下的配置,请解释(1)~(4)处的标有下划线部分配置命令的含义(“◇”后为配置内容
在RAS上存在着两个RJ45的端口,分别为Console与AUX,请问这两个端口的用途是什么?(控制在100个字以内)在调用超级终端程序进行设备连接时,应该对设备的连接参数进行正确设置,参数主要包括串口数据传输率、数据位数。停止位数以及是否有奇偶校验。
随机试题
下列哪项不是呼吸衰竭导致肺性脑病的机制
33冲双流程旋转式压片机旋转一圈可压出()
已知:Fe3++e-=Fe+,=0.77VCu2++2e-=Cu,=0.34V,Fe2++2e-=Fe,=-0.44V,Al3++3e-=Al,=-1.66V。则最强的还原剂是()。
地下、半地下和高层汽车库、甲、乙类物品运输车的汽车库、修车库和1类汽车库、修车库的耐火等级不低于()。
决定被评估资产评估值的最基础的因素是()。
根据有关规定,申请上市的封闭式基金,基金募集金额不得低于()亿元。
2,11,45,136,()
男同学小陈平时自己散漫、学习不认真,一天在课堂上用手机给班上的女同学发短信“曾某,我爱你”。被上课的王老师发现收缴,并将小陈的短信向全班同学宣读,同时指责“思想堕落,道德败坏”。下课后小陈要求王老师归还手机,王老师说这是罪证不能归还,要交学校教导处。关于王
若矩阵的秩为2,求t的值.
Cisco路由器执行showaccess—list命令显示如下一组控制列表信息StandardIPaccesslist30deny127.0.0.0.wildcardbits0.255.255.255deny
最新回复
(
0
)