第四章 抽象数据类型 2023-2024学年高中信息技术粤教版(2019) 选修1

第四章 抽象数据类型 一、选择题 1．一棵包含10个节点的完全二叉树，其叶子节点的个数为（　　） A．3 B．4 C．5 D．6 2．表达式树是包含表达式的数据结构，表达式树对于一些高性能的场景下有较大实用性。如图所示，一个数学表达式可以用一棵表达式树来表示。下列关于该表达式树的描述中不正确的是（　　） A．表达式树的根节点左右子树的深度差不会超过1 B．对该表达式树进行后序遍历得到的后序表达式，实现了无括号处理和优先级处理 C．该表达式树对应的表达式为(6-3)/2+5*(7+2)/8 D．该表达式树中的内部节点比分支节点少一个 3．某二叉树的中序遍历结果为DBEAFGC，后序遍历结果为DEBGFCA，则前序遍历结果为（   ） A．ABDECFG B．ABCDEFG C．ABEDFCG D．ABDECGF 4．某二叉树按从上而下、自左往右的顺序，对节点进行编号，数组存储示意图如下： 0 1 2 3 4 5 6 7 8 A B C D E F G 下列关于该二叉树，说法正确的是（   ） A．该二叉树的叶子节点有4个，分别是C，E，F，G B．该二叉树后序遍历结果为FGDBECA C．该二叉树共有4层，E和F位于同一层 D．该二叉树共有3对兄弟节点 5．某完全二叉树共有300个节点，该二叉树的高度是（    ） A．8 B．9 C．10 D．11 6．由3个结点可以构造出（   ）种不同的二叉树。 A．2 B．3 C．4 D．5 7．下列关于二叉树，说法不正确的是（   ） A．用数组的方式存储二叉树，容易造成空间浪费 B．若有前序和中序遍历可以推导出一棵唯一的二叉树 C．只有最下面两层有叶子节点的二叉树称为完全二叉树 D．完全二叉树的第3层有3个叶子节点，则该树的节点数量可能是8 8．待入栈的序列a有多种出栈序列，以下函数用于判断序列b是否是a的出栈序列，代码如下： python 12.py [2，5，4，3，1]是[1，2，3，4，5]的出栈序列 python 12.py [5，2，3，1，4]不是[1，2，3，4，5]的出栈序列 图2 def judge（a，b）： n=len（a）；st=[-1] *n top=-1；i=j= 0 while i<n： top+=1 ① i+=1 while top>-1 and ② ： top-=1 j+=1 return top==-1 from random import shuffle a=[1，2，3，4，5] b=[1，2，3，4，5] shuffle（b）                    #将序列b的元素随机排序 if judge（a，b）： print（b，'是'，a，'的出栈序列'） else： print（b，'不是'，a，'的出栈序列'） 程序运行结果如第12题图所示。划线处应填写的语句是 A．①st[top]=a[i]        ②st[top]==b[j] B．①st[top]=a[i]    ②st[-1]==b[j] C．①st[top]=b[i]        ②st[top]=a[j] D．①st[top]=b[i]    ②st[-1]==a[j] 9．用数组表示二叉树的示意图如下所示：（    ） 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 B D A E F C 下列说法正确的是（    ） A．该二叉树的深度为3 B．该二叉树是完全二叉树 C．该二叉树有4个叶子节点 D．该二叉树后序遍历的结果为DCEFAB 10．某二叉树的树形结构如下图所示，后序遍历结果为“WUSVTR”，则该二叉树的前序遍历结果为（   ） A．RSTUVW B．RTSVUW C．RTSUWV D．RSUWTV 11．已知一棵完全二叉树共有200个节点，下列说法正确的是（    ） A．该完全二叉树的高度为7 B．该完全二叉树有99个叶子节点 C．该完全二叉树有100个度为2的节点 D．该完全二叉树有1个度为1的节点 12．某二叉树前序遍历为ABDCE，后序遍历为DBECA，则该二叉树可能情况有多少种（   ） A．1 B．2 C．4 D．6 13．某完全二叉树的后序遍历为EBAGDC，则下列说法正确的是（    ） A．该树的深度为4 B．该树有2个叶子节点 C．该树的节点B、G是兄弟节点 D．删除节点E后，该树的前序遍历为CABDG 14．表达式(3+5)*4-8/2的后缀表达式为（   ） A．3 5 + 4 * - 8 2 / B．3 5 + 4 * 8 - 2 / C．3 5 + 4 * 8 2 - / D．3 5 + 4 * 8 2 / - 15．已知一棵二叉树的前序遍历序列为：A-B-D-C-E，后序遍历序列为：D-B-E-C-A，则该二叉树是否 能唯一确定？中序遍历序列是？（   ） A．能唯一确定，中序遍历序列为：B-D-A-E-C B．不能唯一确定， 中序遍历序列可能为： B-D-A-E-C C．能唯一确定，中序遍历序列为：D-C-B-A-E D．不能唯一确定， 中序遍历序列可能为： D-C-B-A-E 16．某二叉树前序遍历的结果为“ABCDEF”，后序遍历的结果为“BEFDCA”，则中序遍历的结果可能是（    ） A．CBDAEF B．CBAEDF C．BAEDFC D．BADCEF 17．一棵二叉树的前序遍历结果为JFDECBHAIG，中序遍历结果为DFEJAHBICG，则该二叉树的深度为（    ） A．6 B．5 C．4 D．3 18．如图所示的二叉树，下列说法正确的是（   ） A．该二叉树是一个完全二叉树 B．该二叉树的深度为4，节点D的度为2 C．该二叉树的叶子节点数比非叶子节点数少一个 D．该二叉树中A是D和E的父节点 19．某二叉树的树形结构如图所示，其后序遍历结果为FBCEAD，则前序遍历结果为（    ） A．ABCDEF B．FEDCBA C．DFACBE D．FDBCAE 20．某二叉树的前序遍历结果为ABC，若该二叉树不是满二叉树，则其后序遍历结果为（    ） A．ABC B．BCA C．CBA D．CAB 试卷第1页，共3页 试卷第1页，共3页 学科网（北京）股份有限公司 参考答案： 1．C 【详解】本题考查的二叉树相关知识。一个具有n个节点的完全二叉树，其其叶子节点的个数为：n/2向上取整，或(n+1)/2向下取整。10/2=5，故选项C正确。 2．A 【详解】本题主要考查树结构。表达式树的根节点左右子树的深度差可以超过1；对该表达式树进行后序遍历得到的后序表达式，实现了无括号处理和优先级处理；该表达式树对应的表达式为(6-3)/2+5*(7+2)/8；该表达式树中的内部节点比分支节点少一个，故本题选A选项。 3．A 【详解】本题考查树的遍历相关知识。 已知中序遍历规则“左根右”和后序遍历规则“左右根”可知：根节点为A，左子树为DBE右子树为 FGC。以此画出二叉树如下： 故其前序遍历结果为：ABDECFG。答案选A。 4．B 【详解】本题考查二叉树。由题意可知， 二叉树如图所示。A选项错误，该二叉树的叶子节点有3个。B选项正确，该二叉树后序遍历结果为FGDBECA。C选项错误，该二叉树共有4层，E和F不位于同一层。D选项错误，该二叉树共有2对兄弟节点。故答案为：B。 5．B 【详解】本题主要考查二叉树的描述。完全二叉树，高度是[log2N]+1，以2为底的对数取整后+1。故该完全二叉树的高度为h=log2300 + 1=9。故本题应选B。 6．D 【详解】本题考查的是二叉树相关知识。五种情况如下： 故选D。 7．C 【详解】本题考查二叉树的存储、遍历及完全二叉树的相关内容。使用数组存储二叉树时，若为一般非完全二叉树，则需要添加一些并不存在的空节点，会造成存储空间的浪费，选项A说法正确；可以由前序、中序遍历序列或中序、后序遍历序列唯一确定一颗二叉树，选项B说法正确；完全二叉树的定义是一个深度为k的有n个节点的二叉树，对树中的节点按从上至下、从左到右的顺序进行编号，如果编号为i(1≤i≤n)的结点与满二叉树中编号为i的结点在二叉树中的位置相同。选项虽然明确最下面两层有叶子节点，但未明确所有叶子节点按照从上至下、从左到右的顺序排列，选项C说法错误；完全二叉树第3层为叶子节点，说明前两层为满二叉树，由此得出，该数叶子节点为8，选项D说法正确。故答案为C选项。 8．A 【详解】本题考查栈的相关知识。根据题干、代码段可以得出：序列b进行随机排序，a序列借助顺序栈st进行入栈、出栈操作，过程中，将出栈元素与随机排序后的序列b进行对比，若对应两个元素相等，则输出b序列是a的出栈序列，否则输出b序列不是a的出栈序列。故①处操作应该是对a序列元素入栈，即st[top]=a[i]，②处是判断栈顶元素与b序列对应位置元素是否相等，即st[top]==b[j]。正确答案是A选项。 9．D 【详解】本题考查的是二叉树。依据题意可知二叉树为： 故其深度为4；不是完全二叉树；该二叉树有3个叶子节点；该二叉树后序遍历的结果为DCEFAB。故选D。 10．D 【详解】本题考查二叉树相关内容。通过观察该二叉树树型结构及分析其后序遍历序列，可得该二叉树具体形态为：   故其前序遍历序列为：RSUWTV。 11．D 【详解】本题主要考查二叉树的描述。该完全二叉树的高度为h=log2n + 1=8；该完全二叉树有200/2=100个叶子节点；由n0=n2+1，因此该完全二叉树有100-1=99个度为2的节点；由n=n0+n1+n2，得到该完全二叉树有200-100-99=1个度为1的节点，故本题选D选项。 12．C 【详解】本题考查二叉树相关内容。根据前序遍历和后序遍历构造二叉树，第一件事一定是找根节点，然后想办法确定左右子树的范围，我们可以根据，前序遍历和后序遍历的特点，前序遍历为【根→左子树→右子树】，后序遍历为：【左子树→右子树→根】，前序遍历和后序遍历中各自的左子树区间的长度肯定是相等的，但是其字母顺序可能是不同的。第一步确定A是根节点，然后确定BD是左子树，CE是右子树。如果BDC是左子树的话，那么后序遍历应DBC而后序遍历为DBE。故BD是左子树，CE是右子树，且B和C分别是左子树和右子树的跟。接下来剩下的D和E分别可能是B和C的左子树或右子树，共有4中情况。如下图 。故本题答案是C选项。 13．D 【详解】本题考查二叉树相关内容。由于是完全二叉树，该树的模型已经确定，根据后序遍历可知该二叉树为 ，该树深度为3，有3个叶子节点，节点B、G是堂兄弟节点，不是兄弟节点，ABC选项说法错误。删除节点E后，该树的前序遍历为CABDG，D选项说法正确。故本题答案是D选项。 14．D 【详解】本题考查二叉树相关内容。将原式按二叉树展开如下图所示: 然后后序遍历可得后缀表达式，因此后缀表达式为“3 5 + 4 * 8 2 / -”，故本题答案为D选项。 15．B 【详解】本题主要考查二叉树的遍历。已知一棵二叉树的前序遍历序列为：A- B- D- C - E可以确定根节点为A，已知后序遍历序列为:D- B- E-C- A可以确定左子树的起点为B，无法确定左子树到哪里结束，同样无法确定右子树的开始节点。所以无法确定唯一性，中序遍历序列可能为:B- D- A- E- C，故本题选B选项。 16．C 【详解】本题主要考查二叉树的遍历。前序遍历的第一个和后序遍历的最后一个一定是树根，前序遍历的第二个不是左子树的根就是右子树的根，如果前序遍历第二个与后序遍历的倒数第二个相同则他是根的右子树否则是根的左子树，因此B是左子树的根，同理可以判断C是右子树的根。结合选项可知，只有选项C，BAEDFC符合题意，故本题选C选项。 17．B 【详解】本题主要考查二叉树的遍历。前序遍历是“根左右”，中序遍历是“左根右”，一棵二叉树的前序遍历结果为JFDECBHAIG，中序遍历结果为DFEJAHBICG，则该二叉树如下： 由图可知，该二叉树的深度为5，故本题选B选项。 18．C 【详解】本题考查的是二叉树。完全二叉树是由满二叉树而引出来的，若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1)) 的结点数都达到最大个数(即1~h-1层为一个满二叉树)，第 h 层所有的结点都连续集中在最左边，这就是完全二叉数。图中所示的二叉树不是一个完全二叉树；该二叉树的深度为4，节点D的度为1；该二叉树的叶子节点数（3）比非叶子节点数（4）少一个；A是B和C的父节点。故本题应选C。 19．C 【详解】 本题考查二叉树的前序遍历。后序遍历规则为“左右根”，已知后序遍历结果为FBCEAD，结合题干中树形结构图可知该二叉树的树形结构应为：，前序遍历规则为“根左右”，根据完整的二叉树结构图，得出前序遍历为DFACBE。故答案为C选项。 20．C 【详解】本题考查的是二叉树。前序遍历结果为ABC，不是满二叉树，故其树可能为： 其后序遍历结果都为：CBA。故本题应选C。 答案第1页，共2页 答案第1页，共2页 学科网（北京）股份有限公司 $$