数据结构-树和二叉树-习题

树与二叉树一.选择题1.假定在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为（）个。A．15B．16C．17D．472.按照二叉树的定义，具有3个结点的不同形状的二叉树有（）种。A.3B.4C.5D.63.按照二叉树的定义，具有3个不同数据结点的不同的二叉树有（）种。A.5B.6C.30D.324.深度为5的二叉树至多有（）个结点。1A.16B.32C.31D.105.设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为（）。A.2hB.2h-1C.2h+1D.h+16.对一个满二叉树2，m个树叶，n个结点，深度为h，则（）。A.n=h+m3B.h+m=2nC.m=h-1D.n=2h-17.任何一棵二叉树的叶结点在先序.中序和后序遍历序列中的相对次序（）。A.不发生改变B.发生改变C.不能确定D.以上都不对8.如果某二叉树的前根次序遍历结果为stuwv，中序遍历为uwtvs，那么该二叉树的后序为（）。A.uwvtsB.vwutsC.wuvtsD.wutsv9.某二叉树的前序遍历结点访问顺序是abdgcefh，中序遍历的结点访问顺序是dgbaechf，则其后序遍历的结点访问顺序是（）。A.bdgcefhaB.gdbecfhaC.bdgaechfD.gdbehfca10.在一非空二叉树的中序遍历序列中，根结点的右边（）。A.只有右子树上的所有结点B.只有右子树上的部分结点C.只有左子树上的部分结点D.只有左子树上的所有结点11.树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历.中序遍历和后序遍历。这里，我们把由树转化得到的二叉树4叫做这1深度为n的二叉树结点至多有2n-12满二叉树是除最后一层无任何子节点外，每一层上的所有结点都有两个子结点的二叉树3对于深度为h的满二叉树，n=20+21+…+2h-1=2h-1，m=2h-1。故而n=h+m。4树转化为二叉树的基本方法是把所有兄弟结点都用线连起来，然后去掉双亲到子女的连线，只留下双亲到第一个子女的连线。因此原来的兄弟关系就变为双亲与右孩子的关系。棵数对应的二叉树。结论（）是正确的。A.树的先根遍历序列与其对应的二叉树的先序遍历序列相同B.树的后根遍历序列与其对应的二叉树的后序遍历序列相同C.树的先根遍历序列与其对应的二叉树的中序遍历序列相同D.以上都不对12.如图所示二叉树的中序遍历序列是（）。A.abcdgefB.dfebagcC.dbaefcgD.defbagc13.一棵二叉树如图所示，其中序遍历的序列为（）。A.abdgcefhB.dgbaechfC.gdbehfcaD.abcdefgh14.设a,b为一棵二叉树上的两个结点，在中序遍历时，a在b前的条件是（）。A．a在b的右方B．a在b的左方C．a是b的祖先D．a是b的子孙15.已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是（）。A.acbedB.decabC.deabcD.cedba16.如下图所示的4棵二叉树，（）不是完全二叉树5。ABCD17.实现任意二叉树的后序遍历的非递归算法而不使用栈结构，最佳方案是二叉树采用（）存储结构。A.二叉链表B.广义表存储结构C.三叉链表6D.顺序存储结构5深度为k的有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时，成为完全二叉树。即除第h层外，其它各层(1～h-1)的结点数都达到最大个数，第h层所有的结点都连续集中在最左边。18.树最适合用来表示（）。A.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数据19.某二叉树结点的中序序列为A.B.C.D.E.F.G，后序序列为B.D.C.A.F.G.E，则其左子树中结点数目为（）。A.3B.2C.4D.520.二叉树是非线性数据结构，所以（）。A.它不能用顺序存储结构存储;B.它不能用链式存储结构存储;C.顺序存储结构和链式存储结构都能存储;D.顺序存储结构和链式存储结构都不能使用21.具有n(n0)个结点的完全二叉树的深度7为（）。A.log2(n)B.10（log2(n)）+1C.log2(n)+1D.log2(n)+122.把一棵树转换为二叉树后，这棵二叉树的形态是（）。A.唯一的B.有多种C.有多种，但根结点都没有左孩子D.有多种，但根结点都没有右孩子23.线索二叉树是一种（）结构8。A．逻辑B．逻辑和存储C．物理D．线性24.将一棵有100个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点编号为1，则编号为49的结点的左孩子的编号为（）。A.98B.99C.50D.4825.设森林F中有三棵树，第一.第二和第三棵树的结点个数分别为M1.M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是（）。A．M1B．M1+M2C．M3D．M2+M326.将一棵有100个结点的完全二叉树从根开始，每一层从左到右依次对结点进行6三叉链表是二叉树的另一种主要的链式存储结构。三叉链表与二叉链表的主要区别在于，它的结点比二叉链表的结点多一个指针域，该域用于存储一个指向本结点双亲的指针。三叉链表的结点形式如下7K层完全二叉树，就是前（K-1）层为满二叉树，第K层均为叶结点，可以不满。所以结点与深度的关系为：2K-1-1n≦2K-1。所以K=log2(n)+18逻辑结构：集合、线性、树和图物理结构：线性存储和非线性存储线性存储结构有顺序、链接、索引、散列4种结构非线性存储结构有：树形存储结构、图形存储结构。编号，根结点编号为1，则编号最大的非叶结点的编号为（）。A.48B.49C.50D.5127.引入二叉线索树的目的是（）。A.加快查找结点的前驱或后继的速度B.为了能在二叉树中方便的进行插入与删除C.为了能方便的找到双亲D.使二叉树的遍历结果唯一28.若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（）。9A．9B．11C．15D．不确定29.一棵树深度为K的完全二叉树至少有（）个结点A．2k–1B.2k-1-1C.2k-1D.2k30.一棵二叉树的前序遍历序列为ABCDEFG，它的中序遍历序列可能是（）。A．CABDEFGB．ABCDEFGC．DACEFBGD．ADCFEG31.有关二叉树下列说法正确的是（）。A．二叉树的度为2B．一棵二叉树的度可以小于2C．二叉树中至少有一个结点的度为2D．二叉树中任何一个结点的度都为232.一个具有1025个结点的二叉树的高h为（）。A．11B．10C．11至1025之间D．10至1024之间33.对于有n个结点的二叉树,其高度为（）。A．nlog2nB．log2nC．log2n+1D．不确定34.已知某二叉树的后序遍历序列是dabec,中序遍历序列是debac,它的先序遍历是（）。A．acbedB．decabC．deabcD．cedba35.若二叉树采用二叉链表存储结构，要交换其所有分支结点左.右子树的位置，利用（）遍历方法最合适。A．前序B．中序C．后序D．按层次9二叉树有如下性质：N0=N2+1，叶子节点个数等于度为2的节点个数+136.在下列存储形式中，（）一个不是树的存储形式？A．双亲表示法B．孩子链表表示法C．孩子兄弟表示法D．顺序存储表示法37.在下列关于二叉树的叙述中，正确的是（）。①只有一个结点的二叉树度为0;②二叉树的度为2；③二叉树的左右子树可任意交换;④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。A．①②③B．②③④C．②④D．①④38.若x是二叉中序线索树中一个不为根的有左孩子的结点则x的前驱为（）。A.X的双亲B.X的右子树中最左的结点C.X的左子树中最右结点D.X的左子树中最右叶结点39.在二叉树结点的先序序列，中序序列和后序序列中，所有叶子结点的先后顺序（）。A．都不相同B．完全相同C．先序和中序相同，而与后序不同D．中序和后序相同，而与先序不同40.在线索化二叉树中，t所指结点没有右子树的充要条件是（）。A.t-Rtag==110B.t-Rchild==NULLC.t-Rtag==1&&t-Rchild==NULLD.以上都不对41.设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为（）。A．2hB．2h-1C．2h+1D．h+142.如右图所示二叉树的中序遍历序列是（）。A．abcdgefB．dfebagcC．dbaefcgD．defbagc10rtag=1时rchild指向后继；ltag=0时lchild指向左子女；ltag=1时lchild指向前驱；rtag=0时rchild指向右子女；43.设a和b为一棵二叉树上的两个结点，在中序遍历时a在b前的条件是（）。A．a是b的左孩子B．b是a的右孩子C．a是b左子树上结点或b是a右子树上结点D．以上三项均可44.假定在一棵二叉树中，双分支结点数为15，单分支结点数为30，则叶子结点数为（）个。A．45B．15C．16D．3145.设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有（）个空指针域。A．2m-1B．2mC．2m+1D．4m46.二叉树的第k层的结点数最多为（）。A．2k-1B．2K+1C．2K-1D．2K-147.设某棵二叉树中有2000个结点，则该二叉树的最小高度为（）。A．9B．10C．11D．1248.一棵有n个结点的树，在把它转换成对应的二叉树后，该二叉树根结点的左子树上共有（）个结点。A．n-2B．n-1C．n+1D．n+249.对于一棵深度为4的三叉树，最多有（）个结点。A．30B．36C．40D．5450.设结点A有3个兄弟结点且结点B为结点A的双亲结点，则结点B的度数数为（）。A．3B．4C．5D．151.关于哈夫曼树，下列说法正确的是()。A．在哈夫曼树中，权值相同的叶子结点都在同一层上B．在哈夫曼树中，权值较大的叶子结点一般离根结点较远C．哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近D．在哈夫曼编码中，当两个字符出现频率相同时，其编码也相同，对于这种情况应作特殊外理二.判断题1.线索二叉树是一种逻辑结构。（×）2.二叉树中每个结点的两棵子树是有序的。（√）3.深度为K的完全二叉树至少有2K-1个结点。（√）4.在哈夫曼树中，权值最小的结点离根结点最近。（×）5.二叉树中每个结点的两棵子树的高度差等于1。（×）6.具有12个结点的完全二叉树有5个度为2的结点。（√）7.二叉树中每个结点有两棵非空子树或有两棵空子树。（×）8.哈夫曼树中没有度为1的结点，所以必为满二叉树。（×）9.二叉树中所有结点个数是2k-1-1，其中k是树的深度。（×）10.二叉树的遍历操作实际上是将非线性结构线性化的过程。（√）11.具有n个结点的满二叉树，其叶结点的个数为（n+1）/2。（√）12.前序和中序遍历用线索树方式存储的二叉树，不必使用栈。（√）13.树的先根遍历序列与其所转化的二叉树的先序遍历序列相同。（√）14.树的后根遍历序列与其所转化的二叉树的后序遍历序列相同。（×）15.由于二叉树中每个结点的度最大为2，所以二叉树是一种特殊的树。（×）16.二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。（×）17.哈夫曼树是带权路径长度最短的树，路径上权值较大的点离根较远。（×）18.二叉树的前序遍历序列中，任意一个结点均处在其子女结点的前面。（√）19.在二叉树结点的先序序列和后序序列中，所有叶子结点的先后顺序完全相同。（√）20.用二叉链表法存储包含n个结点的二叉树，结点的2n个指针区域中有n+1个为空指针。（√）21.对于一棵非空二叉树，它的根结点作为第一层，则它的第i层上最多能有2i—1个结点。（×）22.若二叉树用二叉链表作存贮结构，则在n个结点的二叉树链表中只有n—1个非空指针域。（√）三.填空题1.由３个结点所构成的二叉树有种形