一、单项选择题（共 15 题，每题 2 分，共计 30 分；每题有且仅有一个正确选项）

1. 在 Linux 终端中依次执行如下命令：

   chmod u+x run.sh
   ./run.sh < input.txt > output.txt 2> error.log
   

   下列说法正确的是（）{{ select(1) }}

• chmod u+x run.sh 会给所有用户增加执行权限
• ./run.sh 表示执行当前目录下的 run.sh；标准输入来自 input.txt，标准输出写入 output.txt，标准错误写入 error.log
• 2> error.log 会把标准输出和标准错误都写入 error.log
• < input.txt 表示把程序输出追加到 input.txt 末尾

2. 某程序使用如下比较器定义优先队列：

   struct Node { int d, id; };
   struct Cmp {
       bool operator()(const Node& a, const Node& b) const {
           if (a.d != b.d) return a.d > b.d;
           return a.id < b.id;
       }
   };
   

   若依次插入 {3,1}、{2,5}、{2,4}、{3,9}，下列说法正确的是（）{{ select(2) }}

• top() 优先取 d 最大者；若 d 相同，取 id 最小者
• 弹出顺序为 {2,5}、{2,4}、{3,9}、{3,1}
• 弹出顺序为 {2,4}、{2,5}、{3,1}、{3,9}
• 比较器返回 true 表示 a 应当排在堆顶，因此 {3,9} 最先弹出

3. 有向带权图有 5 个点，边为：

   1->2(2), 1->3(1), 3->2(1), 2->4(2),
   3->4(4), 2->5(3), 4->5(1), 3->5(6)
   

   从点 1 出发，按 Dijkstra 算法同时统计最短路条数。到点 5 的最短距离与最短路条数分别为（）{{ select(3) }}

• 4, 2
• 5, 3
• 5, 4
• 6, 4

4. 某开放寻址散列表长度为 11，散列函数为 h(x)=x mod 11，冲突时使用线性探查。依次插入 22, 1, 13, 24 后，再查找不存在的 35，随后将 35 插入表中。下列说法正确的是（）{{ select(4) }}

• 查找 35 访问 2 个槽，35 插入下标 4，插入后装载因子为 5/11
• 查找 35 访问 3 个槽，35 插入下标 5，插入后装载因子为 5/11
• 查找 35 访问 3 个槽，35 插入下标 4，插入后装载因子为 5/11
• 查找 35 访问 3 个槽，35 插入下标 4，插入后装载因子为 4/11

5. 某前缀编码需要编码 7 个字符，其出现频率分别为：

   3, 5, 6, 8, 12, 15, 20
   

   若使用哈夫曼编码，则最小带权路径长度（WPL）与最长编码长度分别为（）{{ select(5) }}

• 180, 4
• 180, 3
• 172, 4
• 69, 4

6. 对于如下差分约束系统：

   x2 - x1 <= 3
   x3 - x2 <= 2
   x1 - x3 <= -6
   

   将约束 xv - xu <= w 看作有向边 u -> v，边权为 w。下列说法正确的是（）{{ select(6) }}

• 系统有解，因为所有边权之和为负
• 系统无解，因为存在权值和为 3+2-6=-1 的负环
• 系统有解，例如 x1=x2=x3=0
• 只要加入超级源点，差分约束系统一定有解

7. 数组 a=[8,4,6,2,7,3,5,1,9,2,6,4] 的所有连续子数组最小值之和为（）{{ select(7) }}

• 152
• 158
• 161
• 168

8. 字母表为 {a,b,c}。若一个长度为 5 的字符串以集合 P 中任意一个字符串为前缀，则称它被禁止。集合 P 为：

   a, ab, ba, cab, bc, cc, aab, bca
   

   把 P 插入 Trie 后进行剪枝：若某个前缀已经是终止节点，则它的所有后代终止节点都不再保留。问未被禁止的长度为 5 的字符串个数，以及剪枝后 Trie 的节点总数（含根节点）分别为（）{{ select(8) }}

• 63, 9
• 72, 8
• 81, 9
• 72, 9

9. 并查集初始有 9 个单点集合，依次合并：

   (1,2), (2,3), (4,5), (6,7), (5,6), (3,7), (8,9), (1,9), (2,8)
   

   若每次成功合并两个不同集合时，把当前图中"处在同一连通块内的无序点对数"增加 size(A)*size(B)，其中 A,B 为合并前两个连通块；若两点已在同一集合中，则本次合并不改变点对数。最终该点对数与成功合并次数分别为（）{{ select(9) }}

