首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。 【说明】 计算一个整数数组a的最长递增子序列长度的方法描述如下: 假设数组a的长度为n,用数组b的元素b[i]记录以a[i](0≤i<n)为结尾元素的最长递增子序列的长
阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。 【说明】 计算一个整数数组a的最长递增子序列长度的方法描述如下: 假设数组a的长度为n,用数组b的元素b[i]记录以a[i](0≤i<n)为结尾元素的最长递增子序列的长
admin
2016-05-10
78
问题
阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。
【说明】
计算一个整数数组a的最长递增子序列长度的方法描述如下:
假设数组a的长度为n,用数组b的元素b
记录以a
(0≤i<n)为结尾元素的最长递增子序列的长度,则数组a的最长递增子序列的长度为
;其中b
满足最优子结构,可递归定义为:
【C代码】
下面是算法的C语言实现。
(1)常量和变量说明
a:长度为n的整数数组,待求其最长递增子序列
b:长度为n的数组,b
记录以a
(0≤i<n)为结尾元素的最长递增子序列的长度,其中0≤i<n
len:最长递增子序列的长度
i,j:循环变量
temp:临时变量
(2)C程序
#include<stdio.h>
int maxL(int*b,int n){
int i,temp=0;
for(i=0;i<n;i++){
if(b
>temp)
temp=b
;
}
return temp;
}
int main()f
int n, a[1 0 0], b[1 0 0], i, j, len;
scanf(”%d”, &n);
for(i=0; i<n; i++){
scanf(”%d”, &a
);
}
(1) ;
for(i=1; i<n; i++){
for(j =0,len=0; (2) ; j++){
if( (3) &&len<b[j])
len=b[j];
}
(4) ;
}
printf(”len:%d\n”, maxL(b,n));
printf(”\n”);
}
【问题1】
根据说明和C代码,填充C代码中的空(1)~(4)。
【问题2】
根据说明和C代码,算法采用了 (5)设计策略,时间复杂度为 (6) (用O符号表示)。
【问题3】
已知数组a={3,10,5,15,6,8},根据说明和C代码,给出数组b的元素值。
选项
答案
【问题1】 (1)b[0]=1 (2)j<i (3)a[j]<=a[i] (4)b[i]=len+1 【问题2】 (5)动态规划 (6)O(n
2
) 【问题3】 b={1,2,2,3,3,4}
解析
本题考查算法设计与分析以及用C程序设计语言来实现算法的能力。
此类题目要求考生认真阅读题目对问题的描述,理解算法思想,并会用C程序设计语言来实现。
【问题1】
根据题干描述,用一个数组b来记录数组a每个子数组的最长递增子序列的长度,即b
记录a[0..i]的最长递增子序列的长度。首先,只有一个元素的数组的最长递增子序列的长度为1,即给b[0]直接赋值1。因此,空(1)处填写“b[0]=1”。两重for循环中,第一重是从a数组的第二个元素开始,考虑每个子数组a[0..i]的最长递增子序列的长度,第二重是具体的计算过程。考虑子数组a[0..i],其最长递增子序列的长度应该等于子数组a[0..i-1]中的比元素a
小的元素的最长递增子序列的长度加1,当然,可能存在多个元素比元素a
小,那么存在多个最长递增子序列的长度,此时,取最大者。因此,空处填写“j<i”,即考虑子数组a[0..i-1]。空(3)处填写“a[j]<=a
”,要求元素值小于等于a
而且目前的长度应该小于当前考虑的子数组的最长子序列长度。空(4)处填写“b
=len+1”。简单的说,程序是根据题干给出的公式
来实现的。另外,计算的过程不是采用递归的方式,而是以一种自底向上的方式进行的。
【问题2】
从题干说明和C程序来看,这是一个最优化问题,而且问题具有最优子结构,一个序列的最长递增子序列由其子序列的最长递增子序列构成。在计算过程中采用了自底向上的方式来进行,这具有典型的动态规划特征。因此采用的是动态规划设计策略。
C程序中,有两重for循环,因此时间复杂度为O(n
2
)。
【问题3】
输入数组为数组a={3,10,5,15,6,8),很容易得到,子数组a[0..0],a[0..1],…,a[0..5]的最长递增子序列的长度分别为1,2,2,3,3,4,因此答案为b={1,2,2,3,3,4}。该题可以根据题干说明、C代码来计算。由于输入很简单,答案也可以从输入直接计算出来。
转载请注明原文地址:https://kaotiyun.com/show/fdDZ777K
本试题收录于:
软件设计师下午应用技术考试题库软考中级分类
0
软件设计师下午应用技术考试
软考中级
相关试题推荐
为了使DNS_Server1能正确解析本地Web站点的域名,需对DNS_Server1中的DNS服务进行配置。在图1所示的对话框中,新建的区域名称是(1);在图2所示的对话框中,添加的新建主机名称为(2),IP地址栏应填入(3)。将DNS_Serve
请在(1)~(4)空白处填写恰当的内容。DHCP的工作过程是:1)IP租用请求。DHCP客户机启动后,发出一个DHCPDISCOVER消息,其封包的源地址为(1),目标地址为(2)。2)IP租用提供。当DHCP服务器收到DHCPDI
阅读以下关于动态主机配置协议(DHCP)的说明,回答问题1至问题4。【说明】在小型网络中,IP地址的分配一般都采用静态方式,需要在每台计算机上手工配置网络参数,诸如IP地址、子网掩码、默认网关和DNS等。在大型网络中,采用DHCP完成基本网络配置
根据你的网络工程经验,请用250字以内的文字简要描述该21层教学综合大楼网络层次结构设计的要点。(不要求画图)该21层教学综合大楼网络规则方案不仅要体现所设计的网络能满足现有及未来几年信息系统的应用需求,还需具有较高的平均无故障时间和尽可能低的平均故障
阅读以下说明,回答问题1、问题2、问题3和问题4,将解答填入对应栏内。[说明]ATM(AsynchronousTransferMode)顾名思义就是异步传输模式,是国际电信联盟ITU-T制定的标准。实际上在20世纪80年代中期,人们就已经
阅读以下说明,将(n)的含义填入对应栏内。[说明]电子邮件是Internet中应用最广泛的服务,因此安装和配置一个高效与满足实际需求的电子邮件系统是每一个系统管理员的奋斗的目标之一,Linux的出现为构建低成本的、高效的电子邮件服务器提供了
以下是使用E1线路实现多个64Kbit/s专线连接。当链路为T1时,channel-group编号为0~23,Timeslot范围为1~24;当链路为E1时,channel-group编号为0~30,Timeslot范围为1~31.路由器
阅读以下说明,回答问题。【说明】网络地址转换(NAT)的主要目的是解决IP地址短缺问题以及实现TCP负载均衡等。在如图5-5所示的设计方案中,与Internet连接的路由器采用网络地址转换。【问题】请根据路由器的NAT表和
阅读以下有关网络设备安装与调试的叙述,分析设备配置文件,回答问题1至问题3。现以一台远程访问服务器(RemoteAccessServer,RAS)Cisco2509、RJ45为例来说明。第一步,准备安装与调试所需的设备,主要包括RAS
阅读以下说明,回答【问题1】~【问题4】,将解答填入答题纸的对应栏内。【说明】设有A、B、C、D四台主机都处在同一个物理网络中,A主机的IP地址是192.155.12.112,B主机的IP地址是192.155.12.120,C主机的IP地址是19
随机试题
结肠癌最早出现的症状是()。
关于托儿所、幼儿园的选址要求,以下哪项错误?[2000-64]
【真题(中级)】生产预算依据企业设定的存货政策和销售预算中的销售量预测进行编制。预算期生产量等于()。
甲与乙签订一份买卖合同,双方约定,甲提供一批货物给乙,货到后一个月内付款。合同签订后甲迟迟没有发货.乙催问甲,甲称由于资金紧张,暂无法购买生产该批货物的原材料,要求乙先付货款,乙拒绝了甲的要求。乙拒绝先付货款的行为在法律上称为()。
试分析培训需求分析的步骤。
毛泽东在《<共产党人>发刊词》中阐明了中国共产党在中国革命中的几个基本问题,认为正确地理解了这些问题及其相互关系,就等于正确地领导了全部中国革命。这些基本问题是()。
依次填入下列各句横线处的词语,恰当的一组是:( )。①各级领导干部一定要把人民群众的安危冷暖时刻放在心上,勤政为民、扎实工作,为人民群众______实实在在的利益。②下岗分流人员自谋出路,自觉承受改革的艰难,政府相关的再就业优惠政策也当不折不扣地____
多重安全网关是一种网络隔离技术,其对数据交换采用的防护策略是(38)。
Whatistheinternshipstipulationofeachcountrybelow?ChooseFOURanswersfromtheboxandwritethecorrectletter,A-F,ne
Eachandeveryoneofusisresponsibleforthegreenhousegaseswesendinourdailyactionsandchoices.【C1】______,combating
最新回复
(
0
)