第 1 题（2 分）

一个有 $10$ 个顶点的无向简单图（无自环、无重边），要保证该图一定连通，至少需要多少条边？

{{ select(1) }}

• $37$
• $9$
• $10$
• $45$

---

第 2 题（2 分）

一个无向带权图有 $6$ 个顶点、$9$ 条边，边及其权值为：$(1,2,4)$、$(1,3,1)$、$(2,3,2)$、$(2,4,5)$、$(3,4,8)$、$(3,5,10)$、$(4,5,2)$、$(4,6,6)$、$(5,6,3)$。该图最小生成树的边权之和是？

{{ select(2) }}

• $13$
• $12$
• $14$
• $15$

---

第 3 题（2 分）

散列表长度为 $11$，散列函数 $h(x)=x \bmod 11$，使用线性探查法处理冲突。依次插入 $47, 7, 29, 11, 16, 92, 22, 8$，则关键字 $8$ 最终存放在哪个地址（地址从 $0$ 编号）？

{{ select(3) }}

• $8$
• $10$
• $0$
• $9$

---

第 4 题（2 分）

用数组表示的小根堆（下标从 $0$ 开始，元素依次为 $1, 3, 2, 7, 4, 5, 6, 9, 8$）。执行一次「删除最小元素」操作（把末尾元素移到根后下沉）之后，数组的内容是？

{{ select(4) }}

• $2, 3, 5, 7, 4, 6, 8, 9$
• $2, 3, 5, 7, 4, 8, 6, 9$
• $8, 3, 2, 7, 4, 5, 6, 9$
• $2, 4, 5, 7, 8, 6, 9, 3$

---

第 5 题（2 分）

对区间 $[1, 13]$ 递归建一棵线段树（每个结点表示区间 $[l,r]$，当 $l<r$ 时以 $mid=\lfloor (l+r)/2 \rfloor$ 分成 $[l,mid]$ 与 $[mid+1,r]$ 两个子结点），则这棵树共有多少个结点？

{{ select(5) }}

• $26$
• $27$
• $13$
• $25$

---

第 6 题（2 分）

字符串 ababaab 的 KMP 失配数组 $next$（$next[i]$ 表示前 $i$ 个字符组成的前缀中，真前缀与真后缀相等的最大长度，下标从 $1$ 开始）是？

{{ select(6) }}

• $0, 0, 1, 2, 3, 0, 1$
• $0, 1, 0, 1, 2, 2, 3$
• $0, 0, 1, 2, 3, 1, 2$
• $0, 0, 1, 2, 3, 4, 2$

---

第 7 题（2 分）

在 $1 \sim 2026$ 的所有正整数中，既不能被 $3$ 整除、也不能被 $5$ 整除、也不能被 $7$ 整除的数共有多少个？

{{ select(7) }}

• $926$
• $1157$
• $927$
• $1100$

---

第 8 题（2 分）

从 $1, 2, \dots, 12$ 这 $12$ 个数中选出 $4$ 个，要求任意两个所选的数都不相邻（即不存在两个所选数之差为 $1$）。共有多少种不同的选法？

{{ select(8) }}

• $210$
• $126$
• $495$
• $70$

---

第 9 题（2 分）

以下 C++ 代码段中，语句 s++; 的执行次数关于 $n$ 的量级是？

int s = 0;
for (int i = 1; i <= n; i++)
    for (int j = i; j <= n; j += i)
        s++;

{{ select(9) }}

• $\Theta(n)$
• $\Theta(n \log n)$
• $\Theta(n^2)$
• $\Theta(n \sqrt n)$

---

第 10 题（2 分）

一棵二叉树中，度为 $0$ 的结点（叶子）有 $25$ 个，则度为 $2$ 的结点有多少个？

{{ select(10) }}

• $25$
• $26$
• $24$
• 无法确定

---

第 11 题（2 分）

有 $8$ 个元素，初始时每个元素各成一个集合。并查集采用按秩合并（秩为树高，合并时把矮树挂到高树下；等高时把第二棵挂到第一棵下并使第一棵的秩加一），且过程中不做任何查询、因而不发生路径压缩。依次执行 $union(1,2)$、$union(3,4)$、$union(5,6)$、$union(7,8)$、$union(1,3)$、$union(5,7)$、$union(1,5)$ 后，所得这棵树的高度（以边数计）是？

{{ select(11) }}

• $2$
• $4$
• $7$
• $3$

---

第 12 题（2 分）

