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

第 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 \geq 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 题 已知三个点 $PA(x_1, y_1)$、$B(x_2, y_2)$、$C(x_3, y_3)$ 在平面直角坐标系中的坐标。下列 C++ 表达式中，在精度误差范围1e-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

---