首页 › 题库 › GESP编程能力等级认证 › 6 图论算法及综合应用

GESP-C++八级 题库

共 30 道题 ,第 1 / 2 页 · 按题型筛选,点「查看答案」核对解析
章节 6 图论算法及综合应用 清除
1 单选题 适中 GESP编程能力等级认证 ·GESP-C++八级 · 6.2 最短路径

下面是使用邻接矩阵实现的Dijkstra算法的核心片段,用于求单源最短路径。在找到当前距离起点最近的顶点u 后,需要更新其邻接点 j 的距离。横线处应填入的代码是( )。

for (int j = 1; j <= n; j++) { 
    if (!visited[j] && graph[u][j] < INF) { 
      if (________) { // 在此处填入选项 
        dis[j] = dis[u] + graph[u][j]; 
      } 
    } 
}
A
dis[j] < dis[u] + graph[u][j]
B
dis[j] > dis[u] + graph[u][j]
C
graph[u][j] > dis[u] + dis[j]
D
dis[j] > graph[u][j]
答案与解析
正确答案:B
在Dijkstra算法中,选定当前距离起点最近的未处理顶点u后,需遍历其所有邻接点j。对于每个邻接点j,若存在从u到j的边且通过u到达j的路径长度小于当前记录的最短距离,则更新j的最短距离。该判断条件基于比较经由u到达j的路径长度与原记录距离的大小关系,仅当新路径更短时执行更新操作。
题目详情
2 单选题 适中 GESP编程能力等级认证 ·GESP-C++八级 · 6.1 最小生成树

下列程序实现了线性筛法(欧拉筛),用于在O(n)时间内求出1~n之间的所有质数。为了保证每个合数只被其最小质因子筛掉,横线处应填入的语句是( )。

for (int i = 2; i <= n; i++) { 
  if (!not_prime[i]) primes[++cnt] = i; 
  for (int j = 1; j <= cnt && i * primes[j] <= n; j++) { 
    not_prime[i * primes[j]] = true; 
    if (________) break; // 在此处填入选项 
  } 
}
A
i + primes[j] == n
B
primes[j] > i
C
i % primes[j] == 0
D
i % primes[j] != 0
答案与解析
正确答案:C
遍历每个数i,若未被标记为合数,则将其加入质数列表。随后枚举已知质数primes[j],将i与primes[j]的乘积标记为合数。标记过程中,当某个质数primes[j]能整除i时,停止后续标记。因primes[j]是i的最小质因子,后续更大的质数与i相乘所得合数的最小质因子仍为primes[j],应由其他数倍增筛去。
题目详情
3 单选题 适中 GESP编程能力等级认证 ·GESP-C++八级 · 6.1 最小生成树

对连通无向图执行Kruskal算法。已按边权从小到大依次扫描到某条边e=(u,v)。此时在已经构建的部分MST结构中, (u,v)已在同一连通块内。关于边 的处理,下列说法正确的是( )。

A
必须选入MST,否则可能不连通。
B
一定不能选入MST(在此扫描顺序下)。
C
若后续出现更大的边权,可以回溯改选 。
D
只有当是当前最小边时才能舍弃。
答案与解析
正确答案:B
Kruskal算法基于边权递增顺序处理边,维护当前选中边构成的森林连通性。每条边处理时需判断其两端顶点是否已存在于同一连通块中。该判断通过并查集等数据结构实现,用于检测加入该边是否会形成环。若两端已在同一连通块内,则该边连接的是同一树内两节点。此时该边可被跳过而不立即加入MST结构。算法继续处理下一条边,后续选择仅依赖未处理的边及其权值顺序。已舍弃的边不会影响后续连通性决策,且不触发回溯机制。边的选取与否完全由当前连通状态和边权顺序决定。
题目详情
4 单选题 适中 GESP编程能力等级认证 ·GESP-C++八级 · 6.1 最小生成树

小杨想点一杯奶茶外卖,但还差5元起送。于是,小杨决定点一些小料。可选的小料包括:珍珠1元、椰果2元、奶冻3元、奶盖4元。每种小料最多点1份。请问共有多少种满足起送条件的点小料方案?( )。

A

16

B

10

C

9

D

7

答案与解析
正确答案:C
这道题暂未补解析。
题目详情
5 单选题 适中 GESP编程能力等级认证 ·GESP-C++八级 · 6.1 最小生成树

小杨和小刘是好朋友,她们在逛商场时发现新设置的大头贴自拍机,于是决定一起拍一组照片。一组照片包括4张,这4张照片没有顺序区分。拍每张照片时,可以选择有相框或无相框、两人可以分别选择有头饰或无头饰、 还可以从2种位置(小杨在左,或小刘在左)中选出一种。她们不希望一组照片中出现完全相同的相框、头饰、位置的组合。请问一组照片共有多少种不同的方案?( )。

