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

考试说明：

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

---

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

第 1 题 将八进制数 $(375)_8$ 与十六进制数 $(1A)_{16}$ 转换后进行按位异或运算，所得结果的二进制表示为（ ）。

{{ select(1) }}

• 11100111
• 11101111
• 11110011
• 11110001

第 2 题 在 C++ 语言中，已知 int a = 3, b = 4, c = 5;，则表达式 a + b * c > b && c - a != b 的值是（ ）。

{{ select(2) }}

• 0
• 1
• true 且同时修改了变量 a 的值
• 语法错误，编译无法通过

第 3 题 从 1 到 9 这 9 个正整数中任选 3 个不同的数，使得这 3 个数的和为 3 的倍数。不同的选取方案共有（ ）种。

{{ select(3) }}

• 28
• 30
• 36
• 42

第 4 题 已知 4 位格雷码的生成规则满足：二进制码 $B = b_3 b_2 b_1 b_0$ 转换为对应的格雷码 $G = g_3 g_2 g_1 g_0$ 满足公式 $g_3 = b_3$，$g_i = b_{i+1} \oplus b_i$（即 $G = B \oplus (B \gg 1)$）。若十进制数 11 的二进制编码为 $(1011)_2$，则其对应的 4 位格雷码为（ ）。

{{ select(4) }}

• 1110
• 1101
• 1111
• 1010

第 5 题 在具有头结点的单链表中，指针 p 指向某个非末尾结点，若要在 p 之后插入一个由指针 s 指向的新结点，下列操作序列正确的是（ ）。

{{ select(5) }}

• p->next = s; s->next = p->next;
• s->next = p->next; p->next = s;
• s->next = p; p->next = s;
• p->next = s->next; s->next = p;

第 6 题 在 C++ STL 中，std::priority_queue<int> 默认构建的是大根堆，其底层通常采用完全二叉树的顺序数组存储。若当前堆中已有 15 个元素，现调用 push(x) 插入一个新元素并进行 up(向上调整)，在最坏情况下，新元素最多需要进行（ ）次元素交换比较。

{{ select(6) }}

• 3
• 4
• 7
• 15

第 7 题 下列关于常见排序算法的评价，叙述完全正确的一项是（ ）。

{{ select(7) }}

• 快速排序、归并排序和堆排序在最坏情况下的时间复杂度均为 $O(n \log n)$
• 冒泡排序、插入排序和归并排序都是稳定的排序算法
• 快速排序是稳定的，且空间复杂度严格为 $O(1)$
• 选择排序是稳定的，但其平均时间复杂度高达 $O(n^2)$

第 8 题 设散列表（Hash Table）长度为 11，散列函数为 $H(key) = key \bmod 11$。采用线性探测法（Linear Probing）解决冲突。依次插入关键字序列 {12, 23, 34}，则元素 34 最终被存放在散列表中的下标位置是（ ）。

{{ select(8) }}

• 1
• 2
• 3
• 4

第 9 题 一个包含 $n$ 个顶点（$n \ge 3$）且无自环、无重边的连通无向图 $G$，若要保证该图是一棵树，则其必须且仅需满足下列哪项条件？（ ）

{{ select(9) }}

• 图中恰好包含 $n-1$ 条边
• 图中每个顶点的度数都大于等于 2
• 图中存在唯一的欧拉回路
• 图中任意两点间均存在至少两条不重合的简单路径

第 10 题 在贪心算法的应用中，“每一步都采取当前看来最好的局部最优策略”。下列问题中，不能通过经典贪心算法得到全局最优解的是（ ）。

{{ select(10) }}

• 最小生成树问题（Kruskal / Prim 算法）
• 单源最短路径问题且所有边权为非负（Dijkstra 算法）
• 活动安排问题（按结束时间最早排序选择不重叠区间）
• 0-1 背包问题（每个物品只能选 0 次或 1 次）

---

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

（一）阅读程序（贪心与区间合并）

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

struct Interval {
    int l, r;
};

