试卷解析 · 理解每一步

2024-09-Level-8

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

单选题

第 1 题（单选题，2 分）

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

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

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

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

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

正确答案D

解析详情

答案 D类的默认访问权限

思路与推导

class 和 struct 都能定义成员变量和成员函数，但默认访问权限不同：class 默认 private，struct 默认 public。
因此 D 将 struct 的默认权限说成 private，错误。析构函数可为 virtual，而构造函数不能声明为 virtual。

第 2 题（单选题，2 分）

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

n \times \frac{n}{2}

n \times n

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

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

正确答案B

解析详情

答案 B邻接矩阵空间

思路与推导

邻接矩阵用 a[i][j] 表示顶点 i 和 j 的关系，行、列各对应 n 个顶点，因此大小为 $n×n$ ，选 B。
无向图的矩阵通常对称，但“对称”不改变完整矩阵的维度；压缩存储是另一个问题。

第 3 题（单选题，2 分）

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

120

正确答案C

解析详情

答案 C固定点与错排

思路与推导

先从 5 个球中选出恰好放入同名盒子的 2 个，有 $\binom{5}{2}=10$ 种。
剩下 3 个球必须全部放错。若它们为 X、Y、Z，只能循环放成 YZX 或 ZXY，共 2 种错排。
总数为 $10×2=20$ ，选 C。

第 4 题（单选题，2 分）

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

100

正确答案D

解析详情

答案 D分类加法原理

思路与推导

从甲到乙只需在高铁、汽车、轮船三类交通工具中选择一班，三类方案互不重叠。
因此总走法为 $10+5+2=17$ ，选 D。

第 5 题（单选题，2 分）

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

O(n)

O(n \log n)

O(\log n)

O(2^n)

正确答案A

解析详情

答案 A释放二叉树

思路与推导

释放整棵树通常先递归释放左右子树，再释放当前结点，即后序处理。
每个结点恰好释放一次，n 个结点共做 n 次常数级释放操作，时间为 $O(n)$ ，选 A。树高只影响递归栈深度。

第 6 题（单选题，2 分）

在一个单位圆上，随机分布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}$ ，选 A。

第 7 题（单选题，2 分）

下面 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++) {
            // 在此处填入选项
        }
    }
}

swap(a[begin + 1], a[i]);
pailie(begin + 1, end, a);
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 同时满足“交换、递归下一位、回溯还原”这三个步骤。

第 8 题（单选题，2 分）

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

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。

第 9 题（单选题，2 分）

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

#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。

第 10 题（单选题，2 分）

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

解析详情

答案 CKruskal 与并查集

思路与推导

边已按权重从小到大排序，uParent 和 vParent 分别表示两个端点所在连通块的代表。
只有代表不同，即 uParent!=vParent 时，加入这条边才会连接两个连通块而不产生环。随后合并集合并累加边权，因此选 C。

第 11 题（单选题，2 分）

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

解析详情

答案 DPrim 最小生成树的松弛条件

思路与推导

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

第 12 题（单选题，2 分）

下列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

解析详情

答案 BDijkstra 选点

思路与推导

每轮要从“尚未确定最短距离”的顶点中，找 dis 最小的一个。cheak[j]==0 表示 j 尚未确定，dis[j]<minn 表示它优于当前候选。
两条件同时满足才更新 minn 和 minx，因此选 B。实际完整实现还应处理所有剩余顶点均不可达的情况，避免 minx 未初始化。

第 13 题（单选题，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;
    }
}

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

解析详情

答案 BFloyd 松弛

思路与推导

map[i][j] 保存目前从 i 到 j 的最短距离。允许经过中间点 k 后，新路线的长度为 map[i][k]+map[k][j]。
只有原值更大时才应该替换，所以条件是 map[i][j]>map[i][k]+map[k][j]，选 B。
最外层枚举 k，使状态逐步允许更多中间点。

第 14 题（单选题，2 分）

下面程序的 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 把区间分为两半递归排序，然后 Merge 在线性时间内合并这两段。
每层所有区间长度之和为 n，故每层总代价为 $O(n)$ ；不断二分产生 $O(\log n)$ 层。
总时间为 $O(n\log n)$ ，选 A。这里讨论算法过程，临时变长数组在严格标准 C++ 中应换用合法的动态存储。

