第五部分-树--带答案WORD

1、文档可能无法思考全面，请浏览后下载! 第五部分 树一、选择题1高度为h(h>0) 的二叉树最少有( A )个结点A.h B.h-1 C.h+1 D.2h2树型结构最适合用来描述( C )A.有序的数据元素 B.无序的数据元素C.数据元素之间的具有层次关系的数据 D.数据元素之间没有关系的数据3有n(n>0)个结点的完全二叉树的深度是( D )。 A.élog2(n)ù B.élog2(n)+1ù C.ëlog2(n+1)û D.ëlog2(n)+1û4. ( B )又是一棵满二叉树。 A.二叉排序树 B

2、.深度为5有31个结点的二叉树C.有15个结点的二叉树D.哈夫曼(Huffman)树5. 深度为k的满二叉树有( B )个分支结点。A.2k-1 B.2k-1-1 C.2k-2 D.2k-1+16. 若已知一棵二叉树先序序列为ABCDEFG，中序序列为CBDAEGF，则其后序序列为( A )A  CDBGFEA     B  CDBFGEA    C  CDBAGFE    D  BCDAGFE7. 二叉树第i(i>=1)层上至多有( C 

3、)结点。A、ib、ic、id、i8. 在一棵具有5层的满二叉树中结点总数为 (  A )。A. 31             B. 32       C. 33       D. 169. 一个二叉树按顺序方式存储在一个维数组中，如图0 1 2 3 4 5 6 7 8 9 10 11 12 13 14ABCDEFGHIJ则结点E在二叉树的第( C

4、)层。A、1B、2C、3D、410一棵度为3的树中，度为3的结点个数为2，度为2 的结点个数为1，则度为0的结点个数为(  C  ) A4           B5            C6          D78 / 811

5、. 在一棵二叉树上第5层的结点数最多是( B )A 8B 16C 32D 1512. 设一棵完全二叉树共有699个结点，则在该二叉树中的叶子结点数为( B )。A. 349B. 350C. 255D. 35113. 有n(n>0)个结点的完全二叉树的深度是( D )。A. B. C. D. 14下面几个符号串编码集合中，不是前缀编码的是( B )。A. 0,10,110,1111B. 11,10,001,101,0001C. 00,010,0110,1000D. B,C,AA,AC,ABA,ABB,ABC15在一棵三叉树中，度为3的结点个数为2个，度为2的结点个数为1

6、个，度为1的结点个数为2个，则度为0的结点个数为( C )个。A. 4B. 5C. 6D. 716一棵二叉树高度为h，所有结点的度为0或2，则这棵二叉树最少有( B )个结点。A. 2hB. 2h-1C. 2h+1D. h+117将有关二叉树的概念推广到三叉树，则一棵有244个结点的完全三叉树的高度是( C )。A. 4B. 5C. 6D. 718树有先根遍历和后根遍历，树可以转化为对应的二叉树。下面的说法正确的是( B )。A. 树的后根遍历与其对应的二叉树的后根遍历相同B. 树的后根遍历与其对应的二叉树的中根遍历相同C. 树的先根遍历与其对应的二叉树的中根遍历相同D. 以上都不对

7、19按照二叉树的定义，具有3个结点的二叉树有( C )种。A.3B.4C.5D. 620前序遍历序列与中序遍历序列相同的二叉树为( D )。A. 根结点无左子树的二叉树B. 根结点无右子树的二叉树C. 只有根结点的二叉树或非叶子结点只有左子树的二叉树D. 只有根结点的二叉树或非叶子结点只有右子树的二叉树21前序遍历序列与后序遍历序列相同的二叉树为( C )。A. 非叶子结点只有左子树的二叉树B. 根结点无右子树的二叉树C. 只有根结点的二叉树D. 非叶子结点只有右子树的二叉树22设某二叉树有如下特点：结点的子树数目不是2就是0。这样的一棵二叉树中有m(m>0)个子树为0的结点时，该二叉树

8、上的结点总数为( B )。A. 2m+1B. 2m-1C. 2(m+1)D. 2(m-1)23树是结点的集合，它有( A )个根结点。二叉树有( C )个根结点，按一定的规则，任一树都可以转换成唯一对应的二叉树。A. 1且只有1B. 1或多于1C. 0或1D. 至少224当一棵二叉树的前序序列和中序序列分别是HGEDBFCA和EGBDHFAC时，其后序序列必是( B )，层次序列是( C )。A. BDEAGFHCB. EBDGACFHC. HGFEDCBAD. HFGDEABC25二叉树中结点的儿子的顺序是( A )A.确定的 B.可变的 C.任意的 D.未知26在二叉树的二叉链表存储方式中

9、，具有n个结点的二叉树中有（ C ）个非空的指针域。 A.2n B. n+1 C.n-1 D. n二、填空题1深度为 n(n>0) 的二叉树最多有 _2n-1_ 个结点。2对于一棵具有n个结点的二叉树，对应二叉链表中指针总数有 2n 个，其中 n-1 个用于指向孩子结点， n+1 个指针空闲。3一棵深度为6的满二叉树有_31_个非终端结点。4若一棵二叉树中有8个度为2的结点,则它有_9_个叶子。5树中结点A的 _子树的数目_ 称为结点A的度。6一棵深度为4的二叉树最多有 _15_ 个结点。7将         

