树与二叉树一.选择题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=2 h-11深度为n的二叉树结点至多有2n-12满二叉树是除最后一层无任何子节点外，每一层上的所有结点都有两个子结点的二叉树7.任何一棵二叉树的叶结点在先序.中序和后序遍历序列中的相对次序（）。
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叫做这棵数对应的二叉树。
结论（）是正确的。
A.树的先根遍历序列与其对应的二叉树的先序遍历序列相同B.树的后根遍历序列与其对应的二叉树的后序遍历序列相同3对于深度为h的满二叉树，n=20+21+…+2h-1=2h-1，m=2h-1。
故而n=h+m。
4树转化为二叉树的基本方法是把所有兄弟结点都用线连起来，然后去掉双亲到子女的连线，只留下双亲到第一个子女的连线。
因此原来的兄弟关系就变为双亲与右孩子的关系。
1/ 9C.树的先根遍历序列与其对应的二叉树的中序遍历序列相同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. cedba 16.如下图所示的4棵二叉树，（）不是完全二叉树5。
AB C D17.实现任意二叉树的后序遍历的非递归算法而不使用栈结构，最佳方案是二叉树采用（）存储结构。
A. 二叉链表B. 广义表存储结构C. 三叉链表6D. 顺序存储结构18.树最适合用来表示（）。
A. 有序数据元素B. 无序数据元素C. 元素之间具有分支层次关系的数据D. 元素之间无联系的数据19.某二叉树结点的中序序列为A.B.C.D.E.F.G，后序序列为B.D.C.A.F.G.E，则其左子树中结点数目为（）。
A. 3B. 2C. 4D. 55深度为k的有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时，成为完全二叉树。
即除第h 层外，其它各层(1～h-1) 的结点数都达到最大个数，第h 层所有的结点都连续集中在最左边。
6三叉链表是二叉树的另一种主要的链式存储结构。
三叉链表与二叉链表的主要区别在于，它的结点比二叉链表的结点多一个指针域，该域用于存储一个指向本结点双亲的指针。
三叉链表的结点形式如下2/ 920.二叉树是非线性数据结构，所以（）。
A.它不能用顺序存储结构存储;B.它不能用链式存储结构存储;C.顺序存储结构和链式存储结构都能存储;D.顺序存储结构和链式存储结构都不能使用21.具有n(n>0)个结点的完全二叉树的深度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．线性7K层完全二叉树，就是前（K-1）层为满二叉树，第K层均为叶结点，可以不满。
所以结点与深度的关系为：2K-1-1<n≦ 2K-1。
所以K = log2(n) +18逻辑结构：集合、线性、树和图物理结构：线性存储和非线性存储线性存储结构有顺序、链接、索引、散列4种结构非线性存储结构有：树形存储结构、图形存储结构。
24.将一棵有100个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点编号为1，则编号为49的结点的左孩子的编号为（）。
A.98B.99C.50D.4825.设森林F中有三棵树，第一.第二和第三棵树的结点个数分别为M1.M2和M3。
与森林F对应的二叉树根结点的右子树上的结点个数是（）。
A．M1B．M1+M2C．M3D．M2+M326.将一棵有100个结点的完全二叉树从根开始，每一层从左到右依次对结点进行编号，根结点编号为1，则编号最大的非叶结点的编号为（）。
A.48B.49C.50D.5127.引入二叉线索树的目的是（）。
A.加快查找结点的前驱或后继的速度B.为了能在二叉树中方便的进行插入与删除C.为了能方便的找到双亲D.使二叉树的遍历结果唯一28.若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（）。
9A．9B．11C．15D．不确定9二叉树有如下性质：N0 = N2 +1，叶子节点个数等于度为2的节点个数+13/ 929.一棵树深度为K的完全二叉树至少有（）个结点A．2k–1B. 2k-1-1C. 2k-1D. 2k30.一棵二叉树的前序遍历序列为ABCDEFG，它的中序遍历序列可能是（）。
A．CABDEFG B．ABCDEFG C．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．deabc D．cedba35.若二叉树采用二叉链表存储结构，要交换其所有分支结点左.右子树的位置，利用（）遍历方法最合适。
A．前序B．中序C．后序D．按层次36.在下列存储形式中，（）一个不是树的存储形式？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．中序和后序相同，而与先序不同4/ 940.在线索化二叉树中，t所指结点没有右子树的充要条件是（）。
A.t->Rtag==110B.t->Rchild==NULLC.t->Rtag==1 && t->Rchild==NULLD.以上都不对41.设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为（）。
A．2h B．2h-1C．2h+1D．h+142.如右图所示二叉树的中序遍历序列是（）。
A．abcdgefB．dfebagcC．dbaefcgD．defbagc43.设a和b为一棵二叉树上的两个结点，在中序遍历时a在b前的条件是（）。
A．a是b的左孩子B．b是a的右孩子C．a是b左子树上结点或b是a右子树上结点D．以上三项均可10rtag=1 时rchild指向后继；ltag=0 时lchild指向左子女；ltag=1 时lchild指向前驱；rtag=0 时rchild指向右子女；44.假定在一棵二叉树中，双分支结点数为15，单分支结点数为30，则叶子结点数为（）个。
A．45B．15C．16D．3145.设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有（）个空指针域。
A．2m-1B．2m C．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．15/ 951.关于哈夫曼树，下列说法正确的是( )。
A．在哈夫曼树中，权值相同的叶子结点都在同一层上B．在哈夫曼树中，权值较大的叶子结点一般离根结点较远C．哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近D．在哈夫曼编码中，当两个字符出现频率相同时，其编码也相同，对于这种情况应作特殊外理二.判断题1.线索二叉树是一种逻辑结构。