首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列说明和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
114
问题
阅读下列说明和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
软件设计师下午应用技术考试
软考中级
相关试题推荐
VPN使用的隧道协议可以有那几类,分别有哪些协议?VPN路由器配置如下,请解释画线部分含义。Vpdn-group1(1)Accept-dialinprotocol12tpvirtual-template1terminate
阅读以下说明,回答问题。【说明】网络地址转换(NAT)的主要目的是解决IP地址短缺问题以及实现TCP负载均衡等。在如图5-5所示的设计方案中,与Internet连接的路由器采用网络地址转换。【问题】请根据路由器的NAT表和
阅读以下有关网络接入方案的说明,回答问题1~3。【说明】某单位己完成了主干网络的建设任务,现在需要对其职工住宅区的用户接入主干网的技术方案作选型设计。职工住宅已有的通信条件是:(1)电话线(2)电视铜缆。在不重新布线的前提下,以下5种技术方
简述本题中POP3服务的实现过程。要求:(1)仅屏蔽来自200.117.112.0网络的FTP数据信息;(2)仅屏蔽来自192.168.11.12主机对Internet的FTP数据信息请求。请填写完整相关信息,将(1)~(4)处
阅读以下关于网络地址转换(NAT)的技术说明,结合网络拓扑图回答问题1至问题3。【说明】网络地址转换(NAT)技术可用来缓解IP地址短缺问题和实现TCP负载均衡功能。动态地址翻译技术在子网外部使用少量的全局地址,通过路由器进行内部和外部地址的转换
在图4-8所示的无线接待室中WLAN采用的体系结构如图4-9所示,请将(1)~(3)空缺处填写完整IEEE802.11定义了无线局域网(WLAN)的两种工作模式,根据图4-8所示的网络拓朴结构可判断出该WLAN的工作模式是(4)。当前WLAN中主要使
网络负载平衡(NetworkLoadBalancing)的核心是位于网络适配器驱动和(1)之间的WLBS.SYS的筛选器驱动。它采用一种(2),根据传入客户端的(3),以统计方式将其映射到群集主机。当发现到达的数据包时,所有主机同时执行这种映射,以快速
阅读以下基于Windows2003操作系统服务器实施负载平衡策略的技术说明,根据要求回答问题1至问题5。【说明】随着各行业信息化建设的不断深入,对网络应用服务器的处理能力、高可用性提出了更高的要求。尤其是高度信息化的企业中,关键性网络服务已经成
在RAS上存在着两个RJ45的端口,分别为Console与AUX,请问这两个端口的用途是什么?(控制在100个字以内)在调用超级终端程序进行设备连接时,应该对设备的连接参数进行正确设置,参数主要包括串口数据传输率、数据位数。停止位数以及是否有奇偶校验。
随机试题
《拉奥孔》是______的雕塑作品。()
血吸虫病引起的肠道病变包括
女,56岁。剔牙后牙龈出血约1年。高血压病史10年,服用长效心痛定控制较平稳,从未牙周治疗。检查:全口口腔卫生差,牙石(++)~(+++),普遍龈乳头暗红肿大,半球形,覆盖牙面1/3,探诊易出血,漱后可止,PD4~8mm,多数牙I度松动,个别下前牙Ⅱ度松动
A.安氏Ⅰ类B.安氏Ⅱ类,Ⅰ分类C.安氏Ⅱ类,Ⅱ分类D.安氏Ⅲ类E.安氏Ⅲ类,亚类磨牙关系中性,前牙拥挤
患者,男性,38岁。因呼吸道感染伴咳嗽、发热到医院就诊,医嘱给予青霉素80万U肌内注射,每日2次。皮试后5分钟,患者出现胸闷、气急伴濒危感,面色苍白、出冷汗,患者可能发生
根据企业所得税法律制度的规定。下列各项中,属于不征税收入的有()。
保荐机构及其保荐代表人有权列席发行人的股东大会和股东会,但不得参加发行人的监事会。()
构成保险必须具备的要素包括()。
社会主义初级阶段的科学含义是()
下面关于PC机主板芯片组的叙述中,错误的是
最新回复
(
0
)