数据结构6-9章习题(带答案)(1).doc

### 数据结构知识点解析 #### 一、单项选择题解析 **1. 以下说法错误的是：** - **选项分析：** - **A**: 正确。存在这样的二叉树，比如只包含一个节点的二叉树或者左右子树结构完全相同的二叉树，其前序、中序和后序遍历的结果都相同。 - **B**: 错误。二叉树不是树的特殊情形，而是树的一种特殊情况，即每个节点最多有两个子节点。 - **C**: 正确。满二叉树定义为除了最后一层外，每一层的节点数都是最大值，即2^(h-1)，其中h为树的高度，因此所有叶子节点必然在同一层。 - **D**: 正确。在二叉树中，即使只有一个子树，也需要明确它是左子树还是右子树。 **2. 树最适合用来表示：** - **选项分析：** - **A**: 错误。有序数据元素通常使用线性结构如数组或链表表示。 - **B**: 错误。无序数据元素也可以使用其他非线性结构如图来表示。 - **C**: 正确。树是一种典型的非线性数据结构，非常适合表示元素之间的分支层次关系。 - **D**: 错误。元素之间无联系的数据可以使用简单的线性结构来表示。 **3. 下列叙述正确的是：** - **选项分析：** - **A**: 错误。二叉树是一种特殊的有序树，但并不是度为2的有序树，因为二叉树的每个节点最多有两个子节点。 - **B**: 错误。完全二叉树不一定存在度为1的节点，例如满二叉树就是一个特殊的完全二叉树，所有非叶子节点的度均为2。 - **C**: 正确。深度为k的二叉树中结点总数的最大值是2^k - 1，这是因为满二叉树在这个深度下的结点总数。 - **D**: 错误。对于有n个结点的二叉树，其高度可以小于或等于log2(n)+1，而不是必须等于这个值。 **4. 按照二叉树的定义，具有三个节点的二叉树有：** - **选项分析：** - **A**: 错误。3个节点的二叉树数量不止3种。 - **B**: 错误。3个节点的二叉树数量也不止4种。 - **C**: 正确。3个节点的二叉树共有5种不同的形态。 - **D**: 错误。3个节点的二叉树数量并非6种。 **5. 下列叙述中正确的是：** - **选项分析：** - **A**: 错误。二叉树不是度为2的有序树。 - **B**: 错误。二叉树中的结点如果只有一个孩子时，需要区分左孩子还是右孩子。 - **C**: 正确。二叉树中每个结点最多有两个子树，并且有左右之分。 - **D**: 错误。二叉树可能存在两个结点，其中一个为根，另一个既可以是左孩子也可以是右孩子。 **6. 设某二叉树中度数为0的结点数为N0，度数为1的结点数为N1，度数为2的结点数为N2，则下列等式成立的是：** - **选项分析：** - **A**: 错误。对于大多数二叉树而言，N0 ≠ N1 + 1。 - **B**: 错误。对于大多数二叉树而言，N0 ≠ N1 + N2。 - **C**: 正确。在任何二叉树中，N0 = N2 + 1 这个公式总是成立的。 - **D**: 错误。对于大多数二叉树而言，N0 ≠ 2N1 + 1。 **7. 设按照从上到下、从左到右的顺序从1开始对完全二叉树进行顺序编号，则编号为i结点的左孩子结点的编号为：** - **选项分析：** - **A**: 错误。编号为i结点的左孩子结点的编号不是2i+1。 - **B**: 正确。在完全二叉树中，编号为i结点的左孩子结点的编号是2i。 - **C**: 错误。编号为i结点的左孩子结点的编号不是i/2。 - **D**: 错误。编号为i结点的左孩子结点的编号不是2i-1。 **8. 有100个结点的完全二叉树由根开始从上到下从左到右对结点进行编号，根结点的编号为1，编号为46的结点的右孩子的编号为：** - **选项分析：** - **A**: 错误。编号为46的结点的右孩子编号不是50。 - **B**: 错误。编号为46的结点的右孩子编号不是92。 - **C**: 正确。编号为46的结点的右孩子编号是93。 - **D**: 错误。编号为46的结点的右孩子编号不是86。 **9. 若一棵有n个结点的树，则该树中的度之和为：** - **选项分析：** - **A**: 错误。对于一般的树而言，度之和不等于n+1。 - **B**: 错误。对于一般的树而言，度之和不等于n。 - **C**: 正确。对于任何一棵树而言，度之和总是等于n-1。 - **D**: 错误。对于一般的树而言，度之和是可以确定的。 **10. 已知完全二叉树有90个结点，则整个二叉树有：** - **选项分析：** - **A**: 错误。完全二叉树中可能存在度为1的结点。 - **B**: 正确。对于完全二叉树而言，如果有偶数个结点，那么只存在1个度为1的结点；如果有奇数个结点，则不存在度为1的结点。 - **C**: 错误。完全二叉树中可能存在度为1的结点。 - **D**: 错误。对于完全二叉树而言，度为1的结点的数量是可以确定的。 **11. 一棵完全二叉树上有1001个结点，其中叶子结点的个数是：** - **选项分析：** - **A**: 错误。对于1001个结点的完全二叉树，叶子结点数量不会是500。 - **B**: 错误。对于1001个结点的完全二叉树，叶子结点数量不会是505。 - **C**: 正确。对于1001个结点的完全二叉树，叶子结点数量是501。 - **D**: 错误。对于1001个结点的完全二叉树，叶子结点数量不会是503。 **12. 一棵完全二叉树上有2001个结点，其中叶子结点的个数是：** - **选项分析：** - **A**: 错误。对于2001个结点的完全二叉树，叶子结点数量不会是1000。 - **B**: 正确。对于2001个结点的完全二叉树，叶子结点数量是1001。 - **C**: 错误。对于2001个结点的完全二叉树，叶子结点数量不会是1003。 - **D**: 错误。对于2001个结点的完全二叉树，叶子结点数量不会是1005。 **13. 具有50个结点的二叉树中，若用二叉链表存储，其指针域部分用来指向结点的左、右孩子，其余：** - **选项分析：** - **A**: 错误。剩余指针域数量不是49。 - **B**: 错误。剩余指针域数量不是25。 - **C**: 错误。剩余指针域数量不是24。 - **D**: 正确。对于50个结点的二叉树，使用二叉链表存储，总共会有50 * 2 = 100个指针域，其中49个用于指向子节点，剩余51个为空。 **14. 假定在一棵二叉树中，度为2的结点数为15个，度为1的结点数为32个，则叶子结点个数为：** - **选项分析：** - **A**: 错误。叶子结点数量不是15。 - **B**: 正确。根据公式N0 = N2 + 1，叶子结点数量为15 + 1 = 16。 - **C**: 错误。叶子结点数量不是17。 - **D**: 错误。叶子结点数量不是18。 **15. 在下列情况中，可称为二叉树的是：** - **选项分析：** - **A**: 错误。每个结点至多有两棵子树的树不一定是二叉树。 - **B**: 正确。霍夫曼树是一种特殊的二叉树。 - **C**: 错误。每个结点都有两棵子树的有序树不一定是二叉树。 - **D**: 错误。每个结点只有一棵右子树的情况不一定是二叉树。 **16. 利用二叉链表存储树，则根结点的右指针是：** - **选项分析：** - **A**: 错误。根结点的右指针不是指向最左孩子。 - **B**: 错误。根结点的右指针不是指向最右孩子。 - **C**: 错误。根结点的右指针不是非空。 - **D**: 正确。在利用二叉链表存储树时，根结点的右指针通常是空的。 **17. 若二叉树的先序遍历序列和后序遍历序列正好相同则一定是一棵：** - **选项分析：** - **A**: 正确。若二叉树的先序遍历序列和后序遍历序列相同，则这棵树最多只有一个结点。 - **B**: 错误。若二叉树的先序遍历序列和后序遍历序列相同，不一定意味着结点均无左孩子。 - **C**: 错误。若二叉树的先序遍历序列和后序遍历序列相同，不一定意味着结点均无右孩子。 - **D**: 错误。若二叉树的先序遍历序列和后序遍历序列相同，不一定意味着任意一个结点的度不为2。 **18. 赫夫曼树中度为1的结点个数为：** - **选项分析：** - **A**: 错误。赫夫曼树中没有度为1的结点。 - **B**: 错误。赫夫曼树中没有度为1的结点。 - **C**: 正确。赫夫曼树中不存在度为1的结点。 - **D**: 错误。赫夫曼树中不存在度为1的结点。 **19. 设给定权值总数有n个，其哈夫曼树的结点总数为：** - **选项分析：** - **A**: 错误。哈夫曼树的结点总数可以确定。 - **B**: 正确。给定权值总数有n个时，哈夫曼树的结点总数为2n-1。 - **C**: 错误。哈夫曼树的结点总数不是2n+1。 - **D**: 错误。哈夫曼树的结点总数不是2n。 #### 二、判断题解析 **1. 树中元素之间是一对多的结构。** 正确。树结构的一个特点就是父节点可以拥有多个子节点。 **2. 二叉树不能顺序存储只能链式存储。** 错误。二叉树可以采用顺序存储方式，比如使用数组来存储二叉树的结点。 **3. 二叉树没有顺序存储方式，因为它是一种一对多的结构。** 错误。二叉树虽然是一种一对多的结构，但仍可以使用顺序存储方式来存储。 **4. 二叉树只能用二叉链表表示。** 错误。二叉树可以用多种方式表示，包括但不限于二叉链表、顺序存储等方式。 **5. 二叉树的叶子结点只能在最低层。** 错误。在某些情况下，如完全二叉树中，叶子结点也可能出现在倒数第二层。 **6. 二叉树的叶子结点不一定在最低层。** 正确。在某些情况下，叶子结点可能不在最低层，比如在完全二叉树中。 **7. 二叉树的叶子结点也可能在最顶层。** 错误。叶子结点定义为没有子节点的结点，因此不可能出现在最顶层。 **8. 完全二叉树中，若一个结点没有左孩子，则它必为叶子结点。** 正确。在完全二叉树中，如果一个结点没有左孩子，则它必然是叶子结点。 **9. 满二叉树的叶子结点都在同一层上。** 正确。满二叉树定义为除了最后一层外，每一层的节点数都是最大值，因此所有叶子结点都在同一层。 **10. 满二叉树一定是完全二叉树。** 正确。满二叉树是一种特殊的完全二叉树，即所有非叶子节点都有两个子节点，并且所有的叶子节点都位于同一层。