练习题 -- 数据结构与算法 >> 树
共 9 题
第 1/9 题
★
在二叉排序树中插入一个新节点，新节点一定是：
正确答案: C
【数据结构-树与二叉树】
题目：BST插入新节点一定是：
✅ 正确答案：C.叶子节点
错误选项：
❌ A.根节点
❌ B.分支节点
❌ D.内部节点
📖 解析：BST插入总是在叶子位置。
题目：BST插入新节点一定是：
✅ 正确答案：C.叶子节点
错误选项：
❌ A.根节点
❌ B.分支节点
❌ D.内部节点
📖 解析：BST插入总是在叶子位置。
第 2/9 题
★★★
在一棵度为3的树中，有2个度为3的节点，1个度为2的节点，2个度为1的节点，则叶子节点数为：
正确答案: C
【数据结构-树与二叉树】
题目：度为3的树：2个度3，1个度2，2个度1，叶子数：
✅ 正确答案：C.6
错误选项：
❌ A.4
❌ B.5
❌ D.7
📖 解析：总分支数=2×3+1×2+2×1=10=节点数-1→节点数=11。叶子=11-2-1-2=6。
题目：度为3的树：2个度3，1个度2，2个度1，叶子数：
✅ 正确答案：C.6
错误选项：
❌ A.4
❌ B.5
❌ D.7
📖 解析：总分支数=2×3+1×2+2×1=10=节点数-1→节点数=11。叶子=11-2-1-2=6。
第 3/9 题
★★
由权值{2,3,4,5,6}构造的哈夫曼树，其WPL为：
正确答案: B
【数据结构-树与二叉树】
题目：权值{2,3,4,5,6}的哈夫曼树WPL：
✅ 正确答案：B.45
错误选项：
❌ A.42
❌ C.48
❌ D.50
📖 解析：WPL=2×3+3×3+4×2+5×2+6×2=6+9+8+10+12=45。
📌 拓展：哈夫曼树构造：每次选两个最小权值合并，新节点权值求和，重复直到剩一个。WPL=所有叶子权值×路径长度之和。
题目：权值{2,3,4,5,6}的哈夫曼树WPL：
✅ 正确答案：B.45
错误选项：
❌ A.42
❌ C.48
❌ D.50
📖 解析：WPL=2×3+3×3+4×2+5×2+6×2=6+9+8+10+12=45。
📌 拓展：哈夫曼树构造：每次选两个最小权值合并，新节点权值求和，重复直到剩一个。WPL=所有叶子权值×路径长度之和。
第 4/9 题
★★★
完全二叉树1001个节点，叶子数：
正确答案: B
【数据结构-树与二叉树】
题目：完全二叉树1001个节点，叶子数：
✅ 正确答案：B.501
错误选项：
❌ A.500
❌ C.250
❌ D.251
📖 解析：n0=⌈n/2⌉=⌈1001/2⌉=501。
题目：完全二叉树1001个节点，叶子数：
✅ 正确答案：B.501
错误选项：
❌ A.500
❌ C.250
❌ D.251
📖 解析：n0=⌈n/2⌉=⌈1001/2⌉=501。
第 5/9 题
★
完全二叉树按层次编号（根为1），编号为i的节点的父节点编号是：
正确答案: C
【数据结构-树与二叉树】
题目：完全二叉树层序编号i的父节点：
✅ 正确答案：C.⌊i/2⌋
错误选项：
❌ A.2i
❌ B.2i+1
❌ D.⌈i/2⌉
📖 解析：左孩子=2i，右孩子=2i+1，父=⌊i/2⌋。
题目：完全二叉树层序编号i的父节点：
✅ 正确答案：C.⌊i/2⌋
错误选项：
❌ A.2i
❌ B.2i+1
❌ D.⌈i/2⌉
📖 解析：左孩子=2i，右孩子=2i+1，父=⌊i/2⌋。
第 6/9 题
★★★
一棵二叉树的先序序列为ABCDEFG，中序序列为CBAEDFG，则后序序列为：
正确答案: B
【数据结构-树与二叉树】
题目：先序ABCDEFG中序CBAEDFG，后序：
✅ 正确答案：B.CBEGFDA
错误选项：
❌ A.CBEFGDA
❌ C.CBFEGDA
❌ D.CBFGEDA
📖 解析：A根→左CB→右EDFG→后序CBEGFDA。
题目：先序ABCDEFG中序CBAEDFG，后序：
✅ 正确答案：B.CBEGFDA
错误选项：
❌ A.CBEFGDA
❌ C.CBFEGDA
❌ D.CBFGEDA
📖 解析：A根→左CB→右EDFG→后序CBEGFDA。
第 7/9 题
★★★
二叉树的前序序列和中序序列相同，则该二叉树：
正确答案: B
【数据结构-树与二叉树】
题目：二叉树前序和中序序列相同，则该二叉树：
✅ 正确答案：B.所有节点只有右子树
错误选项：
❌ A.满二叉树
❌ C.所有节点只有左子树
❌ D.平衡二叉树
📖 解析：前序=根左右，中序=左根右。相同→无左子树→右斜树。
题目：二叉树前序和中序序列相同，则该二叉树：
✅ 正确答案：B.所有节点只有右子树
错误选项：
❌ A.满二叉树
❌ C.所有节点只有左子树
❌ D.平衡二叉树
📖 解析：前序=根左右，中序=左根右。相同→无左子树→右斜树。
第 8/9 题
★★
AVL树中插入节点导致不平衡，若新节点插在"右子树的右子树"上（RR型），应如何调整？
正确答案: B
【数据结构-树与二叉树】
题目：AVL树RR型调整：
✅ 正确答案：B.左旋
错误选项：
❌ A.右旋
❌ C.先右后左
❌ D.先左后右
📖 解析：RR型=右子树的右子树→左旋。LL型=右旋。LR=先左后右。RL=先右后左。
📌 拓展：AVL调整口诀：LL右旋，RR左旋，LR先左后右，RL先右后左。
题目：AVL树RR型调整：
✅ 正确答案：B.左旋
错误选项：
❌ A.右旋
❌ C.先右后左
❌ D.先左后右
📖 解析：RR型=右子树的右子树→左旋。LL型=右旋。LR=先左后右。RL=先右后左。
📌 拓展：AVL调整口诀：LL右旋，RR左旋，LR先左后右，RL先右后左。
第 9/9 题
★
一棵二叉树有10个度为2的节点，叶子节点数是：
正确答案: C
【数据结构-树与二叉树】
题目：二叉树10个度为2的节点，叶子数：
✅ 正确答案：C.11
错误选项：
❌ A.9
❌ B.10
❌ D.12
📖 解析：n0=n2+1=10+1=11。
题目：二叉树10个度为2的节点，叶子数：
✅ 正确答案：C.11
错误选项：
❌ A.9
❌ B.10
❌ D.12
📖 解析：n0=n2+1=10+1=11。