选择性必修一 第四章 抽象数据类型-普通高中春招考试备考教材 信息技术（第六版）

（2）a、c、b、e、d 第四章　抽象数据类型 一、认识抽象数据类型 抽象数据类型是指由一种数据结构和在其上的一组操作所组成的、并不具体关心数据 的存储结构和操作的具体实现的抽象数据结构。 定义抽象数据类型的基本格式： ADT 抽象数据类型名 　｛ 　数据：<数据描述> 　操作：<基本操作的定义> 　｝ADT 抽象数据类型名 例如，长方形可以抽象为（以 Python 为例）： class rectangle（object）： 　　def __init__（self，a，b）： 　　　　self.a=a 　　　　self.b=b 　def area（self）： 　　　　s=self.a*self.b 　　　　return s 　　def perimeter（self）： 　　　　c=2*self.a+2self.b 　　　　return c 二、用抽象数据类型表示队列和栈 1.用抽象数据类型表示队列 ADT 队列 　　｛ 数据： 　　　　队列元素； 　　　　队头； 82 选择性必修一　数据与数据结构　 　　　　队尾； 　　　操作： 　　　　初始化； 　　　　入队； 　　　　出队； 　　　　求长度； 　　　　判断空； 　　　　判断满； 　　｝ADT 队列 2.用抽象数据类型表示栈 ADT 栈 　　｛ 数据： 　　　　栈元素； 　　　　栈顶； 　　　　栈底； 　　　操作： 　　　　初始化； 　　　　入栈； 　　　　出栈； 　　　　判断空； 　　　　判断满； 　　｝ADT 栈 三、用抽象数据类型表示二叉树 1.树的定义 树是 n（n≥0）个节点的有限集。在任意一棵非空树中：①有且仅有一个特定的称为根的 节点；②当 n＞1 时，其余节点分为 m（m>0）棵互不相交的有限子树，每棵子树又是一棵树。 2.树的基本概念 （1）节点的度：每个节点具有的子树。 （2）分支节点：度为 0 的节点；叶子节点：度大于 0 的节点。 （3）孩子节点、双亲节点、兄弟节点：在一棵树中，每个节点的子树的根，称为该节点的孩 子节点，相应地，该节点被称为孩子节点的父节点。具有同一父节点的孩子节点互称兄弟 节点。 （4）树的深度：树中所有节点的最大层数。 83 3.二叉树的定义 树中每一个节点数最大度数为 2，有左子树或右子树。 4.二叉树的抽象数据类型 二叉树的抽象数据类型的数据部分为一棵用任一种方式表示的二叉树，操作包括初始 化二叉树、建立二叉树、遍历二叉树、查找二叉树、输出二叉树和清除二叉树等。 5.二叉树的遍历 若用 L、D、R 分别表示遍历左子树、访问根结点、遍历右结点，则对于一棵非空二叉树的 遍历有 DLR、DRL、LDR、LRD、RDL、RLD 六种情况。若限定先左后右，则只有三种情况即 DLR（前序遍历）、LDR（中序遍历）、LRD（后序遍历），如图所示。给定了二叉树的任何一种 遍历序列，都无法唯一确定相应的二叉树。但是如果知道了二叉树的中序遍历序列和任意 的另一种遍历序列，就可以唯一地确定二叉树。 先（根）序遍历（根左右）：A B D H E I C F J K G 中（根）序遍历（左根右）： D H B E I A J F K C G 后（根）序遍历（左右根）： H D I E B J K F G C A 随堂练习 一、单项选择题 1. 用抽象数据类型表示栈时，其数据部分不包括（　　）。 A. 栈底 B. 栈顶 C. 数据元素 D. 求栈的长度 2. 中序遍历二叉树，首先访问的是（　　）。 A. 树的根节点 B. 左子树的左边叶子节点 C. 左子树的根节点 D. 左子树的右边叶子节点 3. 下列选项中，说法错误的是（　　）。 A. 完全二叉树包含满二叉树 B. 二分查找又称折半查找，查找前必须先排序 C. 迭代和递归都是非常实用的算法之一，累加、累乘就是递归的应用 D. 在同种类型的数据结构中，地址 a 中存储的是数据 5，地址 b 中存储的数据是 13243424，地址 b 中的数据元素所占的空间和地址 a 中的数据元素所占的空间一 样大 4. 按照二叉树的定义，具有 3 个节点的二叉树有（　　）种。 84 选择性必修一　数据与数据结构　 A.3 B.4 C.5 D.6 5. 以下选项中，不属于完全二叉树的是（　　）。 A. B. C. D. 6. 如果树的根算第一层，那么一棵 n 层的二叉树最多有（　　）个节点。 A.2n-1 B.2n C.2n+1 D.2*n+1 7. 已知包含 7 个节点的二叉树的先根遍历是 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 二、判断题 8. 一般数据类型通常由具体语言系统内部定义，直接提供给用户使用，抽象数据类型通 常由用户自定义。 （　　） 9. 二叉树至少有一个根节点。 （　　） 10. 满二叉树一定是一个完全二叉树。 （　　） 11. 二叉树的叶子节点就是度为 0 的节点。 （　　） 三、填空题 12. 抽象数据类型通常由用户自行定义，包括定义其所包含的数据和在这些数据上所进 行的　　　　。 13. 一棵深度为 n 的满二叉树，共有　　　　个节点。 14. 第 k 层二叉树上最多有　　　　个节点 （k≥1）。 四、应用题 15. 写出下列树形结构的前、中、后序遍历序列。 85 16. 有一棵二叉树，先序遍历序列为 ABDGCEF，中序遍历序列为 DGBAECF，请画出该二 叉树，并写出后序遍历序列。 17. 建立一棵二叉树的示意图，使其中序遍历的结果为 a*b+c/d。 18. 把一个算术表达式表示成一棵二叉树：运算符作为根节点，运算符的前后两个运算 对象分别作为根的左、右两棵子树。请你写出图中二叉树所表示的算术表达式。 第五章　数据结构的应用 一、迭代与递归 1.迭代 迭代是重复反馈过程的活动，其目的通常是为了逼近所需目标或结果。每一次对过程 的重复称为一次迭代，而每一次迭代得到的结果会作为下一次迭代的初始值。 【例】s=1+2+3+…+100 在 Python 中的程序段为： s=0 for i in range（101）： 　 s=s+1 86 第四章 抽象数据类型 四、随堂练习 （一）选择题 1-5 DBCCC 6-7AA （二）判断题 8-11 ✔✖✔✔ （三）填空题 12. 操作 13.-1 14. （四）应用题 15.前：ABDECFG 中：DBEACGF 后：DEBGFCA 16.后：GDBEFCA 图： 17. 18.（a-b)*((c-d/e)/f) 学科网（北京）股份有限公司 $$