数据结构课后习题第七章

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