《树与二叉树》作业 选择题 1. 下列哪种数据结构是非线性的？ A. 队列 B. 栈 C. 树 D. 数组 答案：C 解析：树是一种层次型的数据结构，每个节点可以有多个子节点，因此它是非线性的。 2. 二叉树中，一个节点的左子节点和右子节点分别称为该节点的： A. 父节点和兄弟节点 B. 子节点和父节点 C. 孩子节点和双亲节点 D. 左孩子和右孩子 答案：D 解析：在二叉树中，一个节点的左右子节点分别被称为该节点的左孩子和右孩子。 3. 完全二叉树的特点是： A. 所有叶子节点都在同一层 B. 每一层都是满的 C. 除了最后一层外，其他层都是满的，且最后一层的节点都靠左排列 D. 以上都不是 答案：C 解析：完全二叉树的定义是除了最后一层外，其他层都是满的，且最后一层的节点都靠左排列。 4. 在二叉搜索树（BST）中，对于任意一个节点，其左子树上的所有节点的值： A. 大于该节点的值 B. 小于该节点的值 C. 等于该节点的值 D. A和B都对 答案：B 解析：在二叉搜索树中，左子树上的所有节点的值都小于根节点的值。 5. 下列关于二叉树的叙述中，错误的是： A. 满二叉树一定是完全二叉树 B. 完全二叉树不一定是满二叉树 C. 完全二叉树的高度可以通过节点数计算得出 D. 满二叉树的节点数是2的幂次方减1 答案：D 解析：满二叉树的节点数是2的幂次方，而不是2的幂次方减1。 6. 如果一棵二叉树只有度为0的节点和度为2的节点，那么这棵二叉树一定是： A. 完全二叉树 B. 满二叉树 C. 二叉搜索树 D. 平衡二叉树 答案：B 解析：只有度为0的节点和度为2的节点意味着每个节点要么没有子节点（叶子节点），要么有两个子节点（内部节点），这是满二叉树的定义。 7. 在二叉树的顺序存储结构中，通常使用哪种方式来表示空指针？ A. 1 B. NULL C. 0 D. 答案：C 解析：在顺序存储的二叉树中，通常使用0来表示空指针。 8. 如果一棵二叉树的叶子节点是上一层节点数的两倍，则这棵树一定满足： A. 完全二叉树 B. 满二叉树 C. 二叉搜索树的性质 D. A和B都对 答案：A 解析：如果一棵二叉树的叶子节点是上一层节点数的两倍，这意味着除了最后一层外，其他层都是满的，且最后一层的节点都靠左排列，符合完全二叉树的定义。 9. 在二叉树的前序遍历中，访问节点的顺序是： A. 根 > 左 > 右 B. 左 > 根 > 右 C. 左 > 右 > 根 D. 右 > 根 > 左 答案：A 解析：前序遍历的顺序是先访问根节点，然后递归地访问左子树，最后递归地访问右子树。 填空题 1. 在二叉树中，没有子节点的节点称为_____。 答案：叶子节点或终端节点 解析：叶子节点是指没有子节点的节点。 2. 二叉树的遍历方式包括前序遍历、_____、后序遍历和层序遍历。 答案：中序遍历 解析：二叉树的遍历方式主要有四种：前序遍历、中序遍历、后序遍历和层序遍历。 3. 在完全二叉树中，如果一个节点的索引是i，则其左孩子的索引是_____。 答案：2i + 1 解析：在完全二叉树中，如果一个节点的索引是i，则其左孩子的索引是2i + 1，右孩子的索引是2i + 2。 4. 在二叉搜索树中，对于任意一个节点，其右子树上的所有节点的值_____该节点的值。 答案：大于等于 解析：在二叉搜索树中，右子树上的所有节点的值都大于等于根节点的值。 5. 满二叉树的第k层最多有_____个节点。 答案：2^(k1) 解析：满二叉树的每一层的节点数是上一层的两倍，第k层最多有2^(k1)个节点。 6. 若一棵二叉树采用二叉链表存储结构存储，则其每一个节点包含一个数据元素、一个指向其左孩子的指针和一个指向其_____的指针。 答案：右孩子 解析：二叉链表存储结构中，每个节点包含一个数据元素、一个指向左孩子的指针和一个指向右孩子的指针。 7. 在二叉树的层序遍历中，通常使用_____来实现。 答案：队列 解析：层序遍历是通过队列来实现的，从根节点开 ... ...
