GESP 6级客观题｜树与二叉树基础｜课后作业

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

1. 完全二叉树可以用数组连续高效存储，如果节点从 1 开始编号，则对有两个孩子节点的节点 $i$ ，（ ）。

   {{ select(1) }}

• 左孩子位于 $2i$ ，右孩子位于 $2i+1$
• 完全二叉树的叶子节点可以出现在最后一层的任意位置
• 所有节点都有两个孩子
• 左孩子位于 $2i+1$ ，右孩子位于 $2i+2$

2. 一个含有 $n$ 个节点的完全二叉树，高度为 $\log_2 n$。

   {{ select(2) }}

• 正确
• 错误

3. （ ）只有最底层的节点未被填满，且最底层节点尽量靠左填充。

   {{ select(3) }}

• 完美二叉树
• 完全二叉树
• 完满二叉树
• 平衡二叉树

4. 下列代码中的 tree 向量，表示的是一棵完全二叉树（-1 代表空节点）按照层序遍历的结果。

#include <vector>
std::vector<int> tree = {1, 2, 3, 4, -1, 6, 7};

{{ select(4) }}

• 对
• 错

5. 以下关于树的说法，（ ）是正确的。

   {{ select(5) }}

• 在一棵二叉树中，叶子结点的度一定是2。
• 满二叉树中每一层的结点数等于 2^层数。
• 在一棵树中，所有结点的度之和等于所有叶子结点的度之和。
• 一棵二叉树的先序遍历结果和中序遍历结果一定相同。

6. 下面代码构建的树一定是完全二叉树。（ ）

struct TreeNode {
    int value;
    TreeNode* left;
    TreeNode* right;
};

TreeNode* buildCompleteBinaryTree() {
    TreeNode* root = new TreeNode[1];
    root->left = new TreeNode[2];
    root->right = new TreeNode[3];
    root->left->left = new TreeNode[4];
    root->left->right = new TreeNode[5];
    root->right->left = new TreeNode[6];
    return root;
}

{{ select(6) }}

• 对
• 错