试题内容
阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。
【说明】
计算一个整数数组a的最长递增子序列长度的方法描述如下:
假设数组a的长度为n,用数组b的元素b[i]记录以a[i](0≤i
;其中b[i]满足最优子结构,可递归定义为:
【C代码】
下面是算法的C语言实现。
(1)常量和变量说明
a:长度为n的整数数组,待求其最长递增子序列
b:长度为n的数组,b[i]记录以a[i](0≤i
度,其中0≤i
len:最长递增子序列的长度
i,j:循环变量
temp:临时变量
(2)C程序
#include
int maxL(int*b, int n) {
int i, temp=0;
for(i=0; 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 scanf("%d", &a[i]);
}
(1) ;
for(i=1; i for(j=0, len=0; (2) ; j++) {
if( (3) && len 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的元素值。