第 15 题（单选题，2 分）

下面 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)。这比线性递推慢得多。

判断题

第 1 题（判断题，2 分）

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

正确答案错误

解析详情

答案错误字符编码与按位与

思路与推导

在常见 ASCII 编码中，字符 '3' 的编码为 51，最低二进制位是 1，因此 '3'&1 得到整数 1。
字符 '1' 的编码则是 49，不等于整数 1，所以题目错误。

第 2 题（判断题，2 分）

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

正确答案错误

解析详情

答案错误变量作用域

思路与推导

C++ 允许在函数外定义全局变量，例如在 main 前写 int count=0;，该定义合法。
变量也可定义在函数内成为局部变量，因此“必须在某一个函数定义之内”错误。

第 3 题（判断题，2 分）

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

正确答案错误

解析详情

答案错误排序稳定性

思路与推导

标准冒泡排序仅在相邻两个元素严格逆序时交换；关键字相等的两个元素不会相互越过。
例如两个带标签的 2a、2b 即使移动到新位置，a 与 b 的先后关系仍保持，所以冒泡排序通常是稳定的。

第 4 题（判断题，2 分）

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

正确答案正确

解析详情

答案正确树高与查找路径

思路与推导

二叉排序树查找从根沿一条分支向下，单次比较次数由目标深度决定，并受树高 h 限制。
按本题常用教学口径，树越高查找通常越慢，以 $O(h)$ 描述查找代价，故给定答案为正确。严格说，成功查找的平均次数是平均结点深度加 1，不能对任意树形都断言与最大高度成固定比例。

第 5 题（判断题，2 分）

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

正确答案错误

解析详情

答案错误三角函数角度单位

思路与推导

C++ 的 cos 参数按弧度解释，cos(60) 表示 60 弧度的余弦，不是 60 度的余弦。
60 度对应 $\pi/3$ 弧度，cos(π/3) 才约为 0.5。因此题目虽然返回类型部分符合通常调用情形，但数值判断错误。

第 6 题（判断题，2 分）

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

正确答案正确

解析详情

答案正确最少硬币数

思路与推导

5 枚硬币可以取 7+5+5+5+5=27，因此存在使用 5 枚的可行方案。
若只用 4 枚，最大总额为 28。把任意一枚 7 换成 5 或 2，会分别减少 2 或 5，不可能只减少 1 得到 27。
3 枚或更少至多为 21，也不足，因此最少确为 5 枚。

第 7 题（判断题，2 分）

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

正确答案错误

解析详情

答案错误非负整数解

思路与推导

若 k 组有标号，设各组个数为 x₁,…,xₖ，则 $x_1+⋯+x_k=n$ 且每个值可为 0。
加入 k−1 个隔板并允许相邻隔板，方案数为 $\binom{n+k-1}{k-1}$ 。题中 $\binom{n-1}{k-1}$ 对应每组至少一个，故错误。

第 8 题（判断题，2 分）

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

正确答案正确

解析详情

答案正确浮点除法与面积

思路与推导

直角三角形面积为 $ab/2$ 。表达式 a/2.0 首先按浮点除法执行，不会因 a 为奇数而截断半个单位。
之后再乘 b，例如 a=3、b=5 时得到 1.5×5=7.5，所以此表达式可以计算面积。

第 9 题（判断题，2 分）

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

正确答案正确

解析详情

答案正确公式法复杂度

思路与推导

已知首项、公差和 n，可用常数次运算求末项，再代入 $S_n=n(a_1+a_n)/2$ 。
不论 n 多大，按固定宽度数值运算模型，所做加减乘除次数都不随 n 增长，所以为 $O(1)$ 。

第 10 题（判断题，2 分）

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

正确答案正确

解析详情

答案正确二次询问的真假逻辑

思路与推导

若被问者诚实，另一个路人说谎；说谎者被问去说谎国的路时会指向诚实国，诚实者如实转述，也指向诚实国。
若被问者说谎，另一位诚实者会指出说谎国；说谎者歪曲这一回答，仍指向诚实国。
因此这样问能辨明道路：两种情况下所指的都是诚实国，要去说谎国应走相反方向。