bool cmp(const Interval &a, const Interval &b) {
    if (a.l != b.l) return a.l < b.l;
    return a.r < b.r;
}

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

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

    int ans = 0;
    int cur_l = a[0].l, cur_r = a[0].r;

    for (int i = 1; i < n; i++) {
        if (a[i].l <= cur_r) {
            cur_r = max(cur_r, a[i].r);
        } else {
            ans += (cur_r - cur_l);
            cur_l = a[i].l;
            cur_r = a[i].r;
        }
    }
    ans += (cur_r - cur_l);

    cout << ans << endl;
    return 0;
}

第 11 题 若将 cmp 排序规则改为 return a.r < b.r;，程序的最终输出结果必定不变。

{{ select(11) }}

• 正确
• 错误

第 12 题 该程序的时间复杂度主要瓶颈在于排序，整体时间复杂度为 $O(n \log n)$。

{{ select(12) }}

• 正确
• 错误

第 13 题 若输入数据为：

4
1 3
2 6
8 10
15 18

程序的输出结果是（ ）。

{{ select(13) }}

• 10
• 11
• 12
• 14

第 14 题 若输入 $n$ 个区间且所有区间满足 $a[i].l = 1, a[i].r = 10$，则程序执行完毕后输出为（ ）。

{{ select(14) }}

• $9n$
• $10n$
• 9
• 10

---

（二）阅读程序（分治与归并逆序对）

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

long long cnt = 0;
vector<int> a, tmp;

void mergeSort(int l, int r) {
    if (l >= r) return;
    int mid = l + (r - l) / 2;
    mergeSort(l, mid);
    mergeSort(mid + 1, r);

    int i = l, j = mid + 1, k = l;
    while (i <= mid && j <= r) {
        if (a[i] <= a[j]) {
            tmp[k++] = a[i++];
        } else {
            tmp[k++] = a[j++];
            cnt += (mid - i + 1); // 关键行
        }
    }
    while (i <= mid) tmp[k++] = a[i++];
    while (j <= r) tmp[k++] = a[j++];
    for (int p = l; p <= r; p++) a[p] = tmp[p];
}

