树和二叉树练习课件.ppt

1、树和二叉树练习树和二叉树练习一、选择题一、选择题 1.有一有一“遗传遗传”关系：设关系：设x是是y的父亲，则的父亲，则x可可以把它的属性遗传给以把它的属性遗传给y。表示该遗传关系最合表示该遗传关系最合适的数据结构为（适的数据结构为（）。）。A 向量向量 B.树树 C.图图 D二叉树二叉树 B 2.树最合适用来表示（树最合适用来表示（）。）。A.有序数据元素有序数据元素 B.元素之间具有分支层次关系的数据元素之间具有分支层次关系的数据C.无序数据元素无序数据元素 D.元素之间无联系的数据元素之间无联系的数据.B 3.树树B的层号表示为的层号表示为1a,2b,3d,3e,2c,对应于下面选对应于下

2、面选择的（择的（）。）。A.1a(2b(3d,3e),2c)B.a(b(D.,e),c)C.a(b(d,e),c)D.a(b,d(e),c)c 4.对二叉树的结点从对二叉树的结点从1开始连续编号，要求每个开始连续编号，要求每个结点的编号大于其左，右孩子的编号，同一结结点的编号大于其左，右孩子的编号，同一结点的左，右孩子中，其左孩子编号小于其右孩点的左，右孩子中，其左孩子编号小于其右孩子编号，则可采用（子编号，则可采用（）次序的遍历实现二叉）次序的遍历实现二叉树的结点编号。树的结点编号。A.先序先序 B.中序中序 C.后序后序 D.从根开始按层次遍历从根开始按层次遍历C 5.假定一棵三叉树的结点

3、为假定一棵三叉树的结点为50，则它，则它的最小高度为（的最小高度为（）。）。A.3 B.4 C.5 D.6C 6.在一棵具有在一棵具有K层的满三叉树中，结点总层的满三叉树中，结点总数为（数为（）A.(3k-1)/2 B.3k-1 C.(3k-1)/3 D.3kA 7.按照二叉树的定义，具有按照二叉树的定义，具有3个结点的个结点的二叉树有（二叉树有（）种。）种。A.3 B.4 C.5 D.6C 8.在一棵有在一棵有n个结点的二叉树中，若度为个结点的二叉树中，若度为2的的结点数为结点数为n2，度为度为1的结点数为的结点数为n1,度为度为0的结的结点数为点数为n0，则树的最大高度为（则树的最大高度为

4、（），其叶），其叶结点数为（结点数为（）；树的最小高度为（）；树的最小高度为（），），其叶结点数为（其叶结点数为（）；若采用链表存储）；若采用链表存储结构，则有（结构，则有（）个空链域。）个空链域。A.n/2 B.log2 n+1 C.log2 n D.nE.n0+n1+n2 F.n1+n2 G.n2+1 H.1I.n+1 J.n1 K.n2 L.n1+1EGBGI9.对一个满二叉树，对一个满二叉树，m个树叶，个树叶，n个结点，个结点，深度为深度为h,则则（）。）。A.n=h+m B.B.h+m=2n C.C.m=h-1 D.D.n=2h 1D 10.设高度为设高度为h的二叉树中只有度为的二叉

5、树中只有度为0和度为和度为2 的结点，则此类二叉树中所包含的结点的结点，则此类二叉树中所包含的结点数至少为（数至少为（），至多为（），至多为（）。）。A.2h B.2h 1 C.2h+1 D.h+1 E.2h-1 F.2h 1 G.2h+1+1 H.2h+1 BF 11.在一棵二叉树上第在一棵二叉树上第5层的结点数最层的结点数最多为（多为（）。（假设根结点的层数）。（假设根结点的层数为为0）A.8 B.16 C.15 D.32B 12.深度为深度为5 的二叉树至多有（的二叉树至多有（）个结点。个结点。A.16 B.32 C.31 D.10C 13.一棵有一棵有124个叶结点的完全二叉树，个叶结

