2. 从业资格
  3. 计算一个整数数组a的最长递增子序列长度的方法描述如下： 假设数组a的长度为n，

计算一个整数数组a的最长递增子序列长度的方法描述如下： 假设数组a的长度为n，

考试题库2022-08-02  52
问题 计算一个整数数组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＜nlen：最长递增子序列的长度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（　　）{int n,a[100],b[100],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】（8分）根据说明和C代码，填充C代码中的空（1）～（4）。【问题2】（4分）根据说明和C代码，算法采用了（5）设计策略，时间复杂度为（6）（用O符号表示）。【问题3】（3分）已知数组a={3,10,5,15,6,8}，根据说明和C代码，给出数组b的元素值。
选项
答案
解析 【问题1】
（1）b[0]=1
（2）j＜i
（3）a[j]＜=a
（4）b=len+1
【问题2】
（5）动态规划法
（6）O(n2)
【问题3】
b={1,2,2,3,3,4}
本题考查算法设计与分析技术以及算法的C语言实现，是比较传统的题目，要求考生细心分析题目中所描述的内容。
（1）根据题中说明，b数组记录最长递增子序列的长，故应初始化b[0]=1，这是第一问的答案。两重for循环中，第一重是从a数组的第二个元素开始，考虑每个子数组a[0...i]的最长递增子序列的长度，第二重是具体的计算过程。考虑子数组a[0..i]，其最长递增子序列的长度应该等于子数组a[0..i-1]中的比元素a小的元素的最长递增子序列的长度加1，当然，可能存在多个元素比元素a小，那么存在多个最长递增子序列的长度，此时，取最大者。因此，空（2）填写“j＜i”，即考虑子数组a[0..i-1]第三问为a[j]＜=a，第四问为b=len+1。
（2）算法将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。使用的是动态规划的思想。时间复杂度计算最坏情况下的运算次数，最坏情况时i和j都从1跑到n,故运算n的平方次。算法的时间复杂度为O(n2)。
（3）初始b[0]=1，a[0]=3，a[1]=10进入时b[1]=2，a[2]=5进入时有3、5的序列故b[2]=2，a[3]=15进入时有3、10、15，故子序列为3，a[4]=6时有子序列3、5、6，故为3，当最后一个元素8进入时有3、5、6、8，故b[5]=4。所以b=[1,2,2,3,3,4]。
转载请注明原文地址:https://tihaiku.com/congyezige/2409840.html
本试题收录于： 中级 软件设计师题库软件水平考试初中高级分类

中级 软件设计师

软件水平考试初中高级

相关试题推荐
随机试题
最新回复(0)