• 35, 8
• 36, 8
• 36, 9
• 37, 8

10. 阅读下面程序片段：

    void work(int l, int r) {
        if (l == r) return;
        int mid = (l + r) >> 1;
        vector<int> v;
        for (int i = l; i <= r; ++i) v.push_back(a[i]);
        sort(v.begin(), v.end());
        work(l, mid);
        work(mid + 1, r);
    }
    

    设 n 为 2 的幂，数组 a[1..n] 已经给定，调用 work(1,n)，且不考虑输入输出开销。该程序片段的时间复杂度与额外空间复杂度分别为（）{{ select(10) }}

• $O(n log n), O(log n)$
• $O(n log^2 n), O(n)$
• $O(n^2), O(n log n)$
• $O(n log^2 n), O(n log n)$

11. 无向图边集为：

    1-2, 2-3, 3-1, 3-4, 4-5, 5-6, 6-4, 6-7, 7-8, 8-4
    

    关于欧拉路，下列说法正确的是（）{{ select(11) }}

• 图不连通，因此不存在欧拉路
• 有欧拉回路，因为所有点度数均为偶数
• 有欧拉路但无欧拉回路；若再加入边 3-6，则有欧拉回路
• 只有有向图才讨论欧拉路

12. 有向图有 7 个点，边为：

    1->2, 1->3, 2->4, 2->6, 3->4, 4->5, 5->3, 5->6, 6->7
    

    用 Floyd 传递闭包求所有可达关系，初始化时令 reach[i][i]=true。若最终统计时不计自达关系，则可达有序点对 (u,v) 的个数，以及满足 1 能到达 x 且 x 能到达 7 的点 x 个数分别为（）{{ select(12) }}

• 24, 7
• 23, 6
• 25, 7
• 24, 6

13. 由 8 个字符 A 和 5 个字符 B 组成一个长度为 13 的字符串。要求该字符串的任意一个前缀中，A 的个数都不少于 B 的个数。满足条件的字符串共有（）个{{ select(13) }}

• 429
• 572
• 715
• 1287

14. 在 0 到 200 的整数中，十进制表示不含数字 4，且各位数字和为偶数的整数共有（）个{{ select(14) }}

• 80
• 82
• 84
• 90

15. 一堆石子每次可以取走 1、3 或 4 个，不能操作者负。现在有三堆石子，数量分别为 7,8,10。若用 SG(n) 表示一堆 n 个石子的 SG 函数值，则下列说法正确的是（）{{ select(15) }}

• SG(7)=1, SG(8)=0, SG(10)=1，先手必胜
• SG(7)=0, SG(8)=1, SG(10)=1，先手必胜
• SG(7)=0, SG(8)=1, SG(10)=1，先手必败
• SG(7)=2, SG(8)=3, SG(10)=1，先手必败

二、阅读程序（程序输入不超过数组或字符串定义的范围；判断题正确填对，错误填错；除特殊说明外，判断题1.5分，选择题3分，标注分值题按标注计分，共计40分）

(1)

#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1000000007LL;
int main() {
    string s;
    cin >> s;
    int n = s.size();
    vector<int> pi(n, 0);
    for (int i = 1; i < n; ++i) {
        int j = pi[i - 1];
        while (j > 0 && s[i] != s[j]) j = pi[j - 1];
        if (s[i] == s[j]) ++j;
        pi[i] = j;
    }
    int p = n - pi[n - 1];
    int rep = (n % p == 0 ? n / p : 1);
    vector<int> borders;
    for (int x = pi[n - 1]; x > 0; x = pi[x - 1]) {
        borders.push_back(x);
    }
    long long code = 0;
    for (int x : borders) code = (code * 131 + x) % MOD;
    cout << pi[n - 1] << " " << p << " " << rep << "\n";
    cout << borders.size() << " " << code << "\n";
    return 0;
}

给定输入：

ababababa

16. pi[i] 表示 s[0..i] 的最长真前缀与真后缀相等的长度。（）{{ select(16) }}

• 对
• 错

17. 对给定输入，borders 中的元素依次为 7,5,3,1。（）{{ select(17) }}

• 对
• 错

18. 若 n % p != 0，则 p 一定不是该字符串的周期长度。（2分）（）{{ select(18) }}

