小测试-04月25日

朝外信奥1队4月25日笔测 – 答案及解析

朝外信奥1队 04月25日笔测答案

答案及解析 | 来源：朝外信奥 1 队整理 | 日期：2026-04-25

一、单项选择题（每题 2 分，共 30 分）

题号	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
答案	B	D	A	C	D	D	C	A	C	B	A	A	D	D	D

1.（2 分）表达式 (8 % (-6)) 与 (-8 % 6) 的值分别是（）。

A. -2, -2

B. 2, -2

C. -2, 2

D. 2, 2

【答案】B

【解析】任何一个整数 n 都可以表示成 n = k × q + r，其中 0 ≤ |r| < |q|。被除数是负数，余数也是负数；被除数是正数，余数也是正数。故 (8 % (-6)) = 2，(-8 % 6) = -2。

2.（2 分）设根结点深度为 0，一棵深度为 6 的满三叉树共有（）个结点。

A. (3^6 - 1) / 2

B. 3^6

C. 3^7

D. (3^7 - 1) / 2

【答案】D

【解析】深度为 6 的满三叉树（从深度 0 到深度 6，共 7 层），结点数 = 3⁰ + 3¹ + … + 3⁶ = (3⁷ – 1) / (3 – 1) = (3⁷ – 1) / 2。答案为 D。

3.（2 分）以下不属于调试工具 GDB 中命令的是（）。

A. printf

B. display

C. next

D. step

【答案】A

【解析】printf 是 C++ 中的关键字，不是 GDB 里面的命令，GDB 里面的关键字是 print。

4.（2 分）以下哪个不属于算法最本质的特征（）。

A. 有穷性

B. 确定性

C. 先进性

D. 确切性

【答案】C

【解析】算法应具有有穷性、确切性、输入、输出、可行性五个特征。先进性不属于算法的基本特征。

5.（2 分）以下哪个不属于哈希冲突的常见处理方法（）。

A. 哈希法

B. 线性探查法

C. 二次探查法

D. 固定分配法

【答案】D

【解析】哈希法、线性探查法、二次探查法都是常见的处理哈希地址冲突的方法。

6.（2 分）单源最短路问题的常用算法不包含（）。

A. Bellman-Ford

B. Dijkstra

C. SPFA

D. Kruskal

【答案】D

【解析】Kruskal 是最小生成树算法，不属于单源最短路算法。

7.（2 分）设某算法满足递推式 F(n) = F(n - 1) + 2n，且 F(0) = 0，则其时间复杂度为（）。

A. O(logn)

B. O(n)

C. O(n²)

D. O(nlogn)

【答案】C

【解析】F(n) = F(n-1) + 2n，F(0) = 0，可推导出 F(n) = 2(1+2+…+n) = n(n+1) = O(n²)。

8.（2 分）一棵二叉树一共有 19 个结点，那么叶子结点数不可能是（）。

A. 11

B. 10

C. 9

D. 1

【答案】A

【解析】设叶子结点数为 n₀，度为 2 的结点数为 n₂，则 n₀ = n₂ + 1。若 n₀ = 11，则 n₂ = 10，总数至少为 21，超过 19，矛盾。

9.（2 分）关于拓扑排序，下面说法正确的是（）。

A. 拓扑排序只能用广度优先遍历实现

B. 每个有向图都至少存在一个拓扑排序

C. 拓扑排序一定从入度为 0 的结点开始

D. 拓扑排序的方案一定唯一

【答案】C

【解析】拓扑排序一定从入度为 0 的结点开始。拓扑排序既可以用深度优先遍历实现，也可以用广度优先遍历实现。有环的有向图不能进行拓扑排序。

10.（2 分）下列说法中哪个不是树的性质（）。

A. 任意两个结点之间有且只有一条简单路径

B. 树中有可能有一个简单环

C. 边的数目恰好是顶点数减 1

D. 树中无环

【答案】B

【解析】树中不可能有环。

