首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列说明和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
77
问题
阅读下列说明和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
软件设计师下午应用技术考试
软考中级
相关试题推荐
阅读以下说明,将(n)的含义填入对应栏内。[说明]电子邮件是Internet中应用最广泛的服务,因此安装和配置一个高效与满足实际需求的电子邮件系统是每一个系统管理员的奋斗的目标之一,Linux的出现为构建低成本的、高效的电子邮件服务器提供了
网络维护是网络管理中一项很重要的工作。由于网络协议和网络设备的复杂性,许多故障解决起来绝非像解决单机故障那么简单。网络故障的定位和排除,既需要长期的知识和经验积累,也需要一系列的软件和硬件工具,这样才能解决我们在学习或工作中遇到的网络故障。
VPN使用的隧道协议可以有那几类,分别有哪些协议?VPN路由器配置如下,请解释画线部分含义。Vpdn-group1(1)Accept-dialinprotocol12tpvirtual-template1terminate
在RAS上存在着两个RJ45的端口,分别为“Console”与“AUX”,请问这两个端口的用途是什么?(控制在100个字以内)在第四步中,进入虚拟操作台后,在IOS环境下输入了如下的配置,请解释(1)~(4)处的标有下划线部分配置命令的含义(“◇”后为
阅读以下有关网络设备安装与调试的叙述,分析设备配置文件,回答问题1至问题3。现以一台远程访问服务器(RemoteAccessServer,RAS)Cisco2509、RJ45为例来说明。第一步,准备安装与调试所需的设备,主要包括RAS
阅读以下说明,回答问题1至问题3。【说明】Plug-gw是Linux配置中常带的通用代理程序,可用来代理POP3、HTTP等应用层服务。附图3为某网络结构图,内部网段上有一台POP3服务器和一台FTP服务器。代理服务器中使用ipchains包过滤
阅读以下家庭HFC宽带接入Internet网的技术说明,结合网络连接拓扑图,根据要求回答问题1至问题5。【说明】混合光纤一同轴电缆网(即HFC网)将光纤敷设到小区,再通过光电转换节点,利用CATV的总线式同轴电缆网连接到用户,从而为用户提供Int
阅读以下关于网络地址转换(NAT)的技术说明,结合网络拓扑图回答问题1至问题3。【说明】网络地址转换(NAT)技术可用来缓解IP地址短缺问题和实现TCP负载均衡功能。动态地址翻译技术在子网外部使用少量的全局地址,通过路由器进行内部和外部地址的转换
在图4-8所示的无线接待室中WLAN采用的体系结构如图4-9所示,请将(1)~(3)空缺处填写完整请将以下(11)~(14)空缺处的内容填写完整,并帮助郭工程师解释产生以下网络故障的原因。该网络建成后一直使用正常,但最近发现无线覆盖区域A、B
阅读以下某单位宽带网络接入的技术说明,根据要求回答问题1至问题6。【说明】接入网(AN)泛指用户网络接口(UNI)与业务节点接口(SNI)间实现传送承载功能的实体网络。其目标是建立一种标准化的接,方式,以一个可监控的接入网络,使用户能够获得话音、
随机试题
芒硝的功效是
霍乱弧菌最重要的致病物质是
癃闭的病位虽在膀胱,但与本病关系密切的脏腑还有
A、阻断中枢5一HT受体B、使突触间隙的NA浓度下降C、阻断中枢多巴胺D2受体D、抑制中枢PG合成E、抑制外周PG合成解热镇痛药的解热作用机制是
对全身作用的栓剂说法错误的是
应是执业药师应具有药师以上技术职称,或具有中专(含)以上药学或相关专业的学历
单机试运行负责组织的单位是()。
《中华人民共和国建筑法》规定,( )可以规定实行强制监理的建筑工程的范围。
丙公司2017年12月31日的资产负债表显示:资产总额年初数和年末数分别为4800万元和5000万元,负债总额年初数和年末数分别为2400万元和2500万元,丙公司2017年度收入为7350万元,净利润为294万元。要求:计算总资产
Notonly______(他向我收费过高),buthedidn’tdoagoodrepairjobeither.
最新回复
(
0
)