数据结构 树 考试习题
第五章树
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
B、3
C、4
D、5
10. 由权值分别为 11 ， 8 ， 6 ， 2 ， 5 的叶子结点生成一棵哈夫曼树，它的带权路径长度为（）
A 24
B 71
C 48
D 53
8. 二叉树上叶结点数等于（）。
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=2h
-1 B.h+m=2n C.m=h-1 D. n=h+m
8. 在一棵二叉树的二叉链表中，空指针域数等于非空指针域数加( )。
A.2
B.1
C.0
D.-1
9. 若完全二叉树的结点总个数为100（结点编号从1开始编号，按层序编号），则第58个结点的度为（ ）
A.2
B.1
C.0
D.不确定
10. 已知完全二叉树的第9层有240个结点，则该完全二叉树的结点数是（
）
A.494
B.495
C.496
D.497
二、填空题
1. 一棵深度为5的二叉树，至多有_____________个结点。31
6.图的存储结构有__________________和__________________，遍历图有______________、_____________等方法。邻接矩阵 邻接表 深度优先 广度优先
7.深度为ｋ的完全二叉树最多有 个结点。12 k
8.若按层序对深度为ｋ的完全二叉树中全部结点从１开始编号，则叶子结点可能的最小编号
为 。12
2
+-k
6.设有树如图所示，则结点ｃ的度为___________，层次为___________，树的度为
___________，树的高度为___________。结点ｃ的度为２， 层次
为２， 树的度为３，高度为４
7.深度为ｋ的完全二叉树至少有___________个结点，最多有___________个结点。1
2
-k ，
12-k
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、已知一棵树边的结点为{
（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的结点，……，n k个度为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}。按表中的元素顺序依次插入
50 9 20 30 11 16 14 7 7 2 5
到一棵初始为空的二叉排序树中,画出该二叉排序树,并求在等概率的情况下查找成功的平均查找长度。（10分）
1．设先序遍历某个树的结点次序为ABDEHCFGI ，中序遍历该树的结点次序为DBEHAFCIG,要求画出这个二叉树,并写出该树的后序遍历的结点次序。(6分)
1. .后序:DHEBFIGCA
1．已知一棵树二叉如下，请写出按前序、中序、后序和层次遍历时得到的结点序列。（8分）
A
B C
D E F
G H
前序：
5
.312615243332211ASL =?+?+?+?+?+?=
中序： 后序： 层次：
各遍历次序如下
前序：Ａ，Ｂ，Ｄ，Ｇ，Ｃ，Ｅ，Ｆ，Ｈ 中序：Ｄ，Ｇ，Ｂ，Ａ，Ｅ，Ｃ，Ｈ，Ｆ 后序：Ｇ，Ｄ，Ｂ，Ｅ，Ｈ，Ｆ，Ｃ，Ａ 层次：Ａ，Ｂ，Ｃ，Ｄ，Ｅ，Ｆ，Ｇ，Ｈ
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
.请将下图所示的森林森林转换为所对应的二叉树。
A
B D
E F
C G
H
J
I K N
O
M L
图5-16
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，求出每个字符的哈夫曼编码。
50
9 20
30
11 16 14 7 7 2 5
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) //先序遍历的递归算法
{
if (b!=NULL)
{
printf("%c ",b->data); //访问根结点
PreOrder(b->lchild); //递归访问左子树
PreOrder(b->rchild); //递归访问右子树
}
}
void InOrder(BTNode *b) //中序遍历的递归算法
{
if (b!=NULL)
{
InOrder(b->lchild); //递归访问左子树
printf("%c ",b->data); //访问根结点
InOrder(b->rchild); //递归访问右子树}
}
void PostOrder(BTNode *b) //后序遍历的递归算法{
if (b!=NULL)
{
PostOrder(b->lchild); //递归访问左子树
PostOrder(b->rchild); //递归访问右子树
printf("%c ",b->data); //访问根结点}
}
数据结构复习题
一．判断题（下列各题，正确的请在前面的括号内打√；错误的打×） 第1章 （√）（1）数据的逻辑结构与数据元素本身的内容和形式无关。 （√）（2）一个数据结构是由一个逻辑结构和这个逻辑结构上的一个基本运算集构成的整体。（×）（3）数据元素是数据的最小单位。 （×）（4）数据项是数据的基本单位。 （×）（5）数据的逻辑结构和数据的存储结构是相同的。 （√）（6）数据的逻辑结构是各数据元素之间的逻辑关系，是用户按使用需要而建立的。（√）（7）数据的物理结构是指数据在计算机内实际的存储形式。 （√）（8）从逻辑关系上讲，数据结构主要分为线性结构和非线性结构两类。 （√）（9）数据的存储结构是数据的逻辑结构的存储映像。 （√）（10）算法是对解题方法和步骤的描述。 第2章 （×）（1）链表的物理存储结构具有同链表一样的顺序。 （×）（2）链表的每个结点都恰好包含一个指针域。 （√）（3）线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此属于同一数据对象。 （×）（4）链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。 （×）（5）顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。 （√）（6）数组元素的存储位置是下标的线性函数。 （√）（7）在单链表中，元素的存储位置用指针联系，所以可以从头结点开始查找任何一个元素。 （×）（8）顺序存储线性表的插入和删除操作不需要付出很大的代价，因为平均每次移动仅一半的元素。 （×）（9）顺序存储方式的优点是存储密度大，插入、删除效率高。 （×）（10）在单链表中，要取得某个元素，只要知道该元素的指针即可，因此单链表是随机存取的存储结构。 第3章 （√）（1）大多数排序算法都有比较关键字大小和改变指向记录的指针或移动记录本身两种基本操作。 （×）（2）快速排序在任何情况下都比其它排序方法速度快。 （√）（3）快速排序算法在每一趟排序中都能找到一个元素放在其最终位置上。
数据结构树和二叉树实验报告
《数据结构》课程实验报告 实验名称树和二叉树实验序号 5 实验日期 姓名院系班级学号 专业指导教师成绩 教师评语 一、实验目的和要求 (1)掌握树的相关概念，包括树、结点的度、树的度、分支结点、叶子结点、儿子结点、双亲结点、树 的深度、森林等定义。 (2)掌握树的表示，包括树形表示法、文氏图表示法、凹入表示法和括号表示法等。 (3)掌握二叉树的概念，包括二叉树、满二叉树和完全二叉树的定义。 (4)掌握二叉树的性质。 (5)重点掌握二叉树的存储结构，包括二叉树顺序存储结构和链式存储结构。 (6)重点掌握二叉树的基本运算和各种遍历算法的实现。 (7)掌握线索二叉树的概念和相关算法的实现。 (8)掌握哈夫曼树的定义、哈夫曼树的构造过程和哈夫曼编码产生方法。 (9)掌握并查集的相关概念和算法。 (10)灵活掌握运用二叉树这种数据结构解决一些综合应用问题。 二、实验项目摘要 1．编写一程序，实现二叉树的各种基本运算，并在此基础上设计一个主程序完成如下功能： （1）输出二叉树b; （2）输出H结点的左、右孩子结点值； （3）输出二叉树b的深度； （4）输出二叉树b的宽度； （5）输出二叉树b的结点个数； （6）输出二叉树b的叶子结点个数。 2．编写一程序，实现二叉树的先序遍历、中序遍历和后序遍历的各种递归和非递归算法，以及层次遍历的算法。 三、实验预习内容 二叉树存储结构，二叉树基本运算（创建二叉树、寻找结点、找孩子结点、求高度、输出二叉树）
三、实验结果与分析 7-1 #include
《数据结构》习题集：_树和叉树
第6章树和二叉树 一、选择题 1.有一“遗传”关系，设x是y的父亲，则x可以把它的属性遗传给y，表示该遗传关系最适合的数据结构是（ B ） A、向量 B、树 C、图 D、二叉树 2.树最适合用来表示（ B ） A、有序数据元素 B、元素之间具有分支层次关系的数据 C、无序数据元素 D、元素之间无联系的数据 3.树B 的层号表示为1a,2b,3d,3e,2c，对应于下面选择的（ C ） A、1a(2b(3d,3e),2c) B、a(b(D,e),c) C、a(b(d,e),c) D、a(b,d(e),c) 4.对二叉树的结点从1 开始连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中， 其左孩子的编号小于其右孩子的编号，则可采用（ C ）次序的遍历实现二叉树的结点编号。 A、先序 B、中序 C、后序 D、从根开始按层次遍历 5.按照二叉树的定义，具有3 个结点的二叉树有（C ）种。 A、3 B、4 C、5 D、6 6.在一棵有n个结点的二叉树中，若度为2的结点数为n2，度为1的结点数为n1，度为0的结点数为n0，则树的最大高 度为（ E ），其叶结点数为（ H ）；树的最小高度为（ B ），其叶结点数为（ G ）；若采用链表存储结构，则有（ I ）个空链域。 log+1 C、log2n D、n A、n/2 B、??n2 E、n0+n1+n2 F、n1+n2 G、n2+1 H、1 I、n+1 J、n1K、n2L、n1+1 7.对一棵满二叉树，m 个树叶，n 个结点，深度为h，则（ D ） A、n=m+h B、h+m=2n C、m=h-1 D、n=2h-1 8.设高度为h 的二叉树中只有度为0 和度为2 的结点，则此类二叉树中所包含的结点数至少为（ B ），至多 为（D ）。 A、2h B、2h-1 C、2h-1 D、2h-1 9.在一棵二叉树上第5 层的结点数最多为（B）（假设根结点的层数为1） A、8 B、16 C、15 D、32 10.深度为5 的二叉树至多有（ C ）个结点。 A、16 B、32 C、31 D、10 11.一棵有124 个叶结点的完全二叉树，最多有（B ）个结点 A、247 B、248 C、249 D、250 12.含有129 个叶子结点的完全二叉树，最少有（ D ）个结点 A、254 B、255 C、256 D、257 13.假定有一棵二叉树，双分支结点数为15，单分支结点数为30，则叶子结点数为（ B ）个。 A、15 B、16 C、17 D、47 14.用顺序存储的方法将完全二叉树中所有结点逐层存放在数组R[1…n]中，结点R[i]若有左子树，则左子树是结 点（ B ）。 A、R[2i+1] B、R[2i] C、R[i/2] D、R[2i-1]
数据结构 二叉树练习题答案
数据结构第6章树和二叉树 一、下面是有关二叉树的叙述，请判断正误 （√）1.若二叉树用二叉链表作存贮结构，则在n个结点的二叉树链表中只有n-1个非空指针域。 n个结点的二叉树有n-1条分支 （×）2.二叉树中每个结点的两棵子树的高度差等于1。 （√）3.二叉树中每个结点的两棵子树是有序的。 （×）4.二叉树中每个结点有两棵非空子树或有两棵空子树。 （×）5.二叉树中每个结点的关键字值大于其左非空子树（若存在的话）所有结点的关键字值，且小于其右非空子树 （若存在的话）所有结点的关键字值。 （应当是二叉排序树的特点） （×）6.二叉树中所有结点个数是2k-1-1，其中k是树的深度。（应2k-1） （×）7.二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。 （×）8.对于一棵非空二叉树，它的根结点作为第一层，则它的第i层上最多能有2i -1个结点。
（应2i-1） （√）9.用二叉链表法（link-rlink）存储包含n个结点的二叉树，结点的2n个指针区域中有n+1个为空指针。（用二叉链表存储包含n个结点的二叉树，结点共有2n个链域。由于二叉树中，除根结点外，每一个结点有且仅有一个双亲，所以只有n-1个结点的链域存放指向非空子女结点的指针，即有后继链接的指针仅n-1个，还有n+1个空指针。）采用二叉链表存储有2n个链域，空链域为：2n-（n-1）=n+1 （√）10.具有12个结点的完全二叉树有5个度为2的结点。 最快方法：用叶子数＝[ n/2] ＝6，再求n2=n0-1=5 [n/2] 除的结果四舍五入 二、填空 1．由３个结点所构成的二叉树有5种形态。 2. 一棵深度为6的满二叉树有n1+n2=0+ n2= n0-1=31 个分支结点和26-1 =32个叶子。 注：满二叉树没有度为1的结点，所以分支结点数就是二度结点数。 (或：总结点数为n=2k-1=26-1=63，叶子数为n0= [ n/2] =32，满二叉数没有度为1的结点，由n0=n2+1得n2=n0-1=32-1=31)
数据结构叉树习题含答案
第6章树和二叉树 1．选择题 （1）把一棵树转换为二叉树后，这棵二叉树的形态是（）。 A．唯一的Ｂ．有多种 C．有多种，但根结点都没有左孩子Ｄ．有多种，但根结点都没有右孩子 （2）由3 个结点可以构造出多少种不同的二叉树？（） A．2 B．3 C．4 D．5 （3）一棵完全二叉树上有1001个结点，其中叶子结点的个数是（）。 A．250 B． 500 C．254 D．501 （4）一个具有1025个结点的二叉树的高h为（）。 A．11 B．10 C．11至1025之间 D．10至1024之间（5）深度为h的满m叉树的第k层有（）个结点。(1= 习题六树和二叉树 一、单项选择题 1．以下说法错误的是 ( ) A．树形结构的特点是一个结点可以有多个直接前趋 B．线性结构中的一个结点至多只有一个直接后继 C．树形结构可以表达(组织)更复杂的数据 D．树(及一切树形结构)是一种"分支层次"结构 E．任何只含一个结点的集合是一棵树 2．下列说法中正确的是 ( ) A．任何一棵二叉树中至少有一个结点的度为2 B．任何一棵二叉树中每个结点的度都为2 C．任何一棵二叉树中的度肯定等于2 D．任何一棵二叉树中的度可以小于2 3．讨论树、森林和二叉树的关系，目的是为了（） A．借助二叉树上的运算方法去实现对树的一些运算 B．将树、森林按二叉树的存储方式进行存储 C．将树、森林转换成二叉树 D．体现一种技巧，没有什么实际意义 4．树最适合用来表示 ( ) A．有序数据元素 B．无序数据元素 C．元素之间具有分支层次关系的数据 D．元素之间无联系的数据 5．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（）A．9 B．11 C．15 D．不确定 6．设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是（）。 A．M1 B．M1+M2 C．M3 D．M2+M3 7．一棵完全二叉树上有1001个结点，其中叶子结点的个数是（） A． 250 B． 500 C．254 D．505 E．以上答案都不对 8. 设给定权值总数有n 个，其哈夫曼树的结点总数为( ) A．不确定 B．2n C．2n+1 D．2n-1 9．二叉树的第I层上最多含有结点数为（） A．2I B． 2I-1-1 C． 2I-1 D．2I -1 10．一棵二叉树高度为h,所有结点的度或为0，或为2，则这棵二叉树最少有( )结点A．2h B．2h-1 C．2h+1 D．h+1 11. 利用二叉链表存储树，则根结点的右指针是（）。 A．指向最左孩子 B．指向最右孩子 C．空 D．非空 14．在二叉树结点的先序序列，中序序列和后序序列中，所有叶子结点的先后顺序（）A．都不相同 B．完全相同 C．先序和中序相同，而与后序不同 D．中序和后序相同，而与先序不同 15．在完全二叉树中，若一个结点是叶结点，则它没（）。 A．左子结点 B．右子结点 C．左子结点和右子结点 D．左子结点，右子结点和兄弟结点 16．在下列情况中，可称为二叉树的是（） 第6章树和二叉树 部分答案解释如下。 12. 由二叉树结点的公式：n=n0+n1+n2=n0+n1+(n0-1)=2n0+n1-1，因为n=1001,所以1002=2n0+n1,在完全二叉树树中，n1只能取0或1,在本题中只能取0，故n=501，因此选E。 42.前序序列是“根左右”，后序序列是“左右根”，若要这两个序列相反，只有单支树，所以本题的A和B均对，单支树的特点是只有一个叶子结点，故C是最合适的，选C。A或B 都不全。由本题可解答44题。 47. 左子树为空的二叉树的根结点的左线索为空（无前驱），先序序列的最后结点的右线索为空（无后继），共2个空链域。 52．线索二叉树是利用二叉树的空链域加上线索，n个结点的二叉树有n+1个空链域。 部分答案解释如下。 6．只有在确定何序（前序、中序、后序或层次）遍历后，遍历结果才唯一。 19．任何结点至多只有左子树的二叉树的遍历就不需要栈。 24. 只对完全二叉树适用，编号为i的结点的左儿子的编号为2i(2i<=n)，右儿子是2i+1（2i+1<=n） 37. 其中序前驱是其左子树上按中序遍历的最右边的结点（叶子或无右子女），该结点无右孩子。 38 . 新插入的结点都是叶子结点。 42. 在二叉树上，对有左右子女的结点，其中序前驱是其左子树上按中序遍历的最右边的结点（该结点的后继指针指向祖先），中序后继是其右子树上按中序遍历的最左边的结点（该结点的前驱指针指向祖先）。 44．非空二叉树中序遍历第一个结点无前驱，最后一个结点无后继，这两个结点的前驱线索和后继线索为空指针。 三.填空题 1.(1)根结点(2)左子树(3)右子树 2.(1)双亲链表表示法(2)孩子链表表示法(3)孩 子兄弟表示法 3．p->lchild==null && p->rchlid==null 4.(1) ++a*b3*4-cd (2)18 5.平衡 因子 6. 9 7. 12 8.(1)2k-1 (2)2k-1 9.(1)2H-1 (2)2H-1 (3)H=?log2N?+1 10. 用顺序存储二叉树时，要按完全二叉树的形式存储，非完全二叉树存储时，要加“虚结 点”。设编号为i和j的结点在顺序存储中的下标为s 和t ,则结点i和j在同一层上的条 件是?log2s?=?log2t?。 11. ?log2i?=?log2j?12.(1)0 (2)(n-1)/2 (3)(n+1)/2 (4) ?log2n?+1 13.n 14. N2+1 15.(1) 2K+1-1 (2) k+1 16. ?N/2? 17. 2k-2 18. 64 19. 99 20. 11 21.(1) n1-1 (2)n2+n3 22.(1)2k-2+1（第k层1个结点，总结点个数是2H-1，其双亲是2H-1/2=2k-2）(2) ?log2i?+1 23.69 24. 4 25.3h-1 26. ?n/2? 27. ?log2k?+1 28.(1)完全二叉树 (2)单枝树，树中任一结点（除最后一个结点是叶子外）,只有左子女或 只有右子女。 29.N+1 30.(1) 128(第七层满，加第八层１个) (2) 7 31. 0至多个。任意二叉树，度为１的结点个数没限制。只有完全二叉树，度为１的结点个 数才至多为1。 32．21 33.(1)2 (2) n-1 (3) 1 (4) n (5) 1 (6) n-1 34.(1) FEGHDCB (2)BEF（该二叉树转换成森林，含三棵树，其第一棵树的先根次序是 BEF） 35.(1)先序（2）中序 36. (1)EACBDGF （2）2 37.任何结点至多只有右子女 的二叉树。 38.(1)a (2) dbe (3) hfcg 39.(1) . (2) ...GD.B...HE..FCA 40.DGEBFCA 41．(1)5 （2）略 42.二叉排序树 43.二叉树 44. 前序 45.(1)先根次序（2）中根次序46.双亲的右子树中最左下的叶子结点47.2 48.(n+1)/2 49.31（x的后继是经x的双亲y的右子树中最左下的叶结点） 50.(1)前驱 (2)后 继 51.(1)1 (2)y^.lchild (3)0 (4)x (5)1 (6) y (7)x(编者注：本题按 中序线索化) 52.带权路径长度最小的二叉树，又称最优二叉树 53.69 54.(1)6 (2)261 55.(1)80 (2)001（不唯一）56.2n0-1 57.本题①是表达式求值，②是在二叉排序树中删除值为x的结点。首先查找x，若没有x， 则结束。否则分成四种情况讨论：x结点有左右子树；只有左子树；只有右子树和本身是叶 子。 (1)Postoder_eval(t^.Lchild) (2) Postorder_eval(t^.Rchild) (3)ERROR(无此运 算符)(4)A (5)tempA^.Lchild (6)tempA=NULL(7)q^.Rchild (8)q (9)tempA^.Rchild (10)tempA^.Item 树与二叉树 一.选择题 1.假定在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结 点数为（）个。 A．15B．16C．17D．47 2.按照二叉树的定义，具有3个结点的不同形状的二叉树有（）种。 A. 3 B. 4 C. 5 D. 6 3.按照二叉树的定义，具有3个不同数据结点的不同的二叉树有（）种。 A. 5 B. 6 C. 30 D. 32 4.深度为5的二叉树至多有（）个结点。1 A. 16 B. 32 C. 31 D. 10 5.设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的 结点数至少为（）。 A. 2h B. 2h-1 C. 2h+1 D. h+1 6.对一个满二叉树2，m个树叶，n个结点，深度为h，则（）。 A. n=h+m3 B. h+m=2n C. m=h-1 D. n=2 h-1 1深度为n的二叉树结点至多有2n-1 2满二叉树是除最后一层无任何子节点外，每一层上的所有结点都有两个子结点的二叉树7.任何一棵二叉树的叶结点在先序.中序和后序遍历序列中的相对次序（）。 A.不发生改变 B.发生改变 C.不能确定 D.以上都不对 8.如果某二叉树的前根次序遍历结果为stuwv，中序遍历为uwtvs，那么该二叉 树的后序为（）。 A. uwvts B. vwuts C. wuvts D. wutsv 9.某二叉树的前序遍历结点访问顺序是abdgcefh，中序遍历的结点访问顺序是 dgbaechf，则其后序遍历的结点访问顺序是（）。 A. bdgcefha B. gdbecfha C. bdgaechf D. gdbehfca 10.在一非空二叉树的中序遍历序列中，根结点的右边（）。 A. 只有右子树上的所有结点 B. 只有右子树上的部分结点 C. 只有左子树上的部分结点 D. 只有左子树上的所有结点 11.树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为 先序遍历.中序遍历和后序遍历。这里，我们把由树转化得到的二叉树4叫做这棵数对应的二叉树。结论（）是正确的。 A.树的先根遍历序列与其对应的二叉树的先序遍历序列相同 B.树的后根遍历序列与其对应的二叉树的后序遍历序列相同 3对于深度为h的满二叉树，n=20+21+…+2h-1=2h-1，m=2h-1。故而n=h+m。 4树转化为二叉树的基本方法是把所有兄弟结点都用线连起来，然后去掉双亲到子女的连线，只留下双亲到第一个子女的连线。因此原来的兄弟关系就变为双亲与右孩子的关系。 1/ 9 树和二叉树习题数据结 构 标准化管理处编码[BBX968T-XBB8968-NNJ668-MM9N] 习题六树和二叉树一、单项选择题 1．以下说法错误的是 ( ) A．树形结构的特点是一个结点可以有多个直接前趋B．线性结构中的一个结点至多只有一个直接后继 C．树形结构可以表达(组织)更复杂的数据 D．树(及一切树形结构)是一种"分支层次"结构 E．任何只含一个结点的集合是一棵树 2．下列说法中正确的是 ( ) A．任何一棵二叉树中至少有一个结点的度为2 B．任何一棵二叉树中每个结点的度都为2 C．任何一棵二叉树中的度肯定等于2 D．任何一棵二叉树中的度可以小于2 3．讨论树、森林和二叉树的关系，目的是为了（）A．借助二叉树上的运算方法去实现对树的一些运算B．将树、森林按二叉树的存储方式进行存储 C．将树、森林转换成二叉树 D．体现一种技巧，没有什么实际意义 4．树最适合用来表示 ( ) A．有序数据元素 B．无序数据元素 C．元素之间具有分支层次关系的数据 D．元素之间无联系的数据5．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（） A．9 B．11 C．15 D．不确定 6．设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是（）。 A．M1 B．M1+M2 C．M3 D．M2+M3 7．一棵完全二叉树上有1001个结点，其中叶子结点的个数是（）A． 250 B． 500 C．254 D．505 E．以上答案都不对 8. 设给定权值总数有n 个，其哈夫曼树的结点总数为( ) A．不确定 B．2n C．2n+1 D．2n-1 9．二叉树的第I层上最多含有结点数为（） A．2I B． 2I-1-1 C． 2I-1 D．2I -1 10．一棵二叉树高度为h,所有结点的度或为0，或为2，则这棵二叉树最少有( )结点 第6章树和二叉树自测卷解答 一、下面是有关二叉树的叙述，请判断正误 （√）1. 若二叉树用二叉链表作存贮结构，则在n个结点的二叉树链表中只有n—1个非空指针域。（×）2.二叉树中每个结点的两棵子树的高度差等于1。 （√）3.二叉树中每个结点的两棵子树是有序的。 （×）4.二叉树中每个结点有两棵非空子树或有两棵空子树。 （×）5.二叉树中每个结点的关键字值大于其左非空子树（若存在的话）所有结点的关键字值，且小于其右非空子树（若存在的话）所有结点的关键字值。（应当是二叉排序树的特点） （×）6.二叉树中所有结点个数是2k-1-1，其中k是树的深度。（应2i-1） （×）7.二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。 （×）8.对于一棵非空二叉树，它的根结点作为第一层，则它的第i层上最多能有2i—1个结点。（应2i-1）（√）9.用二叉链表法（link-rlink）存储包含n个结点的二叉树，结点的2n个指针区域中有n+1个为空指针。 （正确。用二叉链表存储包含n个结点的二叉树，结点共有2n个链域。由于二叉树中，除根结点外，每一个结点有且仅有一个双亲，所以只有n-1个结点的链域存放指向非空子女结点的指针，还有n+1个空指针。）即有后继链接的指针仅n-1个。 （√）10. 具有12个结点的完全二叉树有5个度为2的结点。 最快方法：用叶子数＝[n/2]＝6，再求n2=n0-1=5 二、填空（每空1分，共15分） 1．由３个结点所构成的二叉树有5种形态。 2. 一棵深度为6的满二叉树有n1+n2=0+ n2= n0-1=31 个分支结点和26-1 =32个叶子。 注：满二叉树没有度为1的结点，所以分支结点数就是二度结点数。 3．一棵具有２５７个结点的完全二叉树，它的深度为9。 （注：用? log2(n) ?+1= ? 8.xx ?+1=9 4.设一棵完全二叉树有700个结点，则共有350个叶子结点。 答：最快方法：用叶子数＝[n/2]＝350 5. 设一棵完全二叉树具有1000个结点，则此完全二叉树有500个叶子结点，有499个度为2的结点，有1个结点只有非空左子树，有0个结点只有非空右子树。 答：最快方法：用叶子数＝[n/2]＝500 ，n2=n0-1=499。另外，最后一结点为2i属于左叶子，右叶子是空的，所以有1个非空左子树。完全二叉树的特点决定不可能有左空右不空的情况，所以非空右子树数＝0. 6. 一棵含有n个结点的k叉树，可能达到的最大深度为n，最小深度为2。 答：当k=1(单叉树)时应该最深，深度＝n（层）；当k=n-1（n-1叉树）时应该最浅，深度＝2（层），但不包括n=0或1时的特例情况。教材答案是“完全k叉树”，未定量。) 7.二叉树的基本组成部分是：根（N）、左子树（L）和右子树（R）。因而二叉树的遍历次序有六种。最常用的是三种：前序法（即按N L R次序），后序法（即按L R N次序）和中序法（也称对称序法，即按L N R次序）。这三种方法相互之间有关联。若已知一棵二叉树的前序序列是BEFCGDH，中序序列是FEBGCHD，则它的后序序列必是 F E G H D C B。 解：法1：先由已知条件画图，再后序遍历得到结果； 法2：不画图也能快速得出后序序列，只要找到根的位置特征。由前 序先确定root，由中序先确定左子树。例如，前序遍历BEFCGDH中， 根结点在最前面，是B；则后序遍历中B一定在最后面。 法3：递归计算。如B在前序序列中第一，中序中在中间（可知左 右子树上有哪些元素），则在后序中必为最后。如法对B的左右子树同 数据结构练习题 习题1 绪论 1.1 单项选择题 1. 数据结构是一门研究非数值计算的程序设计问题中,数据元素的①、数据信息在计算机中的②以及一组相关的运算等的课程。 ① A．操作对象Ｂ．计算方法Ｃ．逻辑结构Ｄ．数据映象 ② A．存储结构Ｂ．关系Ｃ．运算Ｄ．算法 2. 数据结构DS(Data Struct)可以被形式地定义为DS=（D，R），其中D是①的有限集合，R是D上的②有限集合。 ① A．算法Ｂ．数据元素Ｃ．数据操作Ｄ．数据对象 ② A．操作Ｂ．映象Ｃ．存储Ｄ．关系 3. 在数据结构中，从逻辑上可以把数据结构分成。 A．动态结构和静态结构Ｂ．紧凑结构和非紧凑结构 Ｃ．线性结构和非线性结构Ｄ．内部结构和外部结构 4. 算法分析的目的是①，算法分析的两个主要方面是②。 ① A. 找出数据结构的合理性 B. 研究算法中的输入和输出的关系 C. 分析算法的效率以求改进 D. 分析算法的易懂性和文档性 ② A. 空间复杂性和时间复杂性 B. 正确性和简明性 C. 可读性和文档性 D. 数据复杂性和程序复杂性 5. 计算机算法指的是①，它必具备输入、输出和②等五个特性。 ① A. 计算方法 B. 排序方法 C. 解决问题的有限运算序列 D. 调度方法 ② A. 可行性、可移植性和可扩充性 B. 可行性、确定性和有穷性 C. 确定性、有穷性和稳定性 D. 易读性、稳定性和安全性 1.2 填空题（将正确的答案填在相应的空中） 1. 数据逻辑结构包括、和三种类型，树形结构和图形结构合称为。 2. 在线性结构中，第一个结点前驱结点，其余每个结点有且只有个前驱结点；最后一个结点后续结点，其余每个结点有且只有个后续结点。 3. 在树形结构中，树根结点没有结点，其余每个结点有且只有个直接前驱结点，叶子结点没有结点，其余每个结点的直接后续结点可以。 4. 在图形结构中，每个结点的前驱结点数和后续结点数可以。 5. 线性结构中元素之间存在关系，树形结构中元素之间存在关系，图形结构中元素之间存在关系。 6. 算法的五个重要特性是__ __ , __ __ , ___ _ , __ __ , _ ___。 7. 分析下面算法（程序段），给出最大语句频度，该算法的时间复杂度是__ __。 for (i=0;i 数据结构练习（二叉树） 学号31301374 姓名张一博班级软件工程1301 . 一、选择题 1．按照二叉树定义，具有3个结点的二叉树共有 C 种形态。 (A) 3 (B) 4 (C) 5 (D) 6 2．具有五层结点的完全二叉树至少有 D 个结点。 (A) 9 (B) 15 (C) 31 (D) 16 3．以下有关二叉树的说法正确的是 B 。 (A) 二叉树的度为2 (B)一棵二叉树的度可以小于2 (C) 至少有一个结点的度为2 (D)任一结点的度均为2 4．已知二叉树的后序遍历是dabec，中序遍历是debac，则其前序遍历是 D 。 （A）acbed （B）decab (C) deabc (D) cedba 5．将一棵有1000个结点的完全二叉树从上到下，从左到右依次进行编号，根结点的编号为1，则编号为49的结点的右孩子编号为 B 。 (A) 98 (B) 99 (C) 50 (D) 没有右孩子 6．对具有100个结点的二叉树，若有二叉链表存储，则其指针域共有 D 为空。 (A) 50 (B) 99 (C) 100 (D) 101 7．设二叉树的深度为h，且只有度为1和0的结点，则此二叉树的结点总数为 C 。 (A) 2h (B) 2h-1 (C) h (D) h+1 8．对一棵满二叉树，m个树叶，n个结点，深度为h，则 D 。 (A) n=h+m (B) h+m=2n (C)m=h-1 (D)n=2h-1 9．某二叉树的先序序列和后序序列正好相反，则下列说法错误的是 A 。 (A) 二叉树不存在 (B) 若二叉树不为空，则二叉树的深度等于结点数 (C) 若二叉树不为空，则任一结点不能同时拥有左孩子和右孩子 (D) 若二叉树不为空，则任一结点的度均为1 10．对二叉树的结点从1开始进行编号，要求每个结点的编号大于其左右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用 A 遍历实现编号。 (A) 先序(B)中序(C)后序(D)层序 11．一个具有1025个结点的二叉树的高h为 C 。 (A) 10 (B)11 (C)11~1025 (D)10~1024 12．设n,m为一棵二叉树上的两个结点，在中序遍历时，n在m前的条件是 C 。 ( A) n在m右方(B)n是m祖先 (C) n在m左方(D) n是m子孙 13．实现对任意二叉树的后序遍历的非递归算法而不使用栈结构，最佳方案是二叉树采用 C 存储结构。 (A) 二叉链表(B) 广义表(C)三叉链表(D)顺序 14. 一棵树可转换成为与其对应的二叉树，则下面叙述正确的是 A 。 (A) 树的先根遍历序列与其对应的二叉树的先序遍历相同 (B) 树的后根遍历序列与其对应的二叉树的后序遍历相同 (C) 树的先根遍历序列与其对应的二叉树的中序遍历相同 (D) 以上都不对 二、填空题 1．对一棵具有n个结点的二叉树，当它为一棵完全二叉树时具有最小高度；当它为单分支二叉树时，具有最大高度。 void PreOrder_Nonrecursive(Bitree T)//先序遍历二叉树的非递归算法 { InitStack(S); Push(S,T); //根指针进栈 while(!StackEmpty(S)) { while(Gettop(S,p)&&p) { visit(p->data); push(S,p->lchild); } //向左走到尽头 pop(S,p); if(!StackEmpty(S)) { pop(S,p); push(S,p->rchild); //向右一步 } }//while }//PreOrder_Nonrecursive 一、下面是有关二叉树的叙述，请判断正误 1.二叉树中每个结点的两棵子树的高度差等于1。（） 2.二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。（） 3.对于一棵非空二叉树，它的根结点作为第一层，则它的第i层上最多能有2i —1个结点。（） 4.用二叉链表法（link-rlink）存储包含n个结点的二叉树，结点的2n个指针区域中有n+1个为空指针。（） 5.具有12个结点的完全二叉树有5个度为2的结点。（） 最快方法：用叶子数＝[n/2]＝6，再求n2=n0-1=5 6．二叉树是度为2的有序树（） 7．完全二叉树一定存在度为1的结点（） 8．深度为K的二叉树中结点总数≤2k-1（） 9．由一棵二叉树的先序序列和后序序列可以惟一确定它（） 10．完全二叉树中，若一个结点没有左孩子，则它必是树叶（） 11．用二叉链表存储n个结点的二叉树时，结点的2n个指针中有n+1个空指针（）12．完全二叉树的存储结构通常采用顺序存储结构（） 13．哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近（）14．在中序线索二叉树中，每一非空的线索均指向其祖先结点（） 二、填空 1. 一棵具有２５７个结点的完全二叉树，它的深度为。 2. 用5个权值{3, 2, 4, 5, 1}构造的哈夫曼（Huffman）树的带权路径长度是 3．深度为H 的完全二叉树至少有_____________个结点；至多有_____________个结点4．已知二叉树有50个叶子结点，则该二叉树的总结点数至少是_____________。 5. n（n大于1）个结点的各棵树中，其深度最小的那棵树的深度是_____________。它共有_____________个叶子结点和_____________个非叶子结点，其中深度最大的那棵树的深度是_____________，它共有_____________个叶子结点和_____________个非叶子结点。 三、单项选择题 1．有关二叉树下列说法正确的是（） A）二叉树的度为2 B）一棵二叉树的度可以小于2 C）二叉树中至少有一个结点的度为2 D）二叉树中任何一个结点的度都为2 2．二叉树的第I层上最多含有结点数为（） A）2I B）2I-1-1 C）2I-1D）2I-1 3．具有10个叶结点的二叉树中有（）个度为2的结点 A）8 B）9 C）10 D）11 4．在下述结论中，正确的是（） ①只有一个结点的二叉树的度为0； ②二叉树的度为2； ③二叉树的左右子树可任意交换； ④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。 A）①②③B）②③④C）②④D）①④ 5．由3 个结点可以构造出多少种不同的二叉树？（） A）2 B）3 C）4 D）5 6．引入二叉线索树的目的是（） 第6章树和二叉树 6.1 知识点概述 树（Tree）形结构是一种很重要的非线性结构，它反映了数据元素之间的层次关系和分支关系。在计算机科学中具有广泛的应用。 1、树的定义 树（Tree）是n（n≥0）个数据元素的有限集合。当n＝0时，称这棵树为空树。在一棵非空树T中： （1）有一个特殊的数据元素称为树的根结点，根结点没有前驱结点。 （2）若n>1，除根结点之外的其余数据元素被分成m（m>0）个互不相交的集合T1，T2，…，Tm，其中每一个集合Ti（1≤i≤m）本身又是一棵树。树T1，T2，…，Tm称为这个根结点的子树。 2、树的基本存储结构 （1）双亲表示法 由于树中的每一个结点都有一个唯一确定的双亲结点，所以我们可用一组连续的 存储空间（即一维数组）存储树中的结点。每个结点有两个域：一个是data域，存放结点信息，另一个是parent域，用来存放双亲的位置(指针)。 （2）孩子表示法 将一个结点所有孩子链接成一个单链表形，而树中有若干个结点，故有若干个单 链表，每个单链表有一个表头结点，所有表头结点用一个数组来描述这种方法通常是把每个结点的孩子结点排列起来，构成一个单链表，称为孩子链表。 （3）双亲孩子表示法 双亲表示法是将双亲表示法和孩子表示法相结合的结果。其仍将各结点的孩子结点分别组成单链表，同时用一维数组顺序存储树中的各结点，数组元素除了包括结点本身的信息和该结点的孩子结点链表的头指针之外，还增设一个域，存储该结点双亲结点在数组中的序号。 （4）孩子兄弟表示法 这种表示法又称为树的二叉表示法，或者二叉链表表示法，即以二叉链表作为树的存储结构。链表中每个结点设有两个链域，分别指向该结点的第一个孩子结点和下一个兄弟（右兄弟）结点。 3、二叉树的定义 二叉树（Binary Tree）是个有限元素的集合，该集合或者为空、或者由一个称为根(root)的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成。当集合为空时，称该二叉树为空二叉树。在二叉树中，一个元素也称作一个结点。 4、满二叉树 定义：在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子结点都在同一层上，这样的一棵二叉树称作满二叉树。 5、完全二叉树 定义：一棵深度为k的有n个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为i（1≤i≤n）的结点与满二叉树中编号为i的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。完全二叉树的特点是：叶子结点只能出现在最下层和次下层，且最下层的叶子结点集中在树的左部。 6、二叉树的性质 数据结构－树练习题 一、选择题 1、二叉树的深度为k，则二叉树最多有（ C ）个结点。 A. 2k B. 2k-1 C. 2k-1 D. 2k-1 2、用顺序存储的方法，将完全二叉树中所有结点按层逐个从左到右的顺序存放在一维数组R[1..N]中，若结点R[i]有右孩子，则其右孩子是（ B ）。 A. R[2i-1] B. R[2i+1] C. R[2i] D. R[2/i] 3、设a,b为一棵二叉树上的两个结点，在中序遍历时，a在b前面的条件是（ B ）。 A. a在b的右方 B. a在b的左方 C. a是b的祖先 D. a是b的子孙 4、设一棵二叉树的中序遍历序列：badce，后序遍历序列：bdeca，则二叉树先序遍历序列为（）。 A. adbce B. decab C. debac D. abcde 5、在一棵具有5层的满二叉树中结点总数为（ A ）。 A. 31 B. 32 C. 33 D. 16 6、由二叉树的前序和后序遍历序列（ B ）惟一确定这棵二叉树。 A. 能 B. 不能 7、某二叉树的中序序列为ABCDEFG，后序序列为BDCAFGE，则其左子树中结点数目为（ C ）。 A. 3 B. 2 C. 4 D. 5 8、若以{4,5,6,7,8}作为权值构造哈夫曼树，则该树的带权路径长度为（ C ）。 A. 67 B. 68 C. 69 D. 70 9、将一棵有100个结点的完全二叉树从根这一层开始，每一层上从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的左孩子编号为（A ）。 A. 98 B. 99 C. 50 D. 48 10、表达式a*(b+c)-d的后缀表达式是（ B ）。 A. abcd+- B. abc+*d- C. abc*+d- D. -+*abcd 11、对某二叉树进行先序遍历的结果为ABDEFC，中序遍历的结果为DBFEAC，则后序遍历的结果是（ B ）。 A. DBFEAC B. DFEBCA C. BDFECA D. BDEFAC 12、树最适合用来表示（ C ）。 A. 有序数据元素 B. 无序数据元素 C. 元素之间具有分支层次关系的数据 D. 元素之间无联系的数据 13、表达式A*(B+C)/(D-E+F)的后缀表达式是（ C ） A. A*B+C/D-E+F B. AB*C+D/E-F+ C. ABC+*DE-F+/ D. ABCDED*+/-+ 14、任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序（）。 A. 不发生改变 B. 发生改变 C. 不能确定 D. 以上都不对 15、假定在一棵二叉树中，度为2的结点数为15，度为1的结点数为30，则叶子结点数为（）个。 A. 15 B. 16 C. 17 D. 47 16、由权值为3，6，7，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（）。 A. 51 B. 23 C. 53 D. 74 学生实验报告 学院：软通学院 课程名称：数据结构与算法 专业班级：软件142 班 姓名：邹洁蒙 学号： 0143990 学生实验报告 （二） 一、实验综述 1、实验目的及要求 目的：1）掌握树与二叉树的基本概念； 2）掌握二叉树的顺序存储，二叉链表的先序遍历中序遍历和后序遍历算法； 3）掌握树的双亲表示法。 要求：1）编程：二叉树的顺序存储实现； 2）编程：二叉链表的先序遍历中序遍历和后序遍历实现； 3）编程：树的双亲表示法实现。 2、实验仪器、设备或软件 设备：PC 软件：VC6 二、实验过程(编程，调试，运行；请写上源码，要求要有注释) 1.编程：二叉树的顺序存储实现 代码： BiTree::BiTree()//建立存储空间 { data = new int[MAXSIZE]; count = 0; } void BiTree::AddNode(int e)//加结点 { int temp = 0; data[count] = e; count++;//从编号0开始保存 } 运行截图： 2.编程：二叉链表的先序遍历中序遍历和后序遍历实现代码： void InOrderTraverse(BiTree* Head)//中序遍历 { if (Head) { InOrderTraverse(Head->LeftChild); cout << Head->data<<" "; InOrderTraverse(Head->RightChild); } } void PreOrderTraverse(BiTree* Head)//先序遍历 { if (Head) { cout << Head->data << " "; PreOrderTraverse(Head->LeftChild); PreOrderTraverse(Head->RightChild); } } void PostOrderTraverse(BiTree* Head)//后序遍历 { if (Head) { PostOrderTraverse(Head->LeftChild); PostOrderTraverse(Head->RightChild); cout << Head->data << " "; } } 运行截图：第六章树和二叉树习题数据结构
目前最完整的数据结构1800题包括完整答案树和二叉树答案
数据结构树和二叉树习题
树和二叉树习题数据结构
数据结构第6章二叉树自测题参考答案
(完整版)数据结构练习题(含答案)
数据结构练习(二叉树)
数据结构第6章树练习
数据结构—— 树和二叉树知识点归纳
数据结构-树练习题
数据结构实验报告之树与二叉树