《数据结构》习题汇编06 第六章 树和二叉树 试题

第六章 树和二叉树 试题

一、单项选择题

1. 树中所有结点的度等于所有结点数加（ ）。

A. 0 B. 1 C. -1

D. 2

2. 在一棵树中，（ ）没有前驱结点。 A. 分支结点 B. 叶结点 C. 根结点 D. 空结点

3. 在一棵二叉树的二叉链表中，空指针域数等于非空指针域数加（ ）。

A. 2 B. 1 C. 0 D. -1

4. 在一棵具有n个结点的二叉树中，所有结点的空子树个数等于（ ）。

A. n B. n-1 C. n+1 D. 2*n

5. 在一棵具有n个结点的二叉树的第i层上（假定根结点为第0层，i大于等于0而小于等于树的高度），

最多具有（ ）个结点。

A. 2i B. 2i+1 C. 2i-1 D. 2n

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

7. 在一棵具有35个结点的完全二叉树中，该树的高度为（ ）。假定空树的高度为-1。 A. 5 B. 6 C. 7 D. 8

8. 在一棵具有n个结点的完全二叉树中，分支结点的最大编号为（ ）。假定树根结点的编号为0。 A. ?(n-1)/2? B. ?n/2? C. ?n/2? D. ?n/2? -1

9. 在一棵完全二叉树中，若编号为i的结点存在左孩子，则左子女结点的编号为（ ）。假定根结

点的编号为0

A. 2i B. 2i-1 C. 2i+1 D. 2i+2

10. 在一棵完全二叉树中，假定根结点的编号为0，则对于编号为i（i＞0）的结点，其双亲结点的编号

为（ ）。

A. ?(i+1)/2? B. ?(i-1)/2? C. ?i/2? D. ?i/2? -1

11. 在一棵树的左子女-右兄弟表示法中，一个结点的右孩子是该结点的（ ）结点。 A. 兄弟 B. 子女 C. 祖先 D. 子孙

12. 在一棵树的静态双亲表示中，每个存储结点包含（ ）个域。 A. 1 B. 2 C. 3

D. 4

13. 已知一棵二叉树的广义表表示为a (b (c), d (e ( , g (h) ), f ) )，则该二叉树的高度为

（ ）。假定根结点的高度为0。

1

A. 3

B. 4 C. 5 D. 6

14. 已知一棵树的边集表示为 {, , , , , , ,

}，则该树的高度为（ ）。假定根结点的高度为0。

A. 2 B. 3 C. 4 D. 5

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

16. 利用3, 6, 8, 12这四个值作为叶结点的权值生成一棵霍夫曼树，该树的带权路径长度为（ ）。 A. 55 B. 29 C. 58 D. 38

17. 一棵树的广义表表示为a (b, c (e, f (g) ), d)，当用左子女-右兄弟链表表示时，右指针域

非空的结点个数为（ ）。

A. 1 B. 2 C. 3 D. 4

18. 向具有n个结点的堆中插入一个新元素的时间复杂度为（ ）。

A. O(1) B. O(n) C. O(log2n) D. O(nlog2n)

参考答案：

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的结点数有______个。

2

1. C 6. D 11. A 16. A 2. C 7. A 12. B 17. C 3. A 8. D 13. B 18. C

4. C 9. C 14. B 5. A 10. B 15. D

二、填空题

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 6. 4 11. 6

2. 树根 7. 85 12. 4 3. 叶子 8. 6 13. 2h 4. 2 9. 63 14. 2h+1-1 19. 最小值 24. 19

5. 3 10. 3 15. 2 20. 最大值

16. 根 21. 132 17. 2i+1 18. 2i+2 22. n2+n3+n4 23. n1-1

3

三、判断题

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. 若有一个结点是二叉树中某个子树的中序遍历结果序列的最后一个结点，则它一定是该子树的前序遍

历结果序列的最后一个结点。

4

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

历结果序列的最后一个结点。

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

序遍历结果序列的最后一个结点。

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

序遍历结果序列的最后一个结点。

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

参考答案： 1. 是

6. 否 11. 否 16. 是 21. 否

2. 是 7. 是 12. 否 17. 是 22. 否

3. 否 8. 是 13. 是 18. 否

4. 否 9. 是 14. 否 19. 否

5. 是 10. 否 15. 否 20. 是

四、运算题

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)，分别写出先根、后根、

按层遍历的结果。

先根：__________________________ 后根：__________________________ 按层：__________________________

4. 已知一棵二叉树的前序和中序序列，求该二叉树的后序序列。

前序序列：A, B, C, D, E, F, G, H, I, J 中序序列：C, B, A, E, F, D, I, H, J, G 后序序列：______________________

5. 已知一棵二叉树的中序和后序序列如下，求该二叉树的前序序列。

5

中序序列：c, b, d, e, a, g, i, h, j, f 后序序列：c, e, d, b, i, j, h, g, f, a 前序序列：____________________