6、点的完全二叉树，最多有（最多有（）个结点。个结点。A.247 B.248 C.249 D.250 E.251B 14.含有含有129个叶结点的完全二叉树，个叶结点的完全二叉树，最多有（最多有（）个结点。）个结点。A.254 B.255 C.256 D.257 E.258D 15.假定在一棵二叉树中，双分支结点数为假定在一棵二叉树中，双分支结点数为15，单分支结点数为，单分支结点数为30个，则叶子结点数个，则叶子结点数为（为（）个。）个。A.15 B.16 C.17 D.47B 16.用顺序存储的方法将完全二叉树中所有用顺序存储的方法将完全二叉树中所有结点逐层存放在数组结点逐层存放在数组R1n中

7、，结点中，结点Ri若有左子树，则左子树是结点（若有左子树，则左子树是结点（）。）。A.R2i+1 B.R2i C.Ri/2 D.R2i-1B 17.在一非空二叉树的中序遍历序列中，在一非空二叉树的中序遍历序列中，根结点的左边（根结点的左边（）A.只有右子树上的所有结点只有右子树上的所有结点 B.只有右子树上的部分结点只有右子树上的部分结点C.只有左子树上的部分结点只有左子树上的部分结点 D.只有左子树上的所有结点只有左子树上的所有结点A 18.任何一棵二叉树的叶结点在先序，任何一棵二叉树的叶结点在先序，中序和后序遍历中的相对次序（中序和后序遍历中的相对次序（）。）。A不发生改变不发生改变 B.

8、发生改变发生改变 C.不能确定不能确定 D.以上都不对以上都不对A19.设设n,m为一棵树上的两个结点，在为一棵树上的两个结点，在中序遍历时，中序遍历时，n在在m前的条件是（前的条件是（）。）。A.n在在m右方右方 B.n是是m祖先祖先 B.C.n在在m左方左方 D.n是是m 子孙子孙C 20.一棵完全二叉树按层次遍历的序列一棵完全二叉树按层次遍历的序列为为ABCDEFGHI，则在先序遍历中结则在先序遍历中结点点E 的直接前趋为（的直接前趋为（），后序遍历），后序遍历中结点中结点B 的直接后继是（的直接后继是（）。）。（1）B （2）D （3）A（4）I（5）F（6）C(4)(5)21.已知某

9、二叉树的后序遍历是已知某二叉树的后序遍历是d a b e c，中序遍历序列是中序遍历序列是d e b a c，它的前它的前序遍历序列是（序遍历序列是（）。）。A.acbed B.decab C.deabc D.cedbaD 22.二叉树采用二叉链表作存储结构，二叉树采用二叉链表作存储结构，要交换其所有分支结点左右子树的位要交换其所有分支结点左右子树的位置，利用（置，利用（）遍历方法最合适。）遍历方法最合适。A.前序前序 B.中序中序 C.后序后序 D.层次层次C 23.欲实现任意二叉树的后序遍历的非欲实现任意二叉树的后序遍历的非递归算法而不必使用栈结构，最佳方递归算法而不必使用栈结构，最佳方案

10、是二叉树采用（案是二叉树采用（）存储结构。）存储结构。A.三叉链表三叉链表 B.广义表广义表 C.二叉链表二叉链表.顺序顺序A 24.在线索化二叉树中，所指结点没在线索化二叉树中，所指结点没有左子树的充要条件是（有左子树的充要条件是（）。）。.Tleft=NULL B.Tltag=1 C.Tltag=1 且且Tleft=NULL D 以上都不对以上都不对B 25.线索二叉树是一种（线索二叉树是一种（）结构。）结构。.逻辑逻辑 .逻辑和存储逻辑和存储.物理物理D.线性线性C 26.将图将图6-6中的二叉树按中序线索化，中的二叉树按中序线索化，结点结点X的右指针和的右指针和Y 的左指针分别指的左指

11、针分别指向（向（）。）。（1）A，D (2)B,C (3)D,A （4）C，A(3)ABDCXEY图图6-6 27.在下列三次序的线索二叉树中在下列三次序的线索二叉树中（），对查找指定结点在该次序），对查找指定结点在该次序下的后继效果较差。下的后继效果较差。A.前序线索树前序线索树 B.中序线索树中序线索树 C.后序线索树后序线索树C 28.设中序线索二叉树设中序线索二叉树T是按是按lchild-rchild表表示法存储，欲确定示法存储，欲确定T中结点中结点p在前提下的后在前提下的后继，下述说法不正确的是（继，下述说法不正确的是（）。）。A.若若p有左子女，则该后继为有左子女，则该后继为p的左

