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

考试说明：

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

---

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

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

{{ select(1) }}

• 0x0C
• 0x1C
• 0x0E
• 0x16

第 2 题 在 C++ 语言中，已知 int a = 1, b = 2, c = 3, d = 4;，执行表达式 bool res = (a++ > 1 && ++b > 2) || (c++ == 3 && ++d > 4); 后，变量 a, b, c, d 的值依次为（ ）。

{{ select(2) }}

• a = 2, b = 3, c = 4, d = 5
• a = 2, b = 2, c = 4, d = 5
• a = 1, b = 2, c = 3, d = 4
• a = 2, b = 2, c = 3, d = 5

第 3 题 将 9 个完全相同的苹果分给 3 个不同的小朋友（小明、小华、小红），要求小明至少分到 2 个苹果，小华至少分到 1 个苹果，小红至少分到 3 个苹果，则不同的分配方案总共有（ ）种。

{{ select(3) }}

• 8
• 10
• 15
• 21

第 4 题 若用 5 位二进制表示十进制整数 19，即 $(10011)_2$。根据格雷码生成规则 $G = B \oplus (B >> 1)$，则十进制数 19 对应的 5 位格雷码二进制串为（ ）。

{{ select(4) }}

• 11010
• 11110
• 10101
• 11001

第 5 题 在带头结点的双向循环链表中，每个节点包含指针域 prev 和 next。现欲在指针 p 所指向的节点之后插入一个新节点 s，则下列指针操作序列中，能够正确完成插入且不破坏链表结构的是（ ）。

{{ select(5) }}

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

第 6 题 已知一棵小根二叉堆（Min Heap），用一维数组顺序存储（下标从 1 开始），当前数组元素为 [0, 3, 7, 5, 12, 9, 8, 10]（0 号下标占位不用）。现执行一次“弹出堆顶”操作：将末尾元素 10 移至堆顶并进行下沉（sift down）调整。调整完毕后，堆顶元素变为 5，此时元素 10 最终所在的数组下标为（ ）。

{{ select(6) }}

• 3
• 5
• 6
• 7

第 7 题 下列关于常见经典排序算法的陈述中，错误的是（ ）。

{{ select(7) }}

• 希尔排序是不稳定排序，其平均时间复杂度优于直接插入排序
• 归并排序在最好、最坏与平均情况下的时间复杂度均为 $O(n \log n)$，且属于稳定排序
• 冒泡排序每完成一趟遍历，都能将至少一个未归位元素移动到其最终排序位置
• 快速排序的空间复杂度主要由递归调用栈产生，在最坏情况下的空间复杂度为 $O(\log n)$

第 8 题 将关键字序列 {16, 28, 4, 15, 39} 依次存入长度为 7 的散列表（哈希表）中（下标 $0 \sim 6$）。采用哈希函数 $H(key) = key \bmod 7$，并使用线性探测法解决冲突。当所有关键字插入完毕后，查找成功的平均查找长度（ASL）为（ ）。

{{ select(8) }}

• 1.2
• 1.4
• 1.6
• 1.8

第 9 题 已知一棵度为 3 的树中，度为 1、2、3 的节点数分别为 4、2、1 个，则该树中叶子节点（度为 0 的节点）的数量为（ ）。

{{ select(9) }}

• 4
• 5
• 6
• 7

第 10 题 下列关于无向连通图的图论概念叙述中，正确的是（ ）。

{{ select(10) }}

• 含有 $n$ 个顶点的无向连通图，其边数至少为 $n$ 条
• 若无向连通图中所有顶点的度数均为偶数，则该图一定存在欧拉回路
• 任意一个有向无环图（DAG）其拓扑排序的结果必定是唯一的
• 求解任意两个顶点间的最短路径，Dijkstra 算法的时间复杂度总是优于 Floyd 算法

---

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

阅读程序（一）

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

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

    int left = 0, right = n - 1;
    long long max_area = 0;
    while (left < right) {
        long long current = 1LL * min(h[left], h[right]) * (right - left);
        if (current > max_area) {
            max_area = current;
        }
        if (h[left] < h[right]) {
            left++;
        } else {
            right--;
        }
    }
    cout << max_area << endl;
    return 0;
}

判断题（每题 1 分，共 2 分）

第 11 题 当输入的 $n \le 1$ 时，while 循环体一次也不会执行，程序最终输出为 0。（ ）

{{ select(11) }}

• 正确
• 错误

第 12 题 若将第 20 行的 h[left] < h[right] 修改为 h[left] <= h[right]，对于任意合法输入，程序的最终输出结果一定会发生改变。（ ）

{{ select(12) }}

• 正确
• 错误

单选题（每题 2 分，共 4 分）

第 13 题 若输入 n = 5，输入的数组元素依次为 1 8 6 2 5，则程序的输出结果为（ ）。

{{ select(13) }}

• 12
• 15
• 16
• 18

第 14 题 该算法解决的问题是经典的“盛最多水的容器”（Container With Most Water），其核心时间复杂度为（ ）。

{{ select(14) }}

• $O(n)$
• $O(n \log n)$
• $O(n^2)$
• $O(1)$

---

阅读程序（二）

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

const int MAXN = 100005;
int a[MAXN], temp_arr[MAXN];

