GESP 8级客观题｜最小生成树｜课后作业

考试频率：高频。本卷共 6 题。

1. 下列关于树和图的说法，错误的是（ ）。

   {{ select(1) }}

• 树是一种有向无环图，有向无环图都是一棵树。
• 如果把树看做有向图，每个节点指向其子节点，则该图是弱连通图。
• 个顶点且连通的无向图，其最小生成树一定包含 $N-1$ 个条边。
• $N+1$个顶点、 $N$条边的有向图，一定不是强连通的。

2. 一个无向图包含 n 个顶点，则其最小生成树包含多少条边？（ ）。

   {{ select(2) }}

• $n-1$
• $n$
• $n+1$
• 最小生成树可能不存在。

3. 关于生成树的说法，错误的是（）。

   {{ select(3) }}

• 一个无向连通图可以有多个生成树。
• 一个无向图，只要连通，就一定有生成树。
• n个顶点的无向完全图，有$n^{n-2}$棵生成树。
• n个顶点的无向图，生成树包含n-1条边。

4. 下面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;
}

{{ select(4) }}

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

5. 下面的欧氏筛法程序中，两个横线处应填入的分别是（ ）。

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] < MAXN
n % primes[i] == 0

//B:
n * primes[i] < MAXN
primes[i] > n

//C:
n * primes[i] <= MAXN
n % primes[i] == 0

//D:
n * primes[i] <= MAXN
primes[i] > n

{{ select(5) }}

• A
• B
• C
• D

6. $n$ 个顶点的无向完全图，有 $n^{n-2}$ 棵生成树。（ ）

   {{ select(6) }}

• 对
• 错