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

1. 下面关于 $\tt C$++ 类和对象的说法，错误的是（ ）。

{{ select(1) }}

• 类的析构函数可以为虚函数
• 类的构造函数不可以为虚函数
• $\tt class$ 中成员的默认访问权限为 $\tt private$
• $\tt struct$中成员的默认访问权限为 $\tt private$

2. 对于一个具有 $n$ 个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小为（ ）。

{{ select(2) }}

• $n \times \frac{n}{2}$
• $n \times n$
• $(n-1) \times (n-1)$
• $(n+1) \times (n+1)$

3. 设有编号为 $A$、$B$、$C$、$D$、$E$ 的 $5$ 个球和编号为 $A$、$B$、$C$、$D$、$E$ 的 $5$ 个盒子。现将这 $5$ 个球投入 $5$ 个盒子，要求每个盒子放一个球，并且恰好有两个球的编号与盒子编号相同，问有多少种不同的方法？（ ）

{{ select(3) }}

• $5$
• $120$
• $20$
• $60$

4. 从甲地到乙地，可以乘高铁，也可以乘汽车，还可以乘轮船。一天中，高铁有 $10$ 班，汽车有 $5$ 班，轮船有 $2$ 班。那么一天中乘坐这些交通工具从甲地到乙地共有多少种不同的走法？（ ）

{{ select(4) }}

• $100$
• $60$
• $30$
• $17$

5. $n$ 个结点的二叉树，执行释放全部结点操作的时间复杂度是（ ）。

{{ select(5) }}

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

6. 在一个单位圆上，随机分布 $n$ 个点，求这 $n$ 个点能被一个单位半圆周全部覆盖的概率（ ）。

{{ select(6) }}

• $\frac{n}{2^{n-1}}$
• $\frac{1}{n^2}$
• $\frac{1}{n}$
• $\frac{1}{2^n}$

7. 下面 $\tt pailie$ 函数是一个实现排列的程序，横线处可以填入的是（ ）。

   #include <iostream>
   using namespace std;
   int sum = 0;
   void swap(int & a, int & b) {
       int temp = a;
       a = b;
       b = temp;
   }
   void pailie(int begin, int end, int a[]) {
       if (begin == end) {
           for (int i = 0; i < end; i++)
               cout << a[i];
           cout << endl;
       }
       for (int i = begin; i < end; i++) {
           __________ // 在此处填入选项
       }
   }
   

{{ select(7) }}

• swap(a[begin + 1], a[i]);
  pailie(begin + 1, end, a);
  swap(a[i], a[begin]);
  

• swap(a[begin], a[i]);
  pailie(begin, end, a);
  swap(a[i], a[begin]);
  

• swap(a[begin], a[i]);
  pailie(begin + 1, end, a);
  swap(a[i], a[begin]);
  

• swap(a[begin] + 1, a[i]);
  pailie(begin + 1, end, a);
  swap(a[i], a[begin + 1]);
  

8. 上一题中，如果主函数为如下的程序，则最后的排列数是多少个？（ ）

   int main() {
       int a[5] = {1, 2, 3, 4, 5};
       pailie(0, 5, a);
       return 0;
   }
   

{{ select(8) }}

• $120$
• $60$
• $240$
• $180$

9. 下列程序实现了输出杨辉三角形，代码中横线部分应该填入的是（ ）。

   #include <iostream>
   using namespace std;
   #define N 35
   int a[N][N];
   int main() {
       int n;
       cin >> n;
       for (int i = 1; i <= n; i++)
           for (int j = 1; j <= i; j++) {
               if (j == 1 || j == i)
                   a[i][j] = 1;
               else
                   __________ // 在此处填入选项
           }
       for (int i = 1; i <= n; i++) {
           for (int j = 1; j <= i; j++)
               cout << a[i][j];
           cout<<endl;
       }
       return 0;
   }
   

{{ select(9) }}

• a[i][j] = a[i - 1][j - 1] + a[i - 1][j];
• a[i][j] = a[i][j - 1] + a[i - 1][j];
• a[i][j] = a[i - 1][j] + a[i - 1][j];
• a[i][j] = a[i - 1][j - 1] + a[i][j];

