2019CCF非专业级别软件能力认证第--轮（CSP-S）

考生注意事项：
•试题纸共有12页，答题纸共有1页，满分100分。请在答题纸上作答，写在试题纸上的一律无效。
♦不得使用任何电子设备（如计算器、手机、电子词典等）或查阅任何书籍资料。

您的姓名：



1.若有定义：int a=7; float x=2.5, y=4.7；则表达式x+a%3*(int)(x+y)%2的值是：（）

A.0.000000

B.2.750000

C.2.500000

D.3.500000

2. 下列属于图像文件格式的有（）

A.WMV

B.MPEG

C.JPEG

D.AVI

3.二进制数11 1011 1001 0111 和 01 0110 1110 1011 进行逻辑或运算的结果是（）

A.11 1111 1101 1111

B.11 1111 1111 1101

C.10 1111 1111 1111

D.11 1111 1111 1111

4.编译器的功能是（）

A.将源程序重新组合

B.将一种语言（通常是高级语言）翻译成另一种语言（通常是低级语言）

C.将低级语言翻译成高级语言

D.将一种编程语言翻译成自然语言

5.设变量x为float型且已赋值，则以下语句中能将x中的数值保留到小数点后两位，并将第三位四舍五入的是（）

A.X=(x*100+0.5)/100.0

B.x=(int)(x*100+0.5)/100.0;

C.x=(x/100+0.5)*100.0

D.x=x*100+0.5/100.0;

6.由数字1，1，2，4，8，8所组成的不同的4位数的个数是（）

A.104

B.102

C.98

D.100

7. 排序的算法很多，若按排序的稳定性和不稳定性分类，则（）是不稳定排序。

A.冒泡排序

B.直接插入排序

C.快速排序

D.归并排序

8. G是一个非连通无向图（没有重边和自环），共有28条边，则该图至少有（）个顶点

A.10

B.9

C.11

D.8

一些数字可以颠倒过来看，例如0、1、8颠倒过来看还是本身，6颠倒过来是9，9颠倒过来看还是6，其他数字颠倒过来都不构成数字。类似的，一些多位数也可以颠倒过来看，比如106颠倒过来是901。假设某个城市的车牌只有5位数字，每一位都可以取0到9。请问这个城市有多少个车牌倒过来恰好还是原来的车牌，并且车牌上的5位数能被3整除？（）

A.40

B.25

C.30

D.20

10. 一次期末考试，某班有15人数学得满分，有12人语文得满分，并且有4人语、数都是满分，那么这个班至少有一门得满分的同学有多少人？（）

A.23

B.21

C.20

D.22

11. 设A和B是两个长为n的有序数组，现在需要将A和B合并成一个排好序的数组，请问任何以元素比较作为基本运算的归并算法，在最坏情况下至少要做多少次比较？（）

A.n

B.nlogn

C.2n

D.2n-1

12. 以下哪个结构可以用来存储图（）

A.栈

B.二叉树

C.队列

D.邻接矩阵

13. 以下哪些算法不属于贪心算法？（）

A.Dijkstra算法

B.Floyd算法

C.Prim算法

D.Kruskal算法

14. 有一个等比数列，共有奇数项，其中第一项和最后一项分别是2和118098，中间一项是486，请问一下哪个数是可能的公比？（）

A.5

B.3

C.4

D.2

15.有正实数构成的数字三角形排列形式如图所示。第一行的数为a2,1，a2,2，第n行的数为an,1，an,2，…，an,n。从a1,1开始，每一行的数ai,j只有两条边可以分别通向下一行的两个数ai+1,j和ai+1,j+1。用动态规划算法找出一条从a1,1向下通道an,1，an,2，…，an,n中某个数的路径，使得该路径上的数之和最大。

A.mac{C[i-1][j-1],C[i-1][j]}+ ai,j

B.C[i-1][j-1]+C[i-1][j]

C.max{C[i-1][j-1],c[i-1][j]}+1

D.max{C[i][j-1],C[i-1][j]}+ ai,j

阅读程序一（程序输入不超过数组或字符串定义的范围；判断题正确填√错误填X除特殊说明外，判断题1.5分，选择题3分，共计40分）