11.（2 分）对于完全背包问题，设 f[i] 表示用去 i 的空间能获得的最大价值，则正确的转移方程是（）。

A. f[i] = max(f[i], f[i-w[j]] + v[j])

B. f[i] = max(f[i], f[i-v[j]] + w[j])

C. f[i] = min(f[i], f[i-w[j]] + v[j])

D. f[i] = min(f[i], f[i-v[j]] + w[j])

【答案】A

【解析】完全背包问题的状态转移方程为 f[i] = max(f[i], f[i-w[j]] + v[j])，其中 w[j] 是第 j 件物品的重量，v[j] 是其价值。

12.（2 分）前缀表达式 *+ab*cd 的后缀表达式是（）。

A. ab+cd**

B. abcd*+*

C. ab+*cd

D. a+b*cd*

【答案】A

【解析】前缀 * + a b * c d，逐层转换：+ab → 后缀 ab+，*cd → 后缀 cd*，最终后缀为 ab+cd* *。答案为 A。

13.（2 分）某学校”信奥”小组有男生和女生各 3 名，现从中挑选 2 名学生参加编程竞赛，至少有 1 名男生参加的概率是（）。

A. 0.5

B. 0.6

C. 0.7

D. 0.8

【答案】D

【解析】C(6,2) = 15 种选拔方式。有 1 名男生：C(3,1)×C(3,1) = 9 种；有 2 名男生：C(3,2) = 3 种。概率 = 12/15 = 0.8。

14.（2 分）四面体的顶点及各棱中点共有 10 个点，在其中取 4 个不共面的点，不同取法共有（）。

A. 150

B. 147

C. 144

D. 141

【答案】D

【解析】C(10,4) – 4×C(6,4) – 6 – 3 = 210 – 60 – 6 – 3 = 141 种。

15.（2 分）设全集 E = {a, b, c, d, e}，A = {a, c}，B = {a, b, d}，C = {b, d}，则 (A∩B) ∪ ~C 的结果为（）。

A. {a}

B. {c, e}

C. {a, e}

D. {a, c, e}

【答案】D

【解析】A∩B = {a,c} ∩ {a,b,d} = {a}，~C = {a,c,e}，最终结果为 {a,c,e}。

二、阅读程序题（共 40 分）

(一) 阅读程序，回答 16~21 题

#include
using namespace std;

int dp[502][502];

int main() {
    string s;
    cin >> s;
    for (int j = 0; j <= s.size(); j++) {
        for (int i = 0; i < s.size() - j; i++) {
            dp[i][i + j] = dp[i + 1][i + j] + 1;
            for (int k = i + 1; k <= i + j; k++) {
                if (s[k] == s[i]) {
                    dp[i][i + j] = min(dp[i][i + j], dp[i + 1][k – 1] + dp[k + 1][i + j]);
                }
            }
        }
    }
    cout << dp[0][s.size() - 1] << endl;
    return 0;
}

题号	16	17	18	19	20	21
答案	✓	✗	✗	✗	B	B

16.（3 分）将第 11 行改为 dp[i][j] = INT_MAX - 1;，代码输出结果会改变。（）

A. 对

B. 错

【答案】✓ (对)

【解析】原 dp[i][i+j] 初始化为 dp[i+1][i+j] + 1。若改成 INT_MAX-1，后续 +1 可能溢出，结果改变。

17.（3 分）修改条件为 if (s[i] == s[j])，代码输出结果不变。（）

A. 对

B. 错

【答案】✗ (错)

【解析】原条件 s[k] == s[i]，改为 s[i] == s[j] 完全不同，结果必然改变。

18.（3 分）用贪心算法可以实现与本程序同样的功能。（）

A. 对

B. 错

【答案】✗ (错)

【解析】这是区间 DP 问题，依赖子问题最优性，贪心无法保证全局最优。

19.（3 分）将第 12 行中循环的 k = i + 1 改为 k = 1，代码输出结果不变。（）

A. 对

B. 错

【答案】✗ (错)