A

1820

B

70

C

24

D

16

答案与解析
正确答案:A
这道题暂未补解析。
题目详情
6 单选题 适中 GESP编程能力等级认证 ·GESP-C++八级 · 6.1 最小生成树

下列关于C++类的说法,错误的是( )。

A

派生类对象占用的内存总是不小于基类对象。

B

派生类可以不实现基类的虚函数。

C

如果一个类包含纯虚函数,则它不能包含成员变量。

D

如果一个类包含纯虚函数,则不能用它定义对象。

答案与解析
正确答案:C
这道题暂未补解析。
题目详情
7 单选题 适中 GESP编程能力等级认证 ·GESP-C++八级 · 6.1 最小生成树

下列关于树和图的说法,错误的是( )。

A

每个连通图都存在生成树。

B

每个存在生成树的有向图,都一定是强连通的。

C

保留树的所有节点,并把树的每个节点指向其父节点,则可以将树转换为一个有向弱连通图。

D

保留树的所有节点,并把树的每个节点指向其子节点,则可以将树转换为一个有向无环图。

答案与解析
正确答案:B
这道题暂未补解析。
题目详情
8 单选题 适中 GESP编程能力等级认证 ·GESP-C++八级 · 6.1 最小生成树

一对夫妻生男生女的概率相同。这对夫妻希望儿女双全。请问这对夫妻生下三个孩子时,实现儿女双全的概率是多少?( )。

A

1/4

B

1/2

C

3/4

D

7/8

答案与解析
正确答案:C
这道题暂未补解析。
题目详情
9 单选题 适中 GESP编程能力等级认证 ·GESP-C++八级 · 6.1 最小生成树

二项式(x+y)6的展开式中x2y4项的系数是( )。

A

720

B

120

C

20

D

15

答案与解析
正确答案:D
这道题暂未补解析。
题目详情
10 单选题 适中 GESP编程能力等级认证 ·GESP-C++八级 · 6.1 最小生成树

以下关于贪心法和动态规划的说法中,错误的是( )。

A

动态规划能解决大部分多阶段决策问题。

B

对特定的问题,贪心法不一定适用。

C

当特定的问题适用贪心法时,通常比动态规划的时间复杂度更低。

D

对很多问题,递推实现和递归实现动态规划方法的时间复杂度相当。

答案与解析
正确答案:A
这道题暂未补解析。
题目详情
11 单选题 适中 GESP编程能力等级认证 ·GESP-C++八级 · 6.1 最小生成树

下面程序的输出为( )。

#include <iostream> 
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; 
}
A

45

B

102

C

174

D

3375

答案与解析
正确答案:B
这道题暂未补解析。
题目详情
12 单选题 适中 GESP编程能力等级认证 ·GESP-C++八级 · 6.1 最小生成树

下面 merge_sort 函数试图实现归并排序算法,横线处应该填入的是( )。

A

arr, left, mid

arr, mid, right

B

arr, left, mid + 1

arr, mid + 1, right

C

arr, left, mid

arr, mid + 1, right

D

arr, left, mid + 1

arr, mid + 1, right + 1

答案与解析
正确答案:A
这道题暂未补解析。
题目详情
13 单选题 适中 GESP编程能力等级认证 ·GESP-C++八级 · 6.1 最小生成树

下面Prim算法程序中,横线处应该填入的是( )。

A

graph[u][v] >= 0 && key[v] > graph[u][v]

B

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

C

graph[u][v] == 0 && key[v] > graph[u][v]

D

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

答案与解析
正确答案:D
这道题暂未补解析。
题目详情
14 单选题 适中 GESP编程能力等级认证 ·GESP-C++八级 · 6.1 最小生成树

下面的程序使用出边邻接表表达的带权无向图,则从顶点0到顶点3的最短距离为( )。

A

12

B

11

C

10

D

9

答案与解析
正确答案:D
这道题暂未补解析。
题目详情
15 单选题 适中 GESP编程能力等级认证 ·GESP-C++八级 · 6.1 最小生成树

下面的欧氏筛法程序中,两个横线处应填入的分别是?( )

