第六章树和二叉树试题一、单项选择题1.树中所有结点的度等于所有结点数加（）。

A. 0B. 1C. -1D. 22.在一棵树中，（）没有前驱结点。

A. 分支结点B. 叶结点C. 根结点D. 空结点3.在一棵二叉树的二叉链表中，空指针域数等于非空指针域数加（）。

A. 2B. 1C. 0D. -14.在一棵具有n个结点的二叉树中，所有结点的空子树个数等于（）。

A. nB. n-1C. n+1D. 2*n5.在一棵具有n个结点的二叉树的第i层上（假定根结点为第0层，i大于等于0而小于等于树的高度），最多具有（）个结点。

A. 2iB. 2i+1C. 2i-1D. 2n6.在一棵高度为h（假定根结点的层号为0）的完全二叉树中，所含结点个数不小于（）。

A. 2h-1B. 2h+1C. 2h-1D. 2h7.在一棵具有35个结点的完全二叉树中，该树的高度为（）。

假定空树的高度为-1。

A. 5B. 6C. 7D. 88.在一棵具有n个结点的完全二叉树中，分支结点的最大编号为（）。

假定树根结点的编号为0。

A. ?(n-1)/2?B. ?n/2?C. ?n/2?D. ?n/2? -19.在一棵完全二叉树中，若编号为i的结点存在左孩子，则左子女结点的编号为（）。

假定根结点的编号为0A. 2iB. 2i-1C. 2i+1D. 2i+210.在一棵完全二叉树中，假定根结点的编号为0，则对于编号为i（i＞0）的结点，其双亲结点的编号为（）。

A. ?(i+1)/2?B. ?(i-1)/2?C. ?i/2?D. ?i/2? -111.在一棵树的左子女-右兄弟表示法中，一个结点的右孩子是该结点的（）结点。

A. 兄弟B. 子女C. 祖先D. 子孙12.在一棵树的静态双亲表示中，每个存储结点包含（）个域。

A. 1B. 2C. 3D. 413.已知一棵二叉树的广义表表示为a (b (c), d (e ( , g (h) ), f ) )，则该二叉树的高度为（）。

假定根结点的高度为0。

A. 3B. 4C. 5D. 614.已知一棵树的边集表示为 {<A, B>, <A, C>, <B, D>, <C, E>, <C, F>, <C,G>, <F, H>, <F, I>}，则该树的高度为（）。

假定根结点的高度为0。

A. 2B. 3C. 4D. 515.利用n个值作为叶结点上的权值生成的霍夫曼树中共包含有（）个结点。

A. nB. n+1C. 2*nD. 2*n-116.利用3, 6, 8, 12这四个值作为叶结点的权值生成一棵霍夫曼树，该树的带权路径长度为（）。

A. 55B. 29C. 58D. 3817.一棵树的广义表表示为a (b, c (e, f (g) ), d)，当用左子女-右兄弟链表表示时，右指针域非空的结点个数为（）。

A. 1B. 2C. 3D. 418.向具有n个结点的堆中插入一个新元素的时间复杂度为（）。

A. O(1)B. O(n)C. O(log2n)D. O(nlog2n)参考答案： 1. C 2. C 3. A 4. C 5. A6. D7. A8. D9. C 10. B11. A 12. B 13. B 14. B 15. D16. A 17. C 18. C二、填空题1.对于一棵具有n个结点的树，该树中所有结点的度数之和为______。

2.在一棵树中，______结点没有前驱结点。

3.在一棵树中，______结点没有后继结点。

4.一棵树的广义表表示为a (b (c, d (e, f), g (h) ), i (j, k (x, y) ) )，结点k的所有祖先的结点数为______个。

5.一棵树的广义表表示为a (b (c, d (e, f), g (h) ), i (j, k (x, y) ) )，结点f的层数为______。

假定根结点的层数为0。

6.假定一棵三叉树（即度为3的树）的结点个数为50，则它的最小高度为______。

假定根结点的高度为0。

7.在一棵高度为3的四叉树中，最多含有______结点。

8.在一棵三叉树中，度为3的结点数有2个，度为2的结点数有1个，度为1的结点数为2个，那么度为0的结点数有______个。

9.一棵高度为5的完全二叉树中，最多包含有______个结点。

假定根结点的高度为0。

10.假定一棵树的广义表表示为A (B (C, D (E, F, G), H (I, J) ) )，则该树的高度为______。

假定根结点的高度为0。

11.在一棵二叉树中，假定度为2的结点个数为5个，度为1的结点个数为6个，则叶结点数为______个。

12.假定一棵二叉树的结点个数为18，则它的最小高度为______。

假定根结点的高度为0。

13.在一棵高度为h的理想平衡树（即从0层到h-1层都是满的，第h层的结点分布在该层各处）中，最少含有______个结点。

假定根结点的高度为0。

14.在一棵高度为h的理想平衡树（即从0层到h-1层都是满的，第h层的结点分布在该层各处）中，最多含有______个结点。

假定根结点的高度为0。

15.若将一棵树A (B (C, D, E), F (G (H), I) ) 按照左子女-右兄弟表示法转换为二叉树，该二叉树中度为2的结点个数为______个。

