GESP 6级客观题｜树的遍历｜课后作业

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

1. 以下代码实现了树的哪种遍历方式？

void traverse(TreeNode *root)
{
    if (root == nullptr)
        return;
    cout << root->val << " ";
    traverse(root->left);
    traverse(root->right);
}

{{ select(1) }}

• 前序遍历
• 中序遍历
• 后序遍历
• 层次遍历

2. 已知一棵二叉树的前序遍历序列为 GDAFEMHZ，中序遍历序列为 ADFGEHMZ，则其后序遍历序列为（ ）。

   {{ select(2) }}

• ADFGEHMZ
• ADFGHMEZ
• AFDGEMZH
• AFDHZMEG

3. 若一棵二叉树的先序遍历为：A, B, D, E, C, F、中序遍历为：D, B, E, A, F, C，它的后序遍历为（ ）。

   {{ select(3) }}

• D, E, B, F, C, A
• E, D, B, F, C, A
• D, E, B, C, F, A
• E, D, B, C, F, A

4. 已知二叉树的 中序遍历 是 [D, B, E, A, F, C]，先序遍历 是 [A, B, D, E, C, F]。请问该二叉树的后序遍历结果是（ ）。

   {{ select(4) }}

• [D, E, B, F, C, A]
• [D, B, E, F, C, A]
• [D, E, B, C, F, A]
• [B, D, E, F, C, A]

5. 上⼀题的⼆叉树深度计算还可以采⽤⼆叉树的⼴度优先搜索来实现。以下基于⼆叉树的⼴度优先搜索实现的深度计算函数中横线上应填写（ ）。

#include <queue>
int max_depth_bfs(tree_node* root) {
    if (root == nullptr) {
        return 0; // 如果树为空，深度为 0
    }

    queue <tree_node*> q;
    q.push(root);
    int depth = 0;

    // 使用队列进行层序遍历
    while (!q.empty()) {
        ———————————————————————— // 在此处填入代码
        for (int i = 0; i < level_size; ++i) {
            tree_node* node = q.front();
            q.pop();
            if (node->left) {
                q.push(node->left);
            }
            if (node->right) {
                q.push(node->right);
            }
        }
    }

    return depth;
}

{{ select(5) }}

• int level_size = q.size(); depth++;
• int level_size = 2; depth++;
• int level_size = q.size(); depth += level_size;
• int level_size = 2; depth += level_size;