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

《数据结构-树和二叉树-习题.docx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、树与二叉树一.选择题1.假定在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为（）个。A．15B．16C．17D．472.按照二叉树的定义，具有3个结点的不同形状的二叉树有（）种。A.3B.4C.5D.63.按照二叉树的定义，具有3个不同数据结点的不同的二叉树有（）种。A.5B.6C.30D.324.深度为5的二叉树至多有（）个结点。深度为n的二叉树结点至多有2n-1A.16B.32C.31D.105.设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为（）。A.2hB.2h-1C.2h+1D.h+16.对一个满二叉

2、树满二叉树是除最后一层无任何子节点外，每一层上的所有结点都有两个子结点的二叉树，m个树叶，n个结点，深度为h，则（）。A.n=h+m对于深度为h的满二叉树，n=20+21+…+2h-1=2h-1，m=2h-1。故而n=h+m。B.h+m=2nC.m=h-1D.n=2h-17.任何一棵二叉树的叶结点在先序.中序和后序遍历序列中的相对次序（）。A.不发生改变B.发生改变C.不能确定D.以上都不对8.如果某二叉树的前根次序遍历结果为stuwv，中序遍历为uwtvs，那么该二叉树的后序为（）。A.uwvtsB.vwutsC.wuvtsD.wutsv9.某二叉树的前序遍历结点

3、访问顺序是abdgcefh，中序遍历的结点访问顺序是dgbaechf，则其后序遍历的结点访问顺序是（）。A.bdgcefhaB.gdbecfhaC.bdgaechfD.gdbehfca10.在一非空二叉树的中序遍历序列中，根结点的右边（）。A.只有右子树上的所有结点B.只有右子树上的部分结点C.只有左子树上的部分结点D.只有左子树上的所有结点11.树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历.中序遍历和后序遍历。这里，我们把由树转化得到的二叉树树转化为二叉树的基本方法是把所有兄弟结点都用线连起来，然后去掉双亲到子女的连线，只留下双亲到

4、第一个子女的连线。因此原来的兄弟关系就变为双亲与右孩子的关系。叫做这棵数对应的二叉树。结论（）是正确的。A.树的先根遍历序列与其对应的二叉树的先序遍历序列相同B.树的后根遍历序列与其对应的二叉树的后序遍历序列相同C.树的先根遍历序列与其对应的二叉树的中序遍历序列相同D.以上都不对1.如图所示二叉树的中序遍历序列是（）。A.abcdgefB.dfebagcC.dbaefcgD.defbagc2.一棵二叉树如图所示，其中序遍历的序列为（）。A.abdgcefhB.dgbaechfC.gdbehfcaD.abcdefgh3.设a,b为一棵二叉树上的两个结点，在中序遍历时，

5、a在b前的条件是（）。A．a在b的右方B．a在b的左方C．a是b的祖先D．a是b的子孙4.已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是（）。A.acbedB.decabC.deabcD.cedba5.如下图所示的4棵二叉树，（）不是完全二叉树深度为k的有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时，成为完全二叉树。即除第h层外，其它各层(1～h-1)的结点数都达到最大个数，第h层所有的结点都连续集中在最左边。。ABCD6.实现任意二叉树的后序遍历的非递归算法而不使用栈结构，最佳方案

6、是二叉树采用（）存储结构。A.二叉链表B.广义表存储结构C.三叉链表三叉链表是二叉树的另一种主要的链式存储结构。三叉链表与二叉链表的主要区别在于，它的结点比二叉链表的结点多一个指针域，该域用于存储一个指向本结点双亲的指针。三叉链表的结点形式如下D.顺序存储结构7.树最适合用来表示（）。A.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数据8.某二叉树结点的中序序列为A.B.C.D.E.F.G，后序序列为B.D.C.A.F.G.E，则其左子树中结点数目为（）。A.3B.2C.4D.59.二叉树是非线性数据结构，所以（）。A.它不能用

7、顺序存储结构存储;B.它不能用链式存储结构存储;C.顺序存储结构和链式存储结构都能存储;D.顺序存储结构和链式存储结构都不能使用1.具有n(n>0)个结点的完全二叉树的深度K层完全二叉树，就是前（K-1）层为满二叉树，第K层均为叶结点，可以不满。所以结点与深度的关系为：2K-1-1