2022CCF非专业级别软件能力认证第--轮(CSP-S1)

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

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

您的姓名：



1.在Linux系统终端中，用于切换工作目录的命令为( )。

A. ls

B. cd

C. cp

D. all

2.你同时用time命令和秒表为某个程序在单核CPU的运行计时。假如time命令的输出如下:

A.30s

B. 24s

C.18s

D. 6s

3.若元素a、b、c、d、e、f依次进栈，允许进栈、退栈操作交替进行，但不允许连续三次退栈操作，则不可能得到的出栈序列是( )。

A. dcebfa

B. cbdaef

C. bcaefd

D. afedc

4.考虑对n个数进行排序，以下最坏时间复杂度低于0(n2)的排序方法是()。

A.插入排序

B.冒泡排序

C.归并排序

D.快速排序

5.假设在基数排序过程中，受宇宙射线的影响，某项数据异变为-一个完全不同的值。请问排序算法结束后，可能出现的最坏情况是( )。

A.移除受影响的数据后，最终序列是有序序列

B.移除受影响的数据后，最终序列是前后两个有序的子序列

C.移除受影响的数据后，最终序列是一一个有序的子序列和-一个基本无序的子序列

D.移除受影响的数据后，最终序列基本无序

6.计算机系统用小端(Little Endian) 和大端(Big Endian) 来描述多字节数据的存储地址顺序模式，其中小端表示将低位字节数据存储在低地址的模式、大端表示将高位字节数据存储在低地址的模式。在小端模式的系统和大端模式的系统分别编译和运行以下C++代码段表示的程序，将分别输出什么结果? ( )

A. EF、EF

B. EF、DE

C. DE、EF

D. DE、DE

7.一个深度为5 (根结点深度为1)的完全3叉树，按前序遍历的顺序给结点从1开始编号，则第100号结点的父结点是第( )号。

A.95

B. 96

C. 97

D.98

8.强连通图的性质不包括( ):

A.每个顶点的度数至少为1

B.任意两个顶点之间都有边相连

C.任意两个顶点之间都有路径相连

D.每个顶点至少都连有一-条边

9.考虑由N个顶点构成的有向连通图，采用邻接矩阵的数据结构表示时，该矩阵中至少存在
( )个非零元素。

A.N-1

B.N

C.N+1

D.N^2

10.共有8人选修了程序设计课程，期末大作业要求由2人组成的团队完成。假设不区分每个团队内2人的角色和作用，请问共有多少种可能的组队方案。( )

A.28

B.32

C.56

D. 64

A.20280

B. 52000

C.676000

D.1757600

12.给定地址区间为0~9的哈希表，哈希函数为h(x) = x % 10，采用线性探查的冲突解决策略(对于出现冲突情况，会往后探查第一个空的地址存储:若地址9冲突了则从地址0重新开始探查)。哈希表初始为空表，依次存储(71, 23, 73，99，44，79，89)后，请问89存储在哈希表哪个地址中。( )

A.9

B.0

C.1

D.2

13.对于给定的n,分析以下代码段对应的时间复杂度，其中最为准确的时间复杂度为( )。

A.0(n)

B.0(n logn)

C.0(n√n)

D.0(n2)

14.以比较为基本运算，在n个数的数组中找最大的数，在最坏情况下至少要做( ) 次运算。

A. n/2

B. n-1

C. n

D. n+1

A.5

B.7

C.9

D.13

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

判断题：

16.)当输入为“abcde fg''时，输出为-1。( )。( )

对

错

17.当输入为"abbababbbab abab"时，输出为4。（）

对

错

18.程序总是输出一个整数"0".( )

对

错

单选题

19.该算法最坏情况下的时间复杂度为( )。（）

A.0(n + m)

B.0(n logm)

C.0(m logn)

D.0(nm)

20.f(a, b)与下列( ) 语句的功能最类似。

A.a. find(b)

B.a. rfind(b)

C.a. substr(b)

D.a. compare(b)

21.当输入为“baaabaabaaabaaaa aaaa”，第20行的“j++"语句执行次数为( ) 。

A.9

B.10

C.11

D.12

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

判断题

22.这是一个不稳定的排序算法。( )

对

错

23 .该算法的空间复杂度仅与n有关。( )

对

错

24.该算法的时间复杂度为0(m(n + k))。 ( )

对

错

单选题

25.25.当输入为“5 3 98 26 91 37 46”时，程序第一.次执行到第36行，val[]数组的内容依次为( )

A. 91 26 46 37 98

B. 91 46 37 26 98

C. 98 26 46 91 37

D. 91 37 46 98 26

26.若val[i]的最大值为100，k取( )时算法运算次数最少。( )。

.A.2

B.3

C.10

D.不确定

27.当输入的k比val[i]的最大值还大时，该算法退化为( ) 算法。( )

A. 选择排序

B, 冒泡排序

C. 计数排序

D. 桶排序

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

假设int为32位有符号整数类型，输入的n是不超过47000的自然数、k是不超过int 表示范围的自然数，完成下面的判断题和单选题：

•判断题

28.该算法的时间复杂度为0( log/k n)。（）

对

错

29.删除第23行的强制类型转换，程序的行为不变。（）

对

错

30.除非输入的n为0，否则程序输出的字符数为0(logk|n|]+1)。.（）

对

错

单选题

31.当输入为“100 7”时，输出为( )。

A. 202

B. 1515

C.244

D.1754

32.当输入为“-255"时，输出为()（）

A.1400

B.1401

C401

D.400

33.当输入为“1000000 19时，输出为()（）

A.BG939

B.87GIB

C87GIB

D.7CF1B

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

34 .①处应填（）

A. (m1+m2)*2

B. (m1-m2)+(m1+m2)

C. m1+m2

D.(m1+1)+(m2+1)

36. ②处应填( )

A.a1[m1]==a2[m2]

B. a1[m1]＜=a2[m2]

C. a1[m1]>=a2[m2]

D. a1[m1]!=a2[m2]

37.③处应填( )

A.left1 == right1

B. left1 ＜ right1

C.left1 > right1

D.left1 != right1

38 .④处应填( )

A. y = a1[k-left2 - 1]

B. y = a1[k- 1eft2]

C.y = a2[k-left1- 1]

D.y = a2[k- 1eft1]

39 .⑤处应填( )

A. y = a1[k-1eft2 - 1]

B. y = a1[k-left2]

C.y = a2[k=left1-1]

D. y = a2[k-1eft1]

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

40.①处应填（）

A.dfs(x+t,y-t)+1

B.dfs(x+t, y- t)

C.dfs(x-t,y+t)+1

D.dfs(x -t,y+t)

41 .②处应填（）

A. dfs(x + t, y-t)+1

B.dfs(X+ t, y-t)-1

C.dfs(x-t,y+ t)+1

D.dfs(x-t, y+t)-1

42.③处应填()

A.X==C||y==C

B.X==C&&y==C

C. X>=C||y>=C

D.x >=C&&y>=C

43.④处应填( )

A. dfs(x+t,y-t)+1

B. dfs(x+ t, y-t)-1

C.dfs(x-t,y+t)+1

D. dfs(x-t,y+t)-1

44.⑤处应填( )

A. dfs(x+t,y-t)+1

B.dfs(x+t,y-t)

C.dfs(x - t,y+t)+1

D. dfs(x -t,y+ t)-1