6. 已知一棵二叉树的中序和后序序列如下，求该二叉树的高度（假定空树的高度为-1）和度为2、度为

1的结点及叶结点个数。

中根序列：c, b, d, e, a, g, i, h, j, f 后根序列：c, e, d, b, i, j, h, g, f, a

高度：________ 度为2：________ 度为1：________ 叶子：_________

7. 已知一棵二叉树的静态数组表示（即顺序存储表示）如下，其中0表示空指针，请分别写出该二叉树

的前序、中序、后序遍历的序列。

0 1 2 3 4 5 6 7 8 9 10 11 12

20 8 46 5 15 30 0 0 0 10 18 0 35 前序序列：_________________________________ 中序序列：_________________________________

后序序列：_________________________________

8. 已知一棵树的静态双亲表示如下，其中用 -1表示空指针，树根结点存于0号单元，分别求出该树的

叶子结点数、单分支结点数、两分支结点数和三分支结点数。

序号： 0 1 2 3 4 5 6 7 8 9 10

data: a b c d e f g h i j k parent: -1 0 1 1 3 0 5 6 6 0 9

叶子结点数： ____________ 单分支结点数：____________ 两分支结点数：____________ 三分支结点数：____________

9. 假定一个最大堆（大根堆）为（56, 38, 42, 30, 25, 40, 35, 20），则依次向它插入45和

64两个元素后得到的最大堆为：_________________________________

10. 假定一个最小堆（小根堆）为（20, 35, 50, 57, 42, 70, 83, 65, 86），则依次从中删除三

个最小元素后得到的最小堆为：_________________________________

11. 已知一组数为（56, 48, 25, 16, 74, 52, 83, 45），请把该组数调整为最小堆（即小根堆）。

最小堆：_________________________________ 12. 有7个带权结点，其权值分别为3, 7, 8, 2, 6, 10, 14，试以它们为叶结点生成一棵霍夫曼树，

求出该树的带权路径长度、高度、度为2的结点个数。 带权路径长度：____________ 高度：___________

度为2的结点数：____________

6

13. 设二叉树根结点所在层次为0，树的高度h为距离根最远的叶结点所在层次，则： 高度为h的完全二叉树的不同二叉树棵数：_____________ 高度为h的满二叉树的不同二叉树棵数：_____________

14. 确定满足以下条件的二叉树的可能形态：

二叉树的前序序列与中序序列相同：__________________________ 二叉树的中序序列与后序序列相同：__________________________ 二叉树的前序序列与后序序列相同：__________________________

参考答案：

1. 前序：a, b, c, d, e, f

//2分 中序：c, b, a, e, d, f //2分 后序：c, b, e, f, d, a //1分 按层：a, b, d, c, e, f //1分

2. 前序：A, B, D, G, C, E, F

//2分 中序：B, G, D, A, E, C, F //2分 后序：G, D, B, E, F, C, A //1分 按层：A, B, C, D, E, F, G

//1分

3. 先根：a, b, e, c, f, h, i, j, g, d //2分

后根：e, b, h, i, j, f, g, c, d, a //2分 按层：a, b, c, d, e, f, g, h, i, j //2分

4. 后序序列：C, B, F, E, I, J, H, G, D, A //6分

5. 前序序列：a, b, c, d, e, f, g, h, i, j //6分

6. 高度：5

//2分 度为2：3 //2分 度为1：3 //1分 叶子：4 //1分

7. 前序序列：20, 8, 5, 15, 10, 18, 46, 30, 35

//2分 中序序列：5, 8, 10, 15, 18, 20, 30, 35, 46 //2分 后序序列：5, 10, 18, 15, 8, 35, 30, 46, 20 //2分

8. 叶子结点数： 5

//2分 单分支结点数：3 //2分 两分支结点数：2 //1分 三分支结点数：1 //1分

9. (64, 56, 42, 38, 45, 40, 35, 20, 30, 25) //6分

10. (50, 57, 70, 65, 86, 83)

//6分

7

11. (16, 45, 25, 48, 74, 52, 83, 56)

12. 带权路径长度：131 高度：4

度为2的结点数：6

//3分 //2分 //1分

//3分 //3分 //6分

13. 高度为h的完全二叉树的不同二叉树棵数：2h； 高度为h的满二叉树的不同二叉树棵数：1；

14. 二叉树的前序序列与中序序列相同：所有结点的左子树为空； //2分 二叉树的中序序列与后序序列相同：所有结点的右子树为空； //2分 二叉树的前序序列与后序序列相同：只有一个结点，左右子树为空；//2分

五、算法分析题

1. 已知二叉树中的结点类型用BinTreeNode表示，被定义为:

struct BinTreeNode { ElemType data; BinTreeNode *rightChild; };

*leftChild,

其中data为结点值域，leftChild和rightChild分别为指向左、右子女结点的指针域。下面函数的功能是返回二叉树BT中值为x的结点所在的层号，请在划有横线的地方填写合适的内容。

