#5136. 2022 CCF 非专业级别软件能力认证第一轮 CSP -S1
2022 CCF 非专业级别软件能力认证第一轮 CSP -S1
一、单项选择题(共 15 题,每题 2 分,共计 30 分;每题有且仅有一个正确选项)
- 在Linux系统终端中,用于切换工作目录的命令为( )。 {{ select(1) }}
- ls
- cd
- cp
- all
- 你同时用 time 命令和秒表为某个程序在单核 CPU 的运行计时。假如 time 命令的输出如 下:
real 0m30.721s
user 0m24.579s
sys 0m6.123s
以下最接近秒表计时的时长为( )。 {{ select(2) }}
- 30s
- 24s
- 18s
- 6s
- 若元素 a、b、c、d、e、f 依次进栈,允许进栈、退栈操作交替进行,但不允许连续三次 退栈操作,则不可能得到的出栈序列是( )。 {{ select(3) }}
- dcebfa
- cbdaef
- bcaefd
- afedcb
- 考虑对n个数进行排序,以下最坏时间复杂度低于O(n2)的排序方法是( )。 {{ select(4) }}
- 插入排序
- 冒泡排序
- 归并排序
- 快速排序
- 假设在基数排序过程中,受宇宙射线的影响,某项数据异变为一个完全不同的值。请问排 序算法结束后,可能出现的最坏情况是( )。 {{ select(5) }}
- 移除受影响的数据后,最终序列是有序序列
- 移除受影响的数据后,最终序列是前后两个有序的子序列
- 移除受影响的数据后,最终序列是一个有序的子序列和一个基本无序的子序列
- 移除受影响的数据后,最终序列基本无序
- 计算机系统用小端(Little Endian)和大端(Big Endian)来描述多字节数据的存储地 址顺序模式,其中小端表示将低位字节数据存储在低地址的模式、大端表示将高位字节数 据存储在低地址的模式。在小端模式的系统和大端模式的系统分别编译和运行以下 C++代 码段表示的程序,将分别输出什么结果?( )
unsigned x = 0xDEADBEEF;
unsigned char *p = (unsigned char *)&x;
printf("%X", *p);
{{ select(6) }}
- EF、EF
- EF、DE
- DE、EF
- DE、DE
- 一个深度为 5(根结点深度为 1)的完全 3 叉树,按前序遍历的顺序给结点从 1 开始编号,则第100号结点的父结点是第( )号。 {{ select(7) }}
- 95
- 96
- 97
- 98
- 强连通图的性质不包括( ): {{ select(8) }}
- 每个顶点的度数至少为 1
- 任意两个顶点之间都有边相连
- 任意两个顶点之间都有路径相连
- 每个顶点至少都连有一条边
- 每个顶点度数均为 2 的无向图称为“2 正规图”。由编号为从 1 到 n 的顶点构成的所有 2 正 规图,其中包含欧拉回路的不同2正规图的数量为( )。 {{ select(9) }}
- n!
- (n-1)!
- n!/2
- (n-1)!/2
- 共有8人选修了程序设计课程,期末大作业要求由2人组成的团队完成。假设不区分每个 团队内2人的角色和作用,请问共有多少种可能的组队方案。( ) {{ select(10) }}
- 28
- 32
- 56
- 64
- 小明希望选到形如“省 A·LL𝒟𝒟𝒟𝒟𝒟𝒟”的车牌号。车牌号在“·”之前的内容固定不变;后面 的 5 位号码中,前 2 位必须是大写英文字母,后 3 位必须是阿拉伯数字(L代表 A 至 Z,𝒟𝒟 表示 0 至 9,两个L和三个𝒟𝒟之间可能相同也可能不同)。请问总共有多少个可供选择的车牌号。( ) {{ select(11) }}
- 20280
- 52000
- 676000
- 1757600
- 给定地址区间为0~9的哈希表,哈希函数为h(x) = x % 10,采用线性探查的冲突解决 策略(对于出现冲突情况,会往后探查第一个空的地址存储;若地址 9 冲突了则从地址 0 重新开始探查)。哈希表初始为空表,依次存储(71, 23, 73, 99, 44, 79, 89)后,请 问89存储在哈希表哪个地址中。( ) {{ select(12) }}
- 9
- 0
- 1
- 2
13.对于给定的n,分析以下代码段对应的时间复杂度,其中最为准确的时间复杂度为( )。
int i, j, k = 0;
for (i = 0; i < n; i++) {
for (j = 0; j < n; j*=2) {
k = k + n / 2;
}
}
{{ select(13) }}
14.以比较为基本运算,在n个数的数组中找最大的数,在最坏情况下至少要做( )次运算。 {{ select(14) }}
- n/2
- n-1
- n
- n+1
- ack函数在输入参数“(2,2)”时的返回值为( )。
unsigned ack(unsigned m, unsigned n) {
if (m == 0) return n + 1;
if (n == 0) return ack(m - 1, 1);
return ack(m - 1, ack(m, n - 1));
}
{{ select(15) }}
- 5
- 7
- 9
- 13
二、阅读程序(程序输入不超过数组或字符串定义的范围;判断题正确填√,错误填×;除特 殊说明外,判断题 1.5 分,选择题 3 分,共计 40 分)
(1)
假设输入字符串由 ASCII 可见字符组成,完成下面的判断题和单选题:
判断题
- (1 分)当输入为“abcde fg”时,输出为-1。( ) {{ select(16) }}
- 正确
- 错误
- 当输入为“abbababbbab abab”时,输出为 4。( ) {{ select(17) }}
- 正确
- 错误
- 当输入为“GoodLuckCsp2022 22”时,第 20 行的“j++”语句执行次数为 2。 () {{ select(18) }}
- 正确
- 错误
单选题
- 该算法最坏情况下的时间复杂度为( )。 {{ select(19) }}
- 𝑂(𝑛+𝑚)
- 𝑂(𝑛log𝑚)
- 𝑂(𝑚log𝑛)
- 𝑂(𝑛𝑚)
- f(a, b)与下列( )语句的功能最类似。 {{ select(20) }}
- a.find(b)
- a.rfind(b)
- a.substr(b)
- a.compare(b)
- 当输入为“baaabaaabaaabaaaa aaaa”,第 20 行的“j++”语句执行次数为 ( )。 {{ select(21) }}
- 9
- 10
- 11
- 12
(2)
假设输入的 n 为不大于 100 的正整数,k 为不小于 2 且不大于 100 的正整数,val[i]在 int 表示范围内,完成下面的判断题和单选题:
判断题
22.这是一个不稳定的排序算法。( ) {{ select(22) }}
- 正确
- 错误
23.该算法的空间复杂度仅与n有关。( ) {{ select(23) }}
- 正确
- 错误
24.该算法的时间复杂度为。( ) {{ select(24) }}
- 正确
- 错误
单选题
25.当输入为“5 3 98 26 91 37 46”时,程序第一次执行到第 36 行,val[]数组的 内容依次为( )。 {{ select(25) }}
- 91 26 46 37 98
- 91 46 37 26 98
- 98 26 46 91 37
- 91 37 46 98 26
26.若val[i]的最大值为100,k取( )时算法运算次数最少。 {{ select(26) }}
- 2
- 3
- 10
- 不确定
27.当输入的k比val[i]的最大值还大时,该算法退化为( )算法。 {{ select(27) }}
- 选择排序
- 冒泡排序
- 计数排序
- 桶排序
(3)
假设输入的 n 在 int 范围内,k 为不小于 2 且不大于 36 的正整数,完成下面的判断题和 单选题:
判断题
- 该算法的时间复杂度为。( ) {{ select(28) }}
- 正确
- 错误
- 删除第23行的强制类型转换,程序的行为不变。( ) {{ select(29) }}
- 正确
- 错误
- 除非输入的n为0,否则程序输出的字符数为。( ) {{ select(30) }}
- 正确
- 错误
单选题 31.当输入为“100 7”时,输出为( )。 {{ select(31) }}
- 202
- 1515
- 244
- 1754
32.当输入为“-255 8”时,输出为“( )”。 {{ select(32) }}
- 1400
- 1401
- 417
- 400
33.当输入为“1000000 19”时,输出为“( )”。 {{ select(33) }}
- BG939
- 87GIB
- 1CD428
- 7CF1B
三、 完善程序(单选题,每小题3分,共计30分)
(1) (归并第 k 小)已知两个长度均为 n 的有序数组 a1 和 a2(均为递增序,但不保证严 格单调递增),并且给定正整数 k(1≤k≤2n),求数组 a1 和 a2 归并排序后的数组里 第 k 小的数值。 试补全程序。
- 1处应填( ) {{ select(34) }}
- (m1+m2)*2
- (m1-1)+(m2-1)
- m1+m2
- (m1+1)+(m2+1)
- 2处应填( ) {{ select(35) }}
- a1[m1]==a2[m2]
- a1[m1]<=a2[m2]
- a1[m1]>=a2[m2]
- a1[m1]!=a2[m2]
- 3处应填( ) {{ select(36) }}
- left1==right1
- left1<right1
- left1>right1
- left1!=right1
- 4处应填( ) {{ select(37) }}
- y=a1[k-left2-1]
- y=a1[k-left2]
- y=a2[k-left1-1]
- y=a2[k-left1]
- 5处应填( ) {{ select(38) }}
- y=a1[k-left2-1]
- y=a1[k-left2]
- y=a2[k-left1-1]
- y=a2[k-left1]
(2)(容器分水)有两个容器,容器 1 的容量为为 a 升,容器 2 的容量为 b 升;同时允 许下列的三种操作,分别为:
1)FILL(i):用水龙头将容器 i(i∈{1,2})灌满水;
2)DROP(i):将容器 i 的水倒进下水道;
3)POUR(i,j):将容器 i 的水倒进容器 j(完成此操作后,要么容器 j 被灌满,要
么容器 i 被清空)。
求只使用上述的两个容器和三种操作,获得恰好 c 升水的最少操作数和操作序列。上
述 a、b、c 均为不超过 100 的正整数,且 c≤max{a,b}。
试补全程序。
39.1处应填( ) {{ select(39) }}
- dfs(x+t,y-t)+1
- dfs(x+t,y-t)-1
- dfs(x-t,y+t)+1
- dfs(x-t,y+t)-1
40.2处应填( ) {{ select(40) }}
- dfs(x+t,y-t)+1
- dfs(x+t,y-t)-1
- dfs(x-t,y+t)+1
- dfs(x-t,y+t)-1
41.3处应填( ) {{ select(41) }}
- x==c||y==c
- x==c&&y==c
- x>=c||y>=c
- x>=c&&y>=c
42.4处应填( ) {{ select(42) }}
- dfs(x+t,y-t)+1
- dfs(x+t,y-t)-1
- dfs(x-t,y+t)+1
- dfs(x-t,y+t)-1
43.5处应填( ) {{ select(43) }}
- dfs(x+t,y-t)+1
- dfs(x+t,y-t)-1
- dfs(x-t,y+t)+1
- dfs(x-t,y+t)-1