全国自考数据结构导论（二叉树）模拟试卷1

37． 试编写出先序、中序和后序遍历的非递归算法。

36． 具有n个结点的完全二叉树，顺序存储在一维数组A[1…，z]中，设计算法将A中顺序存储变为二叉链表存储的二叉树。

32． 如下图所示，给出表达式树的前序遍历序列、中序遍历序列和后序遍历序列。

35． 对如下图所示的二叉排序树，给出删除关键字72后的二叉排序树。

30． 画出一棵后序遍历序列与中序遍历序列相同的二叉树。

31． 已知二叉树的前序遍历序列ABDGCEFH，中序遍历序列为DGBAECHF，请画出该二叉树，并给出后序遍历序列。

29． 若以{4，5，6，7，8}作为叶子结点的权值构造哈夫曼树，则其带权路径长度是________。

27． 若一个二叉树的叶子是某子树的中序遍历序列中的最后一个结点，则它必是该子树的_________序列中的最后一个结点。

28． 二叉树的先序序列和中序序列相同的条件是_______。

25． 在哈夫曼树中，权值校大的叶结点一定离根结点__________。

26． 哈夫曼树不存在度为_______的结点。

22． 根据遍历方法不同，线索二叉树分为______、________和_______。

23． 树的后序遍历序列与其对应二叉树的_________遍历序列相同。

24． 若二叉树的右子树为空，则与其对应的森林有________棵树。

20． 一棵二叉树的中序遍历序列为CAEFDRB，后序遍历序列为CFEDABR，则它的前序遍历序列为_________。

21． 已知采用顺序存储结构的一棵二叉树，其存储映像为

则其前序遍历序列为______。

17． 一棵具有10个结点的二叉树共有5个叶结点，则该二叉树有_______个度为2的结点，________个度为1的结点。

18． 一棵具有31个结点的满二叉树，它的高度是_______，共有_________个叶结点。

19． 若二叉树的中序遍历序列与后序遍历序列相同，则该二叉树一定满足_________。

15． 若一棵完全二叉树的结点个数为10，则编号最大的分支结点的编号为_________。

16． 已知采用二叉链表作为存储结构的一棵二叉树共有10个结点，则二叉链表中共有___________个指针域。

14． 以下图中，哪个是哈夫曼树__________。

12． 分别用下列序列构造二叉排序树，与用其他三个序列所构造的结果不同的是__________。

13． 有n个叶子的哈夫曼树的结点总数为_______个。

10． 具有n个结点的线索二叉树上，含有_________个线索。

11． 若对图中所示的二叉树进行中序线索化，则结点D的左右线索域的指针分别指向_______结点。

7． 在下列存储结构中，属于二叉树存储结构的是________。

9． 已知一棵二叉树的前序遍历序列与中序遍历序列相同，则该二叉树是___________。

8． 对下图所示的一棵二叉树进行遍历，得到的遍历序列为CADGEFB，则该遍历序列是______的结果。

5． 具有16个结点的满二叉树，其高度为________。

6． 二叉排序树根结点的左子树中所有结点关键字值_________右子树中所有结点的关键字值。

3． 已知一棵满二叉树有47个结点，则该二叉树有_______个叶子结点。

4． 若一棵二叉树有12个度为0的结点，6个度为1的结点，则有_______个度为2的结点。

1． 已知一棵高度为5的二叉树，则该二叉树的其结点总数为_______。

2． 按照二叉树的定义，具有4个结点的二叉树共有_______种。