首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列说明和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
98
问题
阅读下列说明和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
软件设计师下午应用技术考试
软考中级
相关试题推荐
阅读以下说明,回答问题1、问题2、问题3和问题4,将解答填入对应栏内。[说明]ATM(AsynchronousTransferMode)顾名思义就是异步传输模式,是国际电信联盟ITU-T制定的标准。实际上在20世纪80年代中期,人们就已经
如果ping127.0.0.1(本地循环地址),如果该地址无法Ping通,则说明了是什么原因?在DOS状态下输入tracertwww.ciu.net.cn并执行后,经过一段时间等待,系统会反馈出很多IP地址。出现在最上方(第1条记录)的IP地址是什么
网络维护是网络管理中一项很重要的工作。由于网络协议和网络设备的复杂性,许多故障解决起来绝非像解决单机故障那么简单。网络故障的定位和排除,既需要长期的知识和经验积累,也需要一系列的软件和硬件工具,这样才能解决我们在学习或工作中遇到的网络故障。
VPN使用的隧道协议可以有那几类,分别有哪些协议?VPN路由器配置如下,请解释画线部分含义。Vpdn-group1(1)Accept-dialinprotocol12tpvirtual-template1terminate
阅读以下说明,回答问题。【说明】网络地址转换(NAT)的主要目的是解决IP地址短缺问题以及实现TCP负载均衡等。在如图5-5所示的设计方案中,与Internet连接的路由器采用网络地址转换。【问题】请根据路由器的NAT表和
阅读以下有关网络接入方案的说明,回答问题1~3。【说明】某单位己完成了主干网络的建设任务,现在需要对其职工住宅区的用户接入主干网的技术方案作选型设计。职工住宅已有的通信条件是:(1)电话线(2)电视铜缆。在不重新布线的前提下,以下5种技术方
阅读以下说明,回答【问题1】~【问题4】,将解答填入答题纸的对应栏内。【说明】设有A、B、C、D四台主机都处在同一个物理网络中,A主机的IP地址是192.155.12.112,B主机的IP地址是192.155.12.120,C主机的IP地址是19
在图4-8所示的无线接待室中WLAN采用的体系结构如图4-9所示,请将(1)~(3)空缺处填写完整IEEE802.11定义了无线局域网(WLAN)的两种工作模式,根据图4-8所示的网络拓朴结构可判断出该WLAN的工作模式是(4)。当前WLAN中主要使
在RAS上存在着两个RJ45的端口,分别为Console与AUX,请问这两个端口的用途是什么?(控制在100个字以内)在调用超级终端程序进行设备连接时,应该对设备的连接参数进行正确设置,参数主要包括串口数据传输率、数据位数。停止位数以及是否有奇偶校验。
随机试题
葡萄糖在体内代谢时,通常不会转变生成的化合物是
在一个研讨班上,学员对假、劣药情形、使用法律和法律责任展开了讨论。讨论的情形主要包括四个:一是采用多加矫味剂生产儿童退热药;二是多加药用淀粉少用主药生产降压药;三是部分药品超过有效期;四是某抗菌药物的外包装上标示的适应证与批准的药品说明书中适应证表述不一致
在低电阻接地系统中,流过接地线的单相接地电流为30kA,短路电流持续时间为0.2s,接地线材料为钢质,按热稳定条件(不考虑腐蚀,接地线初始温度40℃)应选择接地线的最小截面为()。
某建筑物按地震作用效应标准组合的基础底面边缘最大压力pmax=380kPa,地基土为中密状态的中砂,问该建筑物基础深宽修正后的地基承载力特征值fa至少应达到()kPa时,才能满足验算天然地基地震作用下的竖向承载力要求。
一个气缸内储存有一定量的单原子分子理想气体,在压缩过程中外界做功209J,此过程气体内能增量120J,外界传给气体的热量为()J。
在全球范围内通过实施( ),可以规范所有组织的环境行为,降低环境风险和法律风险,最大限度地节约能源和资源消耗,从而减少人类活动对环境造成的不利影响,维持和改善人类生存和发展的环境。
关于MA的介绍,以下内容中错误的是()。
隋文帝时,以户等为依据征调赋税、力役,这一措施被称为()。
下列选项中不属于对学生严格教育原则的是()。
下列不属于收入再分配手段的是:
最新回复
(
0
)