连续掷两次均匀的六面骰子，两次点数之和为 $8$ 的概率是？

{{ select(12) }}

• $\dfrac{1}{6}$
• $\dfrac{1}{9}$
• $\dfrac{5}{36}$
• $\dfrac{1}{12}$

---

第 13 题（2 分）

有 $4$ 件物品，(重量, 价值) 依次为 $(5,10)$、$(4,40)$、$(6,30)$、$(3,50)$，背包容量为 $10$，每件物品至多取一次。能获得的最大总价值是？

{{ select(13) }}

• $90$
• $80$
• $100$
• $120$

---

第 14 题（2 分）

欧拉函数 $\varphi(n)$ 表示 $1 \sim n$ 中与 $n$ 互质的正整数个数。已知 $2026 = 2 \times 1013$ 且 $1013$ 是质数，则 $\varphi(2026)$ 的值是？

{{ select(14) }}

• $1013$
• $1012$
• $2025$
• $506$

---

第 15 题（2 分）

十进制数 $2026$ 用十六进制表示是？

{{ select(15) }}

• $\text{7AE}_{16}$
• $\text{3752}_{16}$
• $\text{7EA}_{16}$
• $\text{7E2}_{16}$

---

第 16 题（13 分）

阅读程序（程序输入不超过数组或字符串定义的范围；判断题正确填 A，错误填 B；除特殊说明外，判断题 1.5 分，选择题 3 分，共计 40 分。题中"第 $N$ 行"指代码块中从第一行 #include 起算的第 $N$ 行）

#include <cstdio>
typedef unsigned int uint;
int n;
uint a[100007];
uint f(uint x) {
    uint c = 0;
    while (x) { x &= x - 1; ++c; }
    return c;
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) scanf("%u", &a[i]);
    uint best = 0;
    int cnt = 0;
    for (int i = 1; i <= n; ++i)
        for (int j = i + 1; j <= n; ++j) {
            uint v = a[i] ^ a[j];
            if (f(v) > f(best)) { best = v; cnt = 1; }
            else if (f(v) == f(best)) ++cnt;
        }
    printf("%u %d\n", f(best), cnt);
    return 0;
}

假设输入满足 $2 \leq n \leq 1000$，$a_i$ 为不超过 $2^{32}-1$ 的非负整数。

判断题

16.（$1$ 分）函数 f(x) 返回的是 $x$ 的二进制表示中 $1$ 的个数。（ ）

{{ select(16) }}

• T
• F

17. 当输入的所有 $a_i$ 都相等时，程序输出的第二个数是 $\dfrac{n(n-1)}{2}$。（ ）

{{ select(17) }}

• T
• F

18. 程序输出的第一个数一定不超过 $31$。（ ）

{{ select(18) }}

• T
• F

单选题

19. 当输入为 3 与 1 2 3 时，输出为（ ）。 {{ select(19) }}

• 2 2
• 1 2
• 2 1
• 2 3

20. 记 $w$ 为一个 unsigned int 的二进制位数（本题中 $w=32$）。若把 $w$ 也计入，则该程序的时间复杂度为（ ）。 {{ select(20) }}

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

21. 当输入为 5 与 1 2 4 8 16 时，输出为（ ）。 {{ select(21) }}

• 2 1
• 2 10
• 1 10
• 4 10

---

第 17 题（13.5 分）

#include <algorithm>
#include <cstdio>
int n;
int a[100007], f[100007], g[100007];
int solve1() {
    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        f[i] = 1;
        for (int j = 1; j < i; ++j)
            if (a[j] < a[i] && f[j] + 1 > f[i]) f[i] = f[j] + 1;
        if (f[i] > ans) ans = f[i];
    }
    return ans;
}
int solve2() {
    int len = 0;
    for (int i = 1; i <= n; ++i) {
        int p = (int)(std::lower_bound(g + 1, g + len + 1, a[i]) - g);
        g[p] = a[i];
        if (p > len) len = p;
    }
    return len;
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
    printf("%d %d\n", solve1(), solve2());
    return 0;
}

假设输入满足 $1 \leq n \leq 10^5$，$a_i$ 均为 int 范围内的整数。

判断题

22. 对任意合法输入，程序输出的两个数总是相等。（ ）

{{ select(22) }}

• T
• F

23. 程序运行结束后，数组 g 的前 len 个位置 g[1..len] 中存放的，一定是原序列的某个最长上升子序列。（ ）

{{ select(23) }}

• T
• F

