GESP 客观题评测系统

2024-09-Level-8

试卷解析总览，可直接查看每题答案与解析。

单选题（每题 2 分）

第 1 题（单选题）

下面关于C++类和对象的说法，错误的是（）。

类的析构函数可以为虚函数。

类的构造函数不可以为虚函数。

class中成员的默认访问权限为private。

struct中成员的默认访问权限为private。

正确答案D

解析详情

【答案】D

【考点】C++ 类与结构体的默认访问权限

【解析】 class 的默认访问权限是 private，struct 的默认访问权限是 public。析构函数可以声明为虚函数，而构造函数不能是虚函数，所以错误说法是 D。

【易错点】容易把 class 和 struct 的默认访问权限记反。

第 2 题（单选题）

对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小为（）。

n \times \frac{n}{2}

n \times n

(n-1) \times (n-1)

(n+1) \times (n+1)

正确答案B

解析详情

【答案】B

【考点】图的邻接矩阵表示

【解析】邻接矩阵要为每一对顶点各准备一个位置，行和列都对应 n 个顶点，所以矩阵规模是 n×n。无向图只是在主对角线两侧关于对称轴对称，矩阵大小并不会减半。

【易错点】不要因为无向图边是双向的，就把矩阵大小误写成一半。

第 3 题（单选题）

设有编号为A、B、C、D、E的5个球和编号为A、B、C、D、E的5个盒子。现将这5个球投入5个盒子，要求每个盒子放一个球，并且恰好有两个球的编号与盒子编号相同，问有多少种不同的方法？（）。

120

正确答案C

解析详情

【答案】C

【考点】错排与组合计数

【解析】先选出恰好放对的 2 个球，有 C(5,2)=10 种。剩下 3 个球必须全部放错，3 个元素的错排数 D3=2，所以总数是 10×2=20。

【易错点】 “恰好两个放对”意味着其余 3 个必须全部放错，不能再出现额外对号入座。

第 4 题（单选题）

从甲地到乙地，可以乘高铁，也可以乘汽车，还可以乘轮船。一天中，高铁有10班，汽车有5班，轮船有2班。那么一天中乘坐这些交通工具从甲地到乙地共有多少种不同的走法？（）。

100

正确答案D

解析详情

【答案】D

【考点】分类计数原理

【解析】从甲地到乙地只需在高铁、汽车、轮船三类方案中任选一种，因此总方案数是 10+5+2=17。这里是分类相加，不是分步相乘。

【易错点】看到多个数字时容易机械相乘，但本题三种交通方式互斥，只能做加法。

第 5 题（单选题）

n 个结点的二叉树，执行释放全部结点操作的时间复杂度是（）。

O(n)

O(n \log n)

O(\log n)

O(2^n)

正确答案A

解析详情

【答案】A

【考点】树的遍历复杂度

【解析】释放整棵 n 个结点的二叉树时，每个结点都必须访问并释放一次，因此总操作次数与结点数成正比，时间复杂度是 O(n)。

【易错点】树高可能影响递归深度，但不会改变“每个结点都要处理一次”这一总工作量。

第 6 题（单选题）

在一个单位圆上，随机分布n个点，求这n个点能被一个单位半圆周全部覆盖的概率（）。

\frac{n}{2^{n-1}}

\frac{1}{n^2}

\frac{1}{n}

\frac{1}{2^n}

正确答案A

解析详情

【答案】A

【考点】圆周覆盖概率

【解析】固定任意一个点作为半圆左端点时，另外 n-1 个点都必须落在对应半圆内，概率是 (1/2)^(n-1)。能成为“最左端点”的点共有 n 个，这些情形互斥，所以总概率为 n/2^(n-1)。

【易错点】不要漏掉“哪个点作为覆盖起点”这 n 种对称情况。

第 7 题（单选题）

下面 pailie 函数是一个实现排列的程序，横线处可以填入的是（）。

#include <iostream>
using namespace std;
int sum = 0;
void swap(int & a, int & b) {
    int temp = a;
    a = b;
    b = temp;
}

void pailie(int begin, int end, int a[]) {
    if (begin == end) {
        for (int i = 0; i < end; i++)
            cout << a[i];
            cout << endl;
        }
        for (int i = begin; i < end; i++) {
            // 在此处填入选项
        }
    }
}

