CSP-J 卷

DFS 是深度优先算法的英文简写。

在宽度优先搜索中，通常使用队列来辅助实现。

在深度优先搜索中，通常使用队列来辅助实现。

在非递归实现的树的广度优先搜索中，通常使用栈来辅助实现。

阅读以下二叉树的广度优先搜索代码：

01#include <iostream>
02#include <queue>
03
04using namespace std;
05
06// 二叉树节点的定义
07struct TreeNode {
08    int val;
09    TreeNode* left;
10    TreeNode* right;
11    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
12};
13
14// 宽度优先搜索 (BFS) 迭代实现
15TreeNode* bfs(TreeNode* root, int a) {
16    if (root == nullptr) return nullptr;
17
18    queue<TreeNode*> q;
19    q.push(root);
20
21    while (!q.empty()) {
22        TreeNode* node = q.front();
23        q.pop();
24
25        if (node->val == a)
26            return node;
27
28        cout << node->val << " "; // 先访问当前节点
29
30        if (node->left) q.push(node->left); // 将左子节点入队
31        if (node->right) q.push(node->right); // 将右子节点入队
32    }
33    return nullptr;
34}

使用以上算法，在以下这棵树搜索数值 20 时，可能的输出是（ ）。

阅读以下二叉树的深度优先搜索代码：

01#include <iostream>
02#include <stack>
03
04using namespace std;
05
06// 非递归深度优先搜索 (DFS)
07TreeNode* dfs(TreeNode* root, int a) {
08    if (root == nullptr) return nullptr;
09
10    stack<TreeNode*> stk;
11    stk.push(root);
12
13    while (!stk.empty()) {
14        TreeNode* node = stk.top();
15        stk.pop();
16        if (node->val == a)
17            return node;
18
19        cout << node->val << " "; // 访问当前节点
20
21        if (node->right) stk.push(node->right); // 先压入右子节点
22        if (node->left) stk.push(node->left); // 再压入左子节点
23    }
24    return nullptr;
25}

使用以上算法，在二叉树搜索数值 20 时，可能的输出是（ ）。

阅读以下二叉树的深度优先搜索算法，横线上应填写（）。

01void dfs(TreeNode* root) {
02    if (root == nullptr)
03        return;
04
05    stack<TreeNode*> s;
06    s.push(root);
07    while (!s.empty()) {
08        ____________ // 在此处填入代码
09        cout << node->value << " ";
10
11        if (node->right) s.push(node->right);
12        if (node->left) s.push(node->left);
13    }
14}

阅读以下二叉树的广度优先搜索的代码，横线上应填写（）。

01#include <queue>
02void bfs(TreeNode* root) {
03    if (root == NULL) return;
04
05    queue<TreeNode*> q;
06    q.push(root);
07    while (!q.empty()) {
08        ____________ // 在此处填入代码
09        cout << node->val << " ";
10        if (node->left) {
11            q.push(node->left);
12        }
13        if (node->right) {
14            q.push(node->right);
15        }
16    }
17}

使用宽度优先搜索（BFS）遍历以下这棵树，可能的输出是（ ）。

    1
   / \
  2   3
 / \   \
8   9   6
   / \   \
  4   5   7

请将下面 C++ 实现的深度优先搜索（DFS）代码补充完整，横线处应填入（）。

01struct TreeNode {
02    int val;
03    TreeNode* left;
04    TreeNode* right;
05    TreeNode(int x): val(x), left(nullptr), right(nullptr) {}
06};
07
08void dfs(TreeNode* root, vector<int>& result) {
09    if (root == nullptr) return;
10
11    ____________
12}

给定一个二叉树，返回每一层中最大的节点值，结果以数组形式返回，横线处应填入（）。

01#include <vector>
02#include <queue>
03#include <algorithm>
04
05struct TreeNode {
06    int val;
07    TreeNode* left;
08    TreeNode* right;
09    TreeNode(int x): val(x), left(nullptr), right(nullptr) {}
10};
11
12vector<int> largestValues(TreeNode* root) {
13    vector<int> result;
14    if (!root) return result;
15
16    queue<TreeNode*> q;
17    q.push(root);
18
19    while (!q.empty()) {
20        int sz = q.size();
21        int maxVal = INT_MIN;
22        for (int i = 0; i < sz; ++i) {
23            TreeNode* node;
24            ____________
25            maxVal = max(maxVal, node->val);
26            if (node->left) q.push(node->left);
27            if (node->right) q.push(node->right);
28        }
29        result.push_back(maxVal);
30    }
31
32    return result;
33}

