海中自主招生（信息学特长生）全真模拟试卷（第二套）

考试说明：

1. 本试卷满分 50 分，考试时间 60 分钟。
2. 试卷结构严格对标真实考纲：
   • 第一部分：单项选择题（第 1 ~ 10 题，每题 2 分，共 20 分）
   • 第二部分：程序阅读题（第 11 ~ 22 题，含判断与单选，共 18 分）
   • 第三部分：完善程序题（第 23 ~ 27 题，共 5 空，每题 2~3 分，共 12 分）
3. 请在答题纸或草稿纸上独立闭卷完成，试卷末尾附有 NOI 金牌教练详尽参考答案与逐题深度剖析。

---

第一部分：单项选择题（共 10 题，每题 2 分，共 20 分）

第 1 题 将二进制数 $(11010110)_2$ 与十六进制数 $(2E)_{16}$ 进行按位与（AND）运算，再将所得结果与八进制数 $(53)_8$ 进行按位或（OR）运算，最终结果转换为十六进制表示为（ ）。

{{ select(1) }}

• 0x2F
• 0x2B
• 0x3B
• 0x3F

第 2 题 在 C++ 语言中，已知 int x = 2, y = 3, z = 4;，执行表达式 x += y > z ? y : z *= 2 后，变量 x, y, z 的值分别为（ ）。

{{ select(2) }}

• x = 10, y = 3, z = 8
• x = 6, y = 3, z = 8
• x = 5, y = 3, z = 4
• x = 10, y = 6, z = 8

第 3 题 从 6 名男生和 4 名女生中选出 4 人参加信奥学术交流研讨会，要求男女生都要有，且至少有 2 名男生，则不同的选取方案共有（ ）种。

{{ select(3) }}

• 160
• 170
• 185
• 195

第 4 题 已知 4 位格雷码（Gray Code）的二进制反射生成规则中，十进制数 0 到 15 依次对应唯一的格雷码序列。已知某格雷码为 1101，将其还原为对应的原始二进制数，其二进制表示为（ ）。

{{ select(4) }}

• 1001
• 1010
• 1011
• 1110

第 5 题 在单链表中，指针 head 指向非空单链表的第一个有效节点（不带独立虚拟头结点）。若要将由指针 p 指向的新节点作为整个链表的新的首节点插入，正确的操作语句是（ ）。

{{ select(5) }}

• p->next = head->next; head = p;
• p->next = head; head = p;
• head->next = p; head = p;
• head = p; p->next = head;

第 6 题 在一个初始为空的大根二叉堆（基于 std::priority_queue 逻辑）中，依次插入数据序列 {18, 7, 25, 12, 33, 40, 20}。当所有元素插入完成后，该二叉堆对应的顺序存储数组中，位于数组下标 3（以 1 为根节点编号）的元素是（ ）。

{{ select(6) }}

• 18
• 25
• 33
• 20

第 7 题 对长度为 $n$ 的待排序数组，下列关于经典排序算法在“最好情况”与“最坏情况”下比较次数的叙述，错误的是（ ）。

{{ select(7) }}

• 堆排序在最好和最坏情况下的时间复杂度均为 $O(n \log n)$
• 归并排序在最好和最坏情况下的时间复杂度均为 $O(n \log n)$
• 快速排序在最好情况下的时间复杂度为 $O(n \log n)$，最坏情况下为 $O(n^2)$
• 冒泡排序无论在最好情况还是最坏情况下，其元素比较次数均严格等于 $\frac{n(n-1)}{2}$

第 8 题 设散列表（Hash Table）长度为 13，散列函数为 $H(key) = key \bmod 13$。采用二次探测法（Quadratic Probing，发生冲突时探测序列为 $H(key) + 1^2, H(key) - 1^2, H(key) + 2^2, \dots$ 模 13 取正余数）。若已插入关键字 {26, 39}（分别占据位置 0 和 1），现插入关键字 52，则 52 最终被存放在散列表中的下标位置是（ ）。

{{ select(8) }}

• 2
• 4
• 9
• 12

第 9 题 下列关于树与图的连通性性质的说法，正确的是（ ）。

{{ select(9) }}

• 含有 $n$ 个顶点的无向连通图中，若其边数大于 $n-1$，则该图中必然存在至少一个环（回路）
• 含有 $n$ 个节点、 $n-1$ 条边的无向图必然是一棵连通树
• 具有 $n$ 个顶点的无向完全图 $K_n$，其所有生成树的边数均为 $\frac{n(n-1)}{2}$
• 在任何无向图中，度数为奇数的顶点个数必定是奇数

第 10 题 贪心算法在信奥竞赛中应用极广，但其局部最优必须能证明全局最优。下列哪个经典算法的底层求解策略不属于贪心算法？（ ）

{{ select(10) }}