1 swap(a[begin + 1], a[i]); 2 pailie(begin + 1, end, a); 3 swap(a[i], a[begin]);

swap(a[begin], a[i]); pailie(begin, end, a); swap(a[i], a[begin]);

swap(a[begin], a[i]); pailie(begin + 1, end, a); swap(a[i], a[begin]);

swap(a[begin] + 1, a[i]); pailie(begin + 1, end, a); swap(a[i], a[begin + 1]);

正确答案C

解析详情

【答案】C

【考点】递归生成全排列

【解析】全排列的标准做法是把第 begin 位依次与后面各位交换，递归处理区间 begin+1 到 end，返回后再交换回来恢复现场。只有 C 同时满足“交换、递归下一位、回溯还原”这三个步骤。

【易错点】递归参数必须推进到 begin+1，否则会在同一层重复递归。

第 8 题（单选题）

上一题中，如果主函数为如下的程序，则最后的排列数是多少个？（）。

int main() {
    int a[5] = {1, 2, 3, 4, 5};
    pailie(0, 5, a);
    return 0;
}

120

240

180

正确答案A

解析详情

【答案】A

【考点】全排列计数

【解析】主函数若对 5 个不同元素调用上一题的排列函数，输出的是这 5 个元素的所有排列，总数为 5!=120。程序中的 sum 虽未展示，但排列数量本质上就是 120。

【易错点】全排列数量是阶乘，不是简单的 5×4 或 2^5。

第 9 题（单选题）

下列程序实现了输出杨辉三角形，代码中横线部分应该填入的是（）。

#include <iostream>
using namespace std;
#define N 35
int a[N][N];
int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= i; j++) {
            if (j == 1 || j == i)
                a[i][j] = 1;
            else
                ___ // 在此处填入选项
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= i; j++)
                cout << a[i][j];
            cout << endl;
        }
        return 0;
    }
}

a[i][j] = a[i - 1][j - 1] + a[i - 1][j];

a[i][j] = a[i][j - 1] + a[i - 1][j];

a[i][j] = a[i - 1][j] + a[i - 1][j];

a[i][j] = a[i - 1][j - 1] + a[i][j];

正确答案A

解析详情

【答案】A

【考点】杨辉三角递推关系

【解析】杨辉三角内部元素满足“左上 + 正上”，即 a[i][j] = a[i-1][j-1] + a[i-1][j]。边界位置 j==1 或 j==i 已单独赋成 1，所以横线处应填 A。

【易错点】不要把本行元素 a[i][j-1] 混进递推式，杨辉三角只依赖上一行。

第 10 题（单选题）

下面最小生成树的 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;
        }
    }
}

uParent == vParent

uParent >= vParent

uParent != vParent

uParent <= vParent

正确答案C

解析详情

【答案】C

【考点】Kruskal 最小生成树与并查集

【解析】 Kruskal 按边权从小到大选边，只有当边的两个端点属于不同连通分量时才能加入生成树，否则会成环。因此条件应是 uParent != vParent。

【易错点】判断条件的目标是“避免成环”，不是比较编号大小。

第 11 题（单选题）

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

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]

正确答案D

解析详情

【答案】D

【考点】Prim 最小生成树的松弛条件

【解析】 Prim 更新邻点时，要求 u 到 v 之间确实有边，即 graph[u][v] != 0，同时这条边比当前记录的 key[v] 更小，才执行更新。所以完整条件是 graph[u][v] != 0 && key[v] > graph[u][v]。

【易错点】邻接矩阵里 0 在这里表示“无边”，不是权值更优。

第 12 题（单选题）

下列Dijkstra算法中，横线处应该填入的是（）。

#include <iostream>
using namespace std;

#define N 100
int n, e, s;
const int inf = 0x7ffff;
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];
                }
            }
        }
    }
}

dis[j] > minn && cheak[j] == 0

dis[j] < minn && cheak[j] == 0

dis[j] >= minn && cheak[j] == 0

dis[j] < minn && cheak[j] != 0

正确答案B

解析详情

【答案】B

【考点】Dijkstra 每轮选最小未确定点

【解析】外层每一轮都要从尚未确定的点中选出当前距离最小的那个，因此条件应是 dis[j] < minn && cheak[j] == 0。如果写成大于号，就会选到更大的距离，算法失效。

