数据结构 树 考试习题

数据结构考试内容

第五章 树

11． 不含任何结点的空树( )

A）是一棵树 B）是一棵二叉树 Ｃ）既不是树也不是二叉树 D）是一棵树也是一棵二叉树 12．二叉树是非线性数据结构，所以( )

A）它不能用顺序存储结构存储; B）它不能用链式存储结构存储;

C）顺序存储结构和链式存储结构都能存储; D）顺序存储结构和链式存储结构都不能使用 13．把一棵树转换为二叉树后，这棵二叉树的形态是( ) A）唯一的 B）有多种

C）有多种，但根结点都没有左孩子 D）有多种，但根结点都没有右孩子

9. 11 ， 8 ， 6 ， 2 ， 5 的叶子结点生成一棵哈夫曼树，它的带权路径长度为（ ） A) 24 B) 72 C) 48 D) 53 10.一棵含18个结点的二叉树的高度至少为( )

A) 3 B) 4 C) 6 D) 5 11.下面的二叉树中，( C )不是完全二叉树。

10. 设结点x和结点y是二叉树T中的任意两个结点，若在前序序列中x在y之前，而在中序序列中x在y之后，则x和y的关系是（ ） A）x是y的左兄弟 B）x是y的右兄弟 C）y是x的祖先 D）y是x的孩子

11.设二叉树根结点的层次为1，所有含有15个结点的二叉树中，最小高度是（ ） A） 6 B） 5 C） 4 D） 3 7． 下列陈述中正确的是（ ）

A） 二叉树是度为2的有序树 B） 二叉树中结点只有一个孩子时无左右之分 C） 二叉树中必有度为2的结点 D） 二叉树中最多只有两棵子树，并且有左右之分 8. 树最适合用来表示（ ）

A） 有序数据元素 B） 无序数据元素 C） 元素之间具有分支层次关系的数据 D） 元素之间无联系的元素

数据结构考试内容

9. 3个结点有（ ）不同形态的二叉树

A） 2 B） 3 C） 4 D） 5 6．二叉树是非线性数据结构，( )

A）它不能用顺序存储结构存储; B）它不能用链式存储结构存储; C）顺序存储结构和链式存储结构都能存储; D）顺序存储结构和链式存储结构都不能使用 7．二叉树上叶结点数等于( )

A ) 分支结点数加1 B ) 单分支结点数加1 C ) 双分支结点数加1 D ) 双分支结点数减1

8．如将一棵有n个结点的完全二叉树按顺序存放方式，存放在下标编号为0, 1,…, n-1的一维数组中，设某结点下标为k(k>0)，则其双亲结点的下标是( ) A ) (k-1)/2 B ) (k+1)/2 C ) k/2 D ) k-1 8. 树最适合用来表示（ ）。

A．有序数据元素 B．无序数据元素 C. 元素之间具有分支层次关系的数据 D．元素之间无联系的元素 10.有64个结点的完全二叉树的深度为(

) (根的层次为第1层)。

A. 8 B. 7 C. 6 D. 5

11.在一棵度为3的树中，度为3的结点有2个，度为2的结点有1个，度为1的结点有２个，那么，该树有（ ）个叶子结点。

A. 4 B. 5 C. 6 D. 7 9.一个二叉树按顺序方式存储在一个维数组中，如图

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

A、2 长度为（ ）

A 24 B 71 C 48 D 53 8. 二叉树上叶结点数等于（

）。

B、3

C、4

D、5

10. 由权值分别为 11 ， 8 ， 6 ， 2 ， 5 的叶子结点生成一棵哈夫曼树，它的带权路径

A．分支结点数加1 B．单分支结点数加1 C．双分支结点数加1 D．双分支结点数减1

8. 某二叉树的先序序列和后序序列正好相同，则该二叉树一定是( )的二叉树。 A.空或只有一个结点 B.高度等于其结点数

数据结构考试内容

C.任一结点无左孩子 D.任一结点无右孩子

9. 在有n个结点的二叉链表中，值为空的链域的个数为( ) A. n-1 B. 2n-1 C. n+1 D. 2n+1 10. 一棵含18个结点的二叉树的高度至少为( )

A. 8 B. 7 C. 6 D. 5 11. 深度优先遍历类似于二叉树的( )

A.先序遍历 B. 中序遍历 C. 后序遍历 D. 层次遍历

9. 一棵124个叶结点的完全二叉树，最多应有(

A.245

B.246

C.247

D.248

)个结点。

10. 后缀表达式“ 5 6*3 2 + -”的值为（ ）。

A.15 B.25 C.30 D.35

11. 由权值分别为 11 ， 8 ， 6 ， 2 ， 5 的叶子结点生成一棵哈夫曼树，它的带权路径长度为（

）

