4.1树与二叉树 （分层作业）-高中信息技术选修1数据与数据结构 分层作业

4.1树与二叉树 【夯实基础】 1.树是一种____的数据结构。 A. 非线性 B. 线性 C. 顺序 D. 链式 2.在树结构中，没有子节点的节点称为____。 A. 叶节点 B. 根节点 C. 父节点 D. 子节点 3.一棵树的根节点至任意节点的路径是唯一的，这是树的____特性。 A. 无环性 B. 唯一路径性 C. 层次性 D. 分支性 4.二叉树是每个节点最多有两个子树的树结构，这两个子树分别称为该节点的____。 A. 左子树和右子树 B. 前子树和后子树 C. 第一子树和第二子树 D. 上子树和下子树 5.二叉树的度是指____。 A. 节点的子节点个数的最大值 B. 节点的子节点个数的最小值 C. 树中所有节点的子节点总数 D. 树中所有叶子节点的总数 6.满二叉树是每一个层级都有最大节点数的二叉树，那么高度为h的满二叉树的节点总数是____。 A. 2^h - 1 B. 2^(h-1) C. 2^h D. 2^(h+1) - 1 7.在二叉树中，若一个节点是某节点的父节点的左子节点，则该节点称为该节点的____。 A. 左兄弟 B. 右兄弟 C. 左孩子 D. 右孩子 8.下列哪一项不是二叉树的性质？ A. 是完全二叉树 B. 父节点的值总是大于或等于（最大堆）或小于或等于（最小堆）其子节点的值 C. 总是可以通过调整形成新的堆 D. 每个节点的左右子树高度相差不超过1 【巩固提升】 9.哈夫曼树（最优二叉树）是带权路径长度____的二叉树。 A. 最小 B. 最大 C. 平均值 D. 任意值 10.在二叉树中，从根节点到任意叶子节点的路径上，经过的节点数目称为该路径的____。 A. 深度 B. 高度 C. 层数 D. 路径长度 11.对于一棵满二叉树，第i层的节点数是第i-1层节点数的____倍。 A. 1 B. 2 C. 3 D. 4 12.在二叉树中，具有n个节点的满二叉树的总结点数是____。 A. 2^n B. 2^n - 1 C. 2^(n-1) D. 2^(n+1) - 1 13.在一棵二叉树中，第i层最多可以有的节点数是____。 A. 2^(i-1) B. 2^i C. 2^(i+1) D. i 【拓展应用】 14.对于一棵非空的二叉树，如果叶子节点数为n0，度为2的节点数为n2，则有关系式____。 A. n0 = n2 + 1 B. n0 = n2 - 1 C. n0 = 2n2 + 1 D. n0 = n2 15.在哈夫曼编码中，出现频率较低的字符用____的编码表示。 A. 较长 B. 较短 C. 相同长度 D. 不确定长度 参考答案： 【夯实基础】 1. A. 非线性：树是非线性数据结构，因为它允许一个节点有多个子节点，形成了分支结构。 2. A. 叶节点：在树结构中，没有子节点的节点称为叶节点或终端节点。 3. B. 唯一路径性：树的定义之一是任意两个节点之间有唯一的一条路径，体现了唯一路径性。 4. A. 左子树和右子树：在二叉树中，每个节点最多有两个子节点，分别称为左子树和右子树。 5. A. 节点的子节点个数的最大值：二叉树的度是指节点的最大分支数，即最多子节点数，对于二叉树而言，这个值是2。 6. A. 2^h - 1：高度为h的满二叉树的节点总数遵循公式2^0 + 2^1 + ... + 2^(h-1) = 2^h - 1。 7. C. 左孩子：在二叉树的术语中，一个节点如果是另一个节点的父节点的左子节点，它就是那个节点的左孩子。 8. A. 是完全二叉树：这个选项不是二叉树的一般性质，而是特指一种特殊的二叉树形态；而B、C、D描述的是堆的性质或二叉树的平衡特性。 【巩固提升】 9. A. 最小：哈夫曼树，也称为最优二叉树，是带权路径长度最小的二叉树。 10. D. 路径长度：从根节点到任意叶子节点经过的边数称为路径长度。 11. B. 2：满二叉树每增加一层，节点数翻倍，所以第i层的节点数是第i-1层的2倍。 12. B. 2^n - 1：具有n个节点的满二叉树总结点数遵循2^n - 1的公式。 13. B. 2^i：第i层最多可以有的节点数是2^(i-1) + 2^i = 2^i，因为二叉树每增加一层，节点数最多翻倍。 【拓展应用】 14. A. n0 = n2 + 1：在二叉树中，叶子节点数n0与度为2的节点数n2之间的关系由公式n0 = n2 + 1给出，这是基于二叉树的基本性质推导得出的。 15. A. 较长：哈夫曼编码中，出现频率越低的字符，其编码通常设定得越长，以实现高效的数据压缩。 原创精品资源学科网独家享有版权，侵权必究！6 学科网（北京）股份有限公司 $$