第五部分 树 带答案

第五部分树带答案第五部分树带答案第五部分树带答案xxx公司第五部分树带答案文件编号：文件日期：修订次数：第1.0次更改批准审核制定方案设计，管理制度第五部分树一、选择题1．高度为h(h>0)的二叉树最少有(A)个结点-1C2．树型结构最适合用来描述(C)

A.有序的数据元素B.无序的数据元素

C.数据元素之间的具有层次关系的数据D.数据元素之间没有关系的数据3．有n(n>0)个结点的完全二叉树的深度是(D)。A.log2(n)B.log2(n)+1C.log2(n+1)D.log24.(B)又是一棵满二叉树。A.二叉排序树 B.深度为5有31个结点的二叉树C.有15个结点的二叉树 D.哈夫曼(Huffman)树5.深度为k的满二叉树有(B)个分支结点。-16.若已知一棵二叉树先序序列为ABCDEFG，中序序列为CBDAEGF，则其后序序列为(A)A

CDBGFEA

B

CDBFGEA

C

CDBAGFE

D

BCDAGFE7.二叉树第i(i>=1)层上至多有(C

)结点。A、２ib、２ic、２i－１d、２i－１8.在一棵具有5层的满二叉树中结点总数为(

A)。A.31

B.32

C.33

D.169.一个二叉树按顺序方式存储在一个维数组中，如图01234567891011121314ABCDEFGHIJ则结点E在二叉树的第(C)层。A、1 B、2 C、3 D、10．一棵度为3的树中，度为3的结点个数为2，度为2的结点个数为1，则度为0的结点个数为(

C

)

A．4

B．5

C．6

D．711.在一棵二叉树上第5层的结点数最多是(B) A8 B16 C32 D1512.设一棵完全二叉树共有699个结点，则在该二叉树中的叶子结点数为(B)。 A.349 B.350 C.255 D.35113.有n(n>0)个结点的完全二叉树的深度是(

D)。 A. B. C. D.14．下面几个符号串编码集合中，不是前缀编码的是(

B)。 A.{0,10,110,1111} B.{11,10,001,101,0001} C.{00,010,0110,1000} D.{B,C,AA,AC,ABA,ABB,ABC}15．在一棵三叉树中，度为3的结点个数为2个，度为2的结点个数为1个，度为1的结点个数为2个，则度为0的结点个数为(

C)个。 A.4 B.5 C.6 D.716．一棵二叉树高度为h，所有结点的度为0或2，则这棵二叉树最少有(B)个结点。 A.2h B.2h-1 C.2h+1 D.h+117．将有关二叉树的概念推广到三叉树，则一棵有244个结点的完全三叉树的高度是(C)。 A.4 B.5 C.6 D.718．树有先根遍历和后根遍历，树可以转化为对应的二叉树。下面的说法正确的是(B)。树的后根遍历与其对应的二叉树的后根遍历相同树的后根遍历与其对应的二叉树的中根遍历相同树的先根遍历与其对应的二叉树的中根遍历相同以上都不对19．按照二叉树的定义，具有3个结点的二叉树有(C)种。 A. 3 B. 4 C. 5 D.620．前序遍历序列与中序遍历序列相同的二叉树为(D)。根结点无左子树的二叉树根结点无右子树的二叉树只有根结点的二叉树或非叶子结点只有左子树的二叉树只有根结点的二叉树或非叶子结点只有右子树的二叉树21．前序遍历序列与后序遍历序列相同的二叉树为(C)。非叶子结点只有左子树的二叉树根结点无右子树的二叉树只有根结点的二叉树非叶子结点只有右子树的二叉树22．设某二叉树有如下特点：结点的子树数目不是2就是0。这样的一棵二叉树中有m(m>0)个子树为0的结点时，该二叉树上的结点总数为(B)。 A.2m+1 B.2m-1 23．树是结点的集合，它有(A)个根结点。二叉树有(C)个根结点，按一定的规则，任一树都可以转换成唯一对应的二叉树。 A.1且只有1 B.1或多于1 C.0或1 D.至少224．当一棵二叉树的前序序列和中序序列分别是HGEDBFCA和EGBDHFAC时，其后序序列必是(B)，层次序列是(C)。 A.BDEAGFHC B.EBDGACFH C.HGFEDCBA D.HFGDEABC25．二叉树中结点的儿子的顺序是(A)A.确定的 B.可变的 C.任意的 D.未知26．在二叉树的二叉链表存储方式中，具有n个结点的二叉树中有（C）个非空的指针域。 B.n+1D.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．将

树

转化为二叉树时，其根结点的右子树总是空的。8．哈夫曼树是带权路径长度

最小

的树，通常权值较大的结点离根结点

越近

。9．具有n个叶子的二叉树，每个叶子的权值为wi(1≤i≤n)其中带权路径最小的二叉树被称为___哈夫曼树或最有二叉树______。10．若已知一棵二叉树的先序序列为–+a*b–cd/ef，中序序列为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．一棵完全二叉树有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。三、判断题1．完全二叉树就是满二叉树。(W)2．已知一棵二叉树的前序序列和中序序列可以唯一地构造出该二叉树。(R)四、算法题1．设二叉树T的存储结构为二叉链表,结点结构定义如下：structnode{chardata；//data为字符型structnode*lchild,*rchild；//指向左右孩子的指针}；设root为二叉树T的根指针，对二叉树T执行算法traversal(root),试指出其输出结果；算法(C函数)如下：voidtraversal(structnode*root){if(root){printf("%c",root->data)；traversal(root->lchild)；printf("%c",root->data)；traversal(root->rchild)；}}ACEEFFCABGGBDD2．编写递归算法，计算二叉树中叶子结点的数目。intleaf_count(BiNode*T,int*count)/*初始化时*count=0，用其记录T中叶子结点的个数*/{ if(T){ if(T->lchild==NULL&&T->rchild==NULL) *count++; else{ leaf_count(T->lchild,*count); leaf_count(T->rchild,*count); } }}五、操作题1．二叉树有哪几种基本形态画图说明之。（5种）2．二叉树的顺序存储结构，并写出其先序、后序、中序的遍历序列。012345678910ACBDEGFH先序：ACDEFHBG后序：DFHECGBA中序：DCFEHABG3．给定30个字符组成的电文:DDDDDAAABEEAAFCDAACABBCCCBAADD试为字符A、B、C、D、E、F设计哈夫曼(Huffman)编码。(1)画出相应的哈夫曼树；(2)分别列出A、B、C、D、E、F的哈夫曼码；(3)计算该树的带权路径长度WPL。(WPL=70)4．试将森林F={T1,T2,T3,T4}转换为一棵二叉树。T1T2T3T45．试画出下列二叉树的中序线索二叉树存储结构图。二叉树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．某二叉树的结点数据采用顺序存储表示如