答案与解析

(1)

判断题

1. 正确 (✔)

   • 解析: 这是 KMP 算法中 pi 数组（或称 next 数组）的标准定义。pi[i] 的值被定义为模式串 p 从索引 0 到 i 的子串 p[0...i] 中，同时是其前缀和后缀的最长公共部分的长度。例如，对于 "ababa"，pi[4] 是子串 "ababa" 的最长公共前后缀 "aba" 的长度，即 3。

2. 错误 (✘)

   • 解析: 标准的 KMP 算法在 if (j == m) 的代码块中会包含一个计数器，并且通常会将 j 重置为 pi[j-1] 以便继续寻找下一个可能的匹配（包括重叠的匹配）。此程序虽然在匹配成功后正确地将 j 更新为 pi[j-1]，但它没有设置任何变量来统计匹配发生的次数。因此，它不具备计数功能。

3. 正确 (✔)

   • 解析:
     • 首先，compute_pi("aba") 计算出的 pi 数组为 {0, 0, 1}。
     • 程序开始在文本串 t ("abababa") 中匹配模式串 p ("aba")。
     • i=0,1,2: t 的 "aba" 与 p 匹配，j 变为 3。
     • j == m (3 == 3) 条件成立，程序执行 j = pi[j-1] = pi[2] = 1。
     • i=3: t[3] ('b') 与 p[j] (p[1]='b') 匹配，j 变为 2。
     • i=4: t[4] ('a') 与 p[j] (p[2]='a') 匹配，j 变为 3。
     • j == m 条件再次成立，j 再次被更新为 1。
     • i=5: t[5] ('b') 与 p[j] (p[1]='b') 匹配，j 变为 2。
     • i=6: t[6] ('a') 与 p[j] (p[2]='a') 匹配，j 变为 3。
     • j == m 条件又一次成立，j 更新为 1。
     • 循环结束，j 的最终值为 1，因此程序输出 1。

选择题

4. B. 文本串 t 的后缀能够与模式串 p 的前缀匹配的最大长度

   • 解析: 整个 for 循环可以看作一个状态机（KMP 自动机）在处理文本串 t。变量 j 代表当前状态，即已经匹配上的模式串 p 的前缀长度。当循环遍历完整个 t 后，j 的最终值就表示 t 的后缀与 p 的前缀能够匹配的最大长度。

5. D. 4

   • 解析:
     • p = "abraca", pi 数组为 {0, 0, 0, 1, 0, 1}。
     • t = "abracadabra"。
     • 当 i 从 0 遍历到 5 时, t 的前缀 "abraca" 与 p 完全匹配, j 变为 6。
     • 此时 j == m (6 == 6) 成立，j 被更新为 pi[5] = 1。
     • 继续遍历 t:
       • i=6, t[6]='d', p[1]='b'. 不匹配。j 更新为 pi[j-1]=pi[0]=0。
       • i=7, t[7]='a', p[0]='a'. 匹配。j 变为 1。
       • i=8, t[8]='b', p[1]='b'. 匹配。j 变为 2。
       • i=9, t[9]='r', p[2]='r'. 匹配。j 变为 3。
       • i=10, t[10]='a', p[3]='a'. 匹配。j 变为 4。
     • 循环结束，j 的最终值为 4。

(2)

判断题

6. 正确 (✔)

   • 解析: 该程序通过深度优先搜索（DFS），并使用 dfn (discovery time number) 和 low (low-link value) 数组来识别图中的桥，这是 Tarjan 桥边查找算法的典型实现。low[v] > dfn[u] 是判断边 (u, v) 是否为桥的核心条件。

7. 错误 (✘)

   • 解析: low[u] 被定义为从 u 出发，通过其在DFS树中的子树，能到达的节点的最小 dfn 值。low[u] 的初始值为 dfn[u]，之后它只可能通过 min 操作变得更小或保持不变。因此，恒有 low[u] <= dfn[u]。题目中的 dfn[u] <= low[u] 是错误的。

8. 正确 (✔)

   • 解析: low[v] > dfn[u] 表示从节点 v 的子树出发，无法通过返祖边到达 u 或 u 的任何祖先节点，因此 (u,v) 是桥。如果 low[v] == dfn[u]，表示从 v 的子树出发最远只能到达 u，这意味着存在一个环恰好经过边 (u,v)，所以 (u,v) 不是桥。若将条件改为 >=，就会将这种在环上的边错误地判断为桥。

