北邮C++数据结构课后习题-习题4参考答案VIP专享

习题 41.填空题（1）已知二叉树中叶子数为 50，仅有一个孩子的结点数为 30，则总结点数为（___________）。答案：129（2）4 个结点可构成（___________）棵不同形态的二叉树。答案：12（3） 设树的度为 5，其中度为 1~5 的结点数分别为 6、5、4、3、2 个，则该树共有（___________）个叶子。答案：31（4）在结点个数为n（n>1）的各棵普通树中，高度最小的树的高度是（___________），它有（___________）个叶子结点，（___________）个分支结点。高度最大的树的高度是（___________），它有（___________）个叶子结点，（___________）个分支结点。答案：2 n-1 1 n 1 n-1（5）深度为 k 的二叉树，至多有（___________）个结点。答案：2k-1（6）有 n 个结点并且其高度为 n 的二叉树的数目是（___________）。答案：2n-1 （7）设只包含根结点的二叉树的高度为 1，则高度为 k 的二叉树的最大结点数为（___________），最小结点数为（___________）。答案：2k-1 k（8）将一棵有 100 个结点的完全二叉树按层编号，则编号为 49 的结点为 X，其双亲PARENT（X）的编号为（）。答案：24（9）已知一棵完全二叉树中共有 768 个结点，则该树中共有（___________）个叶子结点。答案：384（10）已知一棵完全二叉树的第 8 层有 8 个结点，则其叶子结点数是（___________）。答案：68 （11）深度为 8（根的层次号为 1）的满二叉树有（___________）个叶子结点。答案：128（12）一棵二叉树的前序遍历是 FCABED，中序遍历是 ACBFED，则后序遍历是（___________）。答案：ABCDEF（13）某二叉树结点的中序遍历序列为 ABCDEFG，后序遍历序列为 BDCAFGE，则该二叉树结点的前序遍历序列为（___________），该二叉树对应的树林包括（___________）棵树。答案：EACBDGF 22.选择题（1）在一棵度为 3 的树中，度为 3 的结点的个数为 2，度为 2 的结点个数为 1，则度为 0 的结点个数为（ ）。A. 4 B. 5 C. 6 D. 7（2）下列陈述中正确的是（ ）。A. 二叉树是度为 2 的有序数B. 二叉树中结点只有一个孩子时无左右之分C. 二叉树中必有度为 2 的结点D. 二叉树中最多只有两棵子树，并且有左右之分（3）树中假如结点 M 有 3 个兄弟，而且 N 是 M 的双亲，则 N 的度是（ ）A. 3 B. 4 C. 5 D. 1（4）设高度为 h 的二叉树上只有度为 0 和度为 2 的结点，则此类二叉树中所包含的结点数...