10. 下面最小生成树的 $\tt Kruskal$ 算法程序中，横线处应该填入的是（ ）。

    #include <iostream>
    #include <vector>
    #include <algorithm>
    using namespace std;
    struct Edge {
        int u, v, weight;
        bool operator <(const Edge & other) const {
            return weight < other.weight;
        }
    };
    int findParent(int vertex, vector<int> & parent) {
        if (parent[vertex] == -1)
            return vertex;
        return parent[vertex] = findParent(parent[vertex], parent);
    }
    int main() {
        int n, m;
        cin >> n >> m; // n: 顶点数, m: 边数
        vector<Edge> edges(m);
        vector<int> parent(n, -1);
        int totalWeight = 0;
        for (int i = 0; i < m; i++)
            cin >> edges[i].u >> edges[i].v >> edges[i].weight;
        sort(edges.begin(), edges.end());
    
        for (const auto & edge : edges) {
            int uParent = findParent(edge.u, parent);
            int vParent = findParent(edge.v, parent);
            if (__________) { // 在此处填入选项
                parent[uParent] = vParent;
                totalWeight += edge.weight;
            }
        }
    }
    

{{ select(10) }}

• uParent == vParent
• uParent >= vParent
• uParent != vParent
• uParent <= vParent

11. 下面 $\tt Prim$ 算法程序中，横线处应该填入的是（ ）。

    #include <iostream>
    #include <vector>
    #include <algorithm>
    using namespace std;
    int prim(vector<vector<int>> & graph, int n) {
        vector<int> key(n, INT_MAX);
        vector<int> parent(n, -1);
        key[0] = 0;
        for (int i = 0; i < n; i++) {
            int u = min_element(key.begin(), key.end()) - key.begin();
            if (key[u] == INT_MAX)
                break;
            for (int v = 0; v < n; v++) {
                if (__________) { // 在此处填入选项
                    key[v] = graph[u][v];
                    parent[v] = u;
                }
            }
        }
        int sum = 0;
        for (int i = 0; i < n; i++) {
            if (parent[i] != -1) {
                cout << "Edge: " << parent[i] << " - " << i << " Weight: " << key[i] << endl;
                sum += key[i];
            }
        }
        return sum;
    }
    int main() {
        int n, m;
        cin >> n >> m;
        vector<vector<int>> graph(n, vector<int>(n, 0));
        for (int i = 0; i < m; i++) {
            int u, v, w;
            cin >> u >> v >> w;
            graph[u][v] = w;
            graph[v][u] = w;
        }
        int result = prim(graph, n);
        cout << "Total weight of the minimum spanning tree: " << result << endl;
        return 0;
    }
    

{{ select(11) }}

• graph[u][v] >= 0 && key[v] > graph[u][v]
• graph[u][v] <= 0 && key[v] > graph[u][v]
• graph[u][v] == 0 && key[v] > graph[u][v]
• graph[u][v] != 0 && key[v] > graph[u][v]

12. 下列 $\tt Dijkstra$ 算法中，横线处应该填入的是（ ）。

    #include <iostream>
    using namespace std;
    
    #define N 100
    int n, e, s;
    const int inf = 0x7fffff;
    int dis[N + 1];
    int cheak[N + 1];
    int graph[N + 1][N + 1];
    int main() {
        for (int i = 1; i <= N; i++)
            dis[i] = inf;
        cin >> n >> e;
        for (int i = 1; i <= e; i++) {
            int a, b, c;
            cin >> a >> b >> c;
            graph[a][b] = c;
        }
        cin >> s;
        dis[s] = 0;
        for (int i = 1; i <= n; i++) {
            int minn = inf, minx;
            for (int j = 1; j <= n; j++) {
                if (__________) { // 在此处填入选项
                    minn = dis[j];
                    minx = j;
                }
            }
            cheak[minx] = 1;
            for (int j = 1; j <= n; j++) {
                if (graph[minx][j] > 0) {
                    if (minn + graph[minx][j] < dis[j]) {
                        dis[j] = minn + graph[minx][j];
                    }
                }
            }
        }
    }
    

{{ select(12) }}

• dis[j] > minn && cheak[j] == 0
• dis[j] < minn && cheak[j] == 0
• dis[j] >= minn && cheak[j] == 0
• dis[j] < minn && cheak[j] != 0