A. 24 B. 71 C. 48 D. 53

7. 对一个满二叉树，m个树叶, n个结点, 深度为为h, 则（ ）。

A. n=2-1 B.h+m=2n C.m=h-1 D. n=h+m

8. 在一棵二叉树的二叉链表中，空指针域数等于非空指针域数加( )。

h

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

9. 若完全二叉树的结点总个数为100（结点编号从1开始编号，按层序编号），则第58个结点的度为（ ）

A.2 B.1 C.0 D.不确定

）

10. 已知完全二叉树的第9层有240个结点，则该完全二叉树的结点数是（

二、填空题

1. 一棵深度为5的二叉树，至多有_____________个结点。31

A.494 B.495 C.496 D.497

6.图的存储结构有__________________和__________________，遍历图有______________、_____________等方法。邻接矩阵 邻接表 深度优先 广度优先 7.深度为ｋ的完全二叉树最多有 个结点。2 1

8.若按层序对深度为ｋ的完全二叉树中全部结点从１开始编号，则叶子结点可能的最小编号

k

数据结构考试内容

为 。2

k 2

1

6.设有树如图所示，则结点ｃ的度为___________，层次为___________，树的度为

___________，树的高度为___________。为２， 树的度为３，高度为４

结点ｃ的度为２， 层次

7.深度为ｋ的完全二叉树至少有___________个结点，最多有___________个结点。2

k 1

，

2k 1

7.对于一棵具有n个结点的二叉树，当进行链接存储时，其二叉链表中的指针域的总数为

_______个，其中_______个用于链接孩子结点，_______个空闲着。2n，n-1，n+1 2. 后缀表达式“2 10 + 5 * 6 – 9 /”的值为 。6 3.由n个权值构成的哈夫曼树共有 个结点。2n-1 6.在一棵树中， ____ 结点没有后继结点。叶

4．后缀表达式“2 10 + 5 * 6 – 9 /”的计算结果为 。6

4.一棵深度为7的二叉树，最多有个结点。127

5.若一棵树的括号表示为A(B,C(E,F(G)),D),该树的叶子结点个数为________ ，该树的度为_____________ ，该树的深度为_____________。4、3、4 6.在有n个叶子结点的哈夫曼树中，总结点数是_______。2n-1

1. 深度为4的完全二叉树最少有______个结点，最多有_______个结点。8

15

6. 假定一棵树的广义表表示为A(B(C(D,E),F,G(H,I,J)),K)，则度为3、2、1、0的结点数分别为______、______、______和______个。2

2

7

6. 若结点A有其他三个兄弟,B是A的双亲结点,B的度是_______________。4

7. 一棵二叉树有67个结点，这些结点的度要么是0，要么是2。这棵二叉树中度为2的结点有_____________个。33

8. 一棵深度为7的二叉树，最多有 个结点。127

数据结构考试内容

三、应用题

1、名词解释：

树，子树，结点的度，叶子结点，孩子，双亲，兄弟，深度，有序树，森林，二叉树，遍历二叉树，树的带权路径长度，哈夫曼树。

2、描述二叉树的性质。

3、从概念上讲，树、森林和二叉树是三种不同的数据结构，将树、森林转换为二叉树的基本目的是什么？指出树和二叉树的主要区别。 4、已知一棵树边的结点为{<I,M>,<I,N>,<E,I>,<B,E>,<B,D>,<A,B>, <G,J>,<G,K>,<C,G>,<C,F>,<H,L>,<C,H.,,A,C>}，试画出这棵树,并回答下列问题：

（1）哪个是根结点？ （2）哪些是叶子结点？

（3）哪个是结点G的双亲？ （4）哪些是结点G的祖先？ （5）哪些是结点G的孩子？ （6）哪些是结点E的子孙？

（7）哪些是结点E的兄弟？哪些是结点F的兄弟？ （8）结点B和N的层次号分别是什么？ （9）树的深度是多少？

5、试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。

6、已知一棵度为k的树中有n1个度为1的结点，n2个度为2的结点， ，nk个度为k 的结点，问该树中有多少个叶子结点？

7、已知在一棵含有n 个结点的树中，只有度为k 的分支结点和度为0的叶子结点。试求该树含有的叶子结点的数目。

8、有n个结点的二叉树，已知叶子结点个数为n0，写出求度为1的结点的个数n1的计算公式；若此树是深度为k的完全二叉树，写出n为最小的公式；若二叉树中仅有度为0和度为2的结点，写出求该二叉树结点个数n的公式。

9、假设n 和m 为二叉树中两结点，用“1”，“0”或“”（分

数据结构考试内容

子树中，b在p的右子树中，则称a在b的左方（即b在a的右方）。 10、找出所有满足下列条件的二叉树：

