《计算机软件技术基础》课后题答案 - 图文(10)

╳10．在二叉树中，具有一个子女的父结点，在中序遍历中，它没有后继的子女结点。

╳11．在二叉树中插入结点，该二叉树便不再是二叉树。 ╳12．用一维数组存储二叉树时，总是以前序遍历存储结点。 √13．已知二叉树的前序遍历和后序遍历序列不能惟一地确定这棵树。 √14．不使用递归，也可以实现二叉树的前序、中序、后序遍历。

√15．在前序遍历二叉树的序列中，任何结点的子树的所有结点都是直接跟在该结点之后。

╳16．有n个结点的不同二叉树有n!棵。

╳17．在哈夫曼编码中，当两个字符出现的频率相同时，其编码也相同，对于这种情况应做特殊处理。 三、填空题

1．树(及一切树形结构)是一种__层次__结构。在树中，__根_结点没有直接前驱。对树上任一结点x来说，x是它的任一子树的根结点惟一的_双亲_。 2．一棵树上的任何结点(不包括根本身)称为根的__子孙__。若B是A的子孙，则称A是B的__祖先__。

3．二叉树第i(i>0)层上至多有__2__个结点。 4．深度为k(k>0)的二叉树至多有__2-1__个结点。

5．对任何二叉树，若度为2的节点数为n2，则叶子数n0=__n2+1__。 6．满二叉树上各层的节点数已达到了二叉树可以容纳的__最大值_。满二叉树也是__完全__二叉树，但反之不然。

7．具有n个结点的完全二叉树的深度为___│log2n│+1___。

8．在顺序存储的二叉树中，编号为i和j的两个结点处在同一层的条件是__ │log2i│ =│ log2j│ ____。

46

ki-1

9．如果将一棵有n个结点的完全二叉树按层编号，则对任一编号为i(0l，则X的双亲PARENT(X)的编号为__│i/2│___。(2)若2i>n，则结点x无__左孩子__且无__右孩子__；否则，X的左孩子LCHILD(X)的编号为__2i __。(3)若2i+1>n，则结点X无__右孩子__；否则，X的右孩子RCHILD(X)的编号为__2i+1__。

10．二叉树通常有___顺序____存储结构和___链式__存储结构两类存储结构。 11．每个二叉链表还必须有一个指向__根__结点的指针，该指针具有标识二叉链表的作用。

12．对二叉链表的访问只能从___根__指针开始。

13．具有n个结点的二叉树中，一共有__2n__个指针域，其中只有__n-1_个用来指向结点的左右孩子，其余的__n+1__个指针域为NULL。

14．已知二叉树中叶子数为40，仅有一个孩子的结点数为20，则总结点数为__99（40+39+20）___。

15．二叉树有不同的链式存储结构，其中最常用的是_二叉链表___与__三叉链表__。

16．可通过在非完全二叉树的“残缺”位置上增设__空指针___将其转化为完全二叉树。

17．具有100个结点的完全二叉树的深度是__7___。 18．深度为90的满二叉树上，第10层有___512___个结点。

19．在__前序__遍历二叉树的序列中，任何结点的子树上的所有结点都是直接跟在该结点之后。

20．具有n个结点的完全二叉树，若按层次从上到下、从左到右对其编号(根结点为1号)，则编号最大的分支结点序号是__│n/2│___，编号最小的分支结点序号是__1_，编号最大的叶结点序号是_n_，编号最小的叶结点序号是__│n/2

47

│+1____。

21．若一棵二叉树的叶子数为n，则该二叉树中左、右子树皆非空的结点个数为__n-1__。

22．任意一棵具有n个结点的二叉树，若它有m个叶子，则该二叉树上度数为1的结点为__n-2m+1__个。

23．设有30个值，用它们构造一棵哈夫曼树，则该哈夫曼树中共有___59__个结点。

24．现有按中序遍历二叉树的结果为ABC，有__5___种不同形态的二叉树可以得到这一遍历结果。

25．以数据集{4，5，6，7，10}为叶结点的权值所构造的哈夫曼树的带权路径长度为_63_.

26．已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树中有__16_个叶结点。

27．设树T的度为4，其中度为1、2、3和4的结点个数分别是4、2、1和1，则T中叶结点的个数是__8_。

28．如果结点a有三个兄弟，而b是a的双亲，则b的度是__4__。

29．一棵树的形状如图6-5所示，它的根结点是__A_，叶结点是__E,J,K,L,O,P,Q,R,N,I__，结点H的度是__3__，这棵树的度是_4_，这棵树的深度是__5__，结点F的儿子结点是_J,K__，结点G的父结点是__C__。

48

30．设结点x有左孩子结点y、右孩子结点z，用三种基本遍历方法得到的遍历序列中x__不一定___是y的前驱，x__不一定__是z的后继，y__一定__是z的前驱(填“一定”，“不”、“不一定”)。

31．在树结构里，有且仅有一个结点没有前驱，称为根。非根结点有且仅有一个_前驱__，且存在一条从根到该结点的__惟一路径__。

32．含有2个结点的二叉树高度至少是__n+1___，至多是__2_(仅含根结点的二叉树高度为1)。

33．设高度为h的二叉树只有度为0和2的结点，则此类二叉树的结点数至少为_2h-1__，至多为__2-1__。 四、应用题

1．分别画出含3个结点的树与二叉树的所有不同形态。 答：略。

2．设在树中，结点x是结点y的双亲，用来表示边。已知一棵树边的集合为：{，，，，，，，，，，}，用树形表示法画出此树，并回答下列问题：

(1)哪个是根结点？ (2)哪些是叶结点？ (3)哪个是g的双亲？ (4)哪些是g的祖先？ (5)哪些是e的子孙？ (6)哪些是f的兄弟？ (7)结点b和j的层次各是多少？ (8)树的深度是多少？ (9)树的度数是多少？

49

h

n

n

答：略。

3．任意一个有n(n>0)个结点的二叉树，已知它有m个叶结点，试证明非叶结点有m-1个度为2，其余度为1。

答：设度为1的结点数n1, 设度为2的结点数n2,分支数B,则有: m+n1+n2=n, B+1=n, B=1*n1+2*n2,即: m+n1+n2=n, n1+2n2+1=n, 解之可得:n2=m-1

4．分别画出图6-6所示二叉树的二叉链表、三叉链表和顺序存储结构。

答：略.

5．分别写出图6-7所示二叉树的前序、中序和后序序列。

答：前序：ABCDEF、中序：CBEFDA和后序：CFEDBA

6．已知一棵二叉树的中序序列和后序序列分别为BDCEAFHG和DECBHGFA，试画出这棵二叉树，并写出其前序遍历序列。 答：前序遍历序列：ABCDEFGH

7．二叉树中的结点进行按层次顺序(每层自左到右)的访问操作称为二叉树的层次遍历，遍历所得到的结点序列称为二叉树的层次序列。现已知一棵二叉树的层次序列为ABCDEFGHIJ，中序序列为DBGEHJACIF，请画出该二又树。

50