数据结构课后习题第七章.pdfVIP

数据结构课后习题第七章--第1页

一、选择题

1.设树T的度为4，其中度为1,2，3和4的结点个数分别为4,2,1,1，则T中的叶

结点的个数为（）。

A.5B.6

C.7D.8

2.设森林F中有三棵树，第一、第二、第三棵树的结点个数分别为M1，M2和

M3。与森林F对应的二叉树根结点的右子树上的结点个数为（）。

A.M1B.M1+M2

C.M3D.M2+M3

3.将一棵树T转换为孩子—兄弟链表表示的二叉树H,则T的后跟序遍历是H的

（）。

A.前序遍历B.中序遍历

C.后序遍历

4.设F是一个森林，B是由F变换得的二叉树。若F中有n个非终端顶点，则

B中右指针域为空的结点有（）。

A.n-1B.n

C.n+1D.n+2

5.如果T是由有序树T转换而来的二叉树，那么T中结点的后序遍历序列就是

2

T的（）遍历序列。

2

A.先序B.中序

C.后序D.层次序

6.在一颗度为4的树T中，若有20个度为4的结点，10个度为3的结点，1

个度为2的结点，10个度为1的结点，则树T中叶结点的个数是（）。

A.41B.42

C.82D.122

二、判断题

1.树形结构中元素之间存在一对多个的关系.（）。

2.将一棵树转成二叉树，根结点没有左子树（）。

3.树与二叉树是两种不同的树形结构。（）

4.对树定义中序遍历和对森林定义后序遍历都无意义（）。

5.由树的先序遍历序列和后序遍历序列可以唯一确定该树（）。

三、填空题

1.树在计算机内的表示方式有（），（），（）。

2.已知一棵树度为3的树有2个度为1的结点，3个度为2的结点，4个度为3

的结点，则该树有（）个叶子结点。

3.每一棵树都能唯一的转换为它所对应的二叉树。若已知一颗二叉树的前序遍历

序列是BEFCGDH，中序遍历序列是FEBGCHD，则它的后序遍历序列是（）。

设上述二叉树是由某棵树转换而成，则该树的先序遍历序列是（）。

4.先序遍历森林正好等同于按（）遍历对应的二叉树，后序遍历森林正好等同

于按（）遍历对应的二叉树。

数据结构课后习题第七章--第1页

数据结构课后习题第七章--第2页

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）树的度数是