一、 选择题
1.设树T的度为4，其中度为1,2，3和4的结点个数分别为4,2,1,1，则T中的叶结点的个数为（ ）。
A.5 B.6
C.7 D.8
2. 设森林F中有三棵树，第一、第二、第三棵树的结点个数分别为M1，M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数为（ ）。
A.M1 B.M1+M2
C.M3 D.M2+M3
3.将一棵树T转换为孩子—兄弟链表表示的二叉树H,则T的后跟序遍历是H的（ ）。
A.前序遍历 B.中序遍历
C.后序遍历
4. 设F是一个森林，B是由F变换得的二叉树。若F中有n个非终端顶点，则B中右指针域为空的结点有（ ）。
A.n-1 B.n
C.n+1 D.n+2
5.如果是由有序树T转换而来的二叉树，那么T中结点的后序遍历序列就是的（ ）遍历序列。
A.先序 B.中序
C.后序 D.层次序
6. 在一颗度为4的树T 中，若有20个度为4的结点，10个度为3的结点，1个度为2的结点，10个度为1的结点，则树T中叶结点的个数是（ ）。
A.41 B.42
C.82 D.122
二、判断题
1.树形结构中元素之间存在一对多个的关系.（ ）。
2.将一棵树转成二叉树，根结点没有左子树（ ）。
3.树与二叉树是两种不同的树形结构。（ ）
4.对树定义中序遍历和对森林定义后序遍历都无意义（ ）。
5.由树的先序遍历序列和后序遍历序列可以唯一确定该树（ ）。
三、填空题
1.树在计算机内的表示方式有（ ），（ ），（ ）。
2.已知一棵树度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树有（ ）个叶子结点。
3.每一棵树都能唯一的转换为它所对应的二叉树。若已知一颗二叉树的前序遍历序列是BEFCGDH，中序遍历序列是FEBGCHD，则它的后序遍历序列是（ ）。设上述二叉树是由某棵树转换而成，则该树的先序遍历序列是（ ）。
4. 先序遍历森林正好等同于按（ ）遍历对应的二叉树，后序遍历森林正好等同于按（ ）遍历对应的二叉树。
5.利用树的孩子兄弟表示法存储，可以将一棵树转换为（ ）。
四、应用题
1.假设在树中，结点x是结点y的双亲，用（x,y）表示树的边。已知一棵树的边集为：{（i,m），（i,n），（b,e），（e,i），（b,d），（a,b），（g,i）,（g,k），（c,g），（c,f），（h,l），（c,h）,（a,c），}用图形表示法画出此树，并回答下列问题。
（1）哪个是根结点？
（2）那些是叶结点？
（3）那个是g的双亲？
（4）那些是g的祖先？
（5）那些是g的孩子？
（6）那些是e的孙子？
（7）那些是e的兄弟？那些是f的兄弟？
（8）结点b和n的层次各是多少？
（9）树的深度是多少？
（10）以结点c为根的子树的深度是多少？
（11）树的度数是多少？
2.一棵度为2的有序树与一棵二叉树有何区别？
3.试分别画出具有4个结点的树和4个结点的二叉树的所有不同形态。
4.一个深度为h的满二叉树有如下性质：第h层上的结点都是叶子结点，其余各层上每个结点都是k棵非空子树。如果按层次顺序（同层自左至右）为全部的结点编号，回答下列问题。
（1）各层的结点数目是多少？
（2）编号为i的双亲结点（若存在）的编号是多少？
（3）编号为i的结点的第j个孩子结点（若存在）的编号是多少？
（4）编号为i的结点有右兄弟的条件是什么？其右兄弟的编号是多少？
5.已知一颗二叉树的前序遍历序列和后序遍历序列分别为ABDGHCEFI和GDHBAECIF，请画出此二叉树。
6.已知一颗二叉树的前序遍历序列和后序遍历序列分别为BDCEAFHG和DECBHGFA，请画出此二叉树。
7.已知一颗二叉树的层次遍历序列为ABCDEFGHIJ，中序遍历序列为DBGEHJACIF，请画出该二叉树。
8.一棵有n（n>0）各结点的d度树，若用多重链表表示，树中每个结点都有d个链域，则在表示该树的多重链表中有多少个空链域？为什么？
9.一棵共有n个结点的树，其中所有分支结点的度均为K，求该树中叶子结点的个数。
10.写出图7.25所示树的的先序和后序遍历序列，并将此树转化成二叉树。
11.写出图7.26所示森林的先序和中序遍历序列，并将此树转化成二叉树。
12.将图7.27所示的二叉树转化成树或森林。
先序中序后序遍历二叉树13.已知一个森林的先序序列和后序序列如下，请构造出该森林。
先序序列：ABCDEFGHIJKLMNO
后续序列：CDEBFHIJGAMLONK
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论