一、单选题（每题 2 分，共 30 分）

1. 为丰富食堂菜谱，炒菜部进行头脑风暴。肉类有鸡肉、牛肉、羊肉、猪肉 $4$ 种，切法有肉排、肉块、肉末 $3$ 种，配菜有圆白菜、油菜、豆腐 $3$ 种，辣度有麻辣、微辣、不辣 $3$ 种。不考虑口感的情况下，选 $1$ 种肉、$1$ 种切法、$1$ 种配菜、$1$ 种辣度产生一道菜（例如：麻辣牛肉片炒豆腐），这样能产生多少道菜？（ ）

{{ select(1) }}

• $13$
• $42$
• $63$
• $108$

2. 已知袋中有 $2$ 个相同的红球、$3$ 个相同的绿球、$5$ 个相同的黄球。每次取出一个不放回，全部取出。可能产生多少种序列？（ ）

{{ select(2) }}

• $6$
• $1440$
• $2520$
• $3628800$

3. 以下二维数组的初始化，哪个是符合语法的？（ ）。

{{ select(3) }}

• int a[][] = {{1, 2}, {3, 4}};
• int a[][2] = {};
• int a[2][2] = {{1, 2, 3}, {4, 5, 6}};
• int a[2][] = {{1, 2, 3}, {4, 5, 6}};

4. 下面有关 $\tt C$++ 拷贝构造函数的说法，错误的是（ ）。

{{ select(4) }}

• 必须实现拷贝构造函数，否则一定会出现编译错误
• 对象作为函数参数、以值传递方式传入函数时，会自动调用拷贝构造函数
• 对象作为函数返回值、以值传递方式从函数返回时，会自动调用拷贝构造函数
• 使用一个对象初始化另一个对象时，会自动调用拷贝构造函数

5. 使用邻接表表达一个无向简单图，图中包含 $v$ 个顶点、$e$ 条边，则该表中边节点的个数为（ ）。

{{ select(5) }}

• $v \times (v-1)$
• $v \times v$
• $2 \times e$
• $e$

6. 关于生成树的说法，错误的是（ ）。

{{ select(6) }}

• 一个无向连通图可以有多个生成树
• 一个无向图，只要连通，就一定有生成树
• $n$ 个顶点的无向完全图，有 $n^{n-2}$ 棵生成树
• $n$ 个顶点的无向图，生成树包含 $n-1$ 条边

7. 已知三个 $\tt double$ 类型的变量 $a$、$b$ 和 $\tt theta$ 分别表示一个三角形的两条边长及二者的夹角（弧度），则下列哪个表达式可以计算这个三角形的周长？（ ）

{{ select(7) }}

• a * b * sin(theta) / 2
• a + b + (a + b) * sin(theta) / 2
• a * b * cos(theta) / 2
• a + b + sqrt(a * a + b * b - 2 * a * b * cos(theta))

8. 在有 $n$ 个元素的二叉排序树中进行查找，其最好、最差时间复杂度分别为（ ）。

{{ select(8) }}

• $O(1)$，$O(n)$
• $O(1)$，$O(\log n)$
• $O(\log n)$，$O(\log n)$
• $O(\log n)$，$O(n)$

9. 如下图所示，半径为 $r$、圆心角为 $t$（弧度）的扇形，下面哪个表达式能够求出顶部阴影部分的面积？（ ）

   

{{ select(9) }}

• r * r * sin(t) / 2
• r * r * t / 2
• r * r * (t - sin(t))
• r * r * (t - sin(t)) / 2

10. 下面程序的时间复杂度为（ ）。

    int fib(int n) {
        if (n <= 1)
            return 1;
        return fib(n - 1) + fib(n - 2);
    }
    

{{ select(10) }}

• $O(2^n)$
• $O(\phi^n)$，其中 $\phi=\frac{\sqrt{5}+1}{2}$
• $O(n)$
• $O(1)$

11. 下面程序的时间复杂度为（ ）。

    int choose(int n, int m) {
        if (m == 0 || m == n)
            return 1;
        return choose(n - 1, m - 1) + choose(n - 1, m);
    }
    

{{ select(11) }}

• $O(2^n)$
• $O(2^m \times (n-m))$
• $O(C(n, m))$
• $O(m \times (n-m))$