12、子女的左子女B 若若p无左子女且有右子女，则该后继无左子女且有右子女，则该后继为为p的右子女的右子女C 若若p无左子女且无右子女，则该后继无左子女且无右子女，则该后继为为p的右线索所指结点的右线索所指结点D.若若p无左子女，从结点无左子女，从结点p开始，追综开始，追综rchild链，直到链，直到rchild不是线索，则这时不是线索，则这时rchid（若不为若不为NULL）所指结点为该后继。）所指结点为该后继。C 29.树的基本遍历策略可分为先根遍历和后树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先根遍历；二叉树的基本遍历策略可分为先序遍历，中序遍历和后序遍历。这里，把序

13、遍历，中序遍历和后序遍历。这里，把由树转化得到的二叉树叫做这棵树对应得由树转化得到的二叉树叫做这棵树对应得二叉树。下面结论正确的是（二叉树。下面结论正确的是（）。）。A树的先根遍历序列与其对应的二叉树树的先根遍历序列与其对应的二叉树的先序遍历序列相同的先序遍历序列相同B树的后序遍历序列与其对应的二叉树树的后序遍历序列与其对应的二叉树的后序遍历序列相同的后序遍历序列相同C树的先根遍历序列与其对应的二叉树树的先根遍历序列与其对应的二叉树的中序遍历序列相同的中序遍历序列相同D以上都不对以上都不对A 30.如果如果T2 是由有序树是由有序树T转换而来的二转换而来的二叉树，那么叉树，那么T 中结点的前序

14、就是中结点的前序就是T2中中结点的（结点的（）。）。A前序前序 B.中序中序 C.后序后序 D.层次序层次序 A 31.如果如果T2 是由有序树是由有序树T转换而来的二转换而来的二叉树，那么叉树，那么T 中结点的后序就是中结点的后序就是T2中中结点的（结点的（）。）。A前序前序 B.中序中序 C.后序后序 D 层次序层次序B 32.如图如图6-7所示的所示的t2是由有序树是由有序树t1转化转化而来的二叉树，那么树而来的二叉树，那么树t1有（有（）个）个叶结点。叶结点。A.4 B.5 C.6 D.7C图6-7abecfhigdj 33.设设T是哈夫曼树，具有是哈夫曼树，具有5个叶结点，个叶结点，

15、树树T的高度最高可以是（的高度最高可以是（）。）。A.1 B.2 C.3D.4 E.5.6D,E 34.由带权为，的四个叶由带权为，的四个叶子结点构造一棵哈夫曼树，该树的带子结点构造一棵哈夫曼树，该树的带权路径长度为（权路径长度为（）。）。.23 B.37 C.46 D.43D 35.若只考虑有序树的情形，则具有若只考虑有序树的情形，则具有个结点的不同形态的树共有（个结点的不同形态的树共有（）种。）种。A.132 B.154.C.429 D.前三者均不正确前三者均不正确A 36.树的后根遍历序列等同于该树对应树的后根遍历序列等同于该树对应的二叉树的（的二叉树的（）先序遍历先序遍历.中序遍历中序

16、遍历.后序遍历后序遍历.层次遍历层次遍历B二、填空题二、填空题 1.在 树 形 结 构 中，树 根 结 点 没 有在 树 形 结 构 中，树 根 结 点 没 有_结点，其余每个结点有且只有结点，其余每个结点有且只有_个前趋结点；叶子结点没有个前趋结点；叶子结点没有_结点，其余每个结点的后继结点可以结点，其余每个结点的后继结点可以_。前趋前趋1 1后继后继任意多个任意多个 2.有一棵树如图所示，回答下面的问题。有一棵树如图所示，回答下面的问题。这棵树的根点是这棵树的根点是_;_;这棵树的叶子结点是这棵树的叶子结点是_;_;结点结点k3k3的度是的度是_;_;这棵树的度为这棵树的度为_;_;这棵树

