2. 计算机
  3. 阅读下列说明和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)为结尾元素的最

admin2015-12-01  59
问题 阅读下列说明和C代码，回答【问题1】至【问题3】，将解答写在答题纸的对应栏内。
    【说明】
    计算一个整数数组a的最长递增子序列长度的方法描述如下：
    假设数组a的长度为n，用数组b的元素b记录以a(0≤i＜n)为结尾元素的最长递增子序列的长度为；其中b满足最优子结构，可递归定义为：

【C代码】
下面是算法的C语言实现。
(1)常量和变量说明
a：长度为n的整数数组，待求其最长递增子序列
b：长度为n的数组，b记录以a(0≤i＜n)为结尾元素的最长递增子序列的长度，其中0≤i＜n
len：最长递增子序列的长度
i，j：循环变量
temp：临时变量
(2)C程序
    #jnclude＜stdio．h＞
    mtmaxL(int*b，mt n){
    mt I，temp=0；
    for(i=0；i＜n；i++){
    (bill＞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])
    Ien=b[j]；
    }
    (4)  ；
    }
    Printf(“len：％d＼n”，maxL(b，n))；
    Printf(“＼n”)；
    }
    【问题1】
    根据说明和C代码，填充C代码中的空(1)～(4)。
    【问题2】
    根据说明和C代码，算法采用了(5)设计策略，时间复杂度为(6)(用0符号表示)
    【问题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}
解析
转载请注明原文地址:https://www.kaotiyun.com/show/jdDZ777K
本试题收录于： 软件设计师下午应用技术考试题库软考中级分类
0

软件设计师下午应用技术考试

软考中级

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