12. 下面程序的时间复杂度为（ ）。

    int primes[MAXP], num = 0;
    bool isPrime[MAXN] = {false};
    void sieve() {
        for (int n = 2; n <= MAXN; n++) {
            if (!isPrime[n])
                primes[num++] = n;
            for (int i = 0; i < num && n * primes[i] <= MAXN; i++) {
                isPrime[n * primes[i]] = true;
                if (n % primes[i] == 0)
                    break;
            }
        }
    }
    

{{ select(12) }}

• $O(n)$
• $O(n \times \log n)$
• $O(n \times \log \log n)$
• $O(n^2)$

13. 下面程序的输出为（ ）。

    #include <iostream>
    using namespace std;
    int a[10][10];
    int main() {
        int m = 5, n = 4;
        for (int x = 0; x <= m; x++)
            a[x][0] = 1;
        for (int y = 1; y <= n; y++)
            a[0][y] = 1;
        for (int x = 1; x <= m; x++)
            for (int y = 1; y <= n; y++)
                a[x][y] = a[x - 1][y] + a[x][y - 1];
        cout << a[m][n] << endl;
        return 0;
    }
    

{{ select(13) }}

• $4$
• $5$
• $126$
• $3024$

14. 下面程序的输出为（ ）。

    #include <iostream>
    using namespace std;
    int main() {
        int cnt = 0;
        for (int x = 0; x <= 10; x++)
            for (int y = 0; y <= 10; y++)
                for (int z = 0; z <= 10; z++)
                    if (x + y + z == 15)
                        cnt++;
        cout << cnt << endl;
        return 0;
    }
    

{{ select(14) }}

• $90$
• $91$
• $96$
• $100$

15. 下面的程序使用邻接矩阵表达的带权无向图，则从顶点 $0$ 到顶点 $3$ 的最短距离为（ ）。

    int weight[4][4] = {
        {  0,   1,   7, 100},
        {  1,   0,   5,  15},
        {  7,   5,   0,   6},
        {100,  15,   6,   0}};
    

{{ select(15) }}

• $100$
• $16$
• $12$
• $13$

二、判断题（每题 2 分，共 20 分）

1. 已知 $\tt int$ 类型的变量 $a$ 和 $b$，则执行语句 a, b = b, a; 后，变量 $a$ 和 $b$ 的值会互换。（ ）

{{ select(16) }}

• 正确
• 错误

2. 一个袋子中有 $3$ 个完全相同的红色小球、$2$ 个完全相同的蓝色小球。每次从中取出 $1$ 个，再放回袋子，这样进行 $3$ 次后，可能的颜色顺序有 $7$ 种。（ ）

{{ select(17) }}

• 正确
• 错误

3. 孙子定理是求解一次同余方程组的方法，最早见于中国南北朝时期（公元 $5$ 世纪）的数学著作《孙子算经》。又称中国余数定理，是中国数学史上的一项伟大成就。（ ）

{{ select(18) }}

• 正确
• 错误

4. $N$ 个顶点的无向完全图有 $N \times (N-1)$ 条边。（ ）

{{ select(19) }}

• 正确
• 错误

5. 为解决哈希函数冲突，在哈希表项内设置链表存储该项内的所有冲突元素，则该哈希表内查找元素的最差时间复杂度为 $O(1)$。（ ）

{{ select(20) }}

• 正确
• 错误

6. 求一个包含 $v$ 个顶点、$e$ 条边的带权连通无向图的最小生成树，$\tt Prim$ 算法的时间复杂度为 $O(v \times e)$。（ ）

{{ select(21) }}

• 正确
• 错误

7. 已知 $\tt int$ 类型的变量 $a$、$b$ 和 $c$ 中分别存储着一个三角形的三条边长，则这个三角形的面积可以通过表达 式 sqrt((a + b + c) * (b + c - a) * (a + c - b) * (a + b - c)) / 4 求得。（ ）

{{ select(22) }}

• 正确
• 错误

8. 可以使用深度优先搜索算法判断图的连通性。（ ）

{{ select(23) }}

• 正确
• 错误

9. 在 $N$ 个元素的二叉排序树中查找一个元素，平均情况的时间复杂度是 $O(\log N)$。（ ）

{{ select(24) }}

• 正确
• 错误

10. 给定 $\tt double$ 类型的变量 $x$，且其值大于等于 $1$，我们可以通过二分法求出 $\log x$ 的近似值。（ ）

{{ select(25) }}

• 正确
• 错误