首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列说明和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
88
问题
阅读下列说明和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);
}
【问题2】
根据题干说明和以上C代码,算法采用了__________(5)设计策略。
分析时间复杂度为__________(6)(用O符号表示)。
选项
答案
(5)动态规划 (6)O(m×n)或O(mn)
解析
根据【问题1】中的分析,已知算法采用动态规划技术,算法的时间复杂度分析过程为:
(1)函数lcs中,有两个一重循环和一个两重循环,时间复杂度为m+n+mn;
(2)函数printiLCS中,有一个一重循环,时间复杂度为m(或n)。
故算法的时间复杂度为O(mn)。
转载请注明原文地址:https://kaotiyun.com/show/KdDZ777K
本试题收录于:
软件设计师下午应用技术考试题库软考中级分类
0
软件设计师下午应用技术考试
软考中级
相关试题推荐
阅读以下关于在ISDN网中应用点对点协议(PPP)和按需拨号路由(DDR)技术的说明,结合网络拓扑图回答问题1至问题4。【说明】综合数字业务网(ISDN)由数字电话和数据传输服务两部分组成,提供基本速率接口(BRI)和基群速率接口(PRI)两种服
阅读以下关于校园网组建的技术说明,根据要求回答问题1至问题4。【说明】某学校新建一栋21层教学综合大楼,楼层两端相距100m,距一端50m处有一弱电竖井,弱电竖井贯穿每层的弱电室。每层楼均有100个信息点(所有信息点要求具有100Mb/s的数据传
解释图10-2中的PVC和SVC。以下是LANE工作过程,其顺序已乱,请排序。①LEC接着便向其他LEC广播这个响应。②在地址表中含有被称为MAC地址的LEC向LEC作出响应。③LES发送多点组播至网络上的其他LEC。④
阅读以下关于网络地址转换(NAT)的技术说明,结合网络拓扑图回答问题1至问题3。【说明】网络地址转换(NAT)技术可用来缓解IP地址短缺问题和实现TCP负载均衡功能。动态地址翻译技术在子网外部使用少量的全局地址,通过路由器进行内部和外部地址的转换
在图4-8所示的无线接待室中WLAN采用的体系结构如图4-9所示,请将(1)~(3)空缺处填写完整IEEE802.11定义了无线局域网(WLAN)的两种工作模式,根据图4-8所示的网络拓朴结构可判断出该WLAN的工作模式是(4)。当前WLAN中主要使
阅读以下电子商务公司应用无线局域网的技术说明,根据要求回答问题1至问题5。【说明】由于市场的不断扩大,A电子商务公司客户数量日益增多。现有的网络已不能满足信息发展的需求,考虑到既要同时满足网络扩容顺利进行及公司日常工作的正常开展,又要保证目前土建
阅读以下某单位宽带网络接入的技术说明,根据要求回答问题1至问题6。【说明】接入网(AN)泛指用户网络接口(UNI)与业务节点接口(SNI)间实现传送承载功能的实体网络。其目标是建立一种标准化的接,方式,以一个可监控的接入网络,使用户能够获得话音、
在RAS上存在着两个RJ45的端口,分别为Console与AUX,请问这两个端口的用途是什么?(控制在100个字以内)在调用超级终端程序进行设备连接时,应该对设备的连接参数进行正确设置,参数主要包括串口数据传输率、数据位数。停止位数以及是否有奇偶校验。
随机试题
偏好;更喜欢n.p______
A.远距分泌B.旁分泌C.自分泌D.神经分泌E.腔分泌促肾上腺皮质激素的作用方式是
下列交感神经对心脏作用的描述,哪一项是错误的
患者,青年男性,咳嗽痰少,痰中带血,血色鲜红,两颧红赤,口干咽燥,潮热盗汗,舌质红,脉细数。乃肺痨阴虚肺热咳血。咳血量甚多,纯血鲜红者,为火热内迫血分,治疗当选方
病人因四肢关节痛,口服布洛芬3次/日,3日后出现上腹不适,恶心,呕吐。呕吐物中少量咖啡样物。既往时有胃部不适,下列处理不妥的是
患者告诉医生,每当他听到自来水的流动声时,就同时听到有人议论他的声音当某一感觉器官处于功能活动状态时,出现涉及另一感觉器官的幻觉
钢-混凝土组合梁混凝土桥面应全断面连续浇筑,以下浇筑顺序正确的是()。
下列关于城建税的说法,正确的是()。
由于对专业收藏知识的匮乏,许多人把仿品当真品收藏,造假卖假、恶意推高收藏品价格的现象________,投机成风。此外,“买假不退”在收藏界已经是________的规矩,卖家没有告知真伪的义务,因此买家如不能分辨真伪买了假货,自认倒霉竟也似乎合乎行规,这更助
举例说明内隐联想测验的基本程序和原理。
最新回复
(
0
)