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

一、单项选择题

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

1、在Linux系统终端中，用于修改文件权限的命令通常是（）。

{{ select(1) }}

• grep
• chmod
• pwd
• echo

2、下列C++表达式的值为（）。

(13 & 10) | (12 ^ 5)

{{ select(2) }}

• 1
• 8
• 9
• 13

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

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

{{ select(3) }}

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

4、若快速排序每次总是选择当前区间的第一个元素作为基准，在输入序列已经升序排列时，其最坏时间复杂度为（）。

{{ select(4) }}

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

5、有4个不同元素依次进栈，允许进栈和出栈操作任意交替进行，则可能的出栈序列共有（）种。

{{ select(5) }}

• 12
• 14
• 16
• 24

6、根结点深度为1，一棵深度为5的满二叉树共有（）个结点。

{{ select(6) }}

• 16
• 31
• 32
• 63

7、一个有7个顶点的有向无环图，最多可以有（）条边。

{{ select(7) }}

• 14
• 20
• 21
• 42

8、7在模26意义下的乘法逆元为（）。

{{ select(8) }}

• 3
• 7
• 11
• 15

9、字符串ABCBDAB和BDCABA的最长公共子序列长度为（）。

{{ select(9) }}

• 2
• 3
• 4
• 5

10、有4个顶点1, 2, 3, 4，有向边为1 → 3, 2 → 3, 2 → 4，则该图共有（）种拓扑排序。

{{ select(10) }}

• 2
• 3
• 4
• 5

11、在一个连通无向带权图中，如果某条边是某个环上权值唯一最大的边，则这条边（）。

{{ select(11) }}

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

12、连续掷两次公平六面骰，点数之和为7的概率为（）。

{{ select(12) }}

• $\frac{1}{6}$
• $\frac{1}{7}$
• $\frac{5}{36}$
• $\frac{7}{36}$

13、有4个物品，重量分别为2, 3, 4, 5，价值分别为3, 4, 5, 8。背包容量为7，每个物品最多选一次，最大总价值为（）。

{{ select(13) }}

• 8
• 9
• 11
• 12

14、一棵有根树中，每个非叶结点恰好有3个儿子。如果这棵树共有40个结点，则叶结点共有（）个。

{{ select(14) }}

• 13
• 26
• 27
• 30

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

{{ select(15) }}

• $O(n)$
• $O(n^{\log_2 3})$
• $O(n \log n)$
• $O(n^2)$

---

二、程序阅读题

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

第1题

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

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

判断题

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

{{ select(16) }}

• 正确
• 错误

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

{{ select(17) }}

• 正确
• 错误

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

{{ select(18) }}

• 正确
• 错误

单项选择题

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

{{ select(19) }}

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

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

{{ select(20) }}

• 1
• 2
• 3
• 4

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

{{ select(21) }}

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

---

第2题

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

int n, m;
bool e[12][12];
long long dp[1 << 12][12];

int main() {
    cin >> n >> m;
    
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        u--, v--;
        e[u][v] = e[v][u] = true;
    }
    
    dp[1][0] = 1;
    
    for (int s = 1; s < (1 << n); s++) {
        for (int u = 0; u < n; u++) {
            if (!dp[s][u])
                continue;
            
            for (int v = 0; v < n; v++) {
                if (!(s >> v & 1) && e[u][v])
                    dp[s | (1 << v)][v] += dp[s][u];
            }
        }
    }
    
    long long ans = 0;
    
    for (int i = 0; i < n; i++)
        ans += dp[(1 << n) - 1][i];
    
    cout << ans << endl;
    return 0;
}

假设 $1 \le n \le 12$，输入图为无向简单图。

判断题

22、程序统计的路径都从编号为1的顶点开始。（）

{{ select(22) }}

• 正确
• 错误

23、当输入图为4个点的完全图时，程序输出6。（）

{{ select(23) }}

• 正确
• 错误

24、程序统计的是从1号点出发的所有简单路径数量。（）

{{ select(24) }}

• 正确
• 错误

单项选择题

25、当输入为：

4 3
1 2
2 3
3 4

程序输出为（）。

{{ select(25) }}

• 1
• 2
• 3
• 6

26、当输入为：

4 4
1 2
2 3
3 4
4 1

程序输出为（）。

{{ select(26) }}

• 1
• 2
• 4
• 6

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

{{ select(27) }}

• $\Theta(2^n)$
• $\Theta(n \cdot 2^n)$
• $\Theta(n^2 \cdot 2^n)$
• $\Theta(n!)$

---

第3题

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

const int N = 55;
const int INF = 1000000000;

int d[N][N];

int main() {
    int n, m;
    cin >> n >> m;
    
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            d[i][j] = (i == j ? 0 : INF);
    
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        d[u][v] = d[v][u] = min(d[u][v], w);
    }
    
    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                if (d[i][k] + d[k][j] < d[i][j])
                    d[i][j] = d[i][k] + d[k][j];
    
    int mx = 0, cnt = 0;
    
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (d[i][j] < INF) {
                mx = max(mx, d[i][j]);
                cnt++;
            }
    
    cout << mx << " " << cnt << endl;
    return 0;
}

