Aug.Day13 8.20总结

【初赛复习进行中】

一、单项选择题

Wrong Problems:

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

A. $144$ MiB (正确)

B. $288$ MiB

C. $1152$ MiB

D. $48$ MiB

分析：

图片总位数：$6114 \times 8192 \times 24=1,202,061,312$(位，bit)

$1,202,061,312 \div 8=150,257,664$(字节，Byte)

$150,257,664 \div 1024=146,736$(千字节，KiB)

$146,736 \div 1024=143.296875≈144$(兆字节，MiB)

选 A。

错误原因：忘记除以 $8$ 了，结果变成了约 $1152$ MiB qwq。

---

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

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

提示：

$$\frac{n}{1^1} + \frac{n}{2^1} + \frac{n}{3^1} +··· \ + \frac{n}{n_1} ≈C_1 \times \log{n} \\ \frac{n}{1^2} + \frac{n}{2^2} + \frac{n}{3^2} +··· \ + \frac{n}{n^2} ≈C_2$$

其中 $C_1,C_2$ 均为常数。

A. $\operatorname{Θ} (n^2)$ (正确)

B. $\operatorname{Θ} (n^2 \log{n})$

C. $\operatorname{Θ} (n \log(n))$

D. $\operatorname{Θ} (n \log^2n)$

分析：

枚举最坏情况，$i=1$。

那么 for (j : 1 ~ n; j += i) 的时间复杂度就是 $\operatorname{Θ} (n)$，for (k : 1 ~ n; k += j) 就是 k += 1, k += 2, k += 3 ...，那么就是 $\operatorname{Θ} (n)$（等差数列时间复杂度为 $\operatorname{Θ} (n)$），加上常数就是 $\operatorname{Θ} (n^2)$。

错误原因：被提示迷惑力 qwq x2。

---

11.依次抛出四个六面骰子，按照抛出顺序将骰子上的数值记为 $a,b,c,d$。则 $(a<b) \ (b>c) \ (c<d)$ 成立的概率为（ ）。

A. $\dfrac{95}{648}$ (正确)

B. $\dfrac{4}{27}$

C. $\dfrac{5}{27}$

D. $\dfrac{1}{6}$

分析：

枚举！枚举！还是枚举！

                                   a = 1
                  |         |        |       |        |
                b = 2     b = 3     b = 4  b = 5    b = 6
                  |       |   |    |  |  | | | | |  | | | | |
          c = 1   c = 1, 2 c = 1, 2, 3 c = 1, 2, 3, 4 c = 1, 2, 3, 4, 5
            |       |        |               |               |
 ans +=:    5     5, 4    5, 4, 3     5, 4, 3, 2      5, 4, 3, 2, 1  -> ans += 55
                      
                                     a = 2
                 |               |            |             |
              b = 3            b = 4         b = 5        b = 6
               |  |          |   |   |    |  |  |  |     | | | | |
              c = 1, 2     c = 1, 2, 3    c = 1, 2, 3, 4 c = 1, 2, 3, 4, 5
                 |               |              |             |
 ans +=:      5, 4           5, 4, 3       5, 4, 3, 2     5, 4, 3, 2, 1 -> ans += 50
                                            
                                   .........
     
                              Tips: a = 6 时，没有成立的。
              
                         ans = 55 + 50 + 41 + 29 + 15 = 190

错误原因：啊啊啊又没想着枚举（ 懒 ），蒙的啊啊啊啊 qwq x3。

---

13.观察如下代码片段：

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$

分析：

union，联合体，特点为所有元素共用一个地址，联合体的大小为其中最大变量的大小。

而这里的最大变量为 enum E，所以需要求 e 的大小。

e 里有 $4$ 个整数，也就是 int 类型，enum 枚举类型中的整数只占一个整型，所以 sizeof (u) = sizeof (e) = 4。

错误原因：对于 enum 类型的大小不熟悉 qwq x4。

---

14.已知某种可用来维护序列的数据结构，支持 $\operatorname{Θ} (\log{n})$ 向某个位置后面插入元素、$\operatorname{Θ} (n)$ 查询某个元素的排名，$\operatorname{Θ} (n \log{n})$ 遍历整个序列，那么用上述三种操作实现插入排序的时间复杂度最坏为（ ）。

A. $\operatorname{Θ} (n^2)$ (正确)

B. $\operatorname{Θ} (n^2 \log{n})$

C. $\operatorname{Θ} (n \log{n})$

D. $\operatorname{Θ} (n \log^2 n)$

分析：

插入排序中 $\operatorname{Θ} (n)$ 是在遍历，另外 $\operatorname{Θ} (n)$ 是查找并在结果数组中赋值，而这里遍历的 $\operatorname{Θ} (n \log n)$ 被 $\operatorname{Θ} (\log n)$ 抵消了，所以就是 $\operatorname{Θ} (n^2)$。

错误原因：对插入排序掌握不牢固（ 连插入排序怎么写都不知道了 ）qwq x5。

---

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

A. $27$

B. $28$

C. $5$ (正确)

D. $4$

分析：

CCF 在 2019 年正式将 NOIP 改为 CSP-J/S，且本试卷制作时间为 2023 年，所以次数是 2023 - 2019 + 1 = 5。

错误原因：阿巴阿巴阿巴还是对 NOI 系列赛事历史不了解 qwq x6。