因为觉得把初赛试题整理放在一篇博客里面显得很拥挤，所以就分成两篇整理啦qwq
上一篇博客
1．在编程时（使用任一种高级语言，不一定是
C
+
+
C++
C++），如果需要从磁盘文件中输入一个很大的二维数组（例如
1000
×
1000
1000\times1000
1000×1000 的
d
o
u
b
l
e
double
double 型数组），按行读（即外层循环是关于行的）与按列读（即外层循环是关于列的）相比，在输入效率上（）。
A. 没有区别
B. 按行读的方式要高一些
C. 按列读的方式要高一些
D. 取决于数组的存储方式。
答案：D
解析： 由于
1000
×
1000
1000 \times 1000
1000×1000的二维数组行与列相同，单纯从执行时间上考虑两者应该是一样的，所以排除
B
B
B，
C
C
C。而如果数组是按行存储的，那么按行读效率要高，如果数据是按列存储的，那么按列读效率要高。
2.某个
M
V
MV
MV 是一段时长
4
4
4 分整的视频文件。它每秒播放
10
10
10 帧图像，每帧图像是一幅分辨率为
2048
×
1152
2048\times1152
2048×1152 像素（长宽比
16
:
9
16:9
16:9）的
32
32
32 位真彩色图像，其画面没有被压缩。其音频的比特率是
128
k
b
p
s
128kbps
128kbps。这个视频文件大约需要占用多大的存储空间？（ ）。
A. 21 GiB
B. 27 GiB
C. 168 GiB
D. 2 GiB
答案：A
解析： 计算过程为：
2048
×
1152
×
32
×
10
×
60
×
4
÷
8
÷
1024
÷
1024
÷
1024
=
21.0975
G
i
B
≈
21
G
i
B
2048\times1152\times32\times10\times60\times4\div8\div1024\div1024\div1024=21.0975 GiB\approx21 GiB
2048×1152×32×10×60×4÷8÷1024÷1024÷1024=21.0975GiB≈21GiB
3.同时扔出
𝑘
𝑘
k 枚完全相同的六面骰子，每个骰子上有
1
1
1 到
6
6
6 的数字。将得到的点数排序后，有（ ）种不同的结果？
A.
6
𝑘
−
2
𝑘
6^𝑘 − 2^𝑘
6k−2k
B.
𝐴
𝑘
+
2
𝑘
−
1
𝐴_{𝑘+2}^{𝑘−1}
Ak+2k−1
C.
6
k
6^k
6k
D.
𝐶
𝑘
+
6
−
1
𝑘
𝐶_{𝑘+6−1}^𝑘
Ck+6−1k
答案：D
解析： 相当于求在
k
+
5
k+5
k+5 个数中取
k
k
k 个数的方案数。
4.定义
m
o
d
\bmod
mod 为取模运算，
𝑛
!
=
1
⋅
2
⋅
3
⋯
𝑛
𝑛! = 1 ⋅ 2 ⋅ 3 ⋯ 𝑛
n!=1⋅2⋅3⋯n，则下式的值为（ ）。
(
(
1
+
1
2
+
1
3
+
1
4
+
⋯
1
10086
)
×
(
10085
!
)
+
10081
)
m
o
d
10086
((1 +\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+⋯\frac{1}{10086})\times(10085!) + 10081) \bmod 10086
((1+21+31+41+⋯100861)×(10085!)+10081)mod10086
A. 10081
B. 10085
C. 0
D. 10083
答案：A
解析： 易知
10086
=
2
×
3
×
41
×
41
10086=2\times3\times41\times41
10086=2×3×41×41 ，
(
1
+
1
2
+
1
3
+
1
4
+
⋯
1
10086
)
×
(
10085
!
)
=
1
×
(
10085
!
)
+
1
2
×
(
10085
!
)
+
1
3
×
(
10085
!
)
+
1
4
×
(
10085
!
)
+
⋯
+
1
10086
×
(
10085
!
)
(1 +\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+⋯\frac{1}{10086})\times(10085!)=1\times(10085!)+\frac{1}{2}\times(10085!)+\frac{1}{3}\times(10085!)+\frac{1}{4}\times(10085!)+⋯+\frac{1}{10086}\times(10085!)
(1+21+31+41+⋯100861)×(10085!)=1×(10085!)+21×(10085!)+31×(10085!)+41×(10085!)+⋯+100861×(10085!) ，则对于每一个
10085
!
n
,
1
≤
n
≤
10086
\frac{10085!}{n},1\le n\le10086
n10085!,1≤n≤10086 ，都有
10085
!
n
∣
10086
\frac{10085!}{n}\mid10086
n10085!∣10086 ，所以题目等价于求
10081
m
o
d
10086
10081\bmod10086
10081mod10086，结果为
10081
10081
10081 。
5. 若某算法的时间计算表示为递推关系式：
T
(
n
)
=
9
T
(
n
/
3
)
+
n
T(n)=9T(n/3)+n
T(n)=9T(n/3)+n
T
(
1
)
=
1
T(1)=1
T(1)=1
则该算法的时间复杂度是（）
A.
Θ
(
n
)
Θ(n)
Θ(n)
B.
Θ
(
2
n
)
Θ(2^n)
Θ(2n)
C.
Θ
(
n
2
)
Θ(n^2)
Θ(n2)
D.
Θ
(
n
l
o
g
n
)
Θ(nlogn)
Θ(nlogn)
答案：C
解析：
假设存在常数
ϵ
>
0
ϵ>0
ϵ>0，使得
f
(
n
)
=
O
(
n
l
o
g
b
(
a
)
−
ϵ
)
f(n)=O(n^{log_b(a)−ϵ})
f(n)=O(nlogb(a)−ϵ) ，则
T
(
n
)
=
Θ
(
n
l
o
g
b
a
)
T(n)=Θ(n^{log_ba})
T(n)=Θ(nlogba) ，由此可知答案。
具体参见该博客
1.设变量
x
x
x 为
i
n
t
int
int 型且已赋值，则以下语句能将
x
x
x 二进制下第
0
∼
𝑘
−
1
0 \sim 𝑘-1
0∼k−1 位清零，并保持其余位不变的操作是（ ） 答案：C 2.由数字1,2,3,4,5,6,7（同一数字可以重复使用）所组成的不同的三位数中有（ ）个是3的倍数 答案：D *注：模数为012时可以组成012、021、102、120、201、210共6种情况，如： 3.用邻接矩阵来存储一张具有
𝑛
𝑛
n 个顶点，
𝑚
𝑚
m 条边的图。则进行深度优先遍历运算的时间复杂度为（ ） 答案：A 4.1414至多可以表示为（ ）个不同的正整数之和 答案：C 5. 以下排序算法中，（ ）是不稳定排序 答案：D 1. 计算机辅助制造的简写是（ ） 答案：A 2.若
𝑛
𝑛
n ,
𝑚
𝑚
m 都是 0~255 中的整数，则有（ ）对
𝑛
𝑛
n ,
𝑚
𝑚
m 满足 n + m = (n and m) xor (n or m)。 答案：B
A. x &= (1<
解析： (1<
A. 43
B. 72
C. 78
D.115
解析： 不难发现将每一位上的数字模3后，3个余数所构成的元素必须为三个0、三个1、三个2、012中的一种。据此对方案进行讨论即可。
三个0：
2
×
2
×
2
=
8
2\times2\times2=8
2×2×2=8种；
三个1：
3
×
3
×
3
=
27
3\times3\times3=27
3×3×3=27种；
三个2：
2
×
2
×
2
=
8
2\times2\times2=8
2×2×2=8种；
012*：
6
×
2
×
3
×
2
=
72
6\times2\times3\times2=72
6×2×3×2=72种；
总方案数：
8
+
27
+
8
+
72
=
115
8+27+8+72=115
8+27+8+72=115种。
123，132，213，231，312，321为6个满足要求的三位数。
A.
O
(
𝑛
2
)
O(𝑛^2)
O(n2)
B.
O
(
𝑚
2
)
O(𝑚^2)
O(m2)
C.
O
(
𝑛
𝑚
)
O(𝑛𝑚 )
O(nm)
D.
O
(
𝑛
+
𝑚
)
O(𝑛+𝑚 )
O(n+m)
解析： 由于是邻接矩阵，对于每个点都必须
O
(
n
)
O(n)
O(n) 找边，所以总复杂度为
O
(
n
2
)
O(n^2)
O(n2)。
A.50
B.51
C.52
D.53
解析： 找到最大的数
n
n
n 满足
n
(
n
+
1
)
2
≤
1414
\tfrac{n(n + 1)}{2}≤1414
2n(n+1)≤1414 即可。
A.桶排序
B.归并排序
C.冒泡排序
D.选择排序
解析： 冒泡排序、插入排序、归并排序、计数排序、桶排序、基数排序为稳定排序；
选择排序、希尔排序、快速排序、堆排序为不稳定排序。
CSP-S2021初赛模拟赛 ⅠⅠ
A.CAM
B.CAD
C.CAI
D.CAT
解析： 考查计算机基础知识。
A.256
B.6561
C.6739
D.65536
解析： 分别考虑每一位，只要满足不都是
1
1
1 即可，因此答案为
3
8
=
6561
3^8 = 6561
38=6561。