首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列说明和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
76
问题
阅读下列说明和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
软件设计师下午应用技术考试
软考中级
相关试题推荐
如果ping127.0.0.1(本地循环地址),如果该地址无法Ping通,则说明了是什么原因?什么命令是一个监控TCP/IP网络的实用的工具,它可以显示实际的网络连接以及每一个网络接口设备的状态信息?什么命令是把网卡物理地址与IP静态地址捆绑在一起?
阅读以下说明、Java源程序和运行测试部分1.HTTP协议。●HTTP请求消息示例:GET/index,htmlHTTP/1.1Accept:image/gif,image/jpeg,*/Acc
在图4-8所示的无线接待室中WLAN采用的体系结构如图4-9所示,请将(1)~(3)空缺处填写完整请将以下(11)~(14)空缺处的内容填写完整,并帮助郭工程师解释产生以下网络故障的原因。该网络建成后一直使用正常,但最近发现无线覆盖区域A、B
阅读以下电子商务公司应用无线局域网的技术说明,根据要求回答问题1至问题5。【说明】由于市场的不断扩大,A电子商务公司客户数量日益增多。现有的网络已不能满足信息发展的需求,考虑到既要同时满足网络扩容顺利进行及公司日常工作的正常开展,又要保证目前土建
阅读以下某单位宽带网络接入的技术说明,根据要求回答问题1至问题6。【说明】接入网(AN)泛指用户网络接口(UNI)与业务节点接口(SNI)间实现传送承载功能的实体网络。其目标是建立一种标准化的接,方式,以一个可监控的接入网络,使用户能够获得话音、
在RAS上存在着两个RJ45的端口,分别为Console与AUX,请问这两个端口的用途是什么?(控制在100个字以内)在第4步中,进入虚拟操作台后,在IOS环境下输入了如下的配置,请解释(1)~(4)处的标有下划线部分配置命令的含义(“◇”后为配置内容
在RAS上存在着两个RJ45的端口,分别为Console与AUX,请问这两个端口的用途是什么?(控制在100个字以内)在调用超级终端程序进行设备连接时,应该对设备的连接参数进行正确设置,参数主要包括串口数据传输率、数据位数。停止位数以及是否有奇偶校验。
随机试题
患者,男性,35岁。因与他人打架,右上臂被刀多处砍伤,右手活动受限。查体:右肘关节活动可,右拇、示、中指不能屈曲,拇指不能外展和桡侧三个半手指掌侧均无感觉。该患者可能损伤
流感病毒最易变异的成分是
局部治疗唇疱疹最有效的药物是
下列何种先心病可出现周围血管征
有关孕期卫生下述哪项不正确()。
求取建筑物折旧的方法很多,以下正确的是()。
支票超过提示付款期限的,付款人可不预付款,出票人对此不承担责任。()
下列关于定期存款的说法,不正确的是()。
某公司与市政府机关共同使用一栋楼房,该楼房占地面积2000平方米,该公司与市政府的占用比例为4:1。当年年初,该公司购买房产价格为4100000元。企业拥有载货汽车10辆,每辆自重5吨。大客车4辆,均为45座(该地车船税的年税额:载重汽车为每吨20元,乘人
追求
最新回复
(
0
)