• 哈夫曼编码（Huffman Coding）构造最优二叉树
• 最小生成树 Prim 算法逐步扩展最近顶点
• 求解每对顶点间最短路径的 Floyd-Warshall 算法
• 单源最短路径 Dijkstra 算法每次松弛最近未访问点

---

第二部分：程序阅读题（共 3 大题，共 18 分）

（一）阅读程序（贪心与区间选点覆盖）

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Segment {
    int l, r;
};

bool cmp(const Segment &a, const Segment &b) {
    return a.r < b.r;
}

int main() {
    int n;
    if (!(cin >> n)) return 0;
    vector<Segment> segs(n);
    for (int i = 0; i < n; i++) {
        cin >> segs[i].l >> segs[i].r;
    }

    sort(segs.begin(), segs.end(), cmp);

    int count = 0;
    int last_point = -2e9;

    for (int i = 0; i < n; i++) {
        if (segs[i].l > last_point) {
            count++;
            last_point = segs[i].r;
        }
    }

    cout << count << endl;
    return 0;
}

第 11 题 该程序解决的是经典“区间选点问题”，即在数轴上选取尽可能少的点，使得每一个给定的闭区间内都至少包含一个选中的点。

{{ select(11) }}

• 正确
• 错误

第 12 题 若将排序规则改为按左端点升序排列（即 if (a.l != b.l) return a.l < b.l;），该贪心策略依然能保证在所有情况下得到正确的最少选点数。

{{ select(12) }}

• 正确
• 错误

第 13 题 若输入数据如下：

5
1 5
2 4
3 6
5 8
7 9

程序的输出结果是（ ）。

{{ select(13) }}

• 2
• 3
• 4
• 5

第 14 题 若输入包含 $n$ 个相互包含且右端点相同的区间（例如：[1, 10], [2, 10], [3, 10], ..., [n, 10]），则程序的输出结果为（ ）。

{{ select(14) }}

• 1
• 2
• $n/2$
• $n$

---

（二）阅读程序（分治与快速选择第 K 大）

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int quickSelect(vector<int>& nums, int l, int r, int k) {
    if (l == r) return nums[l];
    int pivot = nums[l + (r - l) / 2];
    int i = l, j = r;
    while (i <= j) {
        while (nums[i] < pivot) i++;
        while (nums[j] > pivot) j--;
        if (i <= j) {
            swap(nums[i], nums[j]);
            i++;
            j--;
        }
    }
    // 递归查找目标
    if (k <= j) return quickSelect(nums, l, j, k);
    if (k >= i) return quickSelect(nums, i, r, k);
    return nums[k];
}

int main() {
    int n, k;
    if (!(cin >> n >> k)) return 0;
    vector<int> nums(n);
    for (int i = 0; i < n; i++) cin >> nums[i];

    // 寻找升序排序后下标为 k-1 的元素（即第 k 小元素）
    cout << quickSelect(nums, 0, n - 1, k - 1) << endl;
    return 0;
}

第 15 题 quickSelect 算法在划分时没有对左右两部分都进行递归，因此在平均情况下的时间复杂度为 $O(n)$。

{{ select(15) }}

• 正确
• 错误

第 16 题 无论基准元素 pivot 如何选取，quickSelect 在最坏情况下的时间复杂度始终不可能超过 $O(n \log n)$。

{{ select(16) }}

• 正确
• 错误

第 17 题 若输入数据如下：

7 4
12 3 5 7 4 19 26

程序的输出结果是（ ）。

{{ select(17) }}

• 5
• 7
• 12
• 19

第 18 题 若待查找数组包含 $n$ 个全部相等的整数（如全部为 5），查找第 $k$ 小元素时，算法执行 while (i <= j) 循环内部交换的次数最接近（ ）。

{{ select(18) }}

• 1
• $n/2$
• $n$
• $n^2$

---

（三）阅读程序（图论最小生成树 Prim 算法）

#include <iostream>
#include <vector>
using namespace std;

const int INF = 1e9;
int graph[105][105];
int min_dist[105];
bool in_tree[105];

int prim(int n) {
    for (int i = 1; i <= n; i++) {
        min_dist[i] = INF;
        in_tree[i] = false;
    }
    min_dist[1] = 0;
    int total_weight = 0;

    for (int i = 1; i <= n; i++) {
        int u = -1, min_val = INF;
        for (int j = 1; j <= n; j++) {
            if (!in_tree[j] && min_dist[j] < min_val) {
                min_val = min_dist[j];
                u = j;
            }
        }

        if (u == -1 || min_val == INF) return -1; // 不连通

        in_tree[u] = true;
        total_weight += min_val;

        for (int v = 1; v <= n; v++) {
            if (!in_tree[v] && graph[u][v] < min_dist[v]) {
                min_dist[v] = graph[u][v];
            }
        }
    }
    return total_weight;
}