17、的深度为这棵树的深度为_;_;结点结点k3k3的子女是的子女是_;_;结点结点k3k3的父结点是的父结点是_k1k1k2,k5,k7,k4k2,k5,k7,k42 23 34 4K5K5,k6k6k1k1 图6-8k1k2k4k3k5k6k7 3.假 定 一 棵 树 的 广 义 表 表 示 为假 定 一 棵 树 的 广 义 表 表 示 为A(B(E),C(F(H,I,J),G),D),则该树的度为则该树的度为_;树树的深度为的深度为_,终端结点的个数为终端结点的个数为_，单分支，单分支结点的结点的 个数为个数为_,双分支结点的个数为双分支结点的个数为_,三分支结点的个数为三分支结点的个数为_,

18、C结点的双亲结点为结点的双亲结点为_,其孩子结点为其孩子结点为_和和 _结点。结点。3 34 46 61 11 12 2A AF FG G 4.设树设树T中除叶结点外，任意结点的度数是中除叶结点外，任意结点的度数是3，则则T的第的第i层结点的个数为层结点的个数为_。（假设根结点。（假设根结点的层数为的层数为1）3 3i-1 i-1 5.一棵深度为一棵深度为h的满的满k叉树有如下性质：第叉树有如下性质：第h层上层上的节点都是叶子结点，其余各层上的每个结点的节点都是叶子结点，其余各层上的每个结点都有都有k棵非空子树。棵非空子树。如果按层次顺序从如果按层次顺序从1开始对全部结点编号，则第开始对全部结

19、点编号，则第i层上的结点数目是层上的结点数目是_；编号为；编号为n的结点的双的结点的双亲结点（若存在）的编号是亲结点（若存在）的编号是_；编号为编号为n的结点的第的结点的第i个孩子结点（若存在）的个孩子结点（若存在）的编号是编号是_，编号为，编号为n的结点有右兄的结点有右兄弟的条件是弟的条件是_,其右兄弟的编其右兄弟的编号是号是_。k ki-1i-1(n-1)(n-1)*k+i+1k+i+1ink+1(n=0,1,ink+1(n=0,1,2,)2,)n+1n+1 kkn2 6.在具有在具有n(n1)n(n1)个结点的个结点的k k叉树中，叉树中，有有_个空指针。个空指针。n(k-1)+1n(k

20、-1)+1 7.一棵含有一棵含有n个结点的个结点的k叉树，可能达叉树，可能达到的最大深度为到的最大深度为_，最小深度为，最小深度为_。n n loglogk k(n(k-1)+1)(n(k-1)+1)8.一棵深度为一棵深度为k k的满二叉树的结点总数的满二叉树的结点总数为为_,_,一棵深度为一棵深度为k k的完全二叉树的完全二叉树的结点总数的最小值是的结点总数的最小值是_，从左到，从左到右次序给结点编号（从右次序给结点编号（从1 1 开始）则编开始）则编号最小的叶子结点的编号为号最小的叶子结点的编号为_，最大值是最大值是_._.2 2k k-1-12 2k-1k-12 2k-2k-2+1+12

21、 2k-1k-1 9.由由a,b,ca,b,c三个结点构成的二叉树，共三个结点构成的二叉树，共有有_种不同的结构。种不同的结构。5 5 10.设根结点的层次数为设根结点的层次数为0 0，定义树的高度，定义树的高度为树中层次最大的结点的层次加为树中层次最大的结点的层次加 1 1，则，则高度为高度为k k的二叉树具有的结点数目，最少的二叉树具有的结点数目，最少为为_,_,最多是最多是_._.k k2 2k k-1-1 11.N个结点的完全二叉树，个结点的完全二叉树，按从上到下按从上到下的，从左到右给结点顺序编号，则编号最的，从左到右给结点顺序编号，则编号最大的非叶结点编号为大的非叶结点编号为_，编

