CSP-J 卷

在数据压缩编码中的哈夫曼编码方法，在本质上是一种（ ）的策略。

一棵二叉树如下图所示。若采用顺序存储结构，即用一维数组元素存储该二叉树中的结点（根结点的下标为 $1$，若某结点的下标为 $i$，则其左孩子位于下标 $2i$ 处、右孩子位于下标 $2i+1$ 处），则该数组的最大下标至少为（ ）。

假设一棵二叉树的后序遍历序列为 DGJHEBIFCA，中序遍历序列为 DBGEHJACIF，则其前序遍历序列为（ ）。

独根树的高度为 $1$。具有 $61$ 个结点的完全二叉树的高度为（ ）。

假设字母表 {a, b, c, d, e} 在字符串出现的频率分别为 10%、15%、30%、16%、29%。若使用哈夫曼编码方式对字母进行不定长的二进制编码，字母 d 的编码长度为（ ）位。

一棵有 n 个结点的完全二叉树用数组进行存储与表示，已知根结点存储在数组的第 $1$ 个位置。若存储在数组第 $9$ 个位置的结点存在兄弟结点和两个子结点，则它的兄弟结点和右子结点的位置分别是（ ）。

根节点的高度为 1，一棵拥有 2023 个节点的三叉树高度至少为（ ）。

假设有一组字符 {a,b,c,d,e,f}，对应的频率分别为 5%、9%、12%、13%、16%、45%。请问以下哪个选项是字符 a,b,c,d,e,f 分别对应的一组哈夫曼编码？（ ）

给定一棵二叉树，其前序遍历结果为：ABDECFG，中序遍历结果为：DEBACFG。请问这棵树的正确后序遍历结果是什么？（ ）

已知二叉树的前序遍历为 [A, B, D, E, C, F, G]，中序遍历为 [D, B, E, A, F, C, G]，请问该二叉树的后序遍历结果是？（ ）

一棵包含 $1000$ 个结点的完全二叉树，其叶子结点的数量是多少？（ ）

如果一棵二叉树只有根结点，那么这棵二叉树高度为 $1$。请问高度为 $5$ 的完全二叉树有（ ）种不同的形态？

对 hello world 使用霍夫曼编码（Huffman Coding），最少比特（比特）为（ ）。

下面有关树的存储，错误的是（ ）。

构造二叉树 [1,2,3,null,4] （ ）。

哈夫曼编码（Huffman Coding）具有唯一性，因此有确定的压缩率。（ ）

在构建哈夫曼树时，每次应该选择（ ）合并。

一个有 124 个叶子节点的完全二叉树，最多有（ ）个结点。

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

哈夫曼树是一种二叉树。

完全二叉树的任意一层都可以不满。

哈夫曼编码的主要应用领域是有损数据压缩。

使用哈夫曼编码对一些字符进行编码，如果两个字符的频率差异最大，则它们的编码可能出现相同的前缀。

对 "classmycls" 使用哈夫曼（Huffman）编码，最少需要（ ）比特。

二叉树的（ ）第一个访问的节点是根节点。

一棵 5 层的满二叉树中节点数为（ ）。

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

已知字符集 {A, B, C, D} 的出现频率如下表所示：

根据哈夫曼编码法，下面（ ）是正确的哈夫曼树。

已知字符集 {A, B, C, D} 的出现频率为 A:8、B:3、C:1、D:6，根据哈夫曼编码法，各字符的哈夫曼编码是（ ）。

下面代码构建的树一定是完全二叉树：

01struct TreeNode {
02    int value;
03    TreeNode* left;
04    TreeNode* right;
05};
06
07TreeNode* buildCompleteBinaryTree() {
08    TreeNode* root = new TreeNode{1};
09    root->left = new TreeNode{2};
10    root->right = new TreeNode{3};
11    root->left->left = new TreeNode{4};
12    root->left->right = new TreeNode{5};
13    root->right->left = new TreeNode{6};
14    return root;
15}

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

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

以下函数 check() 用于判断一棵二叉树是否为（）。

01bool check(TreeNode* root) {
02    if (!root) return true;
03
04    queue<TreeNode*> q;
05    q.push(root);
06    bool hasNull = false;
07    while (!q.empty()) {
08        TreeNode* cur = q.front(); q.pop();
09        if (!cur) {
10            hasNull = true;
11        } else {
12            if (hasNull) return false;
13            q.push(cur->left);
14            q.push(cur->right);
15        }
16    }
17    return true;
18}

某二叉树共有 $10$ 个结点，记为 A~J，已知它的先序遍历序列为：A B D H I E C F J G，中序遍历序列为：H D I B E A F J C G，则该二叉树的后序遍历序列是（）。

下列关于树的遍历的说法中，正确的一项是（）。