树和二叉树练习.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,对应于下面选择的（）。 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开始连续编号，要求每个结点的编号大于其左，右孩子的编号，同一

2、结点的左，右孩子中，其左孩子编号小于其右孩子编号，则可采用（ ）次序的遍历实现二叉树的结点编号。 A.先序 B. 中序 C. 后序 D. 从根开始按层次遍历,C,5.假定一棵三叉树的结点为50，则它的最小高度为（）。 A. 3 B. 4 C. 5 D. 6,C,6.在一棵具有K层的满三叉树中，结点总数为（） A. (3k-1)/2 B. 3k-1 C. (3k-1)/3 D. 3k,A,7.按照二叉树的定义，具有3个结点的二叉树有（）种。 A. 3 B. 4 C. 5 D. 6,C,8.在一棵有n个结点的二叉树中，若度为2的结点数为n2，度为1的结点数为n1,度为0的结点数为n0，则树的最大高

3、度为（ ），其叶结点数为（）；树的最小高度为（），其叶结点数为（ ）；若采用链表存储结构，则有（）个空链域。 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 + 1,E,G,B,G,I,9.对一个满二叉树，m个树叶，n个结点，深度为h,则 （）。 n = h + m B. h + m = 2n C. m = h -1 D. n = 2h 1,D,10.设高度为h的二叉树中只有度为0和度为2 的结点，则此类二叉树中所包含的结点数至少为（），至多

4、为（）。 A. 2h B. 2h 1 C. 2h + 1 D. h +1 E. 2h-1 F.2h 1 G. 2h+1 +1 H.2h+1,B,F,11. 在一棵二叉树上第5层的结点数最多为（）。（假设根结点的层数为0） A. 8 B. 16 C. 15 D. 32,B,12.深度为5 的二叉树至多有（） 个结点。 A. 16 B. 32 C. 31 D. 10,C,13.一棵有124个叶结点的完全二叉树，最多有（） 个结点。 A. 247 B. 248 C. 249 D. 250 E. 251,B,14. 含有129个叶结点的完全二叉树，最多有（）个结点。 A. 254 B.255 C.25

5、6 D. 257 E. 258,D,15.假定在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为（）个。 A. 15 B. 16 C. 17 D. 47,B,16.用顺序存储的方法将完全二叉树中所有结点逐层存放在数组R1n中，结点Ri若有左子树，则左子树是结点（）。 A.R2i+1 B. R2i C. Ri/2 D. R2i -1,B,17.在一非空二叉树的中序遍历序列中，根结点的左边（） A.只有右子树上的所有结点 B. 只有右子树上的部分结点 C. 只有左子树上的部分结点 D. 只有左子树上的所有结点,A,18.任何一棵二叉树的叶结点在先序，中序和后序遍历中的相对次序

6、（ ）。 A不发生改变 B. 发生改变 C.不能确定 D.以上都不对,A,19.设n,m为一棵树上的两个结点，在中序遍历时，n在m前的条件是（ ）。 n在m右方 B. n是m祖先 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.已知某二叉树的后序遍历是d a b e c ，中序遍历序列是d e b a c，它的前序遍历序列是（）。 A. acbed B. decab C. deabc

7、D .cedba,D,22.二叉树采用二叉链表作存储结构，要交换其所有分支结点左右子树的位置，利用（）遍历方法最合适。 A.前序 B. 中序 C .后序 D .层次,C,23.欲实现任意二叉树的后序遍历的非递归算法而不必使用栈结构，最佳方案是二叉树采用（）存储结构。 A.三叉链表 B. 广义表 C. 二叉链表 .顺序,A,24.在线索化二叉树中，所指结点没有左子树的充要条件是（）。 .Tleft = NULL B. Tltag = 1 C. Tltag =1 且Tleft = NULL D 以上都不对,B,25.线索二叉树是一种（）结构。 .逻辑 .逻辑和存储 .物理D.线性,C,26.将图6

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

9、d链，直到rchild不是线索，则这时rchid（若不为NULL）所指结点为该后继。,C,29.树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历，中序遍历和后序遍历。这里，把由树转化得到的二叉树叫做这棵树对应得二叉树。下面结论正确的是（）。 A树的先根遍历序列与其对应的二叉树的先序遍历序列相同 B树的后序遍历序列与其对应的二叉树的后序遍历序列相同 C树的先根遍历序列与其对应的二叉树的中序遍历序列相同 D以上都不对,A,30.如果T2 是由有序树T转换而来的二叉树，那么T 中结点的前序就是T2中结点的（）。 A前序 B. 中序 C. 后序 D. 层次序,A,31.如果

