数据结构练习 章 树.doc

数据结构练习 第六章 树 一、选择题 1.树最适合用来表示 。 A.有序数据元素 B.无序数据元素 C.元素之间具有分支层次关系的数据 D.元素之间无联系的数据 2.二叉树的第k层的结点数最多为 . A．2k-1 B.2K+1 C.2K-1 D. 2k-1 3.设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有（ ）个空指针域。 A. 2m-1 B. 2m C. 2m+1 D. 4m 4．设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD，则后序遍历该二叉树得到序列为（ ）。 A. BADC B. BCDA C. CDAB D. CBDA 5.设某棵二叉树中有2000个结点，则该二叉树的最小高度为（ ）。 A. 9 B. 10 C. 11 D. 12 6．设一棵二叉树的深度为k，则该二叉树中最多有（ ）个结点。 A. 2k-1 B .2k C. 2k-1 D. 2k-1 7．设某二叉树中度数为0的结点数为N0，度数为1的结点数为Nl，度数为2的结点数为N2，则下列等式成立的是（ ） B. N0 Nl+N2 C. N0 N2+1 D. N0 2N1+l 8．设一棵m叉树中度数为0的结点数为N0，度数为1的结点数为Nl，……，度数为m的结点数为Nm，则N0 （ ）m C. N2+2N3+3N4+……+ m-1 Nm D. 2Nl+3N2+……+ m+1 Nm 9．设一组权值集合W 2，3，4，5，6 ，则由该权值集合构造的哈夫曼树中带权路径长度之和为（ ）。 A. 20 B. 30 C. 40 D. 45 10．设二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树满足的条件是（ ）。 A. 空或只有一个结点 B. 高度等于其结点数 C. 任一结点无左孩子 D. 任一结点无右孩子 11．设某棵三叉树中有40个结点，则该三叉树的最小高度为（ ）。 . 4 C. 5 D. 6 12．深度为k的完全二叉树中最少有（ ）个结点。 A. 2k-1-1 B. 2k-1 C. 2k-1+1 D. 2k-1 13．设某哈夫曼树中有199个结点，则该哈夫曼树中有（ ）个叶子结点。 A. 99 B. 100 C. 101 D. 102 14．设按照从上到下、从左到右的顺序从1开始对完全二叉树进行顺序编号，则编号为i结点的左孩子结点的编号为（ ）。 A. 2i+1 B. 2i C. i/2 D. 2i-1 15．设某棵二叉树的高度为10，则该二叉树上叶子结点最多有（ ）。 A. 20 B. 256 C. 512 D. 1024 16．设一棵完全二叉树中有65个结点，则该完全二叉树的深度为（ ）。 A. 8 B. 7 C. 6 D. 5 17．设一棵三叉树中有2个度数为1的结点，2个度数为2的结点，2个度数为3的结点，则该三叉链权中有（ ）个度数为0的结点。 A. 5 B. 6 C. 7 D. 8 18．设无向图G中的边的集合E a，b ， a，e ， a，c ， b，e ， e，d ， d，f ， f，c ，则从顶点a出发进行深度优先遍历可以得到的一种顶点序列为（ ）。 A. aedfcb B. acfebd C. aebcfd D.aedfbc 19．设F是由T1、T2和T3三棵树组成的森林，与F对应的二叉树为B，T1、T2和T3的结点数分别为N1、N2和N3，则二叉树B的根结点的左子树的结点数为（ ）。 A. N1-1 B. N2-1 C. N2+N3 D. N1+N3 20．设在一棵度数为3的树中，度数为3的结点数有2个，度数为2的结点数有1个，度数为1的结点数有2个，那么度数为0的结点数有（ ）个。 A. 4 B. 5 C. 6 D. 7 21．设一棵m叉树中有N1个度数为1的结点，N2个度数为2的结点，……，Nm个度数为m的结点，则该树中共有（ ）个叶子结点。 A. B. C. D. 22．设一组权值集合W 15，3，14，2，6，9，16，17 ，要求根据这些权值集合构造一棵哈夫曼树，则这棵哈夫曼树的带权路径长度为（ ）。 A.129 B. 219 C. 189 D. 229 23．设某棵二叉树中只有度数为0和度数为2的结点且度数为0的结点数为n，则这棵二叉中共有（ ）个结点。 A. 2n B. n+l C. 2n-1 D. 2n+l 24．由权值分别为3,6,7,2,5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（ ）。 A．51 B．23 C．53 D．74 25．在一棵二叉树中，第4层上的结点数最多为（ ）。 A．31 B．8 C．15 D．16 26．二叉树上叶结点数等于（ ）。 A．分支结