概述：12行if判断如a[i]比前一位小，则从i开始，否则从上次开始14行while循环找ans向后找第一个>a[i]的数12行的判断的意思是，如果后项<=前项，则重新开始，否则从上项开始（蠕动）整个程序含义是找每个a[i]后第一个大于a[i]的位置（如果看懂，后面都很好做）
•判断题

16.第16行输出ans时，ans的值一定大于i。（）

对

错

17. 程序输出的ans小于等于n。（）

对

错

18. 若将第12行的“<”改为“!=”，程序输出的结果不会改变。（）

对

错

19.当程序执行到第16行时，若ans-i>2，则a[i+1]≦a[i]。（）

对

错

20. 若输入的a数组是一个严格单调递增的数列，此程序的时间复杂度是（）。

A. 0(logn)

B . 0(n2)

C. 0(nlog n)

D. 0(n)

21. 最坏情况下，此程序的时间复杂度是（）。

A. 0（n2)

B. 0(log n)

C. 0(n)

D. 0(nlog n)

阅读程序二（程序输入不超过数组或字符串定义的范围；判断题正确填√错误填X除特殊说明外，判断题1.5分，选择题3分，共计40分）

•判断题

22.输入的a和b值应在[0,n-1]的范围内。（）

对

错

23.若输入的a和b值均在[0, n-1]的范围内，则对于任意0≤i＜n，都有0≤fa[i]＜n。（）

对

错

24.若输入的a和b值均在[0,n-1]的范围内，则对于任意0≤i＜n，都有1≤cnt[i] ≤n。（）

对

错

25. 当n等于50时，若a、b的值都在[0,49]的范围内，且在第25行时总是不等于y，那么输出为（）

A. 1276

B. 1176

C.1225

D.1250

26.此程序的时间复杂度是（）

A. O(n)

B.O(logn)

C. O(n2)

D.O(nlogn)

阅读程序三（程序输入不超过数组或字符串定义的范围；判断题正确填√错误填X除特殊说明外，判断题1.5分，选择题3分，共计40分）

提示：
t[0..pre[i]-1]是s[0..i]的子序列；
t[suf[i]+1..tlen-1]是s[i..slen-1]的子序列

•判断题

27.程序输出时，suf数组满足：对任意0≤i＜slen，suf[i] ≤suf[i+1].( )

对

错

28.当t是s的子序列时，输出一定不为0.（）

对

错

29.程序运行到第23行时，“j-i-1”一定不小于0.（）

对

错

30.当t时s的子序列时，pre数组和suf数组满足：对任意0≤i＜slen，pre[i]＞suf[i+1].( )

对

错

30.若tlen=10，输出为0，则slen最小为（）

A. 10

B. 12

C.0

D.1

31.若tlen=10，输出为2，则slen最下为（）

A. 0

B.10

C.12

D.1

34. ①处应填（）

A. unlock[i]＜=0

B. unlock[i]＞=0

C. unlock[i]==0

D. unlock[i]==-1

35. ②处应填（）

A. threshold[i]＞points

B. threshold[i]＞=points

C. points＞threshold[i]

D. points＞=threshold[i]

36.③处应填( )

A. target = -1

B. - -cnt[target]

C. bbonus[target]

D. points += bonus[target]

37 .④处应填( )

A. cnt [child[target][i]] -=1

B. cnt [child[target][i]] =0

C. unlock[child[target][i]] -= 1

D. unlock[child[target][i]] =0

38 .⑤处应填（）

A. unlock[i] = cnt[i]

B. unlock[i] =m

C. unlock[i] = 0

D. unlock[i] =-1

38.①处应填（）

A.0

B.~0ull

C.~0ull^1

D.1

39 .②处应填（）

A.a[j]＜i

B.a[j]==i

C.a[j] != i

D.a[j] >i

40.③处应填()

A. trans |= 1ull ＜＜(b[j] - 1)

B. status |=1ull ＜＜ (b[j]- 1)

C. status +=1ull ＜＜ (b[j]-1)

D. trans +=1ull＜＜ (b[j]-1)

41.④处应填( )

A. ~status | trans

B. status ＆ trans

C. status | trans

D. ~status ＆ trans

42.⑤处应填( )

A. trans = status | trans ^win

B. status = trans >> 1^win

C. trans = status ^trans |win

D. status =status ＜＜1^win