资源简介

粤教版 选修1 第四章 抽象数据类型 单元练习
学校:___________姓名：___________班级：___________考号：___________
一、选择题
1．以下数据结构中不属于线性结构的是（ ）
A．数组 B．链表 C．队列 D．树
2．如图a为一棵二叉树，其数组实现示意图(部分)如图b 所示
图 a
0 1 2 3 4 5 …
A B C D E
图b
下列说法正确的是（ ）
A．该二叉树的前序遍历为ABCDEFG B．该二叉树的高度为 3
C．该二叉树是完全二叉树 D．节点 G 存储在数组下标为 11 的位置
3．设一棵二叉树的中序遍历序列：becfad，后序遍历序列：efcbda，则二叉树前序遍历序列为（ ）
A．abcdef B．bdaefc C．abcefd D．abcfed
4．已知一棵完全二叉树，其第 4 层有3个叶子节点，这棵二叉树的节点数量不可能是( )
A．25 B．24 C．11 D．10
5．已知7个结点的二叉树的前序遍历是 A B D E F C G（字母为结点的编号，以下同），中序遍历是D B F E A G C，则该二叉树的后序遍历是（ ）
A．D F E B G C A B．D F E B A C G C．F B C G E D A D．D F E C A G B
6．一棵度为3，深度为4的树，最多有（ ）个节点。
A．31 B．32 C．40 D．42
7．已知一棵二叉树的前序遍历为ABDECFG，中序遍历为DBEAFCG，则该二叉树的后序遍历序列为(　　)
A．DEBAFGC B．DEBFGCA C．DBEGFCA D．DEBFGCA
8．已知一棵二叉树的前序遍历序列为：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
9．一棵二叉树的前序遍历结果为JFDECBHAIG，中序遍历结果为DFEJAHBICG，则该二叉树的深度为（ ）
A．6 B．5 C．4 D．3
10．有一棵二叉树如图所示，该二叉树的后序遍历结果正确的是（ ）
A．XBCDAYEF B．FEYADCBX C．DBEAFXCY D．DEFABYCX
试卷第1页，共3页
试卷第1页，共3页
参考答案：
1．D
【详解】本题主要考查数据结构的描述。线性结构是一个有序数据元素的集合，如数组、链表和队列。树结构属于非线性结构，故本题选D选项。
2．D
【详解】本题主要考查二叉树的描述。由图可知，该二叉树的前序遍历为ABDCEGF；该二叉树的高度为 4；该二叉树是不完全二叉树；按照数组示意图，可知是逐层自左向右依次存储，没有的元素为空，可推得节点 G 存储在数组下标为 11 的位置，故本题选D选项。
3．C
【详解】本题主要考查二叉树的遍历。从后序遍历中，我们确定了根结点为a，在从中序遍历中得出 b-c-e-f 在根结点的左边，d在根结点的右边，那么我们就可以构建我们的二叉树的雏形。之后就是新根节点b，cef在根右。在之后就是新根c，e根左，f根右，如图所示： ，则二叉树前序遍历序列为abcefd，故本题选C选项。
4．C
【详解】本题主要考查二叉树。完全二叉树除了最后一层，是一棵满二叉树，其节点数为2^k- 1, k是层数，所以为2^3- 1 =7，然后加上第四层最少3个叶子为7+3=10 ,故最少给10个节点，由于是完成二叉树，每增加一个根节点则下面增加两个子节点，所以不可能是11个节点，故本题选C选项。
5．A
【详解】本题主要考查二叉树遍历。前序遍历是 A B D E F C G（即先遍历：根左右），中序遍历是D B F E A G C（左根右的方式），则可以画出该二叉树如下，则该二叉树的后序遍历是（即左右根的方式）：D F E B G C A，故本题选A选项。
6．C
【详解】本题主要考查数据结构。一棵度为3，深度为4的树，则第一层有1个根节点，第二层最多有3个子节点，第三层最多有3*3=9个子节点，第四层最多有3*9=27个子节点，则最多有1+3+9+27=40个节点，故本题选C选项。
7．B
【详解】本题主要考查二叉树的遍历。根据前序遍历为ABDECFG，中序遍历为DBEAFGC可画出该二叉树如下： ，则该二叉树的后序遍历序列为DEBFGCA，故本题选B选项。
8．B
【详解】本题主要考查二叉树的遍历。已知一棵二叉树的前序遍历序列为：A- B- D- C - E可以确定根节点为A，已知后序遍历序列为:D- B- E-C- A可以确定左子树的起点为B，无法确定左子树到哪里结束，同样无法确定右子树的开始节点。所以无法确定唯一性，中序遍历序列可能为:B- D- A- E- C，故本题选B选项。
9．B
【详解】本题主要考查二叉树的遍历。前序遍历是“根左右”，中序遍历是“左根右”，一棵二叉树的前序遍历结果为JFDECBHAIG，中序遍历结果为DFEJAHBICG，则该二叉树如下： 由图可知，该二叉树的深度为5，故本题选B选项。
10．D
【详解】本题主要考查二叉树的遍历。二叉树的后序遍历：即先左子树、再右子树、最后根，故该二叉树的后序遍历结果正确的是DEFABYCX，故本题选D选项。
答案第1页，共2页
答案第1页，共2页

展开更多......

收起↑