一、单项选择题（每题2分，共20分）

1、完全二叉树数组顺序存储，数组下标从1开始，父结点i的右孩子下标是？（） {{ select(1) }}

• i*2
• i*2+1
• i/2
• i‑1

2、结构体数组存储二叉树，用什么值代表该位置为空子树？（） {{ select(2) }}

• 1
• 0
• -1
• 99

3、已知先序+中序序列构建二叉树，先序序列的哪一个字符是根结点？（） {{ select(3) }}

• 最后一个字符
• 第一个字符
• 中间位置字符
• 任意随机字符

4、已知后序+中序序列构建二叉树，后序序列的哪一个字符是根结点？（） {{ select(4) }}

• 第一个字符
• 中间字符
• 最后一个字符
• 第二个字符

5、在先序、中序构建二叉树代码中，变量len代表的含义是？（） {{ select(5) }}

• 二叉树总结点数
• 根结点左子树结点个数
• 右子树结点个数
• 树的高度

6、扩展二叉树使用特殊符号标记空结点，下面一般不会用来标记空结点的是？（） {{ select(6) }}

• #
• .
• A
• *

7、根据扩展先序序列构建二叉树，递归遇到空标记字符，返回值为？（） {{ select(7) }}

• 0
• -1
• 1
• p

8、扩展后序序列构建二叉树，读取字符遍历方向是？（） {{ select(8) }}

• 从左向右
• 从右向左
• 从中间向两边
• 随机读取

9、构建二叉树的全局变量p在代码中的作用是？（） {{ select(9) }}

• 保存根结点下标
• 记录数组中下一个可用的结点下标
• 保存树的高度
• 记录序列字符串长度

10、下面哪一组序列组合不能唯一确定一棵二叉树？（） {{ select(10) }}

• 先序 + 中序
• 后序 + 中序
• 先序 + 后序（普通二叉树，无扩展标记）
• 扩展先序序列

二、判断题（每题2分，共10分）

11、普通二叉树都可以直接使用一维数组顺序存储，空间利用率很高。（） {{ select(11) }}

• 正确
• 错误

12、先序+中序构建二叉树，需要在中序序列找到根的位置，划分左右子树。（） {{ select(12) }}

• 正确
• 错误

13、扩展二叉树需要给所有缺失的孩子位置补充空结点标记。（） {{ select(13) }}

• 正确
• 错误

14、扩展先序构建二叉树时，递归函数内部先构建右子树，再构建左子树。（） {{ select(14) }}

• 正确
• 错误

15、后序加中序构建二叉树时，需要先划分中序的左右子树，再确定后序里面左右子树的边界。（） {{ select(15) }}

• 正确
• 错误