"《华中师大C语言数据结构》第6章树和二叉树自测卷解答及答案分析"

《华中师大c语言数据结构》第六章树和二叉树的自测卷解答涵盖了关于二叉树的几个叙述，需要我们判断其正误，并进行解答和分析。以下是我对每个叙述的判断和解析： 1. 一棵具有 n 个结点的二叉树，若它有 m 个叶子结点，则该二叉树中度为 1 的结点个数是 n-2m+1 (√) 这个叙述正确。一棵二叉树中，叶子结点的度为0，而度为1的结点是有且只有一个子结点的结点。所以一棵具有m个叶子结点的二叉树中，度为1的结点个数应该是m-1。 2. 二叉树中每个结点的两棵子树的高度差等于1 (×) 这个叙述错误。在一棵二叉树中，整棵树的高度是由最深的叶子结点到根结点的距离所决定的。因此，同一个节点的左右子树的高度可能相等、也可能相差较大，没有固定的高度差。 3. 对于一棵非空二叉树，它的根结点作为第一层，则它的第i层上最多能有2i—1个结点。(应2i-1) (√) 这个叙述正确，对于一棵二叉树，它的第i层上最多能有2的(i-1)次方个结点，也即是2^(i-1)个结点。因此，第i层上最多能有2^(i-1)-1个结点。 4. 已知完全二叉树第6层上有10个叶子结点，则这棵二叉树的结点总数最多是107 (√) 这个叙述正确。在一棵完全二叉树中，第i层上的结点个数是2^(i-1)，所以第6层上的结点个数是2^5=32个。而叶子结点是最后一层上的结点，所以第6层上有10个叶子结点。因此，这棵二叉树的结点总数最多是32个。 5. 具有12个结点的完全二叉树有5个度为2的结点。最快方法：用叶子数=[n/2]=6，再求n2=n0-1=5 (×) 这个叙述错误。首先根据完全二叉树的特点，假设有n个结点，其中叶子结点数为k，则非叶子结点数为(k-1)/2。又因为每个度为2的结点会提供两个子结点，所以有k-1个度为2的结点。因此，k-1<=(n-k)/2，将n=12代入则有k-1<=6，可以得出k<=7。所以，具有12个结点的完全二叉树至多有7个叶子结点。 6. 二叉树中每个结点的关键字值大于其左非空子树（若存在的话）所有结点的关键字值，且小于其右非空子树（若存在的话）所有结点的关键字值。(×) 这个叙述错误。在一棵二叉搜索树（BST）中，每个结点的关键字值大于其左子树的所有结点的关键字值，并且小于其右子树的所有结点的关键字值。但在一般的二叉树中，并没有这样的规定。所以，这个叙述是错误的。 通过对以上几个叙述的判断和解析，可以看出对于二叉树的理解还需进一步加强，特别是对于二叉搜索树的特点需要更加熟悉。掌握了二叉树的基本概念和性质，可以更好地理解和应用于解决实际问题。