24. 若把 solve1 中的 a[j] < a[i] 改为 a[j] <= a[i]，同时把 solve2 中的 lower_bound 改为 upper_bound，则对任意输入两个函数的返回值仍然相等。（ ）

{{ select(24) }}

• T
• F

单选题

25. solve1 与 solve2 的时间复杂度依次为（ ）。 {{ select(25) }}

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

26. 当输入为 8 与 3 1 4 1 5 9 2 6 时，输出为（ ）。 {{ select(26) }}

• 5 5
• 4 5
• 3 3
• 4 4

27. 在 solve2 中，循环进行到第 $i$ 轮结束时，g[k]（$1 \leq k \leq len$）的含义是（ ）。 {{ select(27) }}

• 前 $i$ 个数中所有长度为 $k$ 的上升子序列的最小结尾元素
• 前 $i$ 个数中长度为 $k$ 的上升子序列的个数
• 前 $i$ 个数中第 $k$ 小的元素
• 前 $i$ 个数中长度为 $k$ 的上升子序列的最大结尾元素

---

第 18 题（13.5 分）

#include <cstdio>
int n, k;
int a[100007], cnt[100007];
int main() {
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
    int kinds = 0, ans = 0, best = 0;
    for (int l = 1, r = 0; l <= n; ++l) {
        while (r < n && (kinds < k || cnt[a[r + 1]] > 0)) {
            ++r;
            if (cnt[a[r]] == 0) ++kinds;
            ++cnt[a[r]];
        }
        if (r - l + 1 > ans) { ans = r - l + 1; best = l; }
        --cnt[a[l]];
        if (cnt[a[l]] == 0) --kinds;
    }
    printf("%d %d\n", ans, best);
    return 0;
}

假设输入满足 $1 \leq n \leq 10^5$，$1 \leq k \leq n$，$1 \leq a_i \leq 10^5$。

判断题

28. 程序求的是「最长的、其中不同元素种数不超过 $k$ 的连续子数组」的长度，以及这样的子数组中最靠左的一个的起始下标。（ ）

{{ select(28) }}

• T
• F

29. 内层 while 循环的总执行次数是 $O(n)$ 的，因此整个程序的时间复杂度为 $O(n)$。（ ）

{{ select(29) }}

• T
• F

30. 若 $k \geq n$，则程序一定输出 n 1。（ ）

{{ select(30) }}

• T
• F

单选题

31. 当输入为 7 2 与 1 2 1 3 3 2 2 时，输出为（ ）。 {{ select(31) }}

• 3 1
• 4 4
• 4 1
• 5 3

32. 变量 r 在整个程序运行过程中（ ）。 {{ select(32) }}

• 单调不减，且最终一定等于 $n$
• 可能减小
• 单调不减，但最终不一定等于 $n$
• 每轮外层循环都会重新从 $l$ 开始

33. 若把第 $9$ 行的循环条件 kinds < k || cnt[a[r + 1]] > 0 改为 kinds < k，则程序（ ）。 {{ select(33) }}

• 输出不变
• 输出的第一个数可能变小
• 输出的第一个数可能变大
• 会陷入死循环

---

第 19 题（15 分）

三、完善程序（单选题，每小题 3 分，共计 30 分）

（1）（字符串匹配）给定文本串 $s$ 与模式串 $t$（长度分别不超过 $10^6$，均只含小写字母），统计 $t$ 在 $s$ 中出现的次数（允许重叠）。例如 $s=$ aaaa、$t=$ aa 时答案为 $3$。

程序采用 KMP 算法。先对 $t$ 求出失配数组 nxt，其中 nxt[i] 表示 $t$ 的前 $i$ 个字符组成的前缀里，真前缀与真后缀相等的最大长度；再用一个指针 j 表示"当前已匹配的长度"扫描 $s$：字符失配时让 j 沿 nxt 回退，匹配成功时 j 加一；一旦 j 达到 $m$ 就计数一次，并让 j 回退到 nxt[j] 以便继续寻找重叠的下一次出现。试补全程序。

#include <cstdio>
#include <cstring>
const int N = 1000006;
char s[N], t[N];
int nxt[N];
int n, m;
int main() {
    scanf("%s%s", s + 1, t + 1);
    n = strlen(s + 1); m = strlen(t + 1);
    nxt[1] = 0;
    for (int i = 2, j = 0; i <= m; ++i) {
        while (j > 0 && t[i] != t[j + 1]) j = __①__;
        if (t[i] == t[j + 1]) ++j;
        nxt[i] = __②__;
    }
    int cnt = 0;
    for (int i = 1, j = 0; i <= n; ++i) {
        while (j > 0 && __③__) j = nxt[j];
        if (s[i] == t[j + 1]) ++j;
        if (__④__) { ++cnt; j = __⑤__; }
    }
    printf("%d\n", cnt);
    return 0;
}