选择题

9. C. 节点 u 及其在 DFS 树中的所有后代，能通过返祖边到达的节点的最小时间戳

   • 解析: 这是 low-link 值的标准定义。它综合考虑了两种情况：一是通过 u 的子节点 v 递归计算出的 low[v]；二是通过从 u 直接连接到已访问过的邻居 v 的返祖边 dfn[v]。最终 low[u] 是这些值中的最小值。

10. D. 3

    • 解析:
      • 给定的边构成了下图：1-2, 2-3, 3-1 形成一个三角形的环。节点 3 连接一个链条 3-4-5-6。
      • 在一个环内的边 (1-2, 2-3, 3-1) 都不是桥，因为移除任何一条，环内节点依然连通。
      • 边 3-4, 4-5, 5-6 是桥。移除 3-4 会使 {1,2,3} 和 {4,5,6} 断开。同理，移除 4-5 或 5-6 也会导致图断开。
      • 因此，图中共有 3 条桥。

(3)

判断题

11. 正确 (✔)

    • 解析: 函数 count_inversions 采用了分治策略。它将数组分成两半，递归地计算左右两半的逆序对数，然后在合并（merge）两个有序子数组的过程中，计算跨越两部分的逆序对数。这个结构与归并排序完全一致，只是在合并步骤中增加了计数的逻辑。

12. 正确 (✔)

    • 解析: 在竞赛题目中，若未特殊说明，输入的序列通常被假定为某个范围整数的一个排列（permutation），即不含重复元素。在此前提下，pos_a[a[i]] = i; 的作用是建立一个从数值到其在数组 a 中唯一索引的映射。说“第一次出现的位置”是正确的，因为每个元素只会出现一次。

13. 正确 (✔)

    • 解析: 如果序列 a 和 b 完全相同，那么 b[i] = a[i]。在构造数组 p 时，p[i] = pos_a[b[i]] = pos_a[a[i]]。而 pos_a[a[i]] 的值就是 i。因此，数组 p 将会是 {0, 1, 2, ..., n-1}。这是一个完全有序的序列，其逆序对数量为 0。

选择题

14. D. 计算序列 p 的逆序对数量

    • 解析: 从程序的结构看，main 函数的核心任务是构造序列 p，然后调用 count_inversions(p, 0, n - 1) 并输出其返回值。因此，程序最直接、最准确的功能描述就是计算序列 p 的逆序对数量。
    • 延伸解读: 这个问题有更深层的含义。构造出的序列 p 的逆序对数，等价于“将序列 b 变换为序列 a 所需的最少相邻交换次数”，也等于“在 a 和 b 中相对顺序不同”的数对的数量。在选项中，B 选项没有指明是“相邻”交换，这可能引起歧义（非相邻交换的最少次数是 n - 环的个数）。C 选项是正确的解释，但 D 选项是程序行为最直接的描述。在阅读程序题中，选择最直接描述程序计算行为的选项通常是最稳妥的。

15. D. 10

    • 解析:
      • n=5
      • a = {1, 2, 3, 4, 5}
      • b = {5, 4, 3, 2, 1}
      • 首先，根据 a 创建位置映射 pos_a：pos_a[1]=0, pos_a[2]=1, pos_a[3]=2, pos_a[4]=3, pos_a[5]=4。
      • 然后，根据 b 和 pos_a 构造序列 p：
        • p[0] = pos_a[b[0]] = pos_a[5] = 4
        • p[1] = pos_a[b[1]] = pos_a[4] = 3
        • p[2] = pos_a[b[2]] = pos_a[3] = 2
        • p[3] = pos_a[b[3]] = pos_a[2] = 1
        • p[4] = pos_a[b[4]] = pos_a[1] = 0
      • 所以 p = {4, 3, 2, 1, 0}。
      • 最后，计算 p 的逆序对数量。这是一个完全逆序的长度为 5 的序列。对于任何一对索引 (i, j) 且 i < j，都有 p[i] > p[j]，因此任意一对元素都构成逆序对。
      • 总逆序对数量为 C(5, 2) = 5 * (5 - 1) / 2 = 10。