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