首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列说明和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
77
问题
阅读下列说明和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)。在网络A的PCI中执
为了使DNS_Server1能正确解析本地Web站点的域名,需对DNS_Server1中的DNS服务进行配置。在图1所示的对话框中,新建的区域名称是(1);在图2所示的对话框中,添加的新建主机名称为(2),IP地址栏应填入(3)。将DNS_Serve
下图为RouterB上的路由表信息,写出查询路由表的命令:(1)。该路由器上运行的路由协议为(2)。行政办公楼部门A所属网络地址是(3),部门B所属网络地址是(4)。在主机D上使用命令TracertDNSServer,显示结
根据你的网络工程经验,请用250字以内的文字简要描述该21层教学综合大楼网络层次结构设计的要点。(不要求画图)该21层教学综合大楼网络规则方案不仅要体现所设计的网络能满足现有及未来几年信息系统的应用需求,还需具有较高的平均无故障时间和尽可能低的平均故障
阅读以下有关传统局域网络运行和维护的叙述,将应填入(n)处的字句写在对应栏内。在对网络运行及维护前首先要了解网络,包括识别网络对象的硬件情况、判别局域网的拓扑结构和信道访问方式、确定网络互联以及用户负载等。常见的3种拓扑结构是星形、(1)与(2)拓
阅读以下说明、Java源程序和运行测试部分1.HTTP协议。●HTTP请求消息示例:GET/index,htmlHTTP/1.1Accept:image/gif,image/jpeg,*/Acc
在RAS上存在着两个RJ45的端口,分别为“Console”与“AUX”,请问这两个端口的用途是什么?(控制在100个字以内)在第四步中,进入虚拟操作台后,在IOS环境下输入了如下的配置,请解释(1)~(4)处的标有下划线部分配置命令的含义(“◇”后为
阅读以下某单位宽带网络接入的技术说明,根据要求回答问题1至问题6。【说明】接入网(AN)泛指用户网络接口(UNI)与业务节点接口(SNI)间实现传送承载功能的实体网络。其目标是建立一种标准化的接,方式,以一个可监控的接入网络,使用户能够获得话音、
在RAS上存在着两个RJ45的端口,分别为Console与AUX,请问这两个端口的用途是什么?(控制在100个字以内)在调用超级终端程序进行设备连接时,应该对设备的连接参数进行正确设置,参数主要包括串口数据传输率、数据位数。停止位数以及是否有奇偶校验。
随机试题
开发软件所需高成本和产品的低质量之间有着尖锐的矛盾,这种现象称做()。
某患者左前胸部刀刺伤2小时后,感胸闷气短,查体:面色苍白,四肢湿冷,心率120次/min,血压80/70mmhg。颈静脉怒张,首先考虑_______。
大柴胡汤中柴胡与生姜的用量比例是
金融市场是指()等融资活动的场所。
取得报关单位资格的法定要求是企业()。
高校教育研究应该侧重的方面是教育对象、教学内容、教学方法、教学组织形式和教学管理制度。()
甲乙二人分别从A、B两地同时出发,相向而行。若两人按原定速度前进,则4小时相遇;若两人都比原定速度提高1千米/小时,则3小时相遇。若两人同向而行,则甲追上乙需12小时,问甲乙二人原来的速度为多少?()
对于一个使用邻接表存储的有向图G,可以利用深度优先遍历方法,对该图中结点进行拓扑排序。其基本思想是:在遍历过程中,每访问一个顶点,就将其邻接到的顶点的入度减1,并对其未访问的、入度为0的邻接到的顶点进行递归。写出在遍历图的同时进行拓扑排序的算法。
Weuselanguageeveryday.Weliveinaworldofwords.Hardlyanymomentpasseswithsomeonetalking,writingorreading.Indee
RisingbrightandearlyonaSaturdayusedtobeamatterofsurvivalinGermany.【C1】______the1990smostshopsclosedforthe
最新回复
(
0
)