单项选择题15题（每题2分），阅读程序18题（共40分），完善程序10题（每题3分），共100分

一、单项选择题

共15题，每题2分，共计30分。每题有且仅有一个正确选项。

1、在Linux系统终端中，用于在文件中查找包含指定字符串的行的命令通常是（）。

{{ select(1) }}

• grep
• mkdir
• chmod
• pwd

2、若一个32位无符号整数 $x = \text{0x12345678}$ 存储在小端序机器中，则最低地址处存放的字节是（）。

{{ select(2) }}

• 0x12
• 0x34
• 0x56
• 0x78

3、对于如下代码段，其时间复杂度为（）。

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

{{ select(3) }}

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

4、一个初始为空的小根堆依次插入 9, 4, 7, 1, 6, 3，然后连续删除两次堆顶，此时堆顶元素为（）。

{{ select(4) }}

• 3
• 4
• 6
• 7

5、下列图中一定是二分图的是（）。

{{ select(5) }}

• 完全图
• 奇环
• 树
• 含有三角形的图

6、已知一棵二叉树的前序遍历为 A B D E C F，中序遍历为 D B E A F C，则其后序遍历为（）。

{{ select(6) }}

• D E B F C A
• D B E F C A
• D E B C F A
• A B D E C F

7、将5个互不相同的球放入3个互不相同的盒子中，允许盒子为空，共有（）种放法。

{{ select(7) }}

• 15
• 60
• 125
• 243

8、$3^{10} \mod 13$ 的值为（）。

{{ select(8) }}

• 1
• 3
• 9
• 12

9、若一张有向图存在负权边，但不存在负权环，要求单源最短路，通常可以使用（）。

{{ select(9) }}

• Dijkstra算法
• Bellman-Ford算法
• Prim算法
• Kruskal算法

10、将字符串 cat, car, cart, dog, do 插入一棵初始为空的Trie树中，若根结点也计入结点数，则共有（）个结点。

{{ select(10) }}

• 8
• 9
• 10
• 11

11、在一个连通无向带权图中，若一条边是所有横跨某个割的边中权值唯一最小的边，则这条边（）。

{{ select(11) }}

• 一定不在任何最小生成树中
• 一定在所有最小生成树中
• 可能在某棵最小生成树中，也可能不在
• 只有图是完全图时才在最小生成树中

12、有6个任务，每个任务处理时间均为1，且依赖关系为 1→3, 2→3, 3→5, 4→5, 5→6。若每一时刻只能执行一个任务，则最早完成任务6的时间为（）。

{{ select(12) }}

• 4
• 5
• 6
• 7

13、已知逻辑表达式：

bool x = true, y = false, z = true;
bool r = x && y || !y && z;

则 $r$ 的值为（）。

{{ select(13) }}

• true
• false
• 与 $x$ 无关且为 false
• 无法确定

14、连续掷两次公平六面骰，第一次点数为 $x$，第二次点数为 $y$。若 $x < y$，得1分，否则得0分。期望得分为（）。

{{ select(14) }}

• $\dfrac{5}{12}$
• $\dfrac{1}{2}$
• $\dfrac{7}{12}$
• $\dfrac{1}{3}$

15、递归式 $T(n) = T(n/2) + O(n)$ 对应的时间复杂度为（）。

{{ select(15) }}

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

二、程序阅读题

共3题，判断题正确填√，错误填×。

特殊分值说明：

• 第16~18题（判断题）每题2分
• 第19题、第25题（选择题）每题2分
• 其余判断题每题1.5分，其余选择题每题3分

阅读程序（一）

#include <bits/stdc++.h>
using namespace std;
int main() {
    string s;
    cin >> s;
    int n = s.size();
    
    vector<int> z(n);
    int l = 0, r = 0;
    for (int i = 1; i < n; i++) {
        if (i <= r)
            z[i] = min(r - i + 1, z[i - l]);
        
        while (i + z[i] < n && s[z[i]] == s[i + z[i]])
            z[i]++;
        
        if (i + z[i] - 1 > r) {
            l = i;
            r = i + z[i] - 1;
        }
    }
    
    int mx = 0, sum = 0;
    for (int i = 0; i < n; i++) {
        mx = max(mx, z[i]);
        sum += z[i];
    }
    
    cout << mx << " " << sum << endl;
    return 0;
}

假设输入字符串长度不超过 $10^5$，且只包含小写英文字母。

判断题

