树和二叉树练习.ppt

树和二叉树练习树和二叉树练习一、选择题一、选择题1.有一有一“遗传遗传”关系：设关系：设x是是y的父亲，则的父亲，则x可可以把它的属性遗传给以把它的属性遗传给y。表示该遗传关系最合表示该遗传关系最合适的数据结构为（适的数据结构为（）。）。A 向量向量 B.树树 C.图图 D二叉树二叉树 B2.树最合适用来表示（树最合适用来表示（）。）。A.有序数据元素有序数据元素 B.元素之间具有分支层次关系的数据元素之间具有分支层次关系的数据C.无序数据元素无序数据元素 D.元素之间无联系的数据元素之间无联系的数据.B3.树树B的的层层号号表表示示为为1a,2b,3d,3e,2c,对对应应于于下下面面选选择的（择的（）。）。A.1a(2b(3d,3e),2c)B.a(b(D.,e),c)C.a(b(d,e),c)D.a(b,d(e),c)c4.对二叉树的结点从对二叉树的结点从1开始连续编号，要求每个开始连续编号，要求每个结点的编号大于其左，右孩子的编号，同一结结点的编号大于其左，右孩子的编号，同一结点的左，右孩子中，其左孩子编号小于其右孩点的左，右孩子中，其左孩子编号小于其右孩子编号，则可采用（子编号，则可采用（）次序的遍历实现二叉）次序的遍历实现二叉树的结点编号。树的结点编号。A.先序先序 B.中序中序 C.后序后序 D.从根开始按层次遍历从根开始按层次遍历C5.假定一棵三叉树的结点为假定一棵三叉树的结点为50，则它，则它的最小高度为（的最小高度为（）。）。A.3 B.4 C.5 D.6C6.在在一一棵棵具具有有K层层的的满满三三叉叉树树中中，结结点点总总数数为（为（）A.(3k-1)/2 B.3k-1 C.(3k-1)/3 D.3kA7.按按照照二二叉叉树树的的定定义义，具具有有3个个结结点点的的二叉树有（二叉树有（）种。）种。A.3 B.4 C.5 D.6C8.在一棵有在一棵有n个结点的二叉树中，若度为个结点的二叉树中，若度为2的的结点数为结点数为n2，度为度为1的结点数为的结点数为n1,度为度为0的结的结点数为点数为n0，则树的最大高度为（则树的最大高度为（），其叶），其叶结点数为（结点数为（）；树的最小高度为（）；树的最小高度为（），），其叶结点数为（其叶结点数为（）；若采用链表存储）；若采用链表存储结构，则有（结构，则有（）个空链域。）个空链域。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.h+m=2n C.m=h-1 D.n=2h 1D10.设设高高度度为为h的的二二叉叉树树中中只只有有度度为为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 BF11.在在一一棵棵二二叉叉树树上上第第5层层的的结结点点数数最最多为（多为（）。（假假设设根根结结点点的的层层数数为为0）A.8 B.16 C.15 D.32B12.深度为深度为5 的二叉树至多有（的二叉树至多有（）个结点。个结点。A.16 B.32 C.31 D.10C13.一棵有一棵有124个叶结点的完全二叉树，个叶结点的完全二叉树，最多有（最多有（）个结点。个结点。A.247 B.248 C.249 D.250 E.251B14.含有含有129个叶结点的完全二叉树，个叶结点的完全二叉树，最多有（最多有（）个结点。）个结点。A.254 B.255 C.256 D.257 E.258D15.假定在一棵二叉树中，双分支结点数为假定在一棵二叉树中，双分支结点数为15，单分支结点数为，单分支结点数为30个，则叶子结点数个，则叶子结点数为（为（）个。）个。A.15 B.16 C.17 D.47B16.用顺序存储的方法将完全二叉树中所有用顺序存储的方法将完全二叉树中所有结点逐层存放在数组结点逐层存放在数组R1n中，结点中，结点Ri若有左子树，则左子树是结点（若有左子树，则左子树是结点（）。）。A.R2i+1 B.R2i C.Ri/2 D.R2i-1B17.在一非空二叉树的中序遍历序列中，在一非空二叉树的中序遍历序列中，根结点的左边（根结点的左边（）A.只有右子树上的所有结点只有右子树上的所有结点 B.只有右子树上的部分结点只有右子树上的部分结点C.只有左子树上的部分结点只有左子树上的部分结点 D.只有左子树上的所有结点只有左子树上的所有结点A18.任何一棵二叉树的叶结点在先序，任何一棵二叉树的叶结点在先序，中序和后序遍历中的相对次序（中序和后序遍历中的相对次序（）。）。A不发生改变不发生改变 B.发生改变发生改变 C.不能确定不能确定 D.以上都不对以上都不对A19.设设n,m为一棵树上的两个结点，在为一棵树上的两个结点，在中序遍历时，中序遍历时，n在在m前的条件是（前的条件是（）。）。A.n在在m右方右方 B.n是是m祖先祖先 C.n在在m左方左方 D.n是是m 子孙子孙C20.一棵完全二叉树按层次遍历的序列一棵完全二叉树按层次遍历的序列为为ABCDEFGHI，则在先序遍历中结则在先序遍历中结点点E 的直接前趋为（的直接前趋为（），后序遍历），后序遍历中结点中结点B 的直接后继是（的直接后继是（）。）。（1）B （2）D （3）A（4）I（5）F（6）C(4)(5)21.已知某二叉树的后序遍历是已知某二叉树的后序遍历是d a b e c，中序遍历序列是中序遍历序列是d e b a c，它的前它的前序遍历序列是（序遍历序列是（）。）。A.acbed B.decab C.deabc D.cedbaD22.二叉树采用二叉链表作存储结构，二叉树采用二叉链表作存储结构，要交换其所有分支结点左右子树的位要交换其所有分支结点左右子树的位置，利用（置，利用（）遍历方法最合适。）遍历方法最合适。A.前序前序 B.中序中序 C.后序后序 D.层次层次C23.欲实现任意二叉树的后序遍历的非欲实现任意二叉树的后序遍历的非递归算法而不必使用栈结构，最佳方递归算法而不必使用栈结构，最佳方案是二叉树采用（案是二叉树采用（）存储结构。）存储结构。A.三叉链表三叉链表 B.广义表广义表 C.二叉链表二叉链表.顺序顺序A24.在线索化二叉树中，所指结点没在线索化二叉树中，所指结点没有左子树的充要条件是（有左子树的充要条件是（）。）。.Tleft=NULL B.Tltag=1 C.Tltag=1 且且Tleft=NULL D 以上都不对以上都不对B25.线索二叉树是一种（线索二叉树是一种（）结构。）结构。.逻辑逻辑 .逻逻辑辑和和存存储储.物理物理D.线性线性C26.将图将图6-6中的二叉树按中序线索化，中的二叉树按中序线索化，结点结点X的右指针和的右指针和Y 的左指针分别指的左指针分别指向（向（）。）。（1）A，D (2)B,C (3)D,A （4）C，A(3)ABDCXEY图图6-627.在下列三次序的线索二叉树中在下列三次序的线索二叉树中（），对查找指定结点在该次序），对查找指定结点在该次序下的后继效果较差。下的后继效果较差。A.前序线索树前序线索树 B.中序线索树中序线索树 C.后序线索树后序线索树C28.设中序线索二叉树设中序线索二叉树T是按是按lchild-rchild表表示法存储，欲确定示法存储，欲确定T中结点中结点p在前提下的后在前提下的后继，下述说法不正确的是（继，下述说法不正确的是（）。）。A.若若p有左子女，则该后继为有左子女，则该后继为p的左子女的左子女B 若若p无无左左子子女女且且有有右右子子女女，则则该该后后继继为为p的右子女的右子女C 若若p无无左左子子女女且且无无右右子子女女，则则该该后后继继为为p的右线索所指结点的右线索所指结点D.若若p无无左左子子女女，从从结结点点p开开始始，追追综综rchild链链，直直到到rchild不不是是线线索索，则则这这时时rchid（若不为若不为NULL）所指结点为该后继。）所指结点为该后继。C29.树的基本遍历策略可分为先根遍历和后树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先根遍历；二叉树的基本遍历策略可分为先序遍历，中序遍历和后序遍历。这里，把序遍历，中序遍历和后序遍历。这里，把由树转化得到的二叉树叫做这棵树对应得由树转化得到的二叉树叫做这棵树对应得二叉树。下面结论正确的是（二叉树。下面结论正确的是（）。）。A树树的的先先根根遍遍历历序序列列与与其其对对应应的的二二叉叉树树的先序遍历序列相同的先序遍历序列相同B树树的的后后序序遍遍历历序序列列与与其其对对应应的的二二叉叉树树的后序遍历序列相同的后序遍历序列相同C树树的的先先根根遍遍历历序序列列与与其其对对应应的的二二叉叉树树的中序遍历序列相同的中序遍历序列相同D以上都不对以上都不对A30.如果如果T2 是由有序树是由有序树T转换而来的二转换而来的二叉树，那么叉树，那么T 中结点的前序就是中结点的前序就是T2中中结点的（结点的（）。）。A前序前序 B.中序中序 C.后序后序 D.层次序层次序 A31.如果如果T2 是由有序树是由有序树T转换而来的二转换而来的二叉树，那么叉树，那么T 中结点的后序就是中结点的后序就是T2中中结点的（结点的（）。）。A前序前序 B.中序中序 C.后序后序 D 层次序层次序B32.如图如图6-7所示的所示的t2是由有序树是由有序树t1转化转化而来的二叉树，那么树而来的二叉树，那么树t1有（有（）个）个叶结点。叶结点。A.4 B.5 C.6 D.7C图6-7abecfhigdj33.设设T是哈夫曼树，具有是哈夫曼树，具有5个叶结点，个叶结点，树树T的高度最高可以是（的高度最高可以是（）。）。A.1 B.2 C.3D.4 E.5.6D,E34.由带权为，的四个叶由带权为，的四个叶子结点构造一棵哈夫曼树，该树的带子结点构造一棵哈夫曼树，该树的带权路径长度为（权路径长度为（）。）。.23 B.37 C.46 D.43D35.若只考虑有序树的情形，则具有若只考虑有序树的情形，则具有个结点的不同形态的树共有（个结点的不同形态的树共有（）种。）种。A.132 B.154.C.429 D.前三者均不正确前三者均不正确A36.树的后根遍历序列等同于该树对应树的后根遍历序列等同于该树对应的二叉树的（的二叉树的（）先序遍历先序遍历.中序遍历中序遍历.后序遍历后序遍历.层次遍历层次遍历B二、填空题二、填空题1.在在 树树 形形 结结 构构 中中，树树 根根 结结 点点 没没 有有_结结点点，其其余余每每个个结结点点有有且且只只有有_个个前前趋趋结结点点；叶叶子子结结点点没没有有_结结点点，其其余余每每个个结结点点的的后后继继结结点点可可以以_。前趋前趋1 1后继后继任意多个任意多个 2.有一棵树如图所示，回答下面的问题。有一棵树如图所示，回答下面的问题。这棵树的根点是这棵树的根点是_;_;这棵树的叶子结点是这棵树的叶子结点是_;_;结点结点k3k3的度是的度是_;_;这棵树的度为这棵树的度为_;_;这棵树的深度为这棵树的深度为_;_;结点结点k3k3的子女是的子女是_;_;结点结点k3k3的父结点是的父结点是_k1k1k2,k5,k7,k4k2,k5,k7,k42 23 34 4K5K5,k6k6k1k1 图6-8k1k2k4k3k5k6k73.假假 定定 一一 棵棵 树树 的的 广广 义义 表表 表表 示示 为为A(B(E),C(F(H,I,J),G),D),则则该该树树的的度度为为_;树树的的深深度度为为_,终终端端结结点点的的个个数数为为_，单单分分支支结结点点的的 个个数数为为_,双双分分支支结结点点的的个个数数为为_,三三分分支支结结点点的的个个数数为为_,C结结点点的的双双亲亲结结点点为为_,其孩子结点为其孩子结点为_和和 _结点。结点。3 34 46 61 11 12 2A AF FG G4.设树设树T中除叶结点外，任意结点的度数是中除叶结点外，任意结点的度数是3，则则T的第的第i层结点的个数为层结点的个数为_。（假设根结点。（假设根结点的层数为的层数为1）3 3i-1 i-1 5.一棵深度为一棵深度为h的满的满k叉树有如下性质：第叉树有如下性质：第h层上层上的节点都是叶子结点，其余各层上的每个结点的节点都是叶子结点，其余各层上的每个结点都有都有k棵非空子树。棵非空子树。如如果果按按层层次次顺顺序序从从1开开始始对对全全部部结结点点编编号号，则则第第i层层上上的的结结点点数数目目是是_；编编号号为为n的的结结点点的的双双亲亲结结点点（若若存存在在）的的编编号号是是_；编编号号为为n的的结结点点的的第第i个个孩孩子子结结点点（若若存存在在）的的编编号号是是_，编编号号为为n的的结结点点有有右右兄兄弟弟的的条条件件是是_,其其右右兄兄弟弟的的编编号号是是_。k ki i-1-1(n-1)*k+i+1(n-1)*k+i+1iinknk+1(n=0,1,2,+1(n=0,1,2,)n+1n+1 6.在具有在具有n(n1)n(n1)个结点的个结点的k k叉树中，叉树中，有有_个空指针。个空指针。n(k-1)+1n(k-1)+17.一一棵棵含含有有n个个结结点点的的k叉叉树树，可可能能达达到到的的最最大大深深度度为为_，最最小小深深度度为为_。n n loglogk k(n(k-(n(k-1)+1)1)+1)8.一一棵棵深深度度为为k k的的满满二二叉叉树树的的结结点点总总数数为为_,_,一一棵棵深深度度为为k k的的完完全全二二叉叉树树的的结结点点总总数数的的最最小小值值是是_，从从左左到到右右次次序序给给结结点点编编号号（从从1 1 开开始始）则则编编号号最最小小的的叶叶子子结结点点的的编编号号为为_，最大值是最大值是_._.2 2k k-1-12 2k-1k-12 2k-2k-2+1+12 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个个结结点点的的完完全全二二叉叉树树，按按从从上上到到下下的的，从从左左到到右右给给结结点点顺顺序序编编号号，则则编编号号最最大大的的非非叶叶结结点点编编号号为为_，编编号号最最小小的的叶叶结结点点为为_。12.在在一一棵棵二二叉叉树树中中，度度为为0的的结结点点个个数数为为n0,度为度为2的结点个数为的结点个数为n2，则则n0=_.n2+1n2+1 13.一一棵棵二二叉叉树树的的第第i i（i1i1）层层最最多多有有_个个结结点点 ，一一棵棵树树有有n(n0)n(n0)个个结结点点的的 满满二二叉叉树树共共有有_个叶子和个叶子和_个最高非终端结点。个最高非终端结点。2i-12i-1;14.一一棵棵完完全全二二叉叉树树的的第第5 5层层有有5 5个个结结点点，则则共共有有_个个结结点点，其其中中度度为为1 1的的结结点点有有_个个，度度为为0 0的结点有的结点有_个。个。20201 1101015.具具有有n个个结结点点的的完完全全二二叉叉树树，其其叶叶结结点点的的个个数数是是_.16.对对一一棵棵具具有有n个个结结点点的的二二叉叉树树，当当进进行行链链接接存存储储时时，其其二二叉叉链链表表中中的的指指针针域域的的总总数数为为_个个，其其中中_个个用用于于连连接接孩孩子子结结点点，_个空闲着。个空闲着。2n2n n-1n-1 n+1 n+1 17.对对于于一一棵棵具具有有 n个个结结点点的的二二叉叉树树，当当它它为为一一棵棵_二二叉叉树树时时具具有有最最小小高高度度，高高度度为为_，当当它它为为一一棵棵单单支树具有支树具有_高度，高度为高度，高度为_。完全（或理想平衡）完全（或理想平衡）最大最大 n n 18.树树所所对对应应得得二二叉叉树树其其根根结结点点的的_子子树树一一定为空。定为空。右右 19.从从概概念念上上讲讲，树树与与二二叉叉树树是是两两种种不不同同的的数数据据结构，将树转化成二叉树的基本目标是结构，将树转化成二叉树的基本目标是_.树树可以采用二叉可以采用二叉树树的存的存储结储结构并利用构并利用二叉二叉树树的已有算法解决的已有算法解决树树的有关的有关问题问题 20.结结点点最最少少的的树树为为_，结结点点最少的二叉树是最少的二叉树是_.只有一个只有一个结结点点树树 空的二叉空的二叉树树 21.设设根根结结点点的的层层次次数数为为0，定定义义树树的的高高度度为为树树中中层层次次最最大大的的结结点点层层次次加加1，则则高高度度为为k，内内部部结结点点的度数为的度数为1的二叉树有的二叉树有_棵。棵。2 2k-1 k-1 22.一一 棵棵 完完 全全 二二 叉叉 树树 按按 层层 次次 遍遍 历历 的的 序序 列列 为为ABCDEFGHI,则则在在先先序序遍遍历历中中结结点点E 的的直直接接前前趋为趋为_,后序遍历中结点后序遍历中结点B的直接后继是的直接后继是_。I IF F 23.某某二二叉叉树树的的中中序序遍遍历历序序列列为为ABCDEFG，后后序序序序列列为为BDCAFGE，则则该该二二叉叉树树结结点点的的前前序序序序列列为为_,该该二二叉叉树树对对应应的的森森林林包包括括_棵树。棵树。EACBDGF EACBDGF 1 124.用一维数组存放的一棵完全二叉树如图所示。用一维数组存放的一棵完全二叉树如图所示。则则后后序序遍遍历历该该二二叉叉树树时时结结点点访访问问的的顺顺序序为为_。HIDJKEBLFGCA HIDJKEBLFGCA 123456789101112ABCDEFGHIJKL25.在在一一棵棵二二叉叉排排列列树树上上按按_遍遍历历得得到到的的结结点序列是一个有序序列。点序列是一个有序序列。中序中序 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