Page 114 - 高中 信息技术 选择性必修1 数据与数据结构

第四章 抽象数据类型

本章学业评价

同学们完成下列测试题（更多的测试题可以在教科书的配套学习资源包中查看），并

通过“本章扼要回顾”以及本章的项目活动评价，综合评价自己在信息技术知识与技能、
解决实际问题的过程与方法，以及相关情感态度与价值观的形成等方面，是否达到了本章
的学习目标。

1．单选题
（1）如果树的根算第一层，那么一棵n层的二叉树最多有（ ）个结点。
广东教育出版社
n
n
n
A. 2 -1 B. 2 C. 2 +1 D. 2 * n+1
（2）完全二叉树共有（2 * n-1）个结点，则它的叶结点数是（ ）个。
A. n-1 B. n C. 2 * n D. 2 * n-1
（3）已知包含七个结点的二叉树的先根遍历是1 2 4 5 6 3 7（数字为结点的编号，下

同），中根遍历是4 2 6 5 1 7 3，则该二叉树的后根遍历是（ ）。
A. 4 6 5 2 7 3 1 B. 4 6 5 2 1 3 7
C. 4 2 3 1 5 6 7 D. 4 6 5 3 1 7 2
2．思考题

抽象数据类型与一般数据类型的关系是什么？请举例说明。
3．情境题

小明和小白对二叉树的遍历产生了浓厚的兴趣，他们提出了以下问题：
（1）已知前序遍历序列为GDAFEMHZ，中序遍历序列为ADEFGHMZ，请画出这棵
二叉树。
（2）已知一棵二叉树的前序和中序遍历序列，能求出其后序遍历序列吗？其方案

唯一吗？

106 106

9 JOEE