int main() {
    int n;
    if (!(cin >> n)) return 0;
    a.resize(n);
    tmp.resize(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    mergeSort(0, n - 1);
    cout << cnt << endl;
    return 0;
}

第 15 题 该程序利用归并排序的分治思想，其统计的 cnt 本质上是数组中满足 $i < j$ 且 $a[i] > a[j]$ 的逆序对总数。

{{ select(15) }}

• 正确
• 错误

第 16 题 若将关键行中的 cnt += (mid - i + 1); 改为 cnt += (r - j + 1);，程序仍能正确统计出逆序对总数。

{{ select(16) }}

• 正确
• 错误

第 17 题 若输入序列为：

5
5 4 3 2 1

程序的输出结果是（ ）。

{{ select(17) }}

• 5
• 8
• 10
• 15

第 18 题 若输入的数组已经是完全严格升序排列的，则程序的输出结果为（ ）。

{{ select(18) }}

• 0
• 1
• $n-1$
• $\frac{n(n-1)}{2}$

---

（三）阅读程序（图论最小生成树 Kruskal）

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

struct Edge {
    int u, v, w;
};

bool cmp(const Edge &a, const Edge &b) {
    return a.w < b.w;
}

int parent_node[1005];

int find_root(int x) {
    if (parent_node[x] == x) return x;
    return parent_node[x] = find_root(parent_node[x]);
}

int main() {
    int n, m;
    if (!(cin >> n >> m)) return 0;
    vector<Edge> edges(m);
    for (int i = 0; i < m; i++) {
        cin >> edges[i].u >> edges[i].v >> edges[i].w;
    }

    for (int i = 1; i <= n; i++) parent_node[i] = i;
    sort(edges.begin(), edges.end(), cmp);

    int total_weight = 0, edge_count = 0;
    for (int i = 0; i < m; i++) {
        int root_u = find_root(edges[i].u);
        int root_v = find_root(edges[i].v);
        if (root_u != root_v) {
            parent_node[root_u] = root_v;
            total_weight += edges[i].w;
            edge_count++;
            if (edge_count == n - 1) break;
        }
    }

    if (edge_count == n - 1) cout << total_weight << endl;
    else cout << -1 << endl;

    return 0;
}

第 19 题 函数 find_root 中使用了路径压缩优化，这使得单次查询的平摊时间复杂度接近 $O(1)$（反阿克曼函数 $\alpha(n)$）。

{{ select(19) }}

• 正确
• 错误

第 20 题 如果图本身不连通，程序最终将输出 -1。

{{ select(20) }}

• 正确
• 错误

第 21 题 若输入数据为：

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

程序的输出结果是（ ）。

{{ select(21) }}

• 6
• 7
• 8
• 10

第 22 题 Kruskal 算法的核心思想是贪心策略，该算法在边数 $m$ 相对稀疏时效率极高，其总时间复杂度为（ ）。

{{ select(22) }}

• $O(n^2)$
• $O(m \log m)$
• $O(n \log n)$
• $O(m \alpha(n))$

---

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

最长上升子序列（LIS, Longest Increasing Subsequence）

【题目描述】
给定一个长度为 $n$ 的整数数组 $a$（下标从 $1$ 到 $n$），请求出其最长严格单调上升子序列的长度。
为了在海中自招中取得满分，小杨需要实现基于贪心 + 二分查找的优化算法，将时间复杂度优化到 $O(n \log n)$。
该算法维护一个数组 $d$（$1$ 索引），其中 $d[len]$ 表示当前已找到的长度为 $len$ 的上升子序列中，末尾元素的最小值。遍历原数组中的每一个元素 $a[i]$：

• 若 $a[i] > d[len]$，则可将 $a[i]$ 追加在当前最长子序列之后，形成长度为 $len + 1$ 的更长子序列；
• 否则，在数组 $d[1 \dots len]$ 中通过二分查找找到第一个大于等于 $a[i]$ 的位置 $pos$，并用 $a[i]$ 更新 $d[pos]$，以降低末尾元素的值，为后续元素创造更有利的上升空间。

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

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

const int MAXN = 100005;
int a[MAXN];
int d[MAXN]; // d[len] 表示长度为 len 的上升子序列末尾元素的最小值

// 二分查找：在 d[1...len] 中查找第一个大于等于 target 的下标
int binary_search_first_ge(int len, int target) {
    int l = 1, r = len, ans = len;
    while (l <= r) {
        int mid = l + (r - l) / 2;
        if (d[mid] >= target) {
            ans = mid;
            ____(1)____; // 尝试向左寻找更靠前的满足条件的位置
        } else {
            ____(2)____;
        }
    }
    return ans;
}

int main() {
    int n;
    if (!(cin >> n) || n <= 0) return 0;
    for (int i = 1; i <= n; i++) cin >> a[i];

    int len = 1;
    d[1] = a[1]; // 初始化长度为 1 的最小末尾为 a[1]

    for (int i = 2; i <= n; i++) {
        if (____(3)____) {
            // 当前元素大于已知最长子序列的末尾，可直接扩展
            len++;
            ____(4)____;
        } else {
            // 在 d[1...len] 中找到第一个 >= a[i] 的元素并替换
            int pos = binary_search_first_ge(len, a[i]);
            ____(5)____;
        }
    }

    cout << len << endl;
    return 0;
}

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

{{ select(23) }}

• r = mid - 1
• r = mid
• l = mid + 1
• l = mid

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

{{ select(24) }}

• r = mid - 1
• r = mid
• l = mid + 1
• l = mid

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

{{ select(25) }}

• a[i] >= d[len]
• a[i] > d[len]
• a[i] > d[1]
• a[i] < d[len]

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

{{ select(26) }}

• d[len] = a[i]
• d[1] = a[i]
• d[len] = d[len - 1]
• d[i] = a[i]

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

{{ select(27) }}

• d[pos] = a[pos]
• d[len] = a[i]
• d[pos] = a[i]
• d[pos + 1] = a[i]