16、对任意合法输入，$z_0$ 的值始终为0。（）

{{ select(16) }}

• 正确
• 错误

17、若输入字符串中所有字符两两不同，则程序一定输出 0 0。（）

{{ select(17) }}

• 正确
• 错误

18、当输入为 aaaa 时，程序输出为 3 6。（）

{{ select(18) }}

• 正确
• 错误

单项选择题

19、当输入为 ababa 时，程序输出为（）。

{{ select(19) }}

• 1 1
• 2 3
• 3 4
• 4 6

20、当输入为 abcabca 时，$z_3$ 的值为（）。

{{ select(20) }}

• 0
• 1
• 3
• 4

21、该程序的时间复杂度为（）。

{{ select(21) }}

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

阅读程序（二）

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct Mat {
    ll a[2][2];
};

Mat mul(Mat x, Mat y) {
    Mat z;
    memset(z.a, 0, sizeof z.a);
    
    for (int i = 0; i < 2; i++)
        for (int k = 0; k < 2; k++)
            for (int j = 0; j < 2; j++)
                z.a[i][j] += x.a[i][k] * y.a[k][j];
    
    return z;
}

ll sol(ll n) {
    if (n == 0)
        return 0;
    
    Mat r = {1, 0, 0, 1};
    Mat b = {1, 1, 1, 0};
    
    n--;
    
    while (n) {
        if (n & 1)
            r = mul(r, b);
        
        b = mul(b, b);
        n >>= 1;
    }
    
    return r.a[0][0];
}

int main() {
    ll n;
    cin >> n;
    cout << sol(n) << endl;
    return 0;
}

假设输入的 $n$ 是非负整数，且所有计算均不会溢出。

判断题

22、当输入为0时，程序输出0。（）

{{ select(22) }}

• 正确
• 错误

23、当输入为1时，程序输出1。（）

{{ select(23) }}

• 正确
• 错误

24、若删除 if (n & 1)，让 r = mul(r, b); 每轮都执行，程序仍一定正确。（）

{{ select(24) }}

• 正确
• 错误

单项选择题

25、当输入为6时，程序输出为（）。

{{ select(25) }}

• 5
• 8
• 13
• 21

26、函数 sol(n) 的时间复杂度为（）。

{{ select(26) }}

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

27、对 $n \geq 1$，该程序输出的是（）。

{{ select(27) }}

• 第 $n$ 个斐波那契数，其中 $F_1 = 1, F_2 = 1$
• 第 $n+1$ 个斐波那契数，其中 $F_1 = 1, F_2 = 1$
• $2^n$
• $n^2$

阅读程序（三）

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 100005;

ll tr[N << 2], lz[N << 2];

void add(int o, int l, int r, int L, int R, ll v) {
    if (L <= l && r <= R) {
        tr[o] += v;
        lz[o] += v;
        return;
    }
    
    int m = (l + r) >> 1;
    
    if (L <= m)
        add(o << 1, l, m, L, R, v);
    
    if (R > m)
        add(o << 1 | 1, m + 1, r, L, R, v);
    
    tr[o] = max(tr[o << 1], tr[o << 1 | 1]) + lz[o];
}

ll qry(int o, int l, int r, int p) {
    if (l == r)
        return tr[o];
    
    int m = (l + r) >> 1;
    
    if (p <= m)
        return lz[o] + qry(o << 1, l, m, p);
    else
        return lz[o] + qry(o << 1 | 1, m + 1, r, p);
}

int main() {
    int n, q;
    cin >> n >> q;
    
    while (q--) {
        int op;
        cin >> op;
        
        if (op == 1) {
            int l, r;
            ll v;
            cin >> l >> r >> v;
            add(1, 1, n, l, r, v);
        } else {
            int p;
            cin >> p;
            cout << qry(1, 1, n, p) << endl;
        }
    }
    
    return 0;
}

假设输入合法，且所有操作的区间端点都在1到 $n$ 之间。

判断题

28、该程序支持区间加法和单点查询。（）

{{ select(28) }}

• 正确
• 错误

29、在任意时刻，tr[1] 表示整个序列的最大值。（）

{{ select(29) }}

• 正确
• 错误

30、若把 qry 函数中的 lz[o] + 都删去，程序对所有输入仍一定正确。（）

{{ select(30) }}

• 正确
• 错误

单项选择题

31、当输入为：

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

程序输出为（）。

{{ select(31) }}

