GESP 6级客观题｜深度优先搜索 DFS｜课后作业

考试频率：高频。本卷共 6 题。

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

   {{ select(1) }}

• 对
• 错

2. 深度优先搜索（DFS，Depth First Search的简写）属于图算法，其过程是对每一个可能的分支路径深入到不能再深入为止，而且每个节点只能访问一次。( )

   {{ select(2) }}

• 对
• 错

3. 在树的深度优先搜索（DFS）中，使用队列作为辅助数据结构以实现“先进后出”的访问顺序。

   {{ select(3) }}

• 对
• 错

4. 请将下列树的深度优先遍历代码补充完整，横线处应填入（ ）。

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x): val(x), left(nullptr), right(nullptr) {}
};

void dfs(TreeNode* root) {
    if (!root) return;
    ______<TreeNode*> temp; // 在此处填写代码
    temp.push(root);
    while (!temp.empty()) {
        TreeNode* node = temp.top();
        temp.pop();
        cout << node->val << " ";
        if (node->right) temp.push(node->right);
        if (node->left) temp.push(node->left);
    }
}

{{ select(4) }}

• vector
• list
• queue
• stack

5. 面向对象的编程思想主要包括（ ）原则

   {{ select(5) }}

• 贪心、动态规划、回溯
• 并发、并行、异步
• 递归、循环、分治
• 封装、继承、多态

6. 在求解最优化问题时，动态规划常常涉及到两个重要性质，即最优子结构和( )。

   {{ select(6) }}

• 重叠子问题
• 分治法
• 贪心策略
• 回溯算法