CSP-J 卷
复刻
① 本卷为客观题单卷，合计 35 题 · 70 分，全部为客观题；
② 试卷右上角设有 「提交答卷」 与 「重置考试」 按钮，提交后系统自动判分并显示答题正确情况，请确认全部作答后再行提交；
③ 试卷不显示答案，提交后方可查看每题作答与正确答案的对照；
④ 答卷进度会保留在本地缓存中，刷新或再次打开仍可继续作答；
⑤ 本卷仅供学生练习使用；请勿用于其他用途；题面有问题请联系：i64coder@163.com。
判 分 报 告
客 观 题
在数据压缩编码中的哈夫曼编码方法，在本质上是一种（ ）的策略。
B：贪心。哈夫曼每次合并频率最小的两棵树，逐步构建最优前缀码，本质是贪心（局部最优达全局最优）。
一棵二叉树如下图所示。若采用顺序存储结构，即用一维数组元素存储该二叉树中的结点（根结点的下标为 ，若某结点的下标为 ，则其左孩子位于下标 处、右孩子位于下标 处），则该数组的最大下标至少为（ ）。
A：15。顺序存储下根下标 1，左孩子 2i、右孩子 2i+1；图中最深结点位于第 4 层右侧，沿 1→3→7→15 递增，故数组最大下标至少为 15。
假设一棵二叉树的后序遍历序列为 DGJHEBIFCA，中序遍历序列为 DBGEHJACIF，则其前序遍历序列为（ ）。
D：ABDEGHJCFI。后序末位 A 为根；中序中 A 左侧 DBGEHJ 为左子树、右侧 CIF 为右子树；左子树根 D（DB、GEHJ），右子树根 C（I、F）；前序拼接：A+(左前序 BDEGHJ)+(右前序 CFI)=ABDEGHJCFI。
独根树的高度为 。具有 个结点的完全二叉树的高度为（ ）。
D：6。完全二叉树高度 h 满足 2^(h-1) ≤ n < 2^h，n=61 时 2⁵=32≤61<64=2⁶，故 h=6。
假设字母表 {a, b, c, d, e} 在字符串出现的频率分别为 10%、15%、30%、16%、29%。若使用哈夫曼编码方式对字母进行不定长的二进制编码，字母 d 的编码长度为（ ）位。
B：2。频率 10(a),15(b),30(c),16(d),29(e)；合并 10+15=25, 16+25=41, 29+30=59, 41+59=100。d=16 位于第二层，编码长 2。
一棵有 n 个结点的完全二叉树用数组进行存储与表示，已知根结点存储在数组的第 个位置。若存储在数组第 个位置的结点存在兄弟结点和两个子结点，则它的兄弟结点和右子结点的位置分别是（ ）。
C：8、19。完全二叉树顺序存储下，位置 i 的兄弟=i^1=8（异或 1 翻转末位），右子=2i+1=19。
根节点的高度为 1，一棵拥有 2023 个节点的三叉树高度至少为（ ）。
C：8。三叉树高度 h 最多节点 (3^h-1)/2，h=7 时最多 1093<2023，h=8 时最多 3280≥2023，故至少 8。
假设有一组字符 {a,b,c,d,e,f}，对应的频率分别为 5%、9%、12%、13%、16%、45%。请问以下哪个选项是字符 a,b,c,d,e,f 分别对应的一组哈夫曼编码？（ ）
A：1111,1110,101,100,110,0。哈夫曼按频率合并最小两权：5+9=14, 12+13=25, 14+16=30, 25+30=55, 55+45=100。a 深度 4 → 1111, b 1110, c 101, d 100, e 110, f 0；前缀不冲突 ✓。
给定一棵二叉树，其前序遍历结果为：ABDECFG，中序遍历结果为：DEBACFG。请问这棵树的正确后序遍历结果是什么？（ ）
A：EDBFGCA。前序 ABDECFG 根 A；中序 DEBACFG 中 A 左侧 DEB、右侧 CFG；左子树根 B（中序 B 在 DE 后），右子树根 C；前序 DEC→左 D、DEC→中 E、B；右 CFG→F、G；后序 = 左后 + 右后 + 根 = EDB + FGC + A = EDBFGCA。
已知二叉树的前序遍历为 [A, B, D, E, C, F, G]，中序遍历为 [D, B, E, A, F, C, G]，请问该二叉树的后序遍历结果是？（ ）
A：[D,E,B,F,G,C,A]。前序 A,B,D,E,C,F,G 根 A；中序 D,B,E,A,F,C,G 中 A 左 D,B,E；右 F,C,G；递归左子树根 B（中序 D,B,E 中 B 在中），右根 C；后序 = 左后+右后+根 = DEB+FGC+A = DEBFGCA。
一棵包含 个结点的完全二叉树，其叶子结点的数量是多少？（ ）
B：贪心。每步局部最优（合并最小两权）达全局最优。
如果一棵二叉树只有根结点，那么这棵二叉树高度为 。请问高度为 的完全二叉树有（ ）种不同的形态？
A：16。高度 h 的完全二叉树形态数 = 2^(h-1)（除根外每层节点都有「左在右空」或「左右都在」两种选择）；h=5 时 2^4=16。
对 hello world 使用霍夫曼编码（Huffman Coding），最少比特（比特）为（ ）。
B：32。统计 hello world 各字符频率（l 出现 3 次、o 2 次、其余 6 个字符各 1 次），按频率构造哈夫曼树，频率高的编码短，全部字符编码总长 32 比特。
下面有关树的存储，错误的是（ ）。
D：错误项。只有完全二叉树、满二叉树结点下标连续，适合用 list 顺序存储；一般树的下标不连续，用 list 存储会浪费空间，A、B、C 均正确。
构造二叉树 [1,2,3,null,4] （ ）。
A：括号表示法写作「父(左子树)(右子树)」：根 1 的孩子是 2、3，2 的左孩子为空写 ()、右孩子为 4，故为 1(2()(4))(3)。
哈夫曼编码（Huffman Coding）具有唯一性，因此有确定的压缩率。（ ）
B：错误。哈夫曼编码不唯一：合并两个最小权值的顺序、左右孩子摆放方式不同会得到不同的编码树，压缩率也随之改变，不能说有确定的压缩率。
在构建哈夫曼树时，每次应该选择（ ）合并。
A：最小权值的节点。哈夫曼算法每步从森林中选出权值最小的两个结点合并，让高频率字符离根近、编码短，从而保证带权路径长度最小。
一个有 124 个叶子节点的完全二叉树，最多有（ ）个结点。
B：248。叶子 124 个，由 n0=n2+1 得 n2=123；完全二叉树度为 1 的结点最多 1 个，总结点数=124+123+1=248。
若一棵二叉树的先序遍历为：A, B, D, E, C, F，中序遍历为：D, B, E, A, F, C，它的后序遍历为（ ）。
A：由先序知根为 A，中序 DBE 在左、FC 在右；左子树先序 BDE、中序 DBE，B 为左根，D、E 是其左右孩子；右子树先序 CF、中序 FC，C 为右根、F 为其左孩子；后序得 D E B F C A。
哈夫曼树是一种二叉树。
A：正确。哈夫曼树是带权路径长度 WPL 最小的二叉树，每次合并两个最小权值结点生成新结点，所有结点度为 0 或 2，本质就是二叉树。
完全二叉树的任意一层都可以不满。
B：错误。完全二叉树除最后一层外每层都必须排满，最后一层允许不满但结点必须从左到右连续排列；「任意一层都可以不满」把限制放宽到所有层，说法错误。
哈夫曼编码的主要应用领域是有损数据压缩。
B：错误。哈夫曼编码生成前缀码，解码能无损还原原文，主要应用于无损数据压缩（如文件压缩）；有损压缩会丢失信息，如 JPEG，与哈夫曼无关。
使用哈夫曼编码对一些字符进行编码，如果两个字符的频率差异最大，则它们的编码可能出现相同的前缀。
B：错误。哈夫曼编码是前缀码，任意两个字符的编码都互不为对方前缀，这是前缀码的定义性质，与频率差异大小无关，频率差异最大的两个字符也不例外。
对 "classmycls" 使用哈夫曼（Huffman）编码，最少需要（ ）比特。
C：25。统计 classmycls 频率：s 3 次、c 2、l 2、a/m/y 各 1，构造哈夫曼树后 WPL=3×2+2×3+2×2+1×3+1×3+1×3=25 比特。
二叉树的（ ）第一个访问的节点是根节点。
A：先序遍历按根、左、右顺序访问，第一个访问的必是根节点；中序遍历从最左子树开始、后序遍历从最左叶开始，首访都不是根，故只能选 A。
一棵 5 层的满二叉树中节点数为（ ）。
A：31。满二叉树第 i 层有 2^(i-1) 个结点，5 层结点总数=1+2+4+8+16=2^5-1=31，其余选项均非满二叉树总节点数公式的结果。
以下关于树的说法，（ ）是正确的。
B：满二叉树第 k 层结点数为 2^(k-1)，故每层结点数等于 O(2^(层数-1))；叶子结点度为 0 而非 2，A 错；结点度之和等于边数两倍，C 错；先序与中序结果通常不同，D 错。
已知字符集 {A, B, C, D} 的出现频率如下表所示：
| 字符 | 频率 |
|---|---|
| A | 8 |
| B | 3 |
| C | 1 |
| D | 6 |
根据哈夫曼编码法，下面（ ）是正确的哈夫曼树。
A：频率 C1、B3 先合并为 4，再与 D6 合并为 10，最后与 A8 合并为 18，得到根 ABCD 左 A 右 BCD、BCD 左 D 右 BC、BC 左 B 右 C 的树。
已知字符集 {A, B, C, D} 的出现频率为 A:8、B:3、C:1、D:6，根据哈夫曼编码法，各字符的哈夫曼编码是（ ）。
C：按合并 C+B=4、(C+B)+D=10、A+10=18 建树，左 0 右 1 得 A:0、D:11、C:100、B:101，与选项 C 完全一致，且互为前缀码。
下面代码构建的树一定是完全二叉树：
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}
A：正确。层序为 1,2,3,4,5,6：前两层排满，第三层 4、5、6 从左到右连续，6 是 3 的左孩子且 3 无右孩子，满足完全二叉树定义。
已知一棵二叉树的前序遍历序列为 GDAFEMHZ，中序遍历序列为 ADFGHEMZ，则其后序遍历序列为（）。
D：先序首元素 G 是根，中序 ADF 在左、HEMZ 在右；左子树先序 DAF 中序 ADF 得 D(A,F)，右子树先序 EMHZ 中序 HEMZ 得 E(H,M(Z))；后序为 A F D H Z M E G。
已知二叉树的中序遍历是 [D, B, E, A, F, C]，先序遍历是 [A, B, D, E, C, F]。请问该二叉树的后序遍历结果是（）。
A：先序首元素 A 是根，中序 DBE 在左、FC 在右；左子树先序 BDE 中序 DBE 得 B(D,E)，右子树先序 CF 中序 FC 得 C(F)；后序为 D E B F C A。
以下函数 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}
B：完全二叉树。层序遍历中一旦出现空结点（hasNull=true），之后再出现非空结点就返回 false，正是完全二叉树「空结点后无结点」的判断逻辑。
某二叉树共有 个结点，记为 A~J，已知它的先序遍历序列为：A B D H I E C F J G，中序遍历序列为：H D I B E A F J C G，则该二叉树的后序遍历序列是（）。
A：先序首元素 A 是根，中序 HDIBE 在左、FJCG 在右；左子树 B(D(H,I),E)，右子树 C(F(J),G)，后序为 H I D E B J F G C A。
下列关于树的遍历的说法中，正确的一项是（）。
C：先序定根、中序分左右，可唯一确定二叉树；A 深度优先序列不唯一，B 先序+后序不能唯一确定（单孩子方向不明），D 只有先序更不能确定。