• 2 5
• 3 6
• 3 8
• 1 6

32、若依次执行：

1 1 5 2
1 3 4 7

则此时 tr[1] 的值为（）。

{{ select(32) }}

• 2
• 7
• 9
• 11

33、每次操作的时间复杂度为（）。

{{ select(33) }}

• $\Theta(1)$
• $\Theta(\log n)$
• $\Theta(n)$
• $\Theta(n \log n)$

三、完善程序题

共2题，每空3分，共计30分。

完善程序（一）：长度受限最大子段和

给定一个长度为 $n$ 的整数序列 $a_1, a_2, \ldots, a_n$，以及两个整数 $L, R$。求所有长度在 $[L, R]$ 之间的连续子段的最大子段和。

试补全程序。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int N = 200005;
const ll INF = (1LL << 60);

int n, L, R;
ll s[N];
int q[N];

int main() {
    cin >> n >> L >> R;
    
    for (int i = 1; i <= n; i++) {
        ll x;
        cin >> x;
        ① ;
    }
    
    int h = 1, t = 0;
    ll ans = -INF;
    
    for (int i = L; i <= n; i++) {
        int x = i - L;
        
        while (h <= t && ② )
            t--;
        
        ③ ;
        
        while (h <= t && ④ )
            h++;
        
        ans = max(ans, ⑤ );
    }
    
    cout << ans << endl;
    return 0;
}

34、① 处应填（）。

{{ select(34) }}

• s[i] = x
• s[i] = s[i - 1] + x
• s[i] = s[i + 1] + x
• s[i] += x

35、② 处应填（）。

{{ select(35) }}

• s[q[t]] >= s[x]
• s[q[t]] <= s[x]
• q[t] >= x
• q[t] <= x

36、③ 处应填（）。

{{ select(36) }}

• q[++t] = x
• q[++h] = x
• q[t++] = x
• q[h++] = x

37、④ 处应填（）。

{{ select(37) }}

• q[h] < i - R
• q[h] > i - R
• q[h] < i - L
• q[h] > i - L

38、⑤ 处应填（）。

{{ select(38) }}

• s[q[h]] - s[i]
• s[i] + s[q[h]]
• s[i] - s[q[h]]
• s[q[t]] - s[i]

完善程序（二）：删边后的连通块

给定一个 $n$ 个点、$m$ 条边的无向图，接下来按顺序删除 $q$ 条边。对于每一次删除操作，输出删除后图中的连通块个数。

下面的程序采用离线倒序加边的方法解决该问题，试补全程序。

#include <bits/stdc++.h>
using namespace std;

const int N = 200005;

int n, m, q, cc;
int fa[N], u[N], v[N], de[N], vis[N], ans[N];

int fd(int x) {
    if (fa[x] == x)
        return x;
    return ① ;
}

void mg(int x, int y) {
    x = fd(x);
    y = fd(y);
    
    if ( ② ) {
        fa[x] = y;
        cc--;
    }
}

int main() {
    cin >> n >> m >> q;
    
    for (int i = 1; i <= m; i++)
        cin >> u[i] >> v[i];
    
    for (int i = 1; i <= q; i++) {
        cin >> de[i];
        ③ ;
    }
    
    for (int i = 1; i <= n; i++)
        fa[i] = i;
    
    cc = n;
    
    for (int i = 1; i <= m; i++)
        if ( ④ )
            mg(u[i], v[i]);
    
    ans[q] = cc;
    
    for (int i = q; i >= 1; i--) {
        mg(u[de[i]], v[de[i]]);
        ans[i - 1] = cc;
    }
    
    for (int i = 1; i <= q; i++)
        cout << ⑤ << endl;
    
    return 0;
}

39、① 处应填（）。

{{ select(39) }}

• fa[x] = fd(fa[x])
• fd(x)
• fa[fd(x)]
• x

40、② 处应填（）。

{{ select(40) }}

• x == y
• x != y
• fa[x] == y
• cc == 1

41、③ 处应填（）。

{{ select(41) }}

• vis[de[i]] = 1
• vis[i] = 1
• de[vis[i]] = 1
• vis[u[i]] = 1

42、④ 处应填（）。

{{ select(42) }}

• vis[i]
• !vis[i]
• i <= q
• fd(u[i]) == fd(v[i])

43、⑤ 处应填（）。

{{ select(43) }}

• ans[i]
• ans[i - 1]
• ans[q]
• cc