数据结构练 第六章 树.doc

《数据结构练 第六章 树.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数据结构练习第六章树一、选择题1.树最适合用来表示()。A.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数据2.二叉树的第k层的结点数最多为().A．2k-1B.2K+1C.2K-1　　　D.2k-13.设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有（）个空指针域。A.2m-1B.2mC.2m+1D.4m4．设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD，则后序遍历该二叉树得到序列为（）。A.BADCB.BCDAC.CDABD.CBDA5.设某棵二叉树中有2000个结点，

2、则该二叉树的最小高度为（）。A.9B.10C.11D.126．设一棵二叉树的深度为k，则该二叉树中最多有（）个结点。A.2k-1B.2kC.2k-1D.2k-17．设某二叉树中度数为0的结点数为N0，度数为1的结点数为Nl，度数为2的结点数为N2，则下列等式成立的是（）。A.N0=N1+1B.N0=Nl+N2C.N0=N2+1D.N0=2N1+l8．设一棵m叉树中度数为0的结点数为N0，度数为1的结点数为Nl，……，度数为m的结点数为Nm，则N0=（）。A.Nl+N2+……+NmB.l+N2+2N3+3N4+……+(m-1)NmC.N2+2N3+3N4+

3、……+(m-1)NmD.2Nl+3N2+……+(m+1)Nm9．设一组权值集合W={2，3，4，5，6}，则由该权值集合构造的哈夫曼树中带权路径长度之和为（）。A.20B.30C.40D.4510．设二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树满足的条件是（）。A.空或只有一个结点B.高度等于其结点数C.任一结点无左孩子D.任一结点无右孩子11．设某棵三叉树中有40个结点，则该三叉树的最小高度为（）。A.3B.4C.5D.612．深度为k的完全二叉树中最少有（）个结点。A.2k-1-1B.2k-1C.2k-1+1D.2k-113．设某哈夫曼树中

4、有199个结点，则该哈夫曼树中有（）个叶子结点。A.99B.100C.101D.10214．设按照从上到下、从左到右的顺序从1开始对完全二叉树进行顺序编号，则编号为i结点的左孩子结点的编号为（）。A.2i+1B.2iC.i/2D.2i-115．设某棵二叉树的高度为10，则该二叉树上叶子结点最多有（）。A.20B.256C.512D.102416．设一棵完全二叉树中有65个结点，则该完全二叉树的深度为（）。A.8B.7C.6D.517．设一棵三叉树中有2个度数为1的结点，2个度数为2的结点，2个度数为3的结点，则该三叉链权中有（）个度数为0的结点。A.5B

5、.6C.7D.818．设无向图G中的边的集合E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，则从顶点a出发进行深度优先遍历可以得到的一种顶点序列为（）。A.aedfcbB.acfebdC.aebcfdD.aedfbc19．设F是由T1、T2和T3三棵树组成的森林，与F对应的二叉树为B，T1、T2和T3的结点数分别为N1、N2和N3，则二叉树B的根结点的左子树的结点数为（）。A.N1-1B.N2-1C.N2+N3D.N1+N320．设在一棵度数为3的树中，度数为3的结点数有2个，度数为2的结点数有1个，度数为1的

6、结点数有2个，那么度数为0的结点数有（）个。A.4B.5C.6D.721．设一棵m叉树中有N1个度数为1的结点，N2个度数为2的结点，……，Nm个度数为m的结点，则该树中共有（）个叶子结点。A.B.C.D.22．设一组权值集合W=(15，3，14，2，6，9，16，17)，要求根据这些权值集合构造一棵哈夫曼树，则这棵哈夫曼树的带权路径长度为（）。A.129B.219C.189D.22923．设某棵二叉树中只有度数为0和度数为2的结点且度数为0的结点数为n，则这棵二叉中共有（）个结点。A.2nB.n+lC.2n-1D.2n+l24．由权值分别为3,6,7,

7、2,5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（）。A．51B．23C．53D．7425．在一棵二叉树中，第4层上的结点数最多为（）。A．31B．8C．15D．1626．二叉树上叶结点数等于（）。A．分支结点数加1B．单分支结点数加1C．双分支结点数加1D．双分支结点数减127．对某二叉树进行前序遍历的结果为ABDEFC，中序遍历的结果为DBFEAC，则后序周游的结果为（）A．DBFEACB．DFEBCAC．BDFECAD．BDEFAC28．将含100个结点的完全二叉树从根这一层开始，每层上从左到右依次对结点编号，根结点的编号为1。编号为49的结点

8、X的双亲编号为（）A．24B.25C.23D.无法确定29．含有n个结点的二叉树