令 $n$ 是树的节点数，下面代码实现了树的广度优先遍历，其时间复杂度是（）。

01void bfs(TreeNode* root) {
02    if (!root) return;
03    queue<TreeNode*> q;
04    q.push(root);
05    while (!q.empty()) {
06        TreeNode* node = q.front();
07        q.pop();
08        cout << node->val << " ";
09        if (node->left) q.push(node->left);
10        if (node->right) q.push(node->right);
11    }
12}

下列代码实现了树的深度优先遍历，则横线处应填入（）。

01struct TreeNode {
02    int val;
03    TreeNode* left;
04    TreeNode* right;
05    TreeNode(int x): val(x), left(nullptr), right(nullptr) {}
06};
07
08void dfs(TreeNode* root) {
09    if (!root) return;
10    stack<TreeNode*> st;
11    st.push(root);
12    while (!st.empty()) {
13        TreeNode* node = st.top(); st.pop();
14        cout << node->val << " ";
15        if (node->right) st.push(node->right);
16        ____________
17    }
18}

给定一棵二叉树，采用广度优先搜索（BFS）算法，返回右视图所有节点的值。其中右视图定义为：二叉树的右视图是从树的右侧看过去时可见的节点集合，即右视图中的每个节点都是某一层中最右侧的节点。

01struct TreeNode {
02    int val;
03    TreeNode* left;
04    TreeNode* right;
05    TreeNode(int x): val(x), left(nullptr), right(nullptr) {}
06};
07
08vector<int> rightSideView(TreeNode* root) {
09    unordered_map<int, int> rightmostValueAtDepth;
10    int max_depth = -1;
11
12    queue<TreeNode*> nodeQueue;
13    queue<int> depthQueue;
14    nodeQueue.push(root);
15    depthQueue.push(0);
16
17    while (!nodeQueue.empty()) {
18        TreeNode* node = nodeQueue.front(); nodeQueue.pop();
19        int depth = depthQueue.front(); depthQueue.pop();
20
21        if (node != NULL) {
22            max_depth = max(max_depth, depth);
23            rightmostValueAtDepth[depth] = node->val;
24            nodeQueue.push(node->left);
25            nodeQueue.push(node->right);
26            depthQueue.push(____________);
27            depthQueue.push(____________);
28        }
29    }
30
31    vector<int> rightView;
32    for (int depth = 0; ____________; ++depth) {
33        rightView.push_back(rightmostValueAtDepth[depth]);
34    }
35    return rightView;
36}

下列关于树的深度优先搜索（DFS）的说法中，正确的是（）。

在二叉树中，宽度优先搜索算法（BFS）保证从起点到每个节点的访问路径是边数最少的路径（即最短路径）。

给定一个无向图，图的节点编号从 0 到 n-1，图的边以邻接表的形式给出。下面的程序使用深度优先搜索（DFS）遍历该图，并输出遍历的节点顺序。横线处应该填入的是（ ）

01#include <iostream>
02#include <vector>
03#include <stack>
04using namespace std;
05void DFS(int start, vector<vector<int>>& graph, vector<bool>& visited) {
06    stack<int> s;
07    s.push(start);
08    visited[start] = true;
09    while (!s.empty()) {
10        int node = s.top();
11        s.pop();
12        cout << node << " "; // 输出当前节点
13        // 遍历邻接节点
14        for (int neighbor : graph[node]) {
15            if (!visited[neighbor]) {
16                ____________
17                ____________
18            }
19        }
20    }
21}
22int main() {
23    int n, m;
24    cin >> n >> m;
25    vector<vector<int>> graph(n);
26    for (int i = 0; i < m; i++) {
27        int u, v;
28        cin >> u >> v;
29        graph[u].push_back(v);
30        graph[v].push_back(u);
31    }
32    vector<bool> visited(n, false);
33    // 从节点 0 开始DFS遍历
34    DFS(0, graph, visited);
35    return 0;
36}

