当前位置:首页计算机类软件水平考试初级程序员->阅读下列说明和C代码,回答问题,将解答填入答题纸的对应栏内。

阅读下列说明和C代码,回答问题,将解答填入答题纸的对应栏内。

【说明】

计算一个整数数组a的最长递增子序列长度的方法描述如下:

假设数组a的长度为n,用数组b的元素b[i]记录以a[i](0≤i<n)为结尾元素的最长递增子序列的长度为 ;其中b[i]满足最优子结构,可递归定义为:

初级程序员,押题密卷,2021年程序员押题密卷2

【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】(5分)

已知数组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】(4分)

(5)动态规划法

(6)O(n2)

【问题3】(5分)

B={1,2,2,3,3,4}

更新时间:2021-12-03 15:13

包含此试题的试卷

你可能感兴趣的试题

单选题

(  )is the process of transforming information so it is unintelligible to anyone but the intended recipient.

  • A.Encryption
  • B.Decryption
  • C.Security
  • D.Protection
查看答案
单选题

As each application module is completed,it undergoes(  )to ensure that it operates correctly and reliably.

  • A.unit testing
  • B.integration testing
  • C.system testing
  • D.acceptance testing
查看答案
单选题

(  )algorithm specifies the way to arrange data in a particular order.

  • A.Search
  • B.Random
  • C.Sorting
  • D.Merge
查看答案
单选题

After analyzing the source code,(  )generates machine instructions that will carry out the meaning of the program at a later time.

  • A.an interpreter
  • B.a linker
  • C.a compiler
  • D.a converter
查看答案
单选题

(  )can help organizations to better understand the information contained within the data and will also help identify the data that is most important to the business and future business decisions.

  • A.Data processing system
  • B.Big Data analytics
  • C.Cloud computing
  • D.Database management
查看答案
单选题

浏览器开启无痕浏览模式后,(  )依然会被保存下来。

  • A.浏览历史
  • B.搜索历史
  • C.已下载文件
  • D.临时文件
查看答案
单选题

下列协议中,不属于TCP/IP协议簇的是(  )。

  • A.CSMA/CD
  • B.IP
  • C.TCP
  • D.UDP
查看答案
单选题

下列传输介质中,带宽最宽、抗干扰能力最强的是(  )。

  • A.双绞线
  • B.红外线
  • C.同轴电缆
  • D.光纤
查看答案
单选题

数控编程常需要用参数来描述需要加工的零件的图形。在平面坐标系内,确定一个点需要2个独立的参数,确定一个正方形需要(  )个独立的参数。

  • A.3
  • B.4
  • C.5
  • D.6
查看答案
单选题

某书的页码为1,2,3,...,共用数字900个(一个多位数页码包含多个数字),据此可以推断,该书最大的页码为(  )。

  • A.237
  • B.336
  • C.711
  • D.900
查看答案