计算一个整数数组a的最长递增子序列长度的方法描述如下：
假设数组a的长度为n，用数组b的元素b[i]记录以a[i](0≤i＜n)为结尾元素的最长递增予序列的长度，则数组a的最长递增子序列的长度为
；其中b[i]满足最优子结构，可递归定义为：
【C代码】
下面是算法的C语言实现。
（1）常量和变量说明
a：长度为n的整数数组，待求其最长递增子序列
b：长度为n的数组，b[i]记录以a[i](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[i]>temp)
temp=b[i];
}
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[i]);
}
(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[i]
（4）b[i]=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[i]小的元素的最长递增子序列的长度加1，当然，可能存在多个元素比元素a[i]小，那么存在多个最长递增子序列的长度，此时，取最大者。因此，空（2）填写“j＜i”，即考虑子数组a[0..i-1]第三问为a[j]＜=a[i]，第四问为b[i]=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]。
包含此试题的试卷
你可能感兴趣的试题
Advancements in （ ）have contributed to the growth of the automotive industry through the creation and evolution of self-driving vehicles.
-
- A.Artificial Intelligence
- B.Cloud Computing
- C.Internet of Things
- D.Big Data
- 查看答案
In project human resource management , （ ）is not a source of power for the project manager.
-
- A.referent power
- B.expert power
- C.reward power
- D.audit power
- 查看答案
At the project establishment stage , the feasibility study mainly includes techinical feasibility analysis , （ ）, operation environment feasibility analysis and other aspects of feasibility analysis.
-
- A.detail feasibility analysis
- B.opportunity analysis
- C.economic feasibility analysis
- D.risk analysis
- 查看答案
（ ）is a grid that shows the project resources assigned to each work package.
-
- A.Stakeholder engagement assessment matrix
- B.Requirements traceability matrix
- C.Probability and impact matrix
- D.Responsibility assignment matrix
- 查看答案
Xinhua News Agency reported in January 2022，Chian will further promote the developmet of a digital economy during the 14th Five-Year Plan eriod（2021-2025）. The plan also emphasized industrial （ ）transformation.
-
- A.digital
- B.networking
- C.intelligentize
- D.informatization
- 查看答案