（a）它们在先序遍历和中序遍历时，得到的结点访问序列相同； （b）它们在后序遍历和中序遍历时，得到的结点访问序列相同； （c）它们在先序遍历和后序遍历时，得到的结点访问序列相同； 11、分别画出和下列树对应的各个二叉树：

12、画出和下列二叉树相应的森林：

13、画出和下列已知序列对应的树T：

树的先根次序访问序列为GFKDAIEBCHJ； 树的后根次序访问序列为CBEFDGAJIKLH。

14、假设一棵二叉树的中序序列为DCBGEAHFIJK和后序序列为DCEGBFHKJIA。请画出该树。

数据结构考试内容

15、假设一棵二叉树的层序序列为ABCDEFGHIJ和中序序列为DBGEHJACIF。请画出该树。

16、编写递归算法，在二叉树中求位于先序序列中第k个位置的结点的值。

17、编写递归算法，计算二叉树中叶子结点的数目。

5. 用于通信的电文仅由a、b、c、d、e、f、g、h等8个字母组成，字母在电文中出现的频率分别为：007、0.19、0.02、0.06、0.32、0.03、0.21、0.10。试构造相应的哈夫曼树并为这些字母设计哈夫曼编码。（9分） 得到的编码如下 ：

a:0010 b:10 c:00000 d:0001 e:01 f:00001 g:11 h:0011 此题答案不唯一。

5. 设先序遍历某个树的结点次序为ABDEHCFGI，中序遍历该树的结点次序为DBEHAFCIG,要求画出这个二叉树，并写出此二叉树的后序遍历。（10分）

后序： DHFBFIGCA

6. 给定一组权值（5，9，11，2，7，16），试设计相应的哈夫曼树，并计算带权路径长度. （9分）

答案：

带权路径长度=（9+11+16）*2+7*3+（2+5）*4=121

1.已知一组关键字为{25,18,46,2,53,39,32,4,74,67,60,11}。按表中的元素顺序依次插入

数据结构考试内容

到一棵初始为空的二叉排序树中,画出该二叉排序树,并求在等概率的情况下查找成功的平均查找长度。（10分）

1 1 2 2 3 3 3 4 2 5 1 6 ASL 3.5

12

1．设先序遍历某个树的结点次序为ABDEHCFGI，中序遍历该树的结点次序为DBEHAFCIG,要求画出这个二叉树,并写出该树的后序遍历的结点次序。(6分)

1. .后序:DHEBFIGCA

1．已知一棵树二叉如下，请写出按前序、中序、后序和层次遍历时得到的结点序列。（8分）

A

B C

D E F

G H

前序：

数据结构考试内容

中序： 后序： 层次：

各遍历次序如下

前序：Ａ，Ｂ，Ｄ，Ｇ，Ｃ，Ｅ，Ｆ，Ｈ 中序：Ｄ，Ｇ，Ｂ，Ａ，Ｅ，Ｃ，Ｈ，Ｆ 后序：Ｇ，Ｄ，Ｂ，Ｅ，Ｈ，Ｆ，Ｃ，Ａ 层次：Ａ，Ｂ，Ｃ，Ｄ，Ｅ，Ｆ，Ｇ，Ｈ

4. 已知一棵完全二叉树共有999个结点，试求：(写出详细的分析过程) （9分） 1、树的高度（深度） 2、叶子结点的数目 3、度为1的结点数目

深度：10

叶子节点数目：500 度为1的节点数目：0

1.试写出如图所示的二叉树分别按先序、中序、后序遍历时得到的结点序列。

答：DLR：A B D F J G K C E H I L M LDR: B F J D G K A C H E L I M LRD：J F K G D B H L M I E C A

.请将下图所示的森林森林转换为所对应的二叉树。 B

图5-16

A

C E F

H

G

I J

K L

N

O

数据结构考试内容

4．将关键码53，78，65，17，87，09，81，45，23依次插入到一棵初始为空的二叉搜索树中，画出每插入一个关键码后的二叉搜索树。 答案

数据结构考试内容

1.已知一棵二叉树的中序遍历序列为： dfebagc，先序遍历序列为：abdefcg，请画出这棵二叉树

2.设用于通信的电文由７个字母组成，字母在电文中出现的频率分别为0.16、0.38、0.01、0.06、0.24、0.11、0.04，试为这７个字母设计赫夫曼编码。

赫夫曼树：

赫夫曼编码： ａ（0.15）： ｂ（0.39）：

数据结构考试内容

ｃ（0.01）： ｄ（0.06）： ｅ（0.24）： ｆ（0.11）： ｇ（0.04）：

1. 已知用一维数组存放的一棵完全二叉树：ABCDEFGHIJKL，写出该二叉树的先序、中序和后序遍历序列。先序序列：ABDHIEJKCFLG 中序序列：HDIBJEKALFCG 后序序列：HIDJKEBLFGCA