22、号最小的，编号最小的叶结点为叶结点为_。2/n)2/)1(12/nn或 12.在一棵二叉树中，度为在一棵二叉树中，度为0的结点个数为的结点个数为n0,度为度为2的结点个数为的结点个数为n2，则则n0=_.n2+1n2+1 13.一棵二叉树的第一棵二叉树的第i i（i1i1）层最多有层最多有_个个结点结点 ，一棵树有，一棵树有n(n0)n(n0)个结点的个结点的 满二叉树共有满二叉树共有_个叶子和个叶子和_个最高非终端结点。个最高非终端结点。2i-12i-1;2/n2/n 14.一棵完全二叉树的第一棵完全二叉树的第5 5层有层有5 5个结点，则共有个结点，则共有_个结点，其中度为个结点，其中度为

23、1 1的结点有的结点有_个，度为个，度为0 0的结点有的结点有_个。个。20201 11010 15.具有具有n个结点的完全二叉树，其叶结点的个数个结点的完全二叉树，其叶结点的个数是是_.2/n 16.对一棵具有对一棵具有n个结点的二叉树，当进行链接存个结点的二叉树，当进行链接存储时，其二叉链表中的指针域的总数为储时，其二叉链表中的指针域的总数为_个，个，其中其中_个用于连接孩子结点，个用于连接孩子结点，_个空闲着。个空闲着。2n2n n-1n-1 n+1 n+1 17.对于一棵具有对于一棵具有 n个结点的二叉树，当它为一棵个结点的二叉树，当它为一棵_二叉树时具有最小高二叉树时具有最小高度，高

24、度为度，高度为_，当它为一棵单，当它为一棵单支树具有支树具有_高度，高度为高度，高度为_。完全（或理想平衡）完全（或理想平衡）最大最大 n n)1(log2n 18.树所对应得二叉树其根结点的树所对应得二叉树其根结点的_子树一子树一定为空。定为空。右右 19.从概念上讲，树与二叉树是两种不同的数据从概念上讲，树与二叉树是两种不同的数据结构，将树转化成二叉树的基本目标是结构，将树转化成二叉树的基本目标是_.树可以采用二叉树的存储结构并利用树可以采用二叉树的存储结构并利用二叉树的已有算法解决树的有关问题二叉树的已有算法解决树的有关问题 20.结点最少的树为结点最少的树为_，结点，结点最少的二叉树是

25、最少的二叉树是_.只有一个结点树只有一个结点树 空的二叉树空的二叉树 21.设根结点的层次数为设根结点的层次数为0，定义树的高度为树中，定义树的高度为树中层次最大的结点层次加层次最大的结点层次加1，则高度为，则高度为k，内部结点内部结点的度数为的度数为1的二叉树有的二叉树有_棵。棵。2 2k-1 k-1 2 2.一 棵 完 全 二 叉 树 按 层 次 遍 历 的 序 列 为一 棵 完 全 二 叉 树 按 层 次 遍 历 的 序 列 为ABCDEFGHI,则在先序遍历中结点则在先序遍历中结点E 的直接前的直接前趋为趋为_,后序遍历中结点后序遍历中结点B的直接后继是的直接后继是_。I IF F 2

26、3.某二叉树的中序遍历序列为某二叉树的中序遍历序列为ABCDEFG，后后序序列为序序列为BDCAFGE，则该二叉树结点的前序序则该二叉树结点的前序序列为列为_,该二叉树对应的森林包括该二叉树对应的森林包括_棵树。棵树。EACBDGF EACBDGF 1 1 24.用一维数组存放的一棵完全二叉树如图所示。用一维数组存放的一棵完全二叉树如图所示。则 后 序 遍 历 该 二 叉 树 时 结 点 访 问 的 顺 序 为则 后 序 遍 历 该 二 叉 树 时 结 点 访 问 的 顺 序 为_。HIDJKEBLFGCA HIDJKEBLFGCA 123456789101112ABCDEFGHIJKL 25.在一棵二叉排列树上按在一棵二叉排列树上按_遍历得到的结遍历得到的结点序列是一个有序序列。点序列是一个有序序列。中序中序 26.由由n个权值构成的哈夫曼树共有个权值构成的哈夫曼树共有_个结个结点。点。2n-1 2n-1 27.由带权为由带权为3，9，6，2，5的的5个叶子结点构成个叶子结点构成一棵哈夫曼树，则带权路径长度为一棵哈夫曼树，则带权路径长度为_。55 55 28.设设F是一个森林，是一个森林，B是由是由F转换得到的二叉树，转换得到的二叉树，F中有中有n个非终端结点，则个非终端结点，则B中右指针域为空的结中右指针域为空的结点有点有_个。个。n+1 n+1