【易错点】 cheak[j] == 0 表示该点还没确定最短路，不能漏掉这个限制。

第 13 题（单选题）

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

map[i][j] < map[i][k] + map[k][j]

map[i][j] > map[i][k] + map[k][j]

map[i][j] > map[i][k] - map[k][j]

map[i][j] < map[i][k] - map[k][j]

正确答案B

解析详情

【答案】B

【考点】Floyd 最短路转移

【解析】 Floyd 的核心是尝试经过中转点 k 后是否得到更短路径，即若 map[i][j] > map[i][k] + map[k][j]，就用新路径更新原值。只有 B 符合“更短则更新”的转移逻辑。

【易错点】 Floyd 比较的是路径长度之和，不会出现减法转移。

第 14 题（单选题）

下面程序的 Merge_Sort 函数时间复杂度为（）。

void Merge(int a[], int left, int mid, int right) {
    int temp[right - left + 1];
    int i = left;
    int j = mid + 1;
    int k = 0;
    while (i <= mid && j <= right) {
        if (a[i] < a[j])
            temp[k++] = a[i++];
        else
            temp[k++] = a[j++];
    }
    while (i <= mid)
        temp[k++] = a[i++];
    while (j <= right)
        temp[k++] = a[j++];
    for (int m = left, n = 0; m <= right; m++, n++)
        a[m] = temp[n];
}

void Merge_Sort(int a[], int left, int right) {
    if (left == right)
        return;
    int mid = (left + right) / 2;
    Merge_Sort(a, left, mid);
    Merge_Sort(a, mid + 1, right);
    Merge(a, left, mid, right);
}

O(n \log n)

O(n^{2})

O(2^{n})

O(\log n)

正确答案A

解析详情

【答案】A

【考点】归并排序时间复杂度

【解析】 Merge_Sort 每次把区间二分，递归深度约为 log n；每一层合并所有元素的总代价是 O(n)。因此总复杂度为 O(n log n)。

【易错点】不要只看到递归就写 O(log n)，归并时每层还要线性扫描并拷贝元素。

第 15 题（单选题）

下面 fibonacci 函数的时间复杂度为（）。

int fibonacci(int n) {
    if (n <= 1)
        return n;
    else
        return fibonacci(n - 1) + fibonacci(n - 2);
}

O(1)

O(\phi^{n})

\phi = \frac{\sqrt{5}-1}{2}

O(n)

O(n \log n)

正确答案B

解析详情

【答案】B

【考点】递归 Fibonacci 的时间复杂度

【解析】该函数每次会递归调用 fibonacci(n-1) 和 fibonacci(n-2)，形成近似二叉递归树，结点数呈指数级增长，因此时间复杂度是 O(φ^n)。这比线性递推慢得多。

【易错点】递归版 Fibonacci 不是 O(n)；只有用循环或 DP 才能做到线性复杂度。

判断题（每题 2 分）

第 1 题（判断题）

表达式 '3' & 1 的结果为 '1'。

正确答案错误

解析详情

【答案】错误

【考点】字符常量与按位与运算

【解析】字符 '3' 的 ASCII 码是 51，二进制末位为 1，所以 51 & 1 的结果是整数 1，而不是字符 '1'。数值 1 与字符 '1' 不是同一个值。

【易错点】带引号的 '1' 是字符常量，值为 ASCII 49，不是整数 1。

第 2 题（判断题）

在C++语言中，变量定义必须在某一个函数定义之内。

正确答案错误

解析详情

【答案】错误

【考点】C++ 变量定义位置

【解析】 C++ 变量既可以定义在函数内部，也可以定义在所有函数外部作为全局变量，还可以是类成员变量。所以“必须在某一个函数定义之内”这个说法不成立。

【易错点】不要把“局部变量常见于函数内”误当成“所有变量都只能在函数内定义”。

第 3 题（判断题）

冒泡排序一般是不稳定的。

正确答案错误

解析详情

【答案】错误

【考点】冒泡排序的稳定性

【解析】标准冒泡排序只在相邻元素逆序时交换，相等元素不会跨过彼此，因此它是稳定排序。题干说“一般是不稳定的”与事实相反。

【易错点】 “有交换”不等于“不稳定”，关键看相等元素的相对次序是否被改变。

第 4 题（判断题）

