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

第 1 题

小杨要从 A 城到 B 城，又想顺路游览一番。他有两个选项：1、坐高铁路到 C 城游览，再坐高铁或飞机到 B 城；2、坐船到 D 城游览，再坐船、高铁或飞机到 B 城。请问小杨从 A 城到 B 城共有几种交通方案可以选择？（ ）。

{{ select(1) }}

• $2$
• $3$
• $5$
• $6$

---

第 2 题

以下哪个函数声明是符合语法的，且在调用时可以将二维数组的名字作为实际参数传递给形式参数 $a$？（ ）。

{{ select(2) }}

• void QuickSort(int a[][10], int n);
• void QuickSort(int a[5][], int m);
• void QuickSort(int a[][], int n, int m);
• void QuickSort(int ** a, int n, int m);

---

第 3 题

下面有关 C++ 类和对象的说法，错误的是（ ）。

{{ select(3) }}

• 对象的生命周期开始时，会执行构造函数。
• 对象的生命周期结束时，会执行析构函数。
• 类的析构函数可以为虚函数。
• 类的构造函数可以为虚函数。

---

第 4 题

使用邻接矩阵表达 $n$ 个顶点的有向图，则该矩阵的大小为（ ）。

{{ select(4) }}

• $n \times (n + 1)$
• $n \times n$
• $n \times (n - 1)$
• $n \times (n - 1)/2$

---

第 5 题

$5$ 位同学排队，其中一位同学不能排在第一，则共有多少种可能的排队方式？（ ）。

{{ select(5) }}

• $5$
• $24$
• $96$
• $120$

---

第 6 题

一个无向图包含 $n$ 个顶点，则其最小生成树包含多少条边？（ ）。

{{ select(6) }}

• $n - 1$
• $n$
• $n + 1$
• 最小生成树可能不存在。

---

第 7 题

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

{{ select(7) }}

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

---

第 8 题

对有 $n$ 个元素的二叉排序树进行中序遍历，其时间复杂度是（ ）。

{{ select(8) }}

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

---

第 9 题

假设输入参数 $m$ 和 $n$ 满足 $m \leq n$，则下面程序的最差情况的时间复杂度为（ ）。

int gcd(int m, int n) {
    while (m > 0) {
        int t = m;
        m = n % m;
        n = t;
    }
    return n;
}

{{ select(9) }}

• $O(\log(n))$
• $O(n)$
• $O(n \times m)$
• $O(m \times \log(n))$

---

第 10 题

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

long long power_mod(long long a, long long n, long long mod) {
    if (n == 0)
        return 1;
    a = a % mod;
    if (n == 1)
        return a;
    long long pw = power_mod(a, n / 2, mod);
    long long pw2 = pw * pw % mod;
    if (n % 2 == 0)
        return pw2;
    return pw2 * a % mod;
}

{{ select(10) }}

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

---

第 11 题

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

int record_choose[MAXN][MAXM];
int choose(int n, int m) {
    if (m == 0 || m == n)
        return 1;
    if (record_choose[n][m] == 0)
        record_choose[n][m] = choose(n - 1, m - 1) + choose(n - 1, m);
    return record_choose[n][m];
}

{{ select(11) }}

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

---

第 12 题

下面的程序使用出边的邻接表表达有向图，则下列选项中哪个是它表达的图？（ ）。

#include <iostream>

struct Edge {
    int e;
    Edge * next;
};

struct Node {
    Edge * first;
};

int main() {
    Edge e[5] = {{1, nullptr}, {2, &e[2]},
                 {3, nullptr}, {3, nullptr}, {0, nullptr}};
    Node n[4] = {&e[0], &e[1], &e[3], &e[4]};
    // 其他处理
    return 0;
}

{{ select(12) }}

• A
• B
• C
• D

---

第 13 题

下面程序的输出为（ ）。

#include <iostream>
using namespace std;

int main() {
    int cnt = 0;
    for (int a = 1; a <= 10; a++)
        for (int b = 1; b <= 10; b++)
            for (int h = 1; h <= 10; h++)
                if ((a + b) * h == 20)
                    cnt++;
    cout << cnt << endl;
    return 0;
}

{{ select(13) }}

• 12
• 18
• 36
• 42

---

第 14 题

下面程序的输出为（ ）。

#include <iostream>
using namespace std;

int main() {
    const int N = 30;
    int cnt = 0;
    for (int a = 1; a <= N; a++)
        for (int b = a; a + b <= N; b++)
            for (int c = b; a + b + c <= N; c++)
                if (a * a + b * b == c * c)
                    cnt++;
    cout << cnt << endl;
    return 0;
}

{{ select(14) }}

• 3
• 6
• 11
• 22

---

第 15 题

下面的程序中，二维数组 $h$ 和 $v$ 分别代表如下图所示的网格中的水平边的时间消耗和垂直边的时间消耗。程序使用动态规划计算从左下角到右上角的最小时间消耗，则横线处应该填写下列哪个选项的代码？（ ）。

int dis[MAXY][MAXX];
int shortest_path(int x, int y) {
    dis[0][0] = 0;
    for (int i = 0; i < y; i++)
        dis[i + 1][0] = dis[i][0] + v[i][0];
    for (int j = 0; j < x; j++)
        dis[0][j + 1] = dis[0][j] + h[0][j];
    for (int i = 0; i < y; i++)
        for (int j = 0; j < x; j++)
            __________________; // 在此处填写代码
    return dis[y][x];
}

A. dis[i][j] = min(dis[i - 1][j] + v[i - 1][j], dis[i][j - 1] + h[i][j - 1]); B. dis[i][j] = min(dis[i - 1][j] + h[i - 1][j], dis[i][j - 1] + v[i][j - 1]); C. dis[i + 1][j + 1] = min(dis[i][j + 1] + v[i][j + 1], dis[i + 1][j] + h[i + 1][j]); D. dis[i + 1][j + 1] = min(dis[i][j + 1] + h[i][j + 1], dis[i + 1][j] + v[i + 1][j]);

{{ select(15) }}

• dis[i][j] = min(dis[i - 1][j] + v[i - 1][j], dis[i][j - 1] + h[i][j - 1]);
• dis[i][j] = min(dis[i - 1][j] + h[i - 1][j], dis[i][j - 1] + v[i][j - 1]);
• dis[i + 1][j + 1] = min(dis[i][j + 1] + v[i][j + 1], dis[i + 1][j] + h[i + 1][j]);
• dis[i + 1][j + 1] = min(dis[i][j + 1] + h[i][j + 1], dis[i + 1][j] + v[i + 1][j]);