10、;  树          转化为二叉树时，其根结点的右子树总是空的。8哈夫曼树是带权路径长度   最小      的树，通常权值较大的结点离根结点   越近      。9具有n个叶子的二叉树，每个叶子的权值为wi(1in)其中带权路径最小的二叉树被称为 _哈夫曼树或最有二叉树_。10若已知一棵二叉树的先序序列为 + a * b c d

11、 / e f，中序序列为a + b * c d e / f，则其后序序列为_abcd-*+ef/-_。11已知一棵完全二叉树中共有768结点，则该树中共有_384_个叶子结点。12已知二叉树有50个叶子结点，且仅有一个孩子的结点数为30，则总结点数为 129。13对于一棵具有n个结点的二叉树，对应二叉链表中指针总数_2n_个，其中_n-1个用于指向孩子结点。14哈夫曼树是带权路径长度_最小_的树，通常权值较大的结点离根_越近_。15一个深度为k、具有最少结点数的完全二叉树，按层次用自然数依次对结点编号，则编号最小的叶子序号为_2k-2+1_，编号为i的结点所在的层次号是 。16一棵完全二叉树有

12、999个结点，它的深度为 10 ，叶子结点数为 500 个。17如果一棵树有n1个深度为1的结点，n2个深度为2的结点，nm个度为m的结点，则该树中叶子结点数为： 2n2+3n3+m*nm+1-(n2+n3+nm) 18对于一棵具有n个结点的树，该树中所有结点的度数之和为 n-1 。19在一棵二叉树中，假定双分支结点数为5个，单分支结点个数为6个，则叶子结点数为 6 个。20对于一棵二叉树，若一个结点的编号为i，则它的左孩子结点的编号为 2i ，右孩子结点的编号为 2i+1 ，双亲结点的编号为 (i/2)下取整 。21假定一棵二叉树的结点数为18，则它的最少深度为 5 ，最大深度为 18 。

13、三、判断题1完全二叉树就是满二叉树。( W )2已知一棵二叉树的前序序列和中序序列可以唯一地构造出该二叉树。( R )四、算法题1设二叉树T的存储结构为二叉链表,结点结构定义如下： struct node char data； /data为字符型 struct node *lchild,*rchild； /指向左右孩子的指针 ； 设root为二叉树T的根指针，对二叉树T执行算法traversal(root),试指出其输出结果； 算法(C函数)如下： void traversal(struct node *root) if(root) printf("%c",root->

14、;data)； traversal(root->lchild)； printf("%c",root->data)； traversal(root->rchild)； ACEEFFCABGGBDD2编写递归算法，计算二叉树中叶子结点的数目。int leaf_count(BiNode *T, int *count)/*初始化时*count=0，用其记录T中叶子结点的个数*/if(T)if(T->lchild=NULL && T->rchild=NULL)*count+;elseleaf_count(T->lchild, *co

15、unt);leaf_count(T->rchild, *count);五、操作题1二叉树有哪几种基本形态? 画图说明之。（5种）2二叉树的顺序存储结构，并写出其先序、后序、中序的遍历序列。0 1 2 3 4 5 6 7 8 9 10 11121314ACBDE G FH先序：ACDEFHBG后序：DFHECGBA中序：DCFEHABG3给定30个字符组成的电文:D D D D D A A A B E E A A F C D A A C A B B C C C B A A D D试为字符 A、B、C、D、E、F 设计哈夫曼(Huffman)编码。 (1)画出相应的哈夫曼树； (2)分别列出

16、 A、B、C、D、E、F 的哈夫曼码；(3)计算该树的带权路径长度WPL。(WPL=70)4试将森林 F= T1,T2,T3,T4 转换为一棵二叉树。 T1 T2 T3 T45试画出下列二叉树的中序线索二叉树存储结构图。 二叉树6试用孩子兄弟(左孩子右兄弟)表示法画出下列树的存储结构图。 树7已知二叉树的前序遍历序列和中序遍历序列分别是：B,A,C,D,F,E,G和D,C,A,F,G,E,B, 试画出该二叉树。8试用双亲表示法画出下列树T的存储结构图。9假定后序遍历二叉树的结果是A,C,B(1)试画出所有可得到这一结果的不同形态的二叉树；(5种)(2)分别写出这些二叉树的中序遍历序列。ABC,ACB,CAB,BAC,BCA10有9个带权结点 a、b、c、d、e、f、g、h、I，分别带权 4，2，7，12，6，10，5，9，3，试以他们为叶子结点构造一棵哈夫曼树（请按照左子树根结点的权小于等于右子树根结点的权的次序构造）。11某二叉树的结点数据采用顺序存储表示如下：(1) 试画出此二叉树的图形表示。 (2)