long long solve(int L, int R) {
    if (L >= R) return 0;
    int mid = L + (R - L) / 2;
    long long cnt = solve(L, mid) + solve(mid + 1, R);

    int i = L, j = mid + 1, k = L;
    while (i <= mid && j <= R) {
        if (a[i] <= a[j]) {
            temp_arr[k++] = a[i++];
        } else {
            temp_arr[k++] = a[j++];
            cnt += (mid - i + 1);
        }
    }
    while (i <= mid) temp_arr[k++] = a[i++];
    while (j <= R) temp_arr[k++] = a[j++];
    for (int p = L; p <= R; p++) a[p] = temp_arr[p];
    return cnt;
}

int main() {
    int n;
    if (!(cin >> n)) return 0;
    for (int i = 1; i <= n; i++) cin >> a[i];
    cout << solve(1, n) << endl;
    return 0;
}

判断题（每题 1 分，共 2 分）

第 15 题 该程序在递归统计逆序对的同时，会将原数组 a 最终重排为单调不降（非递减）的有序状态。（ ）

{{ select(15) }}

• 正确
• 错误

第 16 题 若将第 16 行的 if (a[i] <= a[j]) 修改为 if (a[i] < a[j])，对于包含重复元素的输入序列，程序的输出结果依然严格保持不变。（ ）

{{ select(16) }}

• 正确
• 错误

单选题（每题 2 分，共 4 分）

第 17 题 若输入 n = 6，且数组元素依次为 5 2 6 3 1 4，则程序的输出结果为（ ）。

{{ select(17) }}

• 8
• 9
• 10
• 11

第 18 题 若输入的数组原本就是由 $n$ 个两两不同的正整数构成的完全降序序列（如 $n, n-1, \dots, 1$），则程序输出的数值恰好等于（ ）。

{{ select(18) }}

• $n(n+1)/2$
• $n(n-1)/2$
• $n^2$
• $n-1$

---

阅读程序（三）

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

struct Edge {
    int u, v, w;
    bool operator<(const Edge& other) const {
        return w < other.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());

    int edge_count = 0;
    long long total_weight = 0;

    for (int i = 0; i < m; i++) {
        int ru = find_root(edges[i].u);
        int rv = find_root(edges[i].v);
        if (ru != rv) {
            parent_node[ru] = rv;
            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;
}

判断题（每题 1 分，共 2 分）

第 19 题 若输入的无向图原本是不连通的（即连通分量个数大于 1），则程序最终必定输出 -1。（ ）

{{ select(19) }}

• 正确
• 错误

第 20 题 若将第 38 行的 parent_node[ru] = rv; 替换为 parent_node[edges[i].u] = edges[i].v;，算法依然能够完全正确地求出最小生成树的权值。（ ）

{{ select(20) }}

• 正确
• 错误

单选题（每题 2 分，共 4 分）

第 21 题 若输入 $n = 4, m = 5$，接下来的 5 行边信息依次为：

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

则程序的最终输出为（ ）。

{{ select(21) }}

• 6
• 7
• 8
• 10

第 22 题 当输入图为稠密图（边数 $m \approx n^2$）时，该算法的时间瓶颈主要集中在边集的排序阶段，其时间复杂度为（ ）。

{{ select(22) }}

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

---

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

题目背景：最长上升子序列（LIS）的二分贪心算法

给定一个长度为 $n$ 的正整数序列 $a_1, a_2, \dots, a_n$。要求从中选出一个子序列，满足其元素严格单调递增，且长度最长。

传统的动态规划转移方程为 $dp[i] = \max_{j < i, a[j] < a[i]} (dp[j] + 1)$，时间复杂度为 $O(n^2)$。当 $n = 10^5$ 时该算法会超时。

为了优化至 $O(n \log n)$，我们维护一个辅助数组 d[len]，表示当前所有长度为 len 的严格上升子序列中，末尾元素的最小值。易知数组 d 具有严格单调递增的性质。

遍历原序列中的每个元素 $a[i]$：

1. 若 $a[i] > d[len]$，说明可以将 $a[i]$ 直接接在当前最长序列后面，使得最大长度增加 1；
2. 否则，在单调数组 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 的上升子序列末尾元素的最小值

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

    int len = 1;
    ____(1)____; // 初始化长度为 1 的上升子序列末尾元素

    for (int i = 2; i <= n; i++) {
        if (____(2)____) {
            // 当前元素大于当前已知最长序列的末尾，直接延长
            ____(3)____;
        } else {
            // 在 d[1...len] 中二分查找第一个 >= a[i] 的位置
            int L = 1, R = len, pos = len;
            while (L <= R) {
                int mid = L + (R - L) / 2;
                if (____(4)____) {
                    pos = mid;
                    R = mid - 1; // 尝试在左半区间寻找更靠前的位置
                } else {
                    L = mid + 1;
                }
            }
            ____(5)____; // 贪心替换
        }
    }

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

第 23 题 请为代码中 ____(1)____ 处选择最恰当的语句（ ）。

{{ select(23) }}

• d[1] = 0
• d[1] = a[1]
• d[len] = a[n]
• d[0] = a[1]

第 24 题 请为代码中 ____(2)____ 处选择最恰当的条件判断（ ）。

{{ select(24) }}

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

第 25 题 请为代码中 ____(3)____ 处选择最恰当的更新语句（ ）。

{{ select(25) }}

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

第 26 题 请为代码中 ____(4)____ 处选择最恰当的二分判定条件（ ）。

{{ select(26) }}

• d[mid] < a[i]
• d[mid] >= a[i]
• d[mid] == a[i]
• d[mid] > d[mid - 1]

第 27 题 请为代码中 ____(5)____ 处选择最恰当的替换语句（ ）。

{{ select(27) }}

• d[pos] = a[i]
• d[pos] = min(d[pos], a[i - 1])
• d[pos + 1] = a[i]
• a[i] = d[pos]