GESP 2025年9月_C++八级试卷
从PDF导入：GESP 2025年9月_C++八级试卷
试卷题目预览
小杨想点一杯奶茶外卖，但还差5元起送。于是，小杨决定点一些小料。可选的小料包括：珍珠1元、椰果2元、奶冻3元、奶盖4元。每种小料最多点1份。请问共有多少种满足起送条件的点小料方案？（ ）。
小杨和小刘是好朋友，她们在逛商场时发现新设置的大头贴自拍机，于是决定一起拍一组照片。一组照片包括4张，这4张照片没有顺序区分。拍每张照片时，可以选择有相框或无相框、两人可以分别选择有头饰或无头饰、 还可以从2种位置（小杨在左，或小刘在左）中选出一种。她们不希望一组照片中出现完全相同的相框、头饰、位置 的组合。请问一组照片共有多少种不同的方案？（ ）。
下列关于C++类的说法，错误的是（ ）。
下列关于树和图的说法，错误的是（ ）。
一对夫妻生男生女的概率相同。这对夫妻希望儿女双全。请问这对夫妻生下三个孩子时，实现儿女双全的概率是多少？（ ）
二项式(x+y)^8的展开式中xy^4项的系数是（ ）。
对一个包含V个顶点、E条边的图，执行广度优先搜索，其最优时间复杂度是（ ）。
以下关于贪心法和动态规划的说法中，错误的是（ ）。
下面程序的输出为（ ）。
#include
using namespace std;
int main() {
int N = 15, cnt = 0;
for (int x = 1; x + x + x <= N; x++)
for (int y = x; x + y + y <= N; y++)
for (int z = y; x + y + z <= N; z++)
cnt++;
cout << cnt << endl;
return 0;
}
下面程序的时间复杂度为（ ）。
int primes[MAXP], num = 0;
bool isPrime[MAXN] = {false};
void sieve() {
for (int n = 2; n <= MAXN; n++) {
if (!isPrime[n])
primes[num++] = n;
for (int i = 0; i < num && n * primes[i] <= MAXN; i++) {
isPrime[n * primes[i]] = true;
if (n % primes[i] == 0)
break;
}
}
}
下列Dijkstra算法，假设图graph中顶点数v、边数e，则程序的时间复杂度为（ ）。
typedef struct Edge {
int in, out;
int len;
struct Edge * next;
} Edge;
void dijkstra(int v, Edge * graph[], int start, int * dis) {
const int MAX_DIS = 0x7fffff;
for (int i = 0; i < v; i++)
dis[i] = MAX_DIS;
dis[start] = 0;
int * visited = new int[v];
for (int i = 0; i < v; i++)
visited[i] = 0;
visited[start] = 1;
for (int t = 0; ; t++) {
int min = MAX_DIS, minv = -1;
for (int i = 0; i < v; i++) {
if (visited[i] == 0 && min > dis[i]) {
min = dis[i];
minv = i;
}
}
if (minv < 0)
break;
visited[minv] = 1;
for (Edge * e = graph[minv]; e != NULL; e = e->next)
if (dis[e->out] > e->len)
dis[e->out] = e->len;
}
delete [] visited;
}
下面count_triple函数的时间复杂度为（ ）。
下面merge_sort函数试图实现归并排序算法，横线处应该填入的是（ ）。
下面Prim算法程序中，横线处应该填入的是（ ）。
int prim(vector
vector
vector
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;
}
}
}
}
下面的程序使用出边邻接表表达的带权无向图，则从顶点0到顶点3的最短距离为（ ）。
#include
using namespace std;
class Edge {
public:
int dest;
int weight;
Edge(int d, int w) : dest(d), weight(w) {}
};
class Graph {
private:
int num_vertex;
vector
public:
Graph(int v) : num_vertex(v), vve(v) {}
void addEdge(int s, int d, int w) {
vve[s].emplace_back(d, w);
vve[d].emplace_back(s, w);
}
};
int main() {
Graph g(4);
g.addEdge(0, 1, 8);
g.addEdge(0, 2, 5);
g.addEdge(1, 2, 1);
g.addEdge(1, 3, 3);
g.addEdge(2, 3, 7);
return 0;
}
C++语言中，表达式'9'^3的结果值为'999'。
下列C++语言代码，能够安全地输出arr[5]的值。
对n个元素的数组进行排序，最差情况的时间复杂度为O(n²)。
有4个红球、3个蓝球和2个绿球排成一排（相同色球视为完全相同），则不同的排列方案数为1260种。
使用math.h或cmath头文件中的函数，对于int类型的变量x，表达式fabs(x)和sqrt(x*x)的结果总是近似相等的。
运算符重载是C++语言静态多态的一种典型体现，而使用C语言则无法实现运算符重载。
存在一个简单无向图满足：顶点数为6，边数为8，6个顶点的度数分别为3、3、3、3、2、2。
已知两个double类型的变量r和theta分别表示一个扇形的圆半径及圆心角（弧度），则扇形的周长可以通过表达式(2+theta)*r求得。
Dijkstra算法的时间复杂度为O(V²)，其中V为图中顶点的数量。
从32名学生中选出2人分别担任男生班长和女生班长（男生班长必须是男生，女生班长必须是女生），则共有C(32,2)/2种不同的选法。
最短距离
时间限制：1.0s 内存限制：512.0MB
给定正整数P、q以及常数N=10⁹。现在构建一张包含N个结点的带权无向图，结点依次以1,2,...,N编号。
对于任意满足1≤u
现在给定n组询问，第i组询问给定两个正整数ai,bi，你需要回答结点ai与结点bi之间的最短距离。
第一行，三个正整数n、p、q。接下来n行，每行两个正整数ai、bi。
输出共n行，每行一个整数，表示结点ai与结点bi之间的最短距离。
【样例输入1】 4 2 4 6 8 2 4 12 16 17 17 【样例输出1】 2 2 4 0 对于所有测试点，保证1≤n≤10⁴，1≤ai,bi≤10⁹，1≤p,q≤10⁹。
最小生成树
时间限制：1.0s 内存限制：512.0MB
给定一张包含n个结点m条边的带权连通无向图，结点依次以1,2,...,n编号。
对于每条边，请你求出从图中移除该条边后，图的最小生成树中所有边的边权和。
特别地，若移除某条边后图的最小生成树不存在，则输出-1。
第一行，两个正整数n、m。接下来m行，每行三个正整数ui、vi、wi。
输出共m行，第i行包含一个整数，表示移除第i条边后的最小生成树边权和，不存在则输出-1。
【样例输入1】 5 5 1 2 4 2 3 3 3 4 1 2 5 2 3 1 8 【样例输出1】 14 15 -1 -1 10 对于所有测试点，保证1≤n≤10⁵，1≤m≤10⁵，1≤wi≤10⁹。