int main() {
    int n, m;
    if (!(cin >> n >> m)) return 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i == j) graph[i][j] = 0;
            else graph[i][j] = INF;
        }
    }
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        if (w < graph[u][v]) {
            graph[u][v] = graph[v][u] = w;
        }
    }
    cout << prim(n) << endl;
    return 0;
}

第 19 题 该程序采用基于邻接矩阵存储的 Prim 算法，其时间复杂度为 $O(n^2)$，在顶点数较少而边数极其稠密的稠密图上表现优于普通 Kruskal 算法。

{{ select(19) }}

• 正确
• 错误

第 20 题 在更新非树顶点的最短距离循环中，如果将 graph[u][v] < min_dist[v] 改为 min_dist[u] + graph[u][v] < min_dist[v]，该算法依然能正确求得最小生成树的权值和。

{{ select(20) }}

• 正确
• 错误

第 21 题 若输入数据如下：

4 5
1 2 2
1 3 3
2 3 1
2 4 4
3 4 2

程序的输出结果是（ ）。

{{ select(21) }}

• 5
• 6
• 7
• 8

第 22 题 若将输入中第一行改为 4 2，且只输入边 (1, 2, 2) 和 (3, 4, 2)，则程序的输出是（ ）。

{{ select(22) }}

• 4
• 2
• 0
• -1

---

第三部分：完善程序题（共 5 题，每题 2.4 分，共 12 分）

并查集与连通块数量统计（Disjoint Set Union, DSU）

【题目描述】
一个社交网络中有 $n$ 个人，编号为 $1$ 到 $n$。初始时，每个人都是相互独立的孤立个体。
现发生 $m$ 次交互事件，每次交互表示编号为 $u$ 的人和编号为 $v$ 的人成为了朋友。朋友关系具有传递性（若 A 与 B 是朋友，B 与 C 是朋友，则 A 与 C 属于同一个朋友圈/连通块）。
每次加边后，若 $u$ 和 $v$ 之前属于不同的朋友圈，则需要将它们的朋友圈合并，并更新当前社交网络中总连通块（朋友圈）的数量。
此外，为了提高查询效率，程序使用路径压缩和按秩合并（按集合大小启发式合并）；若输入查询两个人是否处于同一个连通块，直接比较根节点即可。

请根据题目要求，完善下列代码：

#include <iostream>
#include <vector>
using namespace std;

const int MAXN = 100005;
int parent_node[MAXN];
int set_size[MAXN]; // 记录每个连通块包含的节点数量
int components;     // 当前独立的连通块总数

// 查找根节点（带路径压缩）
int find(int x) {
    if (parent_node[x] == x)
        return x;
    return ____(1)____; // 路径压缩递归赋值并返回根节点
}

// 合并两个集合（按大小合并）
bool unite(int x, int y) {
    int rootX = find(x);
    int rootY = find(y);
    if (rootX == rootY) {
        return false; // 已经在同一个连通块，无需合并
    }
    // 启发式合并：保证小树挂在大树下
    if (set_size[rootX] < set_size[rootY]) {
        swap(rootX, rootY);
    }
    parent_node[rootY] = rootX;
    ____(2)____;       // 更新合并后大集合的大小
    ____(3)____;       // 更新连通块总数
    return true;
}

int main() {
    int n, m;
    if (!(cin >> n >> m)) return 0;

    // 初始化并查集
    components = n;
    for (int i = 1; i <= n; i++) {
        parent_node[i] = i;
        ____(4)____;   // 初始化每个独立集合的大小
    }

    for (int i = 0; i < m; i++) {
        int op, u, v;
        cin >> op >> u >> v;
        if (op == 1) {
            // 合并操作
            unite(u, v);
        } else if (op == 2) {
            // 查询 u 和 v 是否连通
            if (____(5)____) {
                cout << "YES" << endl;
            } else {
                cout << "NO" << endl;
            }
        }
    }

    cout << "Final components: " << components << endl;
    return 0;
}

第 23 题 空 (1) 应填入（ ）。

{{ select(23) }}

• parent_node[x] = find(parent_node[x])
• find(parent_node[x])
• parent_node[x] = parent_node[parent_node[x]]
• parent_node[x] = x

第 24 题 空 (2) 应填入（ ）。

{{ select(24) }}

• set_size[rootX] += set_size[rootY]
• set_size[rootY] += set_size[rootX]
• set_size[rootX] = max(set_size[rootX], set_size[rootY])
• set_size[rootX]++

第 25 题 空 (3) 应填入（ ）。

{{ select(25) }}

• components++
• components--
• components = set_size[rootX]
• components = n - set_size[rootX]

第 26 题 空 (4) 应填入（ ）。

{{ select(26) }}

• set_size[i] = 1
• set_size[i] = 0
• set_size[i] = i
• set_size[i] = n

第 27 题 空 (5) 应填入（ ）。

{{ select(27) }}

• parent_node[u] == parent_node[v]
• find(u) == find(v)
• u == v
• set_size[find(u)] == set_size[find(v)]