1. $\$ 某班级有 $8$ 名男生和 $6$ 名女生，现要选出 $3$ 人组成学习小组，要求小组中至少有 $1$ 名男生和 $1$ 名女生，则不同的选法共有（ ）种。

{{ select(1) }}

• $112$
• $168$
• $224$
• $288$

---

2. $\$ 在杨辉三角中，从第 $0$ 行开始计数，第 $10$ 行的所有数之和为（ ）。

{{ select(2) }}

• $512$
• $1024$
• $2048$
• $4096$

---

3. $\$ 下列代码实现了快速幂算法，其时间复杂度为（ ）。

long long fastPow(long long b, long long e, long long mod) {
    long long result = 1;
    while (e > 0) {
        if (e & 1)
            result = result * b % mod;
        b = b * b % mod;
        e >>= 1;
    }
    return result;
}

{{ select(3) }}

• $O(\log b)$
• $O(\log e)$
• $O(\log mod)$
• $O(e)$

---

4. $\$ 从 $5$ 本不同的数学书和 $4$ 本不同的物理书中选取 $3$ 本书，要求至少包含 $1$ 本数学书，则不同的选法有（ ）种。

{{ select(4) }}

• $60$
• $74$
• $80$
• $84$

---

5. $\$ 在二叉搜索树（BST）中，若中序遍历的序列为 $\{1, 2, 3, 4, 5\}$，且先序遍历的第一个序列元素为 $3$，则下列说法正确的是（ ）。

{{ select(5) }}

• 该树一定是一棵完全二叉树
• 元素 $4$ 和 $5$ 不可能是兄弟节点
• 元素 $1$ 所在节点的深度可能大于 $3$ （根节点深度为 $1$ ）
• 元素 $2$ 一定是元素 $1$ 的父节点

---

6. $\$ 在一个有向带权图中，使用 Dijkstra 算法求单源最短路径时，若使用优先队列（小根堆）优化，其时间复杂度为（ ）。

{{ select(6) }}

• $O(V^2)$
• $O(V \cdot E)$
• $O((V + E) \log V)$
• $O(V^2 \log V)$

---

7. $\$ 对于含 $n$ 个顶点 ($n \ge 2$) 的连通加权有向图，若图中不存在负权环，则任意两点之间的最短路径（简单路径）最多包含（ ）条边。

{{ select(7) }}

• $n$
• $n - 1$
• $n + 1$
• 无法确定，取决于图的具体边数

---

8. $\$ 在使用 Floyd 算法求任意两点间最短路径时，时间复杂度为 $O(V^3)$。若在某次算法执行前，已经用 Dijkstra 算法正确求出了所有点对的最短路并存入了 dist 数组。如果此时继续对该 dist 数组执行一次完整的 Floyd 算法过程（无任何提前终止），执行完毕后 dist 数组内的值（ ）。

{{ select(8) }}

• 会发生改变，因为 Floyd 又做了一次松弛
• 不会发生改变
• 可能变大，因为未针对已有最短路优化
• 可能在某些负权图中陷入死循环

---

9. $\$ 关于图论中的最短路径算法，下列说法中严格正确的是（ ）。

{{ select(9) }}

• Dijkstra 算法能够高效处理包含负权边的有向图。
• Floyd 算法可以求出任意两点间的最短路径，且允许图中存在负权边（但不能有负权环）。
• 单源最短路径算法无法用于无向图，无向图只能通过 BFS 求解。
• Dijkstra 算法的每一步必定从当前未访问的节点中，选取距离起始点最远的节点进行松弛操作。

---

10. $\$ 有 $6$ 个人排成一排照相，其中甲、乙两人必须相邻，且丙不能站在排头的不同排法有（ ）种。

{{ select(10) }}

• $120$
• $144$
• $192$
• $240$

---

11. $\$ 下列代码试图实现 Floyd 算法求所有点对之间的最短路径，横线处应填入（ ）。

void floyd(int n, int dist[][MAXN]) {
    for (int k = 0; k < n; k++)
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                if (___________ ) // 在此处填入选项
                    dist[i][j] = dist[i][k] + dist[k][j];
}

{{ select(11) }}

• dist[i][k] + dist[k][j] < dist[i][j]
• dist[i][k] != INF && dist[k][j] != INF
• dist[i][k] != INF && dist[k][j] != INF && dist[i][k] + dist[k][j] < dist[i][j]
• dist[i][j] == INF

---

12. $\$ 用数字 $0$、$1$、$2$、$3$、$4$ 组成无重复数字的五位偶数，共有（ ）个。

{{ select(12) }}

• $48$
• $60$
• $72$
• $96$

---

13. $\$ 在一个无向带权图中，若使用 Prim 算法从顶点 $0$ 开始构造最小生成树（边权均为正整数，且 graph[u][v] == 0 表示无边），下列代码中横线处应填入（ ）。

int prim(vector<vector<int>>& graph, int n) {
    vector<bool> inMST(n, false);
    vector<int> minEdge(n, INT_MAX);
    minEdge[0] = 0;
    int result = 0;
    for (int i = 0; i < n; i++) {
        int u = -1;
        for (int j = 0; j < n; j++)
            if (!inMST[j] && (u == -1 || minEdge[j] < minEdge[u]))
                u = j;
        inMST[u] = true;
        result += minEdge[u];
        for (int v = 0; v < n; v++)
            if (__________) // 在此处填入选项
                minEdge[v] = graph[u][v];
    }
    return result;
}

{{ select(13) }}

• graph[u][v] && !inMST[v] && graph[u][v] < minEdge[v]
• !inMST[v] && graph[u][v] < minEdge[v]
• graph[u][v] > 0 && !inMST[v]
• !inMST[v] && minEdge[v] > 0

---

14. $\$ 已知三个点 $A(x_1, y_1), B(x_2, y_2), C(x_3, y_3)$ 在平面直角坐标系中的坐标。下列 C++ 表达式中，在精度误差范围 $1\text{e-}8$ 内能正确计算判断这三个点是三点共线的表达式是（ ）。

{{ select(14) }}

• (x2-x1)/(y2-y1) == (x3-x1)/(y3-y1)
• (x2-x1)*(y3-y1)-(x3-x1)*(y2-y1) == 0
• fabs((x2-x1)*(y3-y1)-(x3-x1)*(y2-y1)) < 1e-8
• fabs((x2-x1)/(y2-y1)-(x3-x1)/(y3-y1)) < 1e-8

---

15. $\$ 在 $64$ 位操作系统下（LP64 / LLP64 模型），下面代码的输出结果是（ ）。

#include <iostream>
using namespace std;

int main() {
    int a[4] = {1, 2, 3, 4};
    int (*p)[4] = &a;
    int *q = a;

    cout << sizeof(a) << " ";
    cout << sizeof(p) << " ";
    cout << sizeof(p + 1) << " ";
    cout << sizeof(q + 1) << " ";
    cout << (p + 1) - p << " ";
    cout << (q + 1) - q << endl;
}

{{ select(15) }}

• $16$ $8$ $8$ $8$ $1$ $1$
• $16$ $8$ $16$ $8$ $1$ $1$
• $16$ $8$ $8$ $4$ $4$ $1$
• $16$ $8$ $8$ $8$ $4$ $1$

---