二叉排序树的查找操作的平均时间复杂度，正比于树的高度。

正确答案正确

解析详情

【答案】正确

【考点】二叉排序树查找复杂度

【解析】在二叉排序树中，查找过程沿着一条从根向下的路径进行，比较次数与经过的层数成正比，所以平均时间复杂度与树高同阶。

【易错点】不要把二叉排序树默认当成完全平衡树；复杂度分析通常先看树高。

第 5 题（判断题）

使用 math.h 或 cmath 头文件中的余弦函数，表达式 $\cos(60)$ 的结果类型为 double、值约为 $0.5$ 。

正确答案错误

解析详情

【答案】错误

【考点】三角函数与弧度制

【解析】 C/C++ 的 cos 函数参数按弧度解释，cos(60) 计算的是 60 弧度的余弦，不是 60 度的余弦。结果类型确实是 double，但值并不约等于 0.5，所以整句为错。

【易错点】数学里常说 60°，而程序库里的 cos(60) 默认没有“度”这个单位。

第 6 题（判断题）

你有三种硬币，分别面值2元、5元和7元，每种硬币都有足够多。买一本书需要27元，则最少可以用5个硬币组合起来正好付清，且不需要对方找钱。

正确答案正确

解析详情

【答案】正确

【考点】简单不定方程与最优性判断

【解析】 27 元可以表示为 7+5+5+5+5，一共正好 5 枚硬币。4 枚硬币时虽然总额可到 28，但无法凑出 27，因此最少枚数确为 5。

【易错点】先找到一个可行解还不够，还要继续验证是否还能用更少枚数完成。

第 7 题（判断题）

现有 n 个完全相同的元素，要将其分为 k 组，允许每组可以有 0 个元素，则一共有 $C(n-1, k-1)$ 种分组方案。

正确答案错误

解析详情

【答案】错误

【考点】隔板法适用条件

【解析】把 n 个相同元素分成 k 组且允许某组为 0，对应的是非负整数解个数，应为 C(n+k-1, k-1)。C(n-1, k-1) 对应的是每组至少 1 个元素的情况。

【易错点】 “允许为 0”与“每组至少 1 个”用的是两套不同的隔板法公式。

第 8 题（判断题）

已知 int 类型的变量 a 和 b 中分别存储着一个直角三角形的两条直角边的长度，则该三角形的面积可以通过表达式a / 2.0 * b求得。

正确答案正确

解析详情

【答案】正确

【考点】整数与浮点混合运算

【解析】表达式 a / 2.0 * b 中的 2.0 是 double，a / 2.0 会先做浮点除法，再乘以 b，结果等于 a*b/2 的实数值，能正确表示直角三角形面积。

【易错点】若写成 a / 2 * b，当 a 为奇数时会先发生整除截断。

第 9 题（判断题）

已知等差数列的通项公式 $a_{n}=a_{1}+(n-1)\cdot d$ ，则前n项和的求和公式为 $S_{n}=n\cdot(a_{1}+a_{n})/2$ 。使用这一公式计算 $S_{n}$ 的时间复杂度是 $O(1)$ 。

正确答案正确

解析详情

【答案】正确

【考点】时间复杂度 O(1)

【解析】公式 S_n = n(a_1+a_n)/2 只包含常数次加、乘、除操作，不需要循环或递归，所以计算前 n 项和的时间复杂度是 O(1)。

【易错点】看见“前 n 项和”不一定就是 O(n)，关键要看是否真的逐项累加。

第 10 题（判断题）

诚实国公民只说实话，说谎国公民只说谎话。你来到一处分岔口，一条通往诚实国，一条通往说谎国，但不知是哪一条通往哪里。正在为难之际，走来两位路人，他们都自称是诚实国公民，都说对方是说谎国公民。你想去说谎国，可以这样问其中一位路人：“我要去说谎国，如果我去问另一个路人，他会指向哪一条路？”。

正确答案正确

解析详情

【答案】正确

【考点】真假话推理

【解析】无论你问到的是诚实者还是说谎者，对“另一个人会指哪条路”的回答都会指向诚实国那条路，因此你只要走相反方向，就能到说谎国。题干给出的提问方式可行。

【易错点】这类题通常要把“对方会怎么说”再取一次反向，最后行动往往是按相反方向走。