试题四阅读下列说明和C代码，回答下列问题。[说明] 计算一个整数数组a最长递增子序列长度方法描述如下： 假设数组a长度为n，用数组b元素b[i]记录以a[i](0≤i大于n”)为结尾元素最长递增子序列长度为
其中b[i]满足最优子结构，可递归定义为：
[C代码] 下面是算法C语言实现。 10常量和变量说明 a:长度为n整数数组，待求其最长递增子序列 b:长度为n数组，b[i]记录以a[i](0≤i大于n”)为结尾元素最长递增子序列长度，其中0≤i大于n len:最长递增子序列长度 i,j:循环变量 temp:临时变量11C程序 # jnclude
mtmaxL(int*b,mt n) { mt I, temp=0 for(i=0; i大于n; i++) { (b[i]小于temp) temp=b[i] return temp; int main12 { 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]) Ien=b[j] ___4___; } Printf("len:% d\n",maxL(b,n)) Primtf("\n") }1~4根据说明和C代码，填充C代码中空______～______。5根据说明和C代码，算法采用了______设计策略，时间复杂度为______(用O符号表示)6、已知数组a={3，10，5，15，6，8}，据说明和C代码，给出数组b元素值。
正确答案及解析
正确答案
解析
本题考查最长递增序列问题，是一种动态规划法，也考查时间复杂度计算。1~4、b[0]=1 j大于=i a[j]大于=a[i] b[i]=len+15、动态规划法O(n2) 6、B={1，2，2，3，3，4}
你可能感兴趣的试题
-
- A.V(S2)和P(S4)
- B.P(S2)和V(S4)
- C.P(S2)和P(S4)
- D.V(S2)和V(S4)
- 查看答案
-
- A.V（S1）P（S2）和V（S3）
- B.P（S1）V（S2）和V（S3）
- C.V（S1）V（S2）和V（S3）
- D.P（S1）P（S2）和V（S3）
- 查看答案
-
- A.P（S4）和V（S4）V（S5）
- B.V（S5）和P（S4）P（S5）
- C.V（S3）和V（S4）V（S5）
- D.P（S3）和P（S4）V（P5）
- 查看答案
-
- A.P(S3)和V(S4)V(S5)
- B.V(S3)和P(S4)P(S5)
- C.P(S3)和P(S4)P(S5)
- D.V(S3)和V(S4)V(S5)
- 查看答案
-
- A.P（S2）和P（S4）
- B.P（S2）和V（S4）
- C.V（S2）和P（S4）
- D.V（S2）和V（S4）
- 查看答案