int primes[MAXP], num = 0;
bool isPrime[MAXN + 1] = {false};
void sieve() {
    for (int n = 2; n <= MAXN; n++) {
        if (!isPrime[n])
            primes[num++] = n;
        for (int i = 0; i < num && ________; i++) { // 在此处填入选项
            isPrime[n * primes[i]] = true;
            if (________) // 在此处填入选项
                break;
        }
    }
}
A
n * primes[i] < MAXNn % primes[i] == 0
B
n * primes[i] < MAXNprimes[i] > n
C
n * primes[i] <= MAXNn % primes[i] == 0
D
n * primes[i] <= MAXNprimes[i] > n
答案与解析
正确答案:C

第—空应该保证  n * primes[i] 不超过筛法的范围,第二空应该是如果当前  primes[i] 是 n 的最小素因子 则停止循环。(数论:质数筛法)

题目详情
16 单选题 适中 GESP编程能力等级认证 ·GESP-C++八级 · 6.2 最短路径

下面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;
    }
}
A
map[i][j] = map[i][k] + map[k][j]
B
map[i][k] = map[i][j] - map[k][j]
C
map[i][j] = map[i][k] - map[k][j]
D
map[k][j] = map[i][j] - map[i][k]
答案与解析
正确答案:A

根据 Floyd 算法,如果 i 到 k 加上 k 到 j 的最短路长度小于当前 i 到 j 的最短路长度,则用前者更新后者。 (图论算法: Floyd 算法)

题目详情
17 单选题 适中 GESP编程能力等级认证 ·GESP-C++八级 · 6.2 最短路径

下列Dijkstra算法中,横线处应该填入的是( )。

typedef struct Edge {
	int in, out; // 从下标in顶点到下标out顶点的边
	int len; // 边长度
	struct Edge * next;
} Edge;
// v:顶点个数,graph:出边邻接表,start:起点下标,dis:输出每个顶点的最短距离
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) {
			________; // 在此处填入选项
		}
	}
	delete[] visited;
}
A
if (dis[e->out] > e->len)
	dis[e->out] = e->len;
B
if (dis[e->out] > min + e->len)
	dis[e->out] = min + e->len;
C
if (dis[e->in] > e->len)
	dis[e->in] = e->len;
D
if (dis[e->in] > min + e->len)
	dis[e->in] = min + e->len;
答案与解析
正确答案:B
这道题暂未补解析。
题目详情
18 单选题 适中 GESP编程能力等级认证 ·GESP-C++八级 · 6.1 最小生成树

下面最小生成树的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;
		}
	}
}
A
uParent == vParent
B
uParent >= vParent
C
uParent != vParent
D
uParent <= vParent
答案与解析
正确答案:C

Kruskal基于避圈法和贪心思想,先按照边权升序,依次考虑每条边(x,y,z),如果x和y已经处于同一个生成树中,则过滤掉当前的边,否则将x和y的生成树通过z边连接,同时用并查集维护x和y(联接x和y的集合),组成更大的生成树。

横线处为判断x和y是否处于同一个集合,不是则链接,并更新最小生成树的边权和。答案选C。

题目详情
19 单选题 适中 GESP编程能力等级认证 ·GESP-C++八级 · 6.1 最小生成树

下面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;
}
A
graph[u][v] >= 0 && key[v] > graph[u][v]
B
graph[u][v] <= 0 && key[v] > graph[u][v]
C
graph[u][v] == 0 && key[v] > graph[u][v]
D
graph[u][v] != 0 && key[v] > graph[u][v]
答案与解析
正确答案:D

最小生成树的Prim算法思想:选择圈内的一个点x(一开始随便选一个点作为x),遍历x的所有出边y,从中选取一个边权z最小的y,该(x,y,z)一定是最小生成树的生成边(因为最小生成树的点之间相互连通),程序中key数组就是用来记录过程中每个节点距离圈的距离的最小值,parent数组是记录节点和边权依次加入圈的具体路径(最终形成一棵生成树),横线处是比较圈外距离u最小的边权v,因此答案选D。

题目详情
20 单选题 适中 GESP编程能力等级认证 ·GESP-C++八级 · 6.2 最短路径

下列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];
				}
			}
		}
	}
}
A
dis[j] > minn && cheak[j] == 0
B
dis[j] < minn && cheak[j] == 0
C
dis[j] >= minn && cheak[j] == 0
D
dis[j] < minn && cheak[j] != 0
答案与解析
正确答案:B

朴素dijkstra算法,在非负权图中,用cheak[]标记已经求得最短路的点(因为已经求得,所以后续不会再更新),每次选择距离起点S的未求得最短路(cheak[]==0)的,且最近的节点minx,由非负权图的原因,该节点minxj将加入已经求得最短路的点的集合,同时用minx尝试是否能更新S到其他待球节点的最短路。横线处就是求解距离起点S的未求得最短路(cheak[]==0)的,且最近的节点minx的,因此选B。

题目详情