阅读程序专项训练

(1)

01 #include <iostream>
02 #include <vector>
03 #include <string>
04 #include <numeric>
05
06 using namespace std;
07
08 // 计算 KMP 算法中的 next 数组 (或 pi 数组)
09 vector<int> compute_pi(const string& p) {
10     int m = p.length();
11     vector<int> pi(m);
12     for (int i = 1, j = 0; i < m; i++) {
13         while (j > 0 && p[i] != p[j]) {
14             j = pi[j - 1];
15         }
16         if (p[i] == p[j]) {
17             j++;
18         }
19         pi[i] = j;
20     }
21     return pi;
22 }
23
24 // 主函数
25 int main() {
26     ios_base::sync_with_stdio(false);
27     cin.tie(NULL);
28     string t, p;
29     cin >> t >> p;
30
31     vector<int> pi = compute_pi(p);
32     int n = t.length();
33     int m = p.length();
34     int j = 0; // p 的指针
35
36     for (int i = 0; i < n; i++) {
37         while (j > 0 && t[i] != p[j]) {
38             j = pi[j - 1];
39         }
40         if (t[i] == p[j]) {
41             j++;
42         }
43         if (j == m) {
44             // 匹配成功后，不是重置 j=0，而是继续利用 pi 数组
45             j = pi[j - 1];
46         }
47     }
48
49     cout << j << endl;
50
51     return 0;
52 }

判断题

1. compute_pi 函数计算的 pi[i] 值等于字符串 p 的子串 p[0...i] 的最长公共前缀和后缀的长度。 ( )
2. 该程序的功能是统计模式串 p 在文本串 t 中出现的次数。 ( )
3. 若输入文本串 t 为 "abababa"，模式串 p 为 "aba"，则程序输出为 1。 ( )

选择题

4. 该程序最后输出的整数 j 的含义是 ( )。

   • A. 模式串 p 在文本串 t 中最后一次出现的位置
   • B. 文本串 t 的后缀能够与模式串 p 的前缀匹配的最大长度
   • C. 模式串 p 在文本串 t 中出现的总次数
   • D. 文本串 t 的前缀能够与模式串 p 的后缀匹配的最大长度

5. 若输入文本串 t 为 "abracadabra"，模式串 p 为 "abraca"，则程序输出为 ( )。

   • A. 0
   • B. 1
   • C. 3
   • D. 4

(2)

01 #include <iostream>
02 #include <vector>
03 #include <numeric>
04 #include <algorithm>
05
06 using namespace std;
07
08 int n;
09 vector<vector<int>> adj;
10 vector<int> dfn, low;
11 vector<pair<int, int>> bridges;
12 int timer;
13
14 void find_bridges(int u, int parent) {
15     dfn[u] = low[u] = ++timer;
16
17     for (int v : adj[u]) {
18         if (v == parent) {
19             continue;
20         }
21         if (dfn[v] != 0) { // v has been visited
22             low[u] = min(low[u], dfn[v]);
23         } else { // v has not been visited
24             find_bridges(v, u);
25             low[u] = min(low[u], low[v]);
26             if (low[v] > dfn[u]) {
27                 bridges.push_back({min(u, v), max(u, v)});
28             }
29         }
30     }
31 }
32
33 int main() {
34     cin >> n;
35     int m; // number of edges
36     cin >> m;
37     adj.resize(n + 1);
38     dfn.assign(n + 1, 0);
39     low.assign(n + 1, 0);
40     timer = 0;
41
42     for (int i = 0; i < m; ++i) {
43         int u, v;
44         cin >> u >> v;
45         adj[u].push_back(v);
46         adj[v].push_back(u);
47     }
48
49     for (int i = 1; i <= n; ++i) {
50         if (dfn[i] == 0) {
51             find_bridges(i, -1);
52         }
53     }
54
55     cout << bridges.size() << endl;
56
57     return 0;
58 }

判断题

6. 该程序使用了 Tarjan 算法来寻找图中的“桥”（或称“割边”）。 ( )
7. 对于任意节点 u，dfn[u] 的值一定小于等于 low[u] 的值。 ( )
8. 如果将第 26 行的判断条件 low[v] > dfn[u] 改为 low[v] >= dfn[u]，程序将可能把一些非“桥”的边也识别为“桥”。 ( )

选择题

9. low[u] 值的确切含义是 ( )。

   • A. 节点 u 所在强连通分量的最小时间戳
   • B. 从节点 u 出发能到达的所有邻居节点的最小时间戳
   • C. 节点 u 及其在 DFS 树中的所有后代，能通过返祖边到达的节点的最小时间戳
   • D. 节点 u 在 DFS 树中的父节点的时间戳

10. 假设输入 n=6, m=6，边的连接为 1-2, 2-3, 3-1, 3-4, 4-5, 5-6。则程序的输出为 ( )。

    • A. 0
    • B. 1
    • C. 2
    • D. 3

(3)

01 #include <iostream>
02 #include <vector>
03 #include <cmath>
04 #include <algorithm>
05
06 using namespace std;
07
08 long long count_inversions(vector<int>& arr, int l, int r) {
09     if (l >= r) return 0;
10     int mid = l + (r - l) / 2;
11     long long inv_count = count_inversions(arr, l, mid) + count_inversions(arr, mid + 1, r);
12
13     vector<int> temp;
14     int i = l, j = mid + 1;
15
16     while (i <= mid && j <= r) {
17         if (arr[i] <= arr[j]) {
18             temp.push_back(arr[i++]);
19         } else {
20             temp.push_back(arr[j++]);
21             inv_count += (mid - i + 1);
22         }
23     }
24     while (i <= mid) temp.push_back(arr[i++]);
25     while (j <= r) temp.push_back(arr[j++]);
26
27     for (int k = l; k <= r; ++k) {
28         arr[k] = temp[k - l];
29     }
30
31     return inv_count;
32 }
33
34 int main() {
35     int n;
36     cin >> n;
37     vector<int> a(n), b(n), pos_a(n + 1);
38     for (int i = 0; i < n; ++i) { cin >> a[i]; pos_a[a[i]] = i; }
39     for (int i = 0; i < n; ++i) cin >> b[i];
40
41     vector<int> p(n);
42     for (int i = 0; i < n; ++i) {
43         p[i] = pos_a[b[i]];
44     }
45
46     cout << count_inversions(p, 0, n - 1) << endl;
47
48     return 0;
49 }

判断题

11. count_inversions 函数是一个基于分治思想的归并排序算法的变体。 ( )
12. 第 38 行代码 pos_a[a[i]] = i; 的作用是记录数组 a 中每个元素第一次出现的位置。 ( )
13. 如果两个输入序列 a 和 b 完全相同，则程序的输出必然为 0。 ( )

选择题

14. 该程序最终解决的问题是 ( )。

    • A. 计算两个序列的最长公共子序列长度
    • B. 计算将序列 b 变换为序列 a 所需的最小交换次数
    • C. 计算两个序列中有多少个数字在 a 中的相对顺序与在 b 中的相对顺序不同
    • D. 计算序列 p 的逆序对数量

15. 若输入 n=5，序列 a 为 1 2 3 4 5，序列 b 为 5 4 3 2 1，则程序的输出是 ( )。

    • A. 0
    • B. 4
    • C. 5
    • D. 10