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

树和二叉树一.选择题1.假设一个二叉树中的双分支节点数为15，单分支节点数为30，则叶节点数为()。A.15B.16C.17D.472.如二进制树中所定义，具有三个节点的不同形状的二进制树具有()种类。A.3B。4C .5D。63.如二进制树中所定义，具有三个不同数据节点的不同二进制树具有()种类。A.5B .6C .30D。32深度为5的二进制树最多包含()个节点。深度为n的二叉树节点最大值为2n-1A.16B。32C .31D。105.如果高度设置为h的二进制树中只有度为0、度为2的节点，则这些二进制树中包含的节点数为最小()。A.2hB。2h-1C。2h 1D。h 16.二进制树满是二进制树，每个层次结构(最后一个层次结构除外)的所有节点都有两个子节点，m叶，n节点，如果深度为h()。A.n=h对于m深度为h的整个二进制树，n=20 21.2h-1=2h-1，m=2h-1。因此n=h m。B.h m=2n C. m=h-1 D. n=2 h-17.任意二叉树叶节点迁移顺序。中间顺序和最后顺序遍历序列中的相对顺序()。A.无变更b .变更发生c .不确定d .以上全部错误8.如果二进制树的上一根顺序遍历结果为stuwv，中间顺序遍历为uwtvs，则二进制树的下一个顺序为()。A.uwv tsb.vw utsc.wuvstsd.wutsv9.二进制树以前的遍历节点访问顺序为abdgcefh，中间遍历节点访问顺序为dgbaechf，下一个顺序遍历节点访问顺序为()。A.bdgcefhab . gdbechfhc . bdgaechfd . gdbehfca10.非空二叉树的中间顺序遍历序列中根节点的右侧()。A.仅右侧子树中的所有节点b .仅右侧子树中的部分节点C.仅左侧子树的部分节点仅d .左侧子树的所有节点11.树的基本遍历策略可分为先根遍历和后根遍历。二叉树的基本遍历策略是第一顺序遍历。可以分为中间顺序遍历和下一顺序遍历。在这里，我们从树上得到的二叉树转换成二叉树的基本方法是用线连接所有兄弟节点，然后消除双亲和孩子的连接，只留下双亲和第一个孩子的连接。所以原来的兄弟关系变成了双亲和友爱关系。与此数目相对应的二进制树。结论()是正确的。A.树的第一个根遍历序列与其二进制树的第一个遍历序列相同B.树的后根遍历序列与相应二叉树的后遍历序列相同C.树的第一个根遍历序列与相应二叉树的中间顺序遍历序列相同D.异常错误12.图中所示的二进制树的中间遍历序列为()。A.abcdgefB.dfebagcC.dbaefcgD.defbagc13.顺序横向序列为()，如下图所示。A.abdgcefhB.dgbaechfC.gdbehfcaD.abcdefgh14.将a，b设置为二叉树的两个节点，在中间顺序遍历中，b之前的a的条件是()。A.a在b的右侧，b.a在b的左侧C.a是b的祖先。D. a是b的后代15.二进制树中的最后一个横向序列为dabec，中间横向序列为debac，前一个横向序列为()。A.acbedB。decabC .deabcD。cedba16.下图所示的四个二进制树，()不是具有完全二进制树深度为k的n个节点的二进制树，只有每个节点对应k的完全二进制树中的1到n个节点编号时，才能成为完全二进制树。也就是说，除层h外，每个层(1至h-1)中的节点数达到最大数量，层h中的所有节点连续集中在最左侧。，即可从workspace页面中移除物件。ABCD17.实现任意二叉树的后续遍历而不是堆栈结构的非递归算法，最佳方法是二叉树采用()存储结构。A.二进制列表b .定义的表存储结构c .三次列表三次列表是二进制树的另一个主要链存储结构。第三链接和第二链接的主要区别在于，节点比第二链接表中的节点多一个指针字段，此字段用于存储指向此节点父节点的指针。三阶连结的节点格式如下D.顺序存储结构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)节点的完整二叉树的深度K层完整二叉树，即前(K-1)层是完整的二叉树，K层都是叶节点，可能不满意。因此，节点和深度的关系是2K-1-1r tag=1 rtag=1:00 rchild指向后继。Ltag=0时，lchild指向左边的孩子。Ltag=1时，lchild指向灯泡体。Rtag=0时，rchild表示右边的孩子。B.t-Rchild=NULLC.t-Rtag=1 t-Rchild=NULLD。以上都是错误的41.如果高度设置为h的二进制树中只有度为0、度为2的节点，则这些二进制树中包含的节点数为最小()。A.2hb.2h-1C.2h 1D.h 142.如右图所示，二叉树的中间遍历序列是()。A.ABCD GEFB.dfe bagcC.dbaefcgD.defbagc43.将a和b设置为二进制树的两个节点，在中间顺序遍历中，b前面的a的条件为()。A.a是b的左孩子，b.b是a的右孩子C.a可以是b左侧的子树节点，也可以是b右侧的子树节点d。以上三个项目44.假设一个二进制树中的双分支节点数为15，单分支节点数为30，则叶节点数为()。A.45B.15C.16D.3145.Huffman树的叶节点总数为m，如果将二进制列表用作存储结构，则此hufman树有总计()个空指针域。A.2m-1B.2mC.2m 1D.4m46.二进制树的级别k的节点数为最大值()。A.2k-1b.2k1C.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有三个同级节点，节点b是节点a的父节点，则节点b的度数为()。A.3B.4C.5D.151.关于哈夫曼树，以下陈述是正确的()。A.在Huffman树中，具有相同权重的所有叶节点都位于同一层上B.在Huffman树中，具有较大权重的叶节点通常远离根节点C.Huffman树是权重最大的节点具有权重最接近根的最短路径长度的树D.在霍夫曼编码中，当两个字符以相同的频率出现时，其编码也是相同的，在这种情况下，应该是特殊的外推二.判决问题线索二叉树是逻辑结构。（）二进制树中每个节点的两个子树排序。()深度为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.二进制树的所有节点，如果没有左侧非空子树，