假设边权均为非负整数，且最短路长度不会超过INF。

判断题

28、如果输入中存在重边，程序会保留两点之间边权最小的一条边。（）

{{ select(28) }}

• 正确
• 错误

29、如果图不连通，程序一定输出-1。（）

{{ select(29) }}

• 正确
• 错误

30、变量cnt统计的有序点对中包含$(i, i)$这种点对。（）

{{ select(30) }}

• 正确
• 错误

单项选择题

31、当输入为：

4 3
1 2 3
2 3 4
1 3 10

程序输出为（）。

{{ select(31) }}

• 7 9
• 7 10
• 10 9
• 10 10

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

{{ select(32) }}

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

33、该程序实际求解的是（）。

{{ select(33) }}

• 有向图的单源最短路
• 无向图的所有点对最短路
• 最小生成树
• 拓扑排序

---

三、完善程序题

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

第1题：区间最大值查询

给定一个长度为 $n$ 的整数序列 $a_1, a_2, \ldots, a_n$，有 $q$ 次询问。每次询问给定 $l, r$，求区间 $[l, r]$ 中的最大值。

下面程序使用ST表解决该问题，试补全程序。

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

const int N = 100005;
const int K = 20;

int n, q;
int a[N], lg[N], st[K][N];

int main() {
    cin >> n >> q;
    
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    
    for (int i = 2; i <= n; i++)
        lg[i] = ①;
    
    for (int i = 1; i <= n; i++)
        st[0][i] = a[i];
    
    for (int j = 1; ② <= n; j++) {
        for (int i = 1; i + (1 << j) - 1 <= n; i++) {
            st[j][i] = max(st[j - 1][i], ③);
        }
    }
    
    while (q--) {
        int l, r;
        cin >> l >> r;
        
        int k = ④;
        
        cout << ⑤ << endl;
    }
    
    return 0;
}

34、①处应填（）。

{{ select(34) }}

• lg[i >> 1] + 1
• lg[i - 1] + 1
• lg[i] + 1
• lg[i << 1] + 1

35、②处应填（）。

{{ select(35) }}

• j
• (1 << j)
• (1 << (j - 1))
• n - j

36、③处应填（）。

{{ select(36) }}

• st[j][i + (1 << j)]
• st[j - 1][i + (1 << j)]
• st[j - 1][i + (1 << (j - 1))]
• st[j][i + (1 << (j - 1))]

37、④处应填（）。

{{ select(37) }}

• lg[r - l + 1]
• lg[r + l + 1]
• lg[r - l]
• lg[n]

38、⑤处应填（）。

{{ select(38) }}

• max(st[k][l], st[k][r])
• st[k][l] + st[k][r - (1 << k) + 1]
• min(st[k][l], st[k][r - (1 << k) + 1])
• max(st[k][l], st[k][r - (1 << k) + 1])

---

第2题：01边权最短路

给定一个 $n$ 个点、$m$ 条边的有向图，每条边的边权只可能是0或1。求从 $s$ 到 $t$ 的最短路长度。如果不可达，输出 $-1$。

下面程序使用0-1BFS解决该问题，试补全程序。

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

const int N = 100005;
const int INF = 1000000000;

int n, m, s, t;
int d[N], vis[N];
vector<pair<int, int>> g[N];

int main() {
    cin >> n >> m >> s >> t;
    
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        ①;
    }
    
    for (int i = 1; i <= n; i++)
        d[i] = INF;
    
    deque<int> q;
    d[s] = 0;
    q.push_front(s);
    
    while (!q.empty()) {
        int u = q.front();
        q.pop_front();
        
        if (vis[u])
            continue;
        
        vis[u] = 1;
        
        for (auto e : g[u]) {
            int v = e.first;
            int w = e.second;
            
            if (② < d[v]) {
                d[v] = ②;
                
                if (w == 0)
                    ③;
                else
                    ④;
            }
        }
    }
    
    cout << ⑤ << endl;
    return 0;
}

39、①处应填（）。

{{ select(39) }}

• g[u].push_back({v, w})
• g[v].push_back({u, w})
• g[u].push_back({w, v})
• g[w].push_back({u, v})

40、②处应填（）。

{{ select(40) }}

• d[v] + w
• d[u]
• d[u] + w
• w

41、③处应填（）。

{{ select(41) }}

• q.push_front(v)
• q.push_back(v)
• q.pop_front()
• q.pop_back()

42、④处应填（）。

{{ select(42) }}

• q.push_front(v)
• q.push_back(v)
• q.pop_front()
• q.pop_back()

43、⑤处应填（）。

{{ select(43) }}

• d[s]
• d[t]
• INF
• (d[t] == INF ? -1 : d[t])