34. ①处应填（ ） {{ select(34) }}

• j - 1
• nxt[j - 1]
• 0
• nxt[j]

35. ②处应填（ ） {{ select(35) }}

• j
• j + 1
• i - j
• 0

36. ③处应填（ ） {{ select(36) }}

• s[i] == t[j + 1]
• s[i] != t[j + 1]
• s[i] != t[j]
• j < m

37. ④处应填（ ） {{ select(37) }}

• j == m
• j >= m - 1
• j == m - 1
• i == n

38. ⑤处应填（ ） {{ select(38) }}

• 0
• j - 1
• nxt[j]
• nxt[j - 1]

---

第 20 题（15 分）

（2）（一次免费的最短路）给定一个 $n$ 个点 $m$ 条边的无向带权图（$1 \leq n \leq 10^5$，$0 \leq m \leq 2\times10^5$，边权为不超过 $10^9$ 的非负整数），起点 $S$、终点 $T$。你有一次机会把路径上某一条边的通行费用当作 $0$（也可以不使用这次机会）。求从 $S$ 走到 $T$ 的最小总费用。若 $T$ 不可达，输出一个极大值。

程序使用分层图（拆点）+ 堆优化 Dijkstra：把每个点拆成两个状态，d[u][0] 表示走到 $u$ 且尚未使用免费机会时的最小费用，d[u][1] 表示走到 $u$ 且已经用掉免费机会时的最小费用。层内沿普通边转移、边权照付；从第 $0$ 层跨到第 $1$ 层的转移表示"这条边免费"，边权按 $0$ 计。答案取两层中终点的较小值。试补全程序。

#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
const int N = 100005, M = 400005;
int head[N], nxt_[M], to_[M], w_[M], ec;
int d[N][2];
bool vis[N][2];
int n, m, S, T;
void add(int u, int v, int w) { to_[++ec] = v; w_[ec] = w; nxt_[ec] = head[u]; head[u] = ec; }
struct Node {
    int dis, u, k;
    bool operator<(const Node &o) const { return dis > o.dis; }
};
int main() {
    scanf("%d%d%d%d", &n, &m, &S, &T);
    for (int i = 1; i <= m; ++i) {
        int u, v, w; scanf("%d%d%d", &u, &v, &w);
        add(u, v, w); add(v, u, w);
    }
    memset(d, 0x3f, sizeof(d));
    priority_queue<Node> q;
    __①__;
    q.push((Node){0, S, 0});
    while (!q.empty()) {
        Node cur = q.top(); q.pop();
        int u = cur.u, k = cur.k;
        if (__②__) continue;
        vis[u][k] = true;
        for (int e = head[u]; e; e = nxt_[e]) {
            int v = to_[e], w = w_[e];
            if (d[u][k] + w < d[v][k]) { d[v][k] = d[u][k] + w; q.push((Node){d[v][k], v, k}); }
            if (__③__) { d[v][1] = d[u][0]; q.push((Node){d[v][1], v, 1}); }
        }
    }
    printf("%d\n", __④__);
    return 0;
}

39. ①处应填（ ） {{ select(39) }}

• d[S][1] = 0
• d[S][0] = 1
• d[T][0] = 0
• d[S][0] = 0

40. ②处应填（ ） {{ select(40) }}

• vis[u][1]
• k == 1
• vis[u][k]
• !vis[u][k]

41. ③处应填（ ） {{ select(41) }}

• k == 0 && d[u][0] < d[v][1]
• k == 1 && d[u][1] < d[v][1]
• k == 0 && d[u][0] + w < d[v][1]
• k == 0 && d[u][0] < d[v][0]

42. ④处应填（ ） {{ select(42) }}

• d[T][0]
• d[T][1]
• min(d[T][0], d[T][1])
• max(d[T][0], d[T][1])

43. 若把第 $28$ 行（if (d[u][k] + w < d[v][k]) 所在行）中的 d[v][k] 误写为 d[v][0]，则程序（ ）。 {{ select(43) }}

• 输出不变
• 第 $1$ 层的距离不再被正确更新，答案可能偏大
• 一定输出 $0$
• 会陷入死循环