首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列说明和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
92
问题
阅读下列说明和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);
}
【问题1】
根据以上说明和C代码,填充C代码中的空(1)~(4)。
选项
答案
(1)x[i-1]==y[j-1] (2)max=c[i][j] (3)c[i][j]=0 (4)i=maxi-max
解析
本题考查算法设计与分析和C语言实现算法的相关技术。
此类题目要求考生认真阅读题目,首先理解问题以及求解问题的算法思路。
根据题干说明,给出的问题具有最优子结构,考生应该能想到该题用动态规划或者贪心求解。一般在给出递归定义最优解时,已经比较清楚地给出要用动态规划方法,并且根据给出的C程序,可知以自底向上的方式进行计算,即先求小规模问题的,再求规模更大的问题的解。进入到C程序内部,函数lcs是计算c数组,并确定其最大的元素。在两重循环内,应该是递归公式的迭代求解过程,因此空(1)处填入“x[i-1]=y[j-1]”;若当前的最大长度小于c
[j],则应该更新当前最大长度,即空(2)处填入“max=c
[j]”;空(3)前面是else与if对应,即是x[i-1]≠y[j-1]的情况,根据递归式此处填入“c
[j]=0”;函数printLCS是根据函数lcs计算的结果输出最长公共子串,长度为max,在串x中的最后位置是maxi,而在串y中的最后位置是maxj,因此,空(4)填入“i=maxi—max”。
转载请注明原文地址:https://kaotiyun.com/show/7dDZ777K
本试题收录于:
软件设计师下午应用技术考试题库软考中级分类
0
软件设计师下午应用技术考试
软考中级
相关试题推荐
阅读以下关于在ISDN网中应用点对点协议(PPP)和按需拨号路由(DDR)技术的说明,结合网络拓扑图回答问题1至问题4。【说明】综合数字业务网(ISDN)由数字电话和数据传输服务两部分组成,提供基本速率接口(BRI)和基群速率接口(PRI)两种服
根据你的网络工程经验,请用250字以内的文字简要描述该21层教学综合大楼网络层次结构设计的要点。(不要求画图)该21层教学综合大楼网络规则方案不仅要体现所设计的网络能满足现有及未来几年信息系统的应用需求,还需具有较高的平均无故障时间和尽可能低的平均故障
阅读以下说明,将(n)的含义填入对应栏内。[说明]电子邮件是Internet中应用最广泛的服务,因此安装和配置一个高效与满足实际需求的电子邮件系统是每一个系统管理员的奋斗的目标之一,Linux的出现为构建低成本的、高效的电子邮件服务器提供了
如果ping127.0.0.1(本地循环地址),如果该地址无法Ping通,则说明了是什么原因?什么命令是一个监控TCP/IP网络的实用的工具,它可以显示实际的网络连接以及每一个网络接口设备的状态信息?什么命令是把网卡物理地址与IP静态地址捆绑在一起?
网络维护是网络管理中一项很重要的工作。由于网络协议和网络设备的复杂性,许多故障解决起来绝非像解决单机故障那么简单。网络故障的定位和排除,既需要长期的知识和经验积累,也需要一系列的软件和硬件工具,这样才能解决我们在学习或工作中遇到的网络故障。
阅读以下说明,回答问题1至问题3。【说明】Plug-gw是Linux配置中常带的通用代理程序,可用来代理POP3、HTTP等应用层服务。附图3为某网络结构图,内部网段上有一台POP3服务器和一台FTP服务器。代理服务器中使用ipchains包过滤
在图4-8所示的无线接待室中WLAN采用的体系结构如图4-9所示,请将(1)~(3)空缺处填写完整请将以下(11)~(14)空缺处的内容填写完整,并帮助郭工程师解释产生以下网络故障的原因。该网络建成后一直使用正常,但最近发现无线覆盖区域A、B
网络负载平衡(NetworkLoadBalancing)的核心是位于网络适配器驱动和(1)之间的WLBS.SYS的筛选器驱动。它采用一种(2),根据传入客户端的(3),以统计方式将其映射到群集主机。当发现到达的数据包时,所有主机同时执行这种映射,以快速
请指出图1-12中(1)空缺处传输的是模拟信号,还是数字信号?在图1-12所示的网络拓扑图中,欲使内部网具有构造虚拟网的功能,图中(5)空缺处的交换机应具有哪些功能?
随机试题
肝转移瘤“靶”征在T2加权像上表现的外晕环的病理基础是
简述托马斯二维模式的妥协策略的应用场合。
瞳仁扩大可见于
关于女性月经初潮,下列知识不正确的是
患者,男,62岁。胸闷痛反复发作3年,加重半小时,现胸闷痛彻背,心慌,大汗出,四肢厥冷,面色唇甲青紫,脉沉微欲绝。证属
材料:某教师在“探究酵母菌细胞呼吸的方式”的教学活动中,先让学生结合生活经验提出假设,然后设计实验,进行实验,收集实验数据和资料。最后总结出酵母茵细胞在有氧和无氧不同条件下不同的呼吸方式。问题:教师应怎样组织学生进行这种学习?
影响非专利技术评估价值的因素包括技术的()。
Youaregoingtoreadalistofsubheadingsandatext.Choosethemostsuitablesubheadingfromthelist[A]to[G]foreachnu
A、Thedirectoristoobusytoattendtoyourproposalrightnow.B、Thedirectorwillhelpyoureadtheproposaltomorrowmorning
DearMs.Pascal,Iwouldappreciateverymuchanopportunitytomeetwithyouanddemonstratehowmyuniqueexperienceande
最新回复
(
0
)