• 对
• 错

19. 对给定输入，程序输出为（3分）{{ select(19) }}

• 7 2 1
  4 15822836
  

• 7 2 4
  4 15822836
  

• 5 2 1
  3 657
  

• 7 1 9
  4 15822836
  

20. 若输入为 abcababcab，程序第一行输出为（2分）{{ select(20) }}

• 5 2 1
• 5 5 2
• 2 5 1
• 5 5 1

21. 若输入为 aaaaaa，程序第二行输出为（3分）{{ select(21) }}

• 5 15
• 6 481543708
• 5 481543708
• 5 657

(2)

#include <bits/stdc++.h>
using namespace std;
int n;
long long W;
vector<long long> a;
void gen(int l, int r, vector<long long>& out) {
    int m = r - l;
    for (int mask = 0; mask < (1 << m); ++mask) {
        long long sum = 0;
        for (int i = 0; i < m; ++i) {
            if (mask & (1 << i)) sum += a[l + i];
        }
        if (sum <= W) out.push_back(sum);
    }
}
int main() {
    cin >> n >> W;
    a.resize(n);
    for (int i = 0; i < n; ++i) cin >> a[i];
    int mid = n / 2;
    vector<long long> L, R;
    gen(0, mid, L);
    gen(mid, n, R);
    sort(R.begin(), R.end());
    long long cnt = 0, best = 0;
    for (long long x : L) {
        vector<long long>::iterator it = upper_bound(R.begin(), R.end(), W - x);
        cnt += it - R.begin();
        if (it != R.begin()) {
            --it;
            best = max(best, x + *it);
        }
    }
    cout << cnt << "\n";
    cout << best << "\n";
    return 0;
}

给定输入：

8 17
3 8 4 6 5 7 2 9

22. gen(l,r,out) 枚举的是下标区间 [l,r) 内所有子集的元素和，并且只保留不超过 W 的和。（）{{ select(22) }}

• 对
• 错

23. 若右半部分有两个不同子集的和相同，程序会把它们分别计入答案。（）{{ select(23) }}

• 对
• 错

24. 若把 upper_bound(R.begin(), R.end(), W - x) 改成 lower_bound(R.begin(), R.end(), W - x)，程序输出一定不变。（2分）（）{{ select(24) }}

• 对
• 错

25. 对给定输入，程序输出为（3分）{{ select(25) }}

• 78
  17
  

• 77
  17
  

• 78
  16
  

• 65
  16
  

26. 对给定输入，gen 调用完成后，L.size() 与 R.size() 分别为（3分）{{ select(26) }}

• 13, 13
• 14, 13
• 14, 14
• 16, 16

27. 若仅把给定输入中的 W 改为 16，则程序输出为（3分）{{ select(27) }}

• 68
  16
  

• 78
  17
  

• 65
  16
  

• 68
  15
  

(3)

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 65;
bitset<MAXN> reach[MAXN];
int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) reach[i][i] = 1;
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        reach[u][v] = 1;
    }
    for (int k = 1; k <= n; ++k) {
        for (int i = 1; i <= n; ++i) {
            if (reach[i][k]) reach[i] |= reach[k];
        }
    }
    int pairs = 0, center = 0;
    for (int i = 1; i <= n; ++i) pairs += (int)reach[i].count() - 1;
    for (int x = 1; x <= n; ++x)
        if (reach[1][x] && reach[x][n]) ++center;
    long long mask1 = 0;
    for (int i = 1; i <= n; ++i)
        if (reach[1][i]) mask1 += (1LL << i);
    int code = 0;
    for (int i = 1; i <= n; ++i)
        code = (code * 97 + (int)reach[i].count()) % 100000;
    cout << pairs << " " << center << "\n";
    cout << mask1 << " " << code << "\n";
    return 0;
}

给定输入：

6 7
1 2
1 3
2 4
3 4
4 5
2 6
5 6

28. 程序把每个点到自身的可达关系也设为真，但 pairs 统计时会减去自达关系。（）{{ select(28) }}

• 对
• 错

29. 对给定输入，闭包完成后 reach[3][6] 为真。（）{{ select(29) }}

• 对
• 错

30. 若把 mask1 中的 1LL << i 改成 1 << i，当 n=60 时仍一定安全。（2分）（）{{ select(30) }}

• 对
• 错

