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

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

一、单项选择题（共15题，每题2分，共计30分；每題有且仅有一个正确选项）

您的姓名：



1.中国的国家顶级域名是（）

A. .cn

B. .ch

C. .chn

D. .china

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

A.01 0010 1000 1011

B.01 0010 1001 0011

C.01 0010 1000 0001

D.01 0010 1000 0011

3. 32位整型变量占用（）个字节。

A.32

B.128

C.4

D.8

4. 若有如下程序段，其中s、a、b、c均已定义为整型变量，且a、c均已赋值(c大于0)
s = a;
for (b = 1; b <= c; b++)
s= s -1;
则与上述程序段功能等价的赋值语句是(）

A. s=a-c;

B. s=a-b;

C. s=s-c;

D. s=b-c;

5. 设有100个已排好序的数据元素，采用折半查找时，最大比较次数为（）

A.7

B.10

C.6

D.8

6. 链表不具有的特点是（）

A.插入删除不需要移动元素

B.不必事先估计存储空间

C.所需空间与线性表长度成正比

D.可随机访问任一元素

7. 把8个同样的球放在5个同样的袋子里，允许有的袋子空着不放，问共有多少种不同的分法？（）提示:如果8个球都放在一个袋子里，无论是哪个袋子，都只算同一种分法

A .22

B .24

C .18

D .20

8. —棵二叉树如右图所示，若采用顺序存储结构，即用一维数组元素存储该二叉树中的结点(根结点的下标为1,若某结点的下标为i ,则其左孩子位于下标2i 处、右孩子位于下标2i +1处)，则该数组的最大下标至少为（）。

A .6

B .10

C .15

D .12

9.100以内最大的素数是（）

A .89

B .97

C .91

D .93

10. 319 和 377的最大公约数是（）

A .27

B .33

C .29

D .31

11. 新学期开学了，小胖想减肥，健身教练给小胖制定了两个训练方案。方案一每次连续跑3公里可以消耗300千卡(耗时半小时);方案二每次连续跑5公里可以消耗600干卡(耗时1小时)。小胖每周周一到周四能抽出半小时跑步，周五到周日能抽出一小时跑步。另外，教练建议小胖每周最多跑21公里，否则会损伤膝盖。请问如果小胖想严格执行教练的训练方案，并且不想损伤膝盖，每周最多通过跑步消耗多少千卡？（）

A .3000

B .2500

C .2400

D .2520

12. 一副纸牌除掉大小王有52张牌，四种花色，每种花色13张。假设从这52张牌中随机抽取13张纸牌，则至少()张牌的花色一致。

A .4

B .2

C .3

D .5

13. —些数字可以颠倒过来看，例如0、1、8颠倒过来还是本身，6颠倒过来是9, 9颠倒过来看还6,其他数字颠倒过来都不构成数字。类似的，一些多位数也可以颠倒过来看，比如106颠倒过来是901。假设某个城市的车牌只由5位数字组成，每一位都可以取0到9。请问这个城市最多有多少个车牌倒过来怡好还是原来的车牌？（）

A .60

B .125

C .75

D .100

14. 假设一棵二叉树的后序遍历序列为DGJHEBIFCA，中序遍历序列为DBGEHJACIF,则其前序遍历序列为()。

A.ABCDEFGHIJ

B.ABDEGHJCFI

C.ABDEGJHCFI

D.ABDEGHJFIC

15.以下哪个奖项是计算机科学领域的最高奖?(）

A.图灵奖

B.鲁班奖

C.诺贝尔奖

D.普利策奖

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

概述：将字符串下标是n约数位置的小写字母转大写
•判断题

16.输入的字符串只能由小写字母或大写字母组成。

对

错

17. 若将第8行的“i=1”改为“i = 0”，程序运行时会发生错误。( )

对

错

18. 若将第8行的“i<=n”改为“i*i<=n”，程序运行结果不会改变。（）

对

错

19.若输入的字符串全部由大写字母组成，那么输出的字符串就跟输入的字符串一样。（）

对

错

单选题

20. 若输入的字符串长度为18,那么输入的字符串跟输出的字符串相比，至多有()个字符不同。

A.18

B.6

C.10

D.1

21. 若输入的字符串长度为（），那么，输入的字符串跟输出的字符串相比，至多有36个字符不同。

A.36

B.100000

C.1

D.128

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

假设输入的n和m都是正整数，x和y都是在[1,n]的范围内的整数，完成下面的判断题和选择题

•判断题

22.当m>0时，输出的值一定小于2n。

对

错

23.执行完第27行的“++ans”时，ans一定是偶数。

对

错

24.a[i]和b[i]不可能同时大于0。

对

错

25.若程序运行到第13行时，x总是小于y,那么第15行不会被执行。

对

错

单选题

26. 若m个x‘两两不同，且m个y两两不同，则输出的值为（）

A.2n-2m

B.2n+2

C.2n-2

D.2n

27.若m个x两两不同，且m个y都相等，则输出的值为()

A.2n-2

B.2n

C.2m

D. 2n-2m

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

概述：构造数列a的笛卡尔树（根节点最小且保持中序遍历），并求节点深度与b的加权和.

•判断题

28.果a数组有重复的数字，则程序运行时会发生错误。()

对

错

29.如果b数担全为0,则输出为0()

对

错

单选题

30.当n=100时，最坏情况下，与第12行的比较运算执行的次数最接近的是（）

A.5000

B.600

C.6

D.100

31.当n=100时，最好情况下，与第12行的比较运算执行的次数最接近的是（）

A.100

B.6

C.5000

D.600

32.当n=10时，若b组满足，对任意Osi<n，都有b[i]=i +1,那么输出最大为（）

A.386

B.383

C.384

D.385

33.当n=100时，若b数组满足，对任意0<=i<n，都有b[i]=1,那么输出最小为

A.582

B.580

C.579

D.581

三、完善程序（单选题，每小题3分，共计30分）

(1)

34. ①处应填（）

A. n%2

B.0

C.t

D.1

35. ②处应填（）

A.x - step，y- step

B.x，y+step

C.x-step.y

D.x,y

36.③处应填( )

A.x-step, y-step

B.x+step,y+step

C.x-step, y

D.x, y-step

37 .④处应填( )

A.n-1, n % 2

B.n,0

C.n, n % 2

D.n-1,0

38 .⑤处应填（）

A. 1＜＜(n+1)

B.1＜＜n

B. n+1

D.1＜＜(n-1)

三、完善程序（单选题，每小题3分，共计30分）

(2)

38.①处应填（）

A. ++cnt[i]

B. ++cnt[b[i]]

C. ++cnt[a[i] * maxs + b[i]]

D. ++cnt[a[i]]

39 .②处应填（）

A. ord[--cnt[a[i]]]=i

B. ord[--cnt[b[i]]]=a[i]

C. ord[--cnt[a[i]]]=b[i]

D. ord[--cnt[b[i]]]=i

40.③处应填()

A. ++cnt[b[i]]

B. ++cnt[a[i] * maxs + b[i]]

C. ++cnt[a[i]]

D. ++cnt[i]]

41.④处应填( )

A. res[--cnt[a[ord[i]]]]=ord[i]

B. res[--cnt[b[ord[i]]]]=ord[i]

C. res[--cnt[b[i]]]=ord[i]

D. res[--cnt[a[i]]]=ord[i]

42.⑤处应填( )

A． a[i],b[i]

B. a[res[i]],b[res[i]]

C. a[ord[res[i]]],b[ord[res[i]]]

D. a[res[ord[i]]],b[res[ord[i]]]