泛洪算法的递归实现容易造成溢出，因此大的二维地图算法中，一般使用广度优先搜索实现。

在图像处理或游戏开发中，泛洪（flood fill）算法既可以⽤BFS实现，也可以⽤DFS实现。

下面程序片段主要体现的算法思想是（ ）。

01void dfs(int x, int y) {
02    vis[x][y] = true;
03    for (int k = 0; k < 4; k++) {
04        int nx = x + dx[k], ny = y + dy[k];
05        if (inside(nx, ny) && a[nx][ny] == 1 && !vis[nx][ny])
06            dfs(nx, ny);
07    }
08}

同一个图从同一个起点进行深度优先搜索，访问序列一定与邻接点的枚举顺序无关。

深度优先搜索（DFS）在遍历图时，每当访问到某个顶点后，选择⼀个相邻的未访问顶点继续搜索，直到某个顶点的所有相邻顶点均已被访问，则退回到前⼀顶点继续搜索。该算法主要运⽤了（ ）。

无向图的边为 $(1, 2)$，$(1, 3)$，$(2, 4)$，$(3, 4)$，$(4, 5)$。从顶点 $1$ 开始进行 BFS，每轮根据出队顶点，将与其相邻顶点按编号从小到大入队，则顶点 $4$ 第一次入队时，队列的状态为（ ）。

下列关于深度优先搜索和广度优先搜索的说法，错误的是（ ）。

下面的程序属于哪种算法（ ）。

01int pos[8];
02void queen(int n) {
03    for (int i = 0; i < 8; i++) {
04        pos[n] = i;
05        bool attacked = false;
06        for (int j = 0; j < n; j++)
07            if (pos[n] == pos[j] || pos[n] + n == pos[j] + j || pos[n] - n == pos[j] - j) {
08                attacked = true;
09                break;
10            }
11        if (attacked)
12            continue;
13        if (n == 7) {
14            return;
15        } else {
16            queen(n + 1);
17        }
18    }
19}

围棋游戏中，判断落下一枚棋子后是否会提掉对方的子，可以使用泛洪算法来实现。（ ）

下列选项中，哪个可能是下图的深度优先遍历序列（ ）。

下列选项中，哪个可能是下图的广度优先遍历序列（ ）。

学生在读期间所上的某些课程中需要先上其他的课程，所有课程和课程间的先修关系构成一个有向图 G，有向边 <U, V> 表示课程 U 是课程 V 的先修课，则要找到某门课程 C 的全部先修课下面哪种方法不可行？（ ）

广度优先搜索（BFS）能够判断图是否连通。（ ）

判断图是否连通只能⽤⼴度优先搜索算法实现

有 $V$ 个顶点、$E$ 条边的图的深度优先搜索遍历时间复杂度为（ ）。

判断无向图中是否有环，可以通过广度优先搜索实现

下⾯ pailie 函数是⼀个实现排列的程序，横线处可以填⼊的是（ ）。

01#include <iostream>
02using namespace std;
03int sum = 0;
04void swap(int & a, int & b) {
05    int temp = a;
06    a = b;
07    b = temp;
08}
09void pailie(int begin, int end, int a[]) {
10    if (begin == end) {
11        for (int i = 0; i < end; i++)
12            cout << a[i];
13        cout << endl;
14    }
15    for (int i = begin; i < end; i++) {
16        ___________  // 在此处填入选项
17    }
18}

已知 pailie 函数是实现排列的程序（代码如下），主函数为如下的程序，则最后的排列数是多少个？（ ）。

01#include <iostream>
02using namespace std;
03int sum = 0;
04void swap(int & a, int & b) {
05    int temp = a;
06    a = b;
07    b = temp;
08}
09void pailie(int begin, int end, int a[]) {
10    if (begin == end) {
11        for (int i = 0; i < end; i++)
12            cout << a[i];
13        cout << endl;
14    }
15    for (int i = begin; i < end; i++) {
16        swap(a[begin], a[i]);
17        pailie(begin + 1, end, a);
18        swap(a[i], a[begin]);
19    }
20}

主函数如下：

01int main() {
02    int a[5] = {1, 2, 3, 4, 5};
03    pailie(0, 5, a);
04    return 0;
05}