首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列说明和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
78
问题
阅读下列说明和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至问题3,将解答填入对应的解答栏内。【说明】某校园网申请到了C类网络地址块202.115.0.0/24~202.115.3.0/24。根据网络规划需求,网络中心、图书馆、教学实验楼以及行政办公楼的各个部门需划分到不同网段。
根据你的网络工程经验,请用250字以内的文字简要描述该21层教学综合大楼网络层次结构设计的要点。(不要求画图)该21层教学综合大楼网络规则方案不仅要体现所设计的网络能满足现有及未来几年信息系统的应用需求,还需具有较高的平均无故障时间和尽可能低的平均故障
解释图10-2中的PVC和SVC。以下是LANE工作过程,其顺序已乱,请排序。①LEC接着便向其他LEC广播这个响应。②在地址表中含有被称为MAC地址的LEC向LEC作出响应。③LES发送多点组播至网络上的其他LEC。④
如果ping127.0.0.1(本地循环地址),如果该地址无法Ping通,则说明了是什么原因?在DOS状态下输入tracertwww.ciu.net.cn并执行后,经过一段时间等待,系统会反馈出很多IP地址。出现在最上方(第1条记录)的IP地址是什么
网络维护是网络管理中一项很重要的工作。由于网络协议和网络设备的复杂性,许多故障解决起来绝非像解决单机故障那么简单。网络故障的定位和排除,既需要长期的知识和经验积累,也需要一系列的软件和硬件工具,这样才能解决我们在学习或工作中遇到的网络故障。
阅读以下说明、Java源程序和运行测试部分1.HTTP协议。●HTTP请求消息示例:GET/index,htmlHTTP/1.1Accept:image/gif,image/jpeg,*/Acc
在图4-8所示的无线接待室中WLAN采用的体系结构如图4-9所示,请将(1)~(3)空缺处填写完整请将以下(11)~(14)空缺处的内容填写完整,并帮助郭工程师解释产生以下网络故障的原因。该网络建成后一直使用正常,但最近发现无线覆盖区域A、B
请指出图1-12中(1)空缺处传输的是模拟信号,还是数字信号?图1-12中(2)空缺处是什么设备?该设备在本宽带网络中完成哪些功能?
随机试题
患者,男性,突发腹泻、呕吐2天,于8月6日来诊,每日大便20次以上,呕吐多次,呈喷射状,上厕所时晕厥1次;无明显发热、腹痛等。该患者脱水,体重下降13%,烦躁不安,皮肤弹性消失,口唇极干,有肌肉痉挛,脉搏细速,收缩压80mmHg,尿少。该患者处于下列霍
胰岛素的主要作用是调节
竣工验收是工程建设过程的最后一环。建设单位应做的申报竣工验收的准备工作中不包括( )。
背景资料某建筑公司(乙方)与某学校(甲方)签订了办公楼承建合同,合同约定工期奖罚条件:乙方提前完成该工程l周,甲方奖励乙方10万元,若乙方延误总工期1周,则扣除乙方工程款10万元。合同中约定:施工中实际工程量超过计划工程量10%以上时,超出部分按单价的9
针对事故发生的原因,提出防止相同或类似事故发生的切实可行的预防措施,并督促事故发生单位加以实施,以达到事故调查和处理的最终目的。此款符合“四不放过”事故处理原则的()原则。
某公司近期购入了竞争对手的一些股票,以此作为收购竞争对手长期计划的一部分。然而,该公司对股价短期下跌多少有点担忧。为了规避股价下跌所造成的风险,该公司需要
【真题(初级)】下列情形中,审计人员应扩大应收账款函证范围和数量的是()。
四川风味小吃是( )。
你和小王同时进入单位,你工作踏实,而小王不务正业,却经常请同事吃饭。长久下来,同事觉得你小气、死板。面对这样的情况,你怎么办?
数据库的物理设计是为一个给定的逻辑结构选取一个适合应用环境的______的过程,包括确定数据库在物理设备上的存储结构和存取方法。
最新回复
(
0
)