1. 观察下列代码

   int a[] = {5, 4, 3, 2, 1};
   auto p = a + 3;
   auto q = &p;
   (*q) ++;
   auto k = *p;
   

其中，𝑘 的类型以及 𝑘 的值分别为（ ）。

A. int 类型，值为 1

B. int 类型，值为 3

C. int 指针类型，值为 𝑎 数组的下标为 3 的元素的地址

D. int 指针类型，值为 𝑎 数组的下标为 4 的元素的地址

题解思路

这段代码中的&是取地址符，*是取数值符，地址+1就是下一个的地址，而数组下标是从零开始的，所以+3指的是第四个，后面p的地址q还加了1，目前指向的就是第五个，k又是p的数值，所以k是int类型，值为1。

---

2. 一张大小为 6114 × 8192 的 24 位彩色图片，使用 .bmp 格式存储，占用的空间大小约为（ ）。

A. 144 MiB

B. 288 MiB

C. 1152 MiB

D. 48 MiB

题解思路

基本常识，图片内存大小=长×宽×位数(bit),计算可知，$6114×8192×24=1202061312$，换算一下，就是$1202061312÷8÷1024÷1024=143.39$，选最接近的A。

---

3. 以下程序片段的时间复杂度为（ ）。

int cnt = 0; 
for(int i = 1;i <= n;i ++){
    for(int j = 1;j <= n;j += i){
        for(int k = 1;k <= n;k += j){
            ++ cnt;
        }
    }
}

A. $Θ(𝑛^2 )$

B. $Θ(𝑛 ^2 log 𝑛)$

C. $Θ(𝑛 log 𝑛)$

D. $Θ(𝑛 log^2 𝑛)$

题解思路

让我们逐步分析： 最外层循环：$n$ 中间层循环：$n/1+n/2+n/3+···+n/n$，这些数的平均数约等于是$n/2$，此时我们看作$n/2$ 最内层循环：$n/1+n/2+n/3+···+n/n+n/2+n/4+n/6+···$，这些数的平均数约等于是$n/2$，此时我们看作$n/2$。 那么总时间复杂度就是$n+n/2*n+n/2*n$，忽略常数项、低次项，得到$n^2$，所以总时间复杂度就是$Θ(𝑛^2 )$。

---

4. 依次抛出四个六面骰子，按照抛出顺序将骰子上的数值记为 𝑎, 𝑏, 𝑐, 𝑑。则 $a < b;b > c; c < d$ 同时成立的概率为（ ）。

A. 95/648

B. 4/27

C. 5/27

D. 1/6

题解思路

对于每一个 (a) 的取值，我们可以计算出对应的排列数： (a) 的取值范围为 1 到 5。 对于每一个 (a)，(b) 的取值范围为 (a+1) 到 6。 对于每一个 (b)，(c) 的取值范围为 1 到 (b-1)。 对于每一个 (c)，(d) 的取值范围为 (c+1) 到 6。

公式

---

总排列数 $(N)$ 可以通过累加计算得出：

$N = \sum_\{a=1\}^{5} \left( \sum_{b=a+1}^{6} \left( \sum_{c=1}^{b-1} \left( 6 - c \right) \right) \right)$

通过累加计算，我们可以得出最终的排列数为 190 种。

---

5. 观察如下代码片段：

   union U{
       bool flag1, flag2, flag3, flag4, flag5;
       signed short a;unsigned short b;
       enum E{
           CardA = 0, CardB = 1,CardC = 2, CardD = 142857
       } e;
   } u;
   

其中， sizeof(u) 的值为（ ）。

A. 4

B. 8

C. 13

D. 16

题解思路

• bool 类型成员占 1 字节。
• signed short 和 unsigned short 类型成员各占 2 字节。
• 枚举类型成员占至少 4 字节。 在 union 中，成员共享相同的内存区域，因此 union U 的大小由其中最大的成员决定。在这里，枚举类型 E 的大小为 4 字节，这是 union U 中最大的成员。
• sizeof(u) 的值为 ​4 字节​。

---

6. 已知某种可用来维护序列的数据结构，支持 $Θ(log 𝑛)$ 向某个位置后面插入元素、$Θ(𝑛)$ 查询某个元素的排名，$Θ(𝑛 log 𝑛)$ 遍历整个序列，那么用上述三种操作实现插

入排序的时间复杂度最坏为（ ）。

A. $Θ(𝑛^2 )$

B. $Θ(n^2 log n)$

C. $Θ(n log n)$

D. $Θ(n log^2 n)$

题解思路

插入排序分为找$n$次第一个比$a_i$大数（遍历）、获取排名、插入。可推出总时间复杂度为$T(nlogn+n^2+nlogn)$，省略低次项得出$Θ(𝑛^2 )$。

---

15. 今年是 CCF（中国计算机学会）第（ ）次举办 CSP-J/S（计算机非专业级别的

软件能力认证）？

A. 27

B. 28

C. 5

D. 4

题解思路

基本常识，NOI从2018年改名CSP-J/S。