2. 给定一组权值（5，9，11，2，7，16），试设计相应的哈夫曼树，并计算WPL.

答案：

wpl=（9+11+16）*2+7*3+（2+5）*4=121

1.已知某二叉树的前序序列为EBADCFHGI，中序序列为ABCDEFGHI，请给出二叉树的后序列。 答案：

后序序列:ACDBGIHFE

2．在一份电文中共使用五种字符：A，G，F，U，Y，Z，它们的出现频率依次为12,9,18,7,14，11，求出每个字符的哈夫曼编码。

数据结构考试内容

71 0 1

30 41

0 1 0 1 16 Y(14) 23 F(18) 0 1 0 1

G(9) U(7) A(12) Z(11)

哈夫曼树

A：100 G：000 F：11 U：001 Y：01 Z：101 （或0、1 相反） （8分） 注意：答案不唯一。

3. 已知一棵完全二叉树共有1001个结点，试求：(写出详细的分析过程) （9分） 1、树的高度（深度） 2、叶子结点的数目 3、度为1的结点数目 深度：10

叶子节点数目：501 度为1的节点数目：0

4. 试给下图所示二叉树的前序、中序和后序遍历序列。若一棵二叉树的前序遍历序列为：A B D E G C F，中序遍历序列为：D B E G A C F，试画出此二叉树。（10分）

数据结构考试内容

前序：ABDEGHCF 中序：DBGEHAFC 后序：DGHEBFCA

5. 一组密文原码由字符{A, B, C, D, E, F, G}组成，其出现的频率分别是{9, 11, 5, 7, 8, 2, 3}，设计相应的哈夫曼树并对7个字符编码。（8分） 哈夫曼树略。

编码方案：A：00 B：10 C：010 D：110 E：111 F：0110 G：0111（此题答案不唯一）

四、综合题

2. 在二叉树的链式存储结构中，结点类型定义如下： typedef struct node { ElemType data;

struct node *lchild,*rchild; } BTNode;

以下算法是计算二叉数深度的递归算法，试补充完整。 int BtreeDepth (BTreeNode *BT) //BT是根结点 { if (BT==NULL) return 0； else {

int dep1,dep2； //dep1、dep2分别为根结点左子树、右子树高度 dep1= ； dep2= ； if (dep1>dep2)

return ； else

return ；

}

数据结构考试内容

}

2. BtreeDepth（BT->lchild）

BtreeDepth（BT->rchild） dep1+1 dep2+1 2.编写算法求二叉树的深度（高度）。

2. int BTNodeDepth(BTNode *b) //求二叉树b的深度 {

int lchilddep,rchilddep; if (b==NULL)

return(0); //空树的高度为0 else {

lchilddep=BTNodeDepth(b->lchild); //求左子树的高度为lchilddep rchilddep=BTNodeDepth(b->rchild); //求右子树的高度为rchilddep return (lchilddep>rchilddep)? (lchilddep+1):(rchilddep+1); } }

1.二叉树中结点定义如下，试编写算法，求二叉树中结点的个数。

typedef struct node {

ElemType data; struct node *lchild; struct node *rchild;

//数据元素 //指向左孩子 //指向右孩子

} BTNode;

int Nodes(BTNode *b) //求二叉树b的结点个数

{

int num1,num2;

if (b==NULL)

return 0;

else if (b->lchild==NULL && b->rchild==NULL) return 1; else {

num1=Nodes(b->lchild); num2=Nodes(b->rchild); return (num1+num2+1); }

数据结构考试内容

}

2.下列递归算法实现了交换二叉树中每个结点的左孩子和右孩子，试补充完整。

void exchange(BTNode *b) //初始化时b为根结点 { BTNode *temp; //临时结点变量temp

if(b!=NULL) //if语句实现b的左右孩子交换 { temp=b->lchild;

b->lchild=_________________________; b->rchild=_________________________;

exchange(________________); //递归实现左子树中结点的左右孩子交换 exchange(________________); //递归实现右子树中结点的左右孩子交换 } }

2. b->rchild temp b->lchild b->rchild

1. 二叉树中结点定义如下，编写递归算法实现二叉树的先序、中序、后序遍历。

typedef struct node {

ElemType data; struct node *lchild; struct node *rchild;

//数据元素 //指向左孩子 //指向右孩子

} BTNode;

void PreOrder(BTNode *b) { }

void InOrder(BTNode *b)

//中序遍历的递归算法

if (b!=NULL) { }

printf("%c ",b->data); //访问根结点 PreOrder(b->lchild); PreOrder(b->rchild);

//递归访问左子树 //递归访问右子树 //先序遍历的递归算法