13. 下面 $\tt Floyd$ 算法中，横线处应该填入的是（ ）。

    #include <iostream>
    using namespace std;
    
    #define N 21
    #define INF 99999999
    int map[N][N];
    int main() {
        int n, m, t1, t2, t3;
        cin >> n >> m;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (i == j)
                    map[i][j] = 0;
                else
                    map[i][j] = INF;
            }
        }
        for (int i = 1; i <= m; i++) {
            cin >> t1 >> t2 >> t3;
            map[t1][t2] = t3;
        }
        for (int k = 1; k <= n; k++)
            for (int i = 1; i <= n; i++)
                for (int j = 1; j <= n; j++)
                    if (__________) // 在此处填入选项
                        map[i][j] = map[i][k] + map[k][j];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                cout.width(4);
                cout << map[i][j];
            }
            cout << endl;
        }
    }
    

{{ select(13) }}

• map[i][j] < map[i][k] + map[k][j]
• map[i][j] > map[i][k] + map[k][j]
• map[i][j] > map[i][k] - map[k][j]
• map[i][j] < map[i][k] - map[k][j]

14. 下面程序的 $\tt Merge\_Sort$ 函数时间复杂度为（ ）。

    void Merge(int a[], int left, int mid, int right) {
        int temp[right - left + 1];
        int i = left;
        int j = mid + 1;
        int k = 0;
        while (i <= mid && j <= right) {
            if (a[i] < a[j])
                temp[k++] = a[i++];
            else
                temp[k++] = a[j++];
        }
        while (i <= mid)
            temp[k++] = a[i++];
        while (j <= right)
            temp[k++] = a[j++];
        for (int m = left, n = 0; m <= right; m++, n++)
            a[m] = temp[n];
    }
    void Merge_Sort(int a[], int left, int right) {
        if (left == right)
            return;
        int mid = (left + right) / 2;
        Merge_Sort(a, left, mid);
        Merge_Sort(a, mid + 1, right);
        Merge(a, left, mid, right);
    }
    

{{ select(14) }}

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

15. 下面 $\tt fibonacci$ 函数的时间复杂度为（ ）。

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

{{ select(15) }}

• $O(1)$
• $O(\phi^n)$，$\phi = \frac{\sqrt 5 - 1}{2}$
• $O(n)$
• $O(n \log n)$

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

1. 表达式 '3' & 1 的结果为 '1'。（ ）

{{ select(16) }}

• 正确
• 错误

2. 在 $\tt C$++ 语言中，变量定义必须在某一个函数定义之内。（ ）

{{ select(17) }}

• 正确
• 错误

3. 冒泡排序一般是不稳定的。（ ）

{{ select(18) }}

• 正确
• 错误

4. 二叉排序树的查找操作的平均时间复杂度，正比于树的高度。（ ）

{{ select(19) }}

• 正确
• 错误

5. 使用 $\tt math.h$ 或 $\tt cmath$ 头文件中的余弦函数，表达式 cos(60) 的结果类型为 $\tt double$、值约为 $0.5$。（ ）

{{ select(20) }}

• 正确
• 错误

6. 你有三种硬币，分别面值 $2$ 元、$5$ 元和 $7$ 元，每种硬币都有足够多。买一本书需要 $27$ 元，则最少可以用 $5$ 个硬币组合起来正好付清，且不需要对方找钱。（ ）

{{ select(21) }}

• 正确
• 错误

7. 现有 $n$ 个完全相同的元素，要将其分为 $k$ 组，允许每组可以有 $0$ 个元素，则一共有 $C(n-1, k-1)$ 种分组方案。（ ）

{{ select(22) }}

• 正确
• 错误

8. 已知 $\tt int$ 类型的变量 $a$ 和 $b$ 中分别存储着一个直角三角形的两条直角边的长度，则该三角形的面积可以通过表达式 a / 2.0 * b 求得。（ ）

{{ select(23) }}

• 正确
• 错误

9. 已知等差数列的通项公式 $a_n = a_1 + (n-1)\cdot d$，则前 $n$ 项和的求和公式为 $S_n = n \cdot (a_1 + a_n) / 2$。使用这一公式计算 $S_n$ 的时间复杂度是 $O(1)$。（ ）

{{ select(24) }}

• 正确
• 错误

10. 诚实国公民只说实话，说谎国公民只说谎话。你来到一处分岔口，一条通往诚实国，一条通往说谎国，但不知是哪一条通往哪里。正在为难之际，走来两位路人，他们都自称是诚实国公民，都说对方是说谎国公民。你想去说谎国，可以这样问其中一位路人：“我要去说谎国，如果我去问另一个路人，他会指向哪一条路？”。（ ）

{{ select(25) }}

• 正确
• 错误