《《数据结构》习题汇编06-第六章-树和二叉树-试题Word版》由会员分享，可在线阅读，更多相关《《数据结构》习题汇编06-第六章-树和二叉树-试题Word版（18页珍藏版）》请在金锄头文库上搜索。
1、第六章 树和二叉树 试题一、单项选择题1. 树中所有结点的度等于所有结点数加（ ）。 A. 0 B. 1 C. -1 D. 22. 在一棵树中，（ ）没有前驱结点。 A. 分支结点 B. 叶结点 C. 根结点 D. 空结点3. 在一棵二叉树的二叉链表中，空指针域数等于非空指针域数加（ ）。 A. 2 B. 1 C. 0 D. -14. 在一棵具有n个结点的二叉树中，所有结点的空子树个数等于（ ）。 A. n B. n-1 C. n+1 D. 2*n5. 在一棵具有n个结点的二叉树的第i层上（假定根结点为第0层，i大于等于0而小于等于树的高度），最多具有（ ）个结点。 A. 2i B. 2i+1
2、 C. 2i-1 D. 2n6. 在一棵高度为h（假定根结点的层号为0）的完全二叉树中，所含结点个数不小于（ ）。 A. 2h-1 B. 2h+1 C. 2h-1 D. 2h7. 在一棵具有35个结点的完全二叉树中，该树的高度为（ ）。假定空树的高度为-1。 A. 5 B. 6 C. 7 D. 88. 在一棵具有n个结点的完全二叉树中，分支结点的最大编号为（ ）。假定树根结点的编号为0。 A. (n-1)/2 B. n/2 C. n/2 D. n/2 -19. 在一棵完全二叉树中，若编号为i的结点存在左孩子，则左子女结点的编号为（ ）。假定根结点的编号为0 A. 2i B. 2i-1 C. 2
3、i+1 D. 2i+210. 在一棵完全二叉树中，假定根结点的编号为0，则对于编号为i（i0）的结点，其双亲结点的编号为（ ）。 A. (i+1)/2 B. (i-1)/2 C. i/2 D. i/2 -111. 在一棵树的左子女-右兄弟表示法中，一个结点的右孩子是该结点的（ ）结点。 A. 兄弟 B. 子女 C. 祖先 D. 子孙12. 在一棵树的静态双亲表示中，每个存储结点包含（ ）个域。 A. 1 B. 2 C. 3 D. 413. 已知一棵二叉树的广义表表示为a (b (c), d (e ( , g (h) ), f ) )，则该二叉树的高度为（ 推荐精选）。假定根结点的高度为0。 A
4、. 3 B. 4 C. 5 D. 614. 已知一棵树的边集表示为 , , , , , , , ，则该树的高度为（ ）。假定根结点的高度为0。 A. 2 B. 3 C. 4 D. 515. 利用n个值作为叶结点上的权值生成的霍夫曼树中共包含有（ ）个结点。 A. n B. n+1 C. 2*n D. 2*n-116. 利用3, 6, 8, 12这四个值作为叶结点的权值生成一棵霍夫曼树，该树的带权路径长度为（ ）。 A. 55 B. 29 C. 58 D. 3817. 一棵树的广义表表示为a (b, c (e, f (g) ), d)，当用左子女-右兄弟链表表示时，右指针域非空的结点个数为（ ）
5、。 A. 1 B. 2 C. 3 D. 418. 向具有n个结点的堆中插入一个新元素的时间复杂度为（ ）。 A. O(1) B. O(n) C. O(log2n) D. O(nlog2n)参考答案：1. C 2. C 3. A4. C5. A6. D7. A8. D9. C10. B11. A12. B13. B14. B15. D16. A17. C18. C二、填空题1. 对于一棵具有n个结点的树，该树中所有结点的度数之和为_。2. 在一棵树中，_结点没有前驱结点。3. 在一棵树中，_结点没有后继结点。4. 一棵树的广义表表示为a (b (c, d (e, f), g (h) ), i (
6、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
7、 (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
8、), F (G (H), I) ) 按照左子女-右兄弟表示法转换为二叉树，该二叉树中度为2的结点个数为_个。16. 一棵树按照左子女-右兄弟表示法转换成对应的二叉树，则该二叉树中_结点肯定没有右子女。17. 在一个堆的顺序存储中，若一个元素的下标为i（0in-1），则它的左子女元素的下标为_。18. 在一个堆的顺序存储中，若一个元素的下标为i（0in-1），则它的右子女元素的下标为_。19. 在一个小根堆（即最小堆）中，堆顶结点的值是所有结点中的_。 20. 在一个大根堆（即最大堆）中，堆顶结点的值是所有结点中的_。21. 6个结点可构造出_种不同形态的二叉树。22. 设森林F中有4棵树，第1
9、、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-12. 树根3. 叶子4. 25. 36. 47. 858. 69. 6310. 311. 612. 413. 2h14. 2h+1-115. 216. 根17.
10、2i+118. 2i+219. 最小值20. 最大值推荐精选21. 13222. n2+n3+n423. n1-124. 19三、判断题1. 当向一个小根堆（最小堆）中插入一个具有最小值的元素时，该元素需要逐层向上调整，直到被调整到堆顶位置为止。2. 当从一个小根堆（最小堆）中删除一个元素时，需要把堆尾元素填补到堆顶位置，然后再按条件把它逐层向下调整，直到调整到合适位置为止。3. 二叉树是一棵无序树。4. 在一棵二叉树中，假定每个结点只有左子女，没有右子女，对它分别进行前序遍历和后序遍历，则具有相同的遍历结果。5. 在一棵二叉树中，假定每个结点只有左子女，没有右子女，对它分别进行中序遍历和后序
11、遍历，则具有相同的遍历结果。6. 在一棵二叉树中，假定每个结点只有左子女，没有右子女，对它分别进行前序遍历和中序遍历，则具有相同的遍历结果。7. 在一棵二叉树中，假定每个结点只有左子女，没有右子女，对它分别进行前序遍历和按层遍历，则具有相同的遍历结果。8. 在树的存储中，若使每个结点带有指向前驱结点的指针，将在算法中为寻找前驱结点带来方便。9. 对于一棵具有n个结点，其高度为h的二叉树，进行任一种次序遍历的时间复杂度为O(n)。10. 对于一棵具有n个结点，其高度为h的二叉树，进行任一种次序遍历的时间复杂度为O(h)。11. 对于一棵具有n个结点的任何二叉树，进行前序、中序或后序的任一种次序遍
12、历的空间复杂度为O(log2n)。12. 在一棵具有n个结点的线索化二叉树中，每个结点的指针域可能指向子女结点，也可能作为线索，使之指向某一种遍历次序的前驱或后继结点，所有结点中作为线索使用的指针域共有n个。13. 线索化二叉树中的每个结点通常包含有5个数据成员。14. 线索化二叉树中的每个结点通常包含有3个数据成员。15. 对具有n个结点的堆进行插入一个元素运算的时间复杂度为O(n)。16. 从具有n个结点的堆中删除一个元素，其时间复杂度为O(log2n)。17. 二叉树是树的特殊情形。推荐精选18. 若有一个结点是二叉树中某个子树的中序遍历结果序列的最后一个结点，则它一定是该子树的前序遍历结果序列的最后一个结点。19. 若有一个结点是二叉树中某个子树的前序遍历结果序列的最后一个结点，则它一定是该子树的中序遍历结果序列的最后一个结点。20. 若有一个叶子结点是二叉树中某个子树的中序遍历结果序列的最后一个结点，则它一定是该子树的前序遍历结果序列