【解析】当 i > 0 时，k = 1 会导致 k < i + 1，访问 dp[i+1][k-1] 中 k-1 < i 的未初始化区域，结果会改变。

20.（4 分）本程序的时间复杂度是（）。

A. O(n²)

B. O(n³)

C. O(n² log n)

D. O(n⁴)

【答案】B

【解析】三层循环：外层 j(0~n) × 中层 i(0~n-j) × 内层 k(i+1~i+j) ≈ O(n³)。

21.（4 分）对于输入 aaogog，本程序的输出为（）。

A. 1

B. 2

C. 3

D. 5

【答案】B

【解析】经 g++ 实际编译运行验证结果为 2。

(二) 阅读程序，回答 22~27 题

#include 
using namespace std;

int parent[100000], sz[100000];
int n, m, components;

void initialize() {
    for (int i = 0; i < n; i++) {
        parent[i] = i;
        sz[i] = 1;
    }
}

int find(int a) {
    if (parent[a] == a) return a;
    return find(parent[a]);
}

void merge(int a, int b) {
    a = find(a), b = find(b);
    if (a == b) return;
    –components;
    if (sz[a] > sz[b]) swap(a, b);
    parent[a] = b;
    sz[b] += sz[a];
}

int findsz(int a) {
    return sz[find(a)];
}

int main() {
    cin >> n >> m;
    initialize();
    components = n;
    int maxComponents = 1;
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        merge(a, b);
        maxComponents = max(maxComponents, findsz(a));
        cout << components << ” “ << maxComponents << endl;
    }
}

题号	22	23	24	25	26	27
答案	✗	✓	✓	✗	B	C

22.（3 分）如果输入的 a 和 b 从 1 开始编号，程序依然可以正常运行。（）

A. 对

B. 错

【答案】✗ (错)

【解析】数组初始化范围 0~n-1，若输入 1 起始则 parent[n] 未初始化（值为 0），与 parent[0] 冲突。

23.（3 分）该程序计算了无向图的连通分量数。（）

A. 对

B. 错

【答案】✓ (对)

【解析】components 初始 n，每次 merge 合并两个不同集合时减 1。

24.（3 分）合并操作总是将较小树的根结点合并到较大树的根结点下。（）

A. 对

B. 错

【答案】✓ (对)

【解析】if (sz[a] > sz[b]) swap(a, b); 确保小树合并到大树下。

25.（3 分）为了确保程序不发生错误，需要保证输入的 a 和 b 互不相同。（）

A. 对

B. 错

【答案】✗ (错)

【解析】若 a == b，merge 中 find(a) == find(b)，直接 return，不影响结果。

26.（4 分）程序运行结束时，maxComponents 变量可以存储的最大值是（）。

A. n / 2

B. n

C. m / 2

D. m

【答案】B

【解析】全部合并到同一个连通分量时，findsz 返回 n。

27.（4 分）如果 merge 总是将结点 b 合并到结点 a，不论 sz 大小如何，最坏运行时间会如何变化（）。

A. 变快

B. 保持不变

C. 变慢

D. 无法确定

【答案】C

【解析】按大小合并保证树高 ≤ log₂n。无视大小可能形成链，find 退化为 O(n)，总体变慢。

三、完善程序（共 30 分）

(一) 根据题意，完成下面程序

// 输入一个整数 x 和 n 个 [0, 2^21 – 1] 范围内的整数，
// 求从任意位置开始的最大区间异或和。
// 如果有多个这样的子区间，则选择最短子区间，输出左右端点。

#include
using namespace std;

const int MAXN = 1e5 + 10;
const int MAXM = MAXN * 21;
int n, x;
int s[MAXN], id[MAXM];
int tree[MAXM][2], idx;

void insert(int x, int k) {
    int p = @;
    for (int i = 20; i >= 0; i–) {
        int u = x >> i & 1;
        if (!tree[p][u]) @;
        @;
    }
    id[p] = k;
}

