2026年3月 GESP C++ 8级

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

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

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

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;
}

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

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

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

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

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

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

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

下列代码试图实现 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];
}

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

在一个无向带权图中，若使用 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;
}

已知三个点在平面直角坐标系中的坐标。下列 C++ 表达式中，在精度误差范围 $1e-8$ 内能正确计算判断这三个点是三点共线的表达式是（ ）。

在 $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;
}

在 C++ 中，若结构体中包含一个 static 成员变量，则该变量的存储空间属于结构体对象的一部分。（ ）

对于任意正整数 $n$ ，二项式 $(a+b)^n$ 展开式中各项的二项式系数之和等于 $2^n$ 。（ ）

在 C++ 中，若函数参数类型为 const int &，则该参数既可以绑定左值，也可以绑定右值。（ ）

若一个无向图的最小生成树唯一，则图中所有边权必定各不相同。（ ）

使用快速排序对 $n$ 个元素进行排序时，无论最好、最坏还是平均情况，时间复杂度均为 $O(n \log n)$。（ ）

若一个图中所有顶点的度数为偶数，则一定存在欧拉回路。（ ）

使用倍增法预处理区间最值问题时，预处理的时间复杂度为 $O(n \log n)$，查询的时间复杂度为 $O(1)$。（ ）

如果将一个连通无向图 $G$ 中所有边的权值都统一增加同一个正整数常数 $c$，形成图 $G'$。则 $G$ 的最小生成树中每条边在 $G'$ 中对应的边组成的树，一定是 $G'$ 的最小生成树。（ ）

在图论算法中，Kruskal 算法和 Prim 算法都可以用来求解最小生成树，且这两者的贪心策略无论在任何连通无向图上求得的最小生成树总边权和必定相同。（ ）

在动态规划问题中，“状态转移方程+递推”和“递归+记忆化搜索”通常是解决同一问题的两种不同实现方式，它们的时间复杂度总是相同的。（ ）