该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

集训客观题

本题共有 $10$ 道单项选择题，每题 $10$ 分，共 $100$ 分。

1. BFS 中的访问标记

在无权图上用 BFS 求从起点到其它点的最短距离。为了避免同一个点被多次加入队列，通常应该在什么时候把一个点标记为已经访问？

{{ select(1) }}

• 第一次加入队列时
• 从队列中取出时
• BFS 全部结束后
• 什么时候标记都不会影响入队次数

2. 出栈顺序

有一个空栈，数字 $1,2,3,4$ 按照从小到大的顺序依次入栈。每个数字入栈后，可以选择立刻出栈，也可以先留在栈中。下面哪个序列不可能成为出栈序列？

{{ select(2) }}

• $1,2,3,4$
• $2,1,4,3$
• $3,1,2,4$
• $4,3,2,1$

3. 差分数组还原

一个长度为 $5$ 的序列 $a$ 的差分数组为

原序列 $a$ 是哪一个？

{{ select(3) }}

• $[2,-1,3,-2,1]$
• $[2,1,4,2,3]$
• $[2,1,3,1,2]$
• $[2,3,6,4,5]$

4. 前缀和计数

给定序列

它有多少个连续子段的和等于 $4$？

{{ select(4) }}

• $2$
• $3$
• $4$
• $5$

5. 排队接水

有 $4$ 位同学依次接水，接水时间分别为：

若每次只能有一位同学接水，为了让所有同学的等待时间总和最小，应该采用哪种顺序？

{{ select(5) }}

• $A,B,C,D$
• $D,B,A,C$
• $C,A,B,D$
• $B,D,C,A$

6. 区间修改后的求值

长度为 $8$ 的数组初始全为 $0$。依次进行以下区间加操作：

操作全部完成后，$a_4+a_5+a_6$ 的值是多少？

{{ select(6) }}

• $5$
• $6$
• $7$
• $8$

7. 无权图最短路

无向图有 $6$ 个点，边为：

边权都是 $1$，从点 $1$ 到点 $6$ 的最短路长度是多少？

{{ select(7) }}

• $2$
• $3$
• $4$
• $5$

8. 网格最短路

在下面的网格中，S 是起点，T 是终点，. 可以通过，# 不能通过。每一步只能向上、下、左、右相邻格子移动。

S..
.#.
..T

从 S 到 T 最少需要走多少步？

{{ select(8) }}

• $2$
• $3$
• $4$
• 无法到达

9. 活动选择

有 $5$ 个活动，时间区间分别为：

若两个活动满足前一个活动的结束时间不晚于后一个活动的开始时间，就可以同时选择。最多能选择多少个活动？

{{ select(9) }}

• $2$
• $3$
• $4$
• $5$

10. 连通块

下面是一个 $5\times 6$ 的网格，# 表示陆地，. 表示水域。两个陆地格子如果上下左右相邻，就属于同一个连通块。

##..#.
.#..#.
...##.
.#....
.#.##.

这个网格中陆地连通块的数量和最大连通块的面积分别是多少？

{{ select(10) }}

• $3,4$
• $4,4$
• $4,5$
• $5,4$