16.一棵树按照左子女-右兄弟表示法转换成对应的二叉树，则该二叉树中______结点肯定没有右子女。

17.在一个堆的顺序存储中，若一个元素的下标为i（0≤i≤n-1），则它的左子女元素的下标为______。

18.在一个堆的顺序存储中，若一个元素的下标为i（0≤i≤n-1），则它的右子女元素的下标为______。

19.在一个小根堆（即最小堆）中，堆顶结点的值是所有结点中的______。

20.在一个大根堆（即最大堆）中，堆顶结点的值是所有结点中的______。

21.6个结点可构造出________种不同形态的二叉树。

22.设森林F中有4棵树，第1、2、3、4棵树的结点个数分别为n1、n2、n3、n4，当把森林F转换成一棵二叉树后，其根结点的右子树中有________个结点。

23.设森林F中有4棵树，第1、2、3、4棵树的结点个数分别为n1、n2、n3、n4，当把森林F转换成一棵二叉树后，其根结点的左子树中有________个结点。

24.将含有82个结点的完全二叉树从根结点开始顺序编号，根结点为第0号，其他结点自上向下，同一层自左向右连续编号。

则第40号结点的双亲结点的编号为________。

参考答案： 1. n-1 2. 树根 3. 叶子 4. 25. 36. 47. 858. 69. 63 10. 311. 6 12. 4 13. 2h14. 2h+1-1 15. 216. 根17. 2i+1 18. 2i+2 19. 最小值20. 最大值21. 132 22. n2+n3+n4 23. n1-1 24. 19三、判断题1.当向一个小根堆（最小堆）中插入一个具有最小值的元素时，该元素需要逐层向上调整，直到被调整到堆顶位置为止。

2.当从一个小根堆（最小堆）中删除一个元素时，需要把堆尾元素填补到堆顶位置，然后再按条件把它逐层向下调整，直到调整到合适位置为止。

3.二叉树是一棵无序树。

4.在一棵二叉树中，假定每个结点只有左子女，没有右子女，对它分别进行前序遍历和后序遍历，则具有相同的遍历结果。

5.在一棵二叉树中，假定每个结点只有左子女，没有右子女，对它分别进行中序遍历和后序遍历，则具有相同的遍历结果。

6.在一棵二叉树中，假定每个结点只有左子女，没有右子女，对它分别进行前序遍历和中序遍历，则具有相同的遍历结果。

7.在一棵二叉树中，假定每个结点只有左子女，没有右子女，对它分别进行前序遍历和按层遍历，则具有相同的遍历结果。

8.在树的存储中，若使每个结点带有指向前驱结点的指针，将在算法中为寻找前驱结点带来方便。

9.对于一棵具有n个结点，其高度为h的二叉树，进行任一种次序遍历的时间复杂度为O(n)。

10.对于一棵具有n个结点，其高度为h的二叉树，进行任一种次序遍历的时间复杂度为O(h)。

11.对于一棵具有n个结点的任何二叉树，进行前序、中序或后序的任一种次序遍历的空间复杂度为O(log2n)。

12.在一棵具有n个结点的线索化二叉树中，每个结点的指针域可能指向子女结点，也可能作为线索，使之指向某一种遍历次序的前驱或后继结点，所有结点中作为线索使用的指针域共有n个。

13.线索化二叉树中的每个结点通常包含有5个数据成员。

14.线索化二叉树中的每个结点通常包含有3个数据成员。

15.对具有n个结点的堆进行插入一个元素运算的时间复杂度为O(n)。

16.从具有n个结点的堆中删除一个元素，其时间复杂度为O(log2n)。

17.二叉树是树的特殊情形。

18.若有一个结点是二叉树中某个子树的中序遍历结果序列的最后一个结点，则它一定是该子树的前序遍历结果序列的最后一个结点。

19.若有一个结点是二叉树中某个子树的前序遍历结果序列的最后一个结点，则它一定是该子树的中序遍历结果序列的最后一个结点。

20.若有一个叶子结点是二叉树中某个子树的中序遍历结果序列的最后一个结点，则它一定是该子树的前序遍历结果序列的最后一个结点。

21.若有一个叶子结点是二叉树中某个子树的前序遍历结果序列的最后一个结点，则它一定是该子树的中序遍历结果序列的最后一个结点。

22.若将一批杂乱无章的数据按堆结构组织起来, 则堆中各数据必然按自小到大的顺序排列起来。

参考答案： 1. 是 2. 是 3. 否 4. 否 5. 是6. 否7. 是8. 是9. 是10. 否11. 否12. 否13. 是14. 否15. 否16. 是17. 是18. 否19. 否20. 是21. 否22. 否四、运算题1.假定一棵二叉树的广义表表示为a (b (c), d (e, f) )，分别写出对它进行前序、中序、后序、按层遍历的结果。

前序：__________________中序：__________________后序：__________________按层：__________________2.假定一棵二叉树的广义表表示为A (B ( , D (G) ), C (E, F) )，分别写出对它进行前序、中序、后序、按层遍历的结果。

前序：__________________________中序：__________________________后序：__________________________按层：__________________________3.假定一棵普通树的广义表表示为a (b (e), c (f (h, i, j), g), d)，分别写出先根、后根、按层遍历的结果。