Question

数据结构 习题精练

谢谢各位谁能给我答案！

三、填空题
1.任何非空树中有且仅有一个结点没有前驱结点，该结点就是树的___________。
2.结点A有三个兄弟，B是A的双亲结点，结点B的度是___________。
3.已知树中结点总数为n，则此树中所有结点的度之和为___________。
4.度为k的树中第i层最多有___________个结点。
5.深度为h的k叉树最多有个___________结点。
6.具有n个结点的k叉树的最小深度为___________。
7.在具有n个结点的各棵树中，其中深度最小的那棵树的深度是___________，它共有_______个叶结点和 个非叶结点；其中深度最大的那棵树的深度是___________，它共有___________个叶结点和___________个非叶结点。
8.三个结点的树的共有_______种形态，三个结点的二叉树共有_______种形态。
9.非空二叉树中第i层最多有________个结点。
10.深度为h的二叉树最多有___________个结点。
11.具有n个结点的完全二叉树的深度h=___________。
12.具有2000个结点的二叉树的深度至少为___________，至多为___________。
13.若一棵二叉树有10个叶结点，则该二叉树中度为2的结点的个数为___________。
14.如果二叉树中度为2的结点的数目为n2，则其叶结点的数目n0为___________。
15.对具有n个结点的完全二叉树按层次从上到下，每一层从左到右的次序对所有结点进行编号，编号为i的结点的双亲结点的编号为 ，左孩子的编号为___________，右孩子的编号为___________，编号最小的叶结点的序号是___________。
16.若具有n个结点的二叉树采用二叉链表存储结构，则该链表中有___________个指针域，其中___________个指针域存放非空指针，___________个指针域存放空指针nil。
17.设深度为h的二叉树只有度为0和2的结点，该二叉树的结点数可能达到的最大值为___________，最小值为___________。
18.二叉树的遍历方式通常有___________、___________、___________和___________四种。

19.对二叉树进行___________，可以得到该二叉树中结点组成的排序序列。
20.二叉树的前序遍历序列为ABCEFDGH，中序遍历序列为AECFBGDH，其后序遍历序列为___________。
21.已知按前序遍历二叉树的结果为ABC，则共有___________种不同的二叉树可以得到这一遍历结果。
22.已知序列(34,76,45,18,26,54,92,65)，按照逐点插入法建立一棵二叉排序树，该二叉排序树的深度是___________。
23.具有n0个结点的哈夫曼树共有___________个结点。
24.哈夫曼树的叶结点数目为n0，则分支总数B为___________。
五、问题求解题
1.若一棵树有n1个度为1的结点，n2个度为2的结点，……，nm个度为m的结点。求该树中叶结点的个数，写出推导过程。
2.树与二叉树的相互转换，二叉树和树林的相互转换。
3.有一棵二叉树的结点数据采用顺序存储结构，画出该二叉树的逻辑结构。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
E A F D H C G I B
4.设二叉树BT的根结点指针为6，存储结构如下所示，画出该二叉树的逻辑结构。
地址 1 2 3 4 5 6 7 8 9 10
Lchild 0 0 2 3 7 5 8 0 10 1
Data J H F D B A C E G I
Rchild 0 0 0 9 4 0 0 0 0 0
5.一棵具有n个结点的二叉树采用二叉链存储结构，该二叉树所有结点共有多少个空指针域？写出推导过程。
6.满二叉树的分支数为B，叶结点数目为n0，证明满足B=2(n0-1)。

Answer 1

1,根节点 2,4 3,2(n-1) 4,k的（i-1）次方 5，k的h次方再减1 6,log(2)n+1 7,1,n-1,1,n-1,1,n-1 8,2,5 9,2的(i-1)次方