下列 C++ 代码的输出结果是（　　）。

使用 cmath 或 math.h 中的数学库函数，下列说法中正确的是（　　）。

有 4 个字符，出现次数分别为 1、2、3、4。构造哈夫曼树后，出现次数为 1 的字符的哈夫曼编码长度为（　　）。

从 4 × 5 个点连接成的网格的左上角走到右下角，每次只能向右或向下移动，不同的路径共有（　　）条。

在含有 n 个结点的二叉排序树中查找一个元素，平均时间复杂度和最坏时间复杂度分别为（　　）。

有 4 堆石子，数量分别为 1、2、3、4。每次可以合并相邻两堆，合并代价为两堆石子数之和。将所有石子合并成一堆的最小总代价为（　　）。

在无权图中，使用 BFS 从起点开始遍历，并在访问由结点 u 扩展的相邻结点 v 时记录 dist[v] = dist[u] + 1，且起点的 dist 为 0，则最终 dist[v] 表示的是（　　）。

在二维网格上实现泛洪填充时，为了防止递归层数过深，最适合的非递归实现方式是（　　）。

关于哈希表，下列说法正确的是（　　）。

下列 C++ 代码的输出结果是（　　）。

用动态规划求两个序列 a1 和 a2 的最长公共子序列长度，若 dp[i][j] 表示 a1 前 i 个元素与 a2 前 j 个元素的 LCS 长度。当 a1[i-1] = a2[j-1] 时，正确的状态转移是（　　）。

下列代码是一维数组优化 0/1 背包的核心片段，执行后 dp[8] 的输出结果是（　　）。

若要求排序后相等元素的相对顺序保持不变，下列排序算法中最不适宜使用的是（　　）。

下列代码片段的时间复杂度为（　　）。

已知 int a[6] = {1, 3, 5, 7, 9, 11}; int p = a + 1;，则表达式 (p + 3) 的值是（　　）。

使用 cmath 或 math.h 中的函数，表达式 exp(0) 的结果值为 1.0，且类型为 double。

采用开放定址法处理冲突的哈希表中，删除一个元素后可以直接将该位置置空，不会影响后续查找。

在哈夫曼树中，出现次数更多的叶子结点，其深度总是更小。

在一个有向图中，所有顶点的入度之和总是等于所有顶点的出度之和。

广度优先搜索通常借助队列实现，深度优先搜索通常借助栈或递归实现。

快速排序的平均时间复杂度为 O(n log n)，最坏时间复杂度也为 O(n log n)。

为解决 0/1 背包问题，使用一维数组优化时，内层容量循环应从大到小枚举。

使用邻接表存储图时，遍历某个顶点的所有邻边所需时间与图中顶点数成正比。

在按层序从 1 开始对结点编号的完全二叉树中，编号为 i（i > 1）的结点的父结点编号为 ⌊i/2⌋。

在定义了数组 int arr[10]; 后，表达式 arr 和表达式 &arr[0] 总是等价的。

必经之路

试题名称：必经之路
时间限制：1.0 s
内存限制：512.0 MB
给定一张有 n 个结点 m 条边的有向图 G，G 中的结点依次以 1, 2, …, n 编号。第 i 条边（1 ≤ i ≤ m）从结点 uᵢ 指向结点 vᵢ。
G 中任一入度为 0 的结点可以作为合法起点，任一出度为 0 的结点可以作为合法终点。
如果 G 中所有可能的从合法起点到合法终点的路径都会经过结点 u，则称 u 是必经点。注意必经点可以为合法起点或合法终点。
请你求出 G 中所有必经点的编号。
例如，在下图中合法起点有点 1 与点 2，合法终点有点 7 与点 8。

所有合法起点到合法终点的路径为：

因此必经点有两个，编号分别为 4、5。

第一行，两个正整数 n, m，表示有向图 G 中的结点数与边数。
接下来 m 行，每行两个正整数 uᵢ, vᵢ，表示一条从结点 uᵢ 指向结点 vᵢ 的有向边。
保证 G 中至少有一个合法起点、至少有一个合法终点，且至少存在一条从一个合法起点到一个合法终点路径，同时不存在孤立点（即出度和入度都为 0 的点）。

第一行，一个整数，表示必经点的数量 k。
如果存在必经点，则第二行从小到大输出 G 中所有必经点的编号。

【输入样例 1】
<img src="/static/uploads/images/dcc0d569a62e.png" style="max-width:35%;border-radius:6px;margin:8px 0;" />
【输出样例 1】
<img src="/static/uploads/images/8d8075e1fa54.png" style="max-width:35%;border-radius:6px;margin:8px 0;" />

【输入样例 2】
<img src="/static/uploads/images/6c85d323af3e.png" style="max-width:35%;border-radius:6px;margin:8px 0;" />
【输出样例 2】
0
【数据范围】
对于 40% 的测试点，保证 1 ≤ n ≤ 100，1 ≤ m ≤ 200。
对于所有测试点，保证 1 ≤ n ≤ 1000，1 ≤ m ≤ 2000。保证 G 中至少有一个合法起点、至少有一个合法终点，且至少存在一条从一个合法起点到一个合法终点路径，同时不存在孤立点（即出度和入度都为 0 的点）。

括号序列

试题名称：括号序列
时间限制：1.0 s
内存限制：512.0 MB
对于字符串 S 与 T，如果从 S 中删除任意多个字符可以得到 T，那么 T 是 S 的子序列。换言之，T 是选取 S 中的若干字符按下标顺序连接而成的。两个子序列不同当且仅当选取的下标不同。
例如 sun 是 sequence 的子序列，因为从 sequence 中删除 eq、e 和 ce 可以得到 sun；sequence 有 2⁸ 个不同的子序列，其中有空字符串，也有三个不同的子序列 e，因为 sequence 的第 2、5、8 个字符都为 e，分别保留这三个字符得到的子序列是不同的。
对于字符串 S，如果 S 满足以下条件那么 S 是合法括号序列：
S 是空字符串，或者
S 可由（、合法括号序列、）三者连接得到，或者
S 可由两个合法括号序列连接得到。
例如 ()、(())、(()()) 都是合法括号序列。但是 ()）、（ 不是合法括号序列。
给定一个长度为 n 的仅包含（与）的字符串 S。请你求出 S 所有 2ⁿ 个子序列中有多少个合法括号序列。由于答案可能很大，请你输出答案对 10⁹ 取模的结果。
例如，S 为 ))()(( 时共有 3 个子序列是合法括号序列，分别为空字符串与两个不同的子序列 ()。
对于 40% 的测试点，保证 1 ≤ n ≤ 400。
对于所有测试点，保证 1 ≤ n ≤ 2000。

第一行，一个正整数 n，表示字符串 S 的长度。
第二行，长度为 n 的仅包含（与）的字符串 S。

输出一行，一个整数，表示 S 的合法括号子序列的数量对 10⁹ 取模的结果。

【输入样例 1】
<img src="/static/uploads/images/20e44b2c3344.png" style="max-width:35%;border-radius:6px;margin:8px 0;" />
【输出样例 1】
3
【输入样例 2】
<img src="/static/uploads/images/76feb9d6f596.png" style="max-width:35%;border-radius:6px;margin:8px 0;" />
【输出样例 2】
333666220
【数据范围】
对于 40% 的测试点，保证 1 ≤ n ≤ 400。
对于所有测试点，保证 1 ≤ n ≤ 2000。