31. 对给定输入，程序输出为（4分）{{ select(31) }}

• 14 6
  126 37780
  

• 14 5
  63 37780
  

• 15 6
  126 50308
  

• 30 6
  126 50308
  

32. 若在给定输入中再加入一条边 6 1，第一行输出会变为（4分）{{ select(32) }}

• 14 6
• 30 6
• 30 5
• 15 6

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

(1)（访问长度统计）

有 n 个点，每个点恰有一条出边 to[i]。从点 i 出发，不断沿出边移动，直到下一步将进入已经经过的点为止。记 ans[i] 为这个过程中经过的不同点数。求所有 ans[i] 的和与最大值。

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> to(n + 1), indeg(n + 1, 0), ans(n + 1, 0);
    vector<vector<int> > rev(n + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> to[i];
        rev[to[i]].push_back(i);
        ____(1)____;
    }
    queue<int> q;
    vector<int> inCycle(n + 1, 1);
    for (int i = 1; i <= n; ++i)
        if (indeg[i] == 0) q.push(i);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        inCycle[u] = 0;
        int v = to[u];
        if (____(2)____) q.push(v);
    }
    queue<int> bfs;
    for (int i = 1; i <= n; ++i) {
        if (inCycle[i] && ans[i] == 0) {
            vector<int> cyc;
            int u = i;
            do {
                cyc.push_back(u);
                u = ____(3)____;
            } while (u != i);
            int len = (int)cyc.size();
            for (int x : cyc) {
                ans[x] = ____(4)____;
                bfs.push(x);
            }
        }
    }
    while (!bfs.empty()) {
        int u = bfs.front();
        bfs.pop();
        for (int v : rev[u]) {
            if (ans[v]) continue;
            ans[v] = ____(5)____;
            bfs.push(v);
        }
    }
    long long sum = 0;
    int mx = 0;
    for (int i = 1; i <= n; ++i) {
        sum += ans[i];
        mx = max(mx, ans[i]);
    }
    cout << sum << " " << mx << "\n";
    return 0;
}

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

• ++indeg[i]
• --indeg[to[i]]
• ++indeg[to[i]]
• indeg[i] = to[i]

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

• indeg[v] == 0
• --indeg[v] == 0
• ++indeg[v] == 0
• inCycle[v] == 0

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

• to[u]
• rev[u][0]
• to[i]
• u + 1

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

• len
• 1
• ans[to[x]] + 1
• (int)rev[x].size()

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

• ans[u]
• ans[u] + 1
• ans[to[v]] - 1
• mx + 1

(2)（能量补给）

从位置 0 出发前往终点 L。初始能量为 start，每前进 1 单位距离消耗 1 点能量。途中有 n 个补给点，每个补给点有位置 pos 和补给量 gain。到达补给点后可以选择是否使用该补给，求到达终点所需使用补给的最少次数；若无法到达，输出 -1。

#include <bits/stdc++.h>
using namespace std;
struct Station {
    long long pos, gain;
};
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    long long L, start;
    cin >> n >> L >> start;
    vector<Station> a(n + 1);
    for (int i = 0; i < n; ++i) {
        cin >> a[i].pos >> a[i].gain;
    }
    a[n] = Station{L, 0};
    sort(a.begin(), a.end(), ____(6)____);
    priority_queue<long long> heap;
    long long energy = start, last = 0;
    int used = 0;
    for (int i = 0; i <= n; ++i) {
        long long dist = a[i].pos - last;
        energy -= ____(7)____;
        while (energy < 0 && !heap.empty()) {
            energy += ____(8)____;
            heap.pop();
            ++used;
        }
        if (energy < 0) {
            cout << -1 << "\n";
            return 0;
        }
        ____(9)____;
        last = a[i].pos;
    }
    cout << ____(10)____ << "\n";
    return 0;
}

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

• [](const Station& x, const Station& y) { return x.pos < y.pos; }
• [](const Station& x, const Station& y) { return x.gain > y.gain; }
• greater<Station>()
• [](const Station& x, const Station& y) { return x.pos > y.pos; }

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

• a[i].pos
• last
• dist
• a[i].gain

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

• heap.size()
• a[i].gain
• heap.top() - energy
• heap.top()

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

• heap.pop()
• heap.push(a[i].gain)
• energy += a[i].gain
• ++used

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

• used
• energy
• heap.size()
• used + (energy < 0)