10、T2 是由有序树T转换而来的二叉树，那么T 中结点的后序就是T2中结点的（）。 A前序 B. 中序 C.后序 D 层次序,B,32.如图6-7所示的t2是由有序树t1转化而来的二叉树，那么树t1有（）个叶结点。 A . 4 B. 5 C. 6 D. 7,C,33.设T是哈夫曼树，具有5个叶结点，树T的高度最高可以是（）。 A . 1 B. 2 C. 3 D. 4 E. 5 . 6,D,E,34.由带权为，的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为（）。 .23 B. 37 C. 46 D . 43,D,35.若只考虑有序树的情形，则具有个结点的不同形态的树共有（）种。 A.132 B

11、. 154. C. 429 D. 前三者均不正确,A,36.树的后根遍历序列等同于该树对应的二叉树的（） 先序遍历.中序遍历 . 后序遍历.层次遍历,B,二、填空题,1.在树形结构中，树根结点没有_结点，其余每个结点有且只有_个前趋结点；叶子结点没有_结点，其余每个结点的后继结点可以_。,前趋,1,后继,任意多个,2.有一棵树如图所示，回答下面的问题。 这棵树的根点是_; 这棵树的叶子结点是_; 结点k3的度是_;这棵树的度为_; 这棵树的深度为_;结点k3的子女是_; 结点k3的父结点是_,k1,k2,k5,k7,k4,2,3,4,K5,k6,k1,3.假定一棵树的广义表表示为A(B(E),

12、C(F(H,I,J),G),D),则该树的度为_;树的深度为_,终端结点的个数为_，单分支结点的 个数为_,双分支结点的个数为_,三分支结点的个数为_,C结点的双亲结点为_,其孩子结点为_和 _结点。,3,4,6,1,1,2,A,F,G,4.设树T中除叶结点外，任意结点的度数是3，则T的第i层结点的个数为_。（假设根结点的层数为1）,3i-1,5.一棵深度为h的满k叉树有如下性质：第h层上的节点都是叶子结点，其余各层上的每个结点都有k棵非空子树。 如果按层次顺序从1开始对全部结点编号，则第i层上的结点数目是_；编号为n的结点的双亲结点（若存在）的编号是_ ；编号为n的结点的第i个孩子结点（若存

13、在）的编号是_ ，编号为n的结点有右兄弟的条件是_,其右兄弟的编号是_。,ki-1,(n-1)*k+i+1,ink+1(n=0,1,2,),n+1,6.在具有n(n1)个结点的k叉树中， 有_个空指针。,n(k-1)+1,7.一棵含有n个结点的k叉树，可能达到的最大深度为_，最小深度为_ 。,n,logk(n(k-1)+1),8.一棵深度为k的满二叉树的结点总数为_,一棵深度为k的完全二叉树的结点总数的最小值是_，从左到右次序给结点编号（从1 开始）则编号最小的叶子结点的编号为_，最大值是_.,2k-1,2k-1,2k-2+1,2k-1,9.由a,b,c三个结点构成的二叉树，共有_种不同的结构

14、。,5,10.设根结点的层次数为0，定义树的高度为树中层次最大的结点的层次加 1 ，则高度为k的二叉树具有的结点数目，最少为_,最多是_.,k,2k-1,11. N个结点的完全二叉树， 按从上到下的，从左到右给结点顺序编号，则编号最大的非叶结点编号为_，编号最小的叶结点为_ 。,12.在一棵二叉树中，度为0的结点个数为n0,度为2的结点个数为n2，则n0=_.,n2 +1,13.一棵二叉树的第i（i1）层最多有_个结点 ，一棵树有n(n0)个结点的 满二叉树共有_个叶子和_个最高非终端结点。,2i-1,;,14.一棵完全二叉树的第5层有5个结点，则共有_个结点，其中度为1的结点有_个，度为0的

15、结点有_个。,20,1,10,15.具有n个结点的完全二叉树，其叶结点的个数是_.,16.对一棵具有n个结点的二叉树，当进行链接存储时，其二叉链表中的指针域的总数为_个，其中_个用于连接孩子结点， _个空闲着。,2n,n-1,n+1,17.对于一棵具有 n个结点的二叉树，当它为一棵_二叉树时具有最小高度，高度为_ ，当它为一棵单支树具有_高度，高度为_。,完全（或理想平衡）,最大,n,18.树所对应得二叉树其根结点的_子树一定为空。,右,19.从概念上讲，树与二叉树是两种不同的数据结构，将树转化成二叉树的基本目标是_.,树可以采用二叉树的存储结构并利用 二叉树的已有算法解决树的有关问题,20.结点最少的树为_ ，结点最少的二叉树是_.,只有一个结点树,空的二叉树,21.设根结点的层次数为0 ，定义树的高度为树中层次最大的结点层次加1，则高度为k，内部结点的度数为1的二叉树有_棵。,2k-1,22.一棵完全二叉树按层次遍历的序列为ABCDEFGHI,则在先序遍历中结点E 的直接前趋为_,后序遍历中结点B的直接后继是_。,I,F,23.某二叉树的中序遍历序列为ABCDEFG，后序序列为BDCAFGE，则该二叉树结点的前序序列为_,该二叉树对