int query(int x) {
    int p = 0;
    for (int i = 20; i >= 0; i–) {
        int u = x >> i & 1;
        if (@) p = tree[p][u ^ 1];
        else p = tree[p][u];
    }
    return id[p];
}

int main() {
    cin >> n;
    insert(s[0], 0);
    int res = -1;
    int l, r;
    for (int i = 1; i <= n; ++i) {
        cin >> x;
        s[i] = s[i – 1] ^ x;
        int k = query(s[i]);
        int maxn = @;
        if (maxn > res) {
            res = maxn;
            l = k + 1, r = i;
        }
        @;
    }
    cout << res << ” “ << l << ” “ << r << endl;
    return 0;
}

0425

题号	34	35	36	37	38
答案	A	A	C	B	A

34.（6 分）@ 处应填（）。

A. 0

B. 1

C. idx

D. n

【答案】A

【解析】Trie 根结点编号固定为 0。

35.（6 分）第一个 @、第二个 @ 依次应填（）。

A. tree[p][u] = ++idx；p = tree[p][u]

B. tree[p][u] = ++p；p = idx

C. tree[p][u] = idx；p = ++idx

D. tree[p][u] = 0；p = tree[p][u]

【答案】A

【解析】标准 Trie 插入逻辑：① 子结点不存在时用 ++idx 创建新结点：tree[p][u] = ++idx;；② 移动到子结点：p = tree[p][u];

36.（6 分）query 函数中的 @ 处应填（）。

A. tree[p][u]

B. !tree[p][u]

C. tree[p][u ^ 1]

D. !tree[p][u ^ 1]

【答案】C

【解析】求最大异或值应优先走相反位（若存在）：if (tree[p][u ^ 1]) p = tree[p][u ^ 1];，否则走相同位。条件为检查相反位是否存在。

37.（6 分）maxn = @ 处应填（）。

A. s[i] * s[k]

B. s[i] ^ s[k]

C. s[l] ^ s[r]

D. s[i] + s[k]

【答案】B

【解析】s[] 为前缀异或数组，区间 [k+1, i] 的异或值 = s[i] ^ s[k]。

38.（6 分）循环内最后一个 @ 处应填（）。

A. insert(s[i], i)

B. insert(s[r], r)

C. insert(s[i], i – 1)

D. insert(s[r], r – 1)

【答案】A

【解析】每轮将当前前缀异或 s[i] 插入 Trie，位置编号为 i，供后续查询使用。

四面体 10 点取 4 个不共面点

四面体的 10 个点中取 4 个不共面的点

四面体有 4 个顶点、6 条棱的中点，共 10 个点。要从中取 4 个不共面的点，可以先算“四点总取法”，再减去“四点共面”的取法。

题目： 四面体的顶点及各棱中点共有 10 个点，在其中取 4 个不共面的点，不同取法共有多少种？

图形示意

四点总取法

C(10,4)=210

先不管共不共面，10 个点里任取 4 个，一共有 210 种。

4 个面上的共面取法

4 × C(6,4)=4×15=60

每个面上都有 3 个顶点和 3 条边中点，共 6 个点，所以每个面能产生 15 种四点共面取法。

额外的 9 组共面点

6+3=9

这里分成两类：前 6 组是“棱上的 3 点 + 对棱中点”，后 3 组是“4 个中点共面”。

最终答案

210 – 60 – 9 = 141

141 种

为什么额外是 9 组

第 1 类：四点都在四面体的某一个面上，共 4 × C(6,4)=60 种。
第 2 类：一条棱上的 3 个点，加上对棱的中点，共 6 组。
第 3 类：4 个中点共面，共 3 组。
有 6 组平面：一条棱上的 3 个点，加上对棱的中点。例如 A, AB, B, CD。
还有 3 组平面：4 个中点共面。例如 AB, AC, BD, CD。
因此四点共面的总数是 60+9=69，所求不共面取法就是 210-69=141。

Previous Topic

Back to Lesson

Next Topic