int NodeLevel ( BinTreeNode * BT, ElemType& x ) {

if ( BT == NULL ) return –1; else if ( BT->data == x ) return 0; else {

//空树的层号为-1

//根结点的层号为0

//向子树中查找x结点

int c1 = NodeLevel ( BT->leftChild, x ); if ( c1 >= 0 ) _________(1)_________; int c2 =_________(2)__________; ___________(3)____________;

else return -1; //在树中不存在x结点返回-1

} }

(1) _____________________________________________ (2) _____________________________________________ (3) _____________________________________________

2. 已知二叉树中的结点类型用BinTreeNode表示，被定义为: struct BinTreeNode {

ElemType data; BinTreeNode *leftChild, *rightChild; };

其中data为结点值域，leftChild和rightChild分别为指向左、右子女结点的指针域。下面函数的功能是从二叉树BT中查找值为x的结点，返回指向其父结点的指针。若该结点不存在或为树根结点则返回空。算法中参数PT的初值为NULL。请在划有横线的地方填写合适的内容。

BinTreeNode* ParentPtr ( BinTreeNode* BT, BinTreeNode* PT, ElemType& x ) {

8

if ( BT == NULL ) return NULL;

else if ( BT->data == x ) return PT; else {

if ( PT = ParentPtr ( BT->leftChild, BT, x ) ) _______(1)________; ________________________(2)________________________; else _______(3)________; }

}

(1) _____________________________________________ (2) _____________________________________________ (3) _____________________________________________

3. 已知二叉树中的结点类型用BinTreeNode表示，被定义为: struct BinTreeNode {

ElemType data; BinTreeNode *leftChild, *rightChild; };

其中data为结点值域，leftChild和rightChild分别为指向左、右子女结点的指针域。根据下面函数的定义指出函数的功能。算法中参数BT指向一棵二叉树的树根结点。

BinTreeNode* BinTreeSwopX ( BinTreeNode * BT ) { if ( BT == NULL ) return NULL; else {

BinTreeNode* pt = new BinTreeNode; pt->data = BT->data;

pt->rightChild = BinTreeSwopX ( BT->leftChild ); pt->lefthild = BinTreeSwopX ( BT->rightChild ); return pt; } }

算法功能：___________________________________________________

4. 已知二叉树中的结点类型用ThreeTreeNode表示，被定义为: struct ThreeTreeNode {

datatype data; ThreeTreeNode *leftChild, *rightChild, *parent; }; 其中data为结点值域，leftChild和rightChild分别为指向左、右子女结点的指针域，parent为指向父结点的指针域。根据下面函数的定义指出函数的功能。算法中参数T指向一棵二叉树的树根结点，x保存一个结点的值。

ThreeTreeNode* PN ( ThreeTreeNode * T, datatype& x ) { if ( T == NULL ) return NULL; else {

ThreeTreeNode* mt;

if ( T->data == x ) return T->parent;

else if ( mt = PN ( T->leftChild, x ) ) return mt; else if ( mt = PN ( T->rightChild, x ) ) return mt;

9

return NULL; } }

算法功能：__________________________________________________

5. 已知二叉树中的结点类型用BinTreeNode表示，被定义为: struct BinTreeNode {

ElemType data; BinTreeNode *leftChild, *rightChild; };

其中data为结点值域，leftChild和rightChild分别为指向左、右子女结点的指针域。根据下面函数的定义指出函数的功能。算法中参数BT指向一棵二叉树的根结点。

void BTC ( BinTreeNode* BT ) { if ( BT != NULL ) {

if ( BT->leftChild != NULL && BT->rightChild != NULL ) if ( BT->leftChild->data > BT->rightChild->data ) { BinTreeNode* t = BT->leftChild; BT->leftChild = BT->rightchild; BT->rightChild = t; }

BTC ( BT->leftChild ); BTC ( BT->rightChild ); }

}

算法功能：_________________________________________________

6. 已知二叉树中的结点类型用BinTreeNode表示，被定义为: struct BinTreeNode {

char data; BinTreeNode *leftChild, *rightChild;};

其中data为结点值域，leftChild和rightChild分别为指向左、右子女结点的指针域。假定指针bt指向一棵二叉树，该二叉树的广义表表示为a (b (a, d (f) ), c (e ( , a (k) ), b) )，整数变量C的值为0，若：

(1) 执行BTC1( bt, ’a’, C ) 调用后，C的值为________; (2) 执行BTC1( bt, ’b’, C ) 调用后，C的值为________; (3) 执行BTC1( bt, ’c’, C) 调用后，C的值为________; (4) 执行BTC1( bt, ’g’, C) 调用后，C的值为________;

void BTC1( BinTreeNode* BT, char x, int& k ) { if ( BT != NULL ) {

if ( BT->data == x ) k++; BTC1( BT->leftChild, x, k ); BTC1( BT->rightChild, x, k ); }

}

10

本文来源：https://www.bwwdw.com/article/dost.html