数据库系统l试题库及答案 第6章 树和二叉树.docx
《数据库系统l试题库及答案 第6章 树和二叉树.docx》由会员分享，可在线阅读，更多相关《数据库系统l试题库及答案 第6章 树和二叉树.docx（21页珍藏版）》请在冰点文库上搜索。
数据库系统l试题库及答案第6章树和二叉树
第6章树和二叉树
6.1知识点:
树和二叉树的基本概念
一、填空题
1.高度为h，度为m的树中至少有___________个结点，至多有______________个结点。
2.树的结点是由及若干指向其子树的组成；结点拥有的子树数称为；度为0的结点称为；度不为0的结点成为；树中结点的最大度数称为；树的最大层次称为_____________。
3.对于一棵具有n个结点的树，该树中所有结点的度数之和为___________。
4.如果结点A有3个兄弟结点，而且B是A的双亲，则B的度是___________。
5.二叉树是另一种树形结构，它的特点是。
6.一颗度数为k且有2k-1个结点的二叉树称为。
7.深度为k，且有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1到n的结点一一对应时，称之为。
8.一棵深度为6的满二叉树有个分支结点和个叶子。
9.一棵具有257个结点的完全二叉树，它的深度为。
10.设一棵完全二叉树具有1000个结点，则此完全二叉树有个叶子结点，有个度为2的结点，有个结点只有非空左子树，有个结点只有非空右子树。
11.由3个结点可以构成__________种形态的的二叉树，可以构成种形态的树。
12.将含有82个结点的完全二叉树从根结点开始顺序编号，根结点为第1号，其他结点自上向下，同一层自左向右连续编号。
则第40号结点的双亲结点的编号为。
13.一棵高度为5的完全二叉树中，最多包含有____________个结点。
14.一棵具有n个结点的二叉树，若它有n0个叶子结点，则该二叉树上度为1的结点n1=____________。
15.在高度为h（h>=0）的二叉树中至多可以有__________个结点，至少可以有___________个结点。
16.n个结点的二叉树最大高度是____________,最小高度是_______________。
二、选择题
1.（）不含任何结点的空树（）。
A.是一棵树B.是一棵二叉树C.是一棵树也是一棵二叉树D.既不是树也不是二叉树
2.（）一棵度为4的树中度为1、2、3、4的结点个数为4、3、2、1，则该树的结点总数为（）。
A.21B.26C.27D.24
3.（）具有10个叶子结点的二叉树中有个度为2的结点。
A.8B.9C.10D.11
4.（）在一棵高度为h（假定根结点的层号为1）的完全二叉树中，所含结点个数不小于（）。
A．
B．
C．
D．
5.（）如下的4棵二叉树中，（）不是完全二叉树。
A．B.C.D.
6.（）设树T的度为4，其中度为1，2，3,4的结点个数分别为4，2，1，1则T中的叶子数为（）。
A．5B．6C．7D．8
7.（）从供选择的答案中，选出应填入下面叙述内的最确切的解答，把相应编号写在答卷的对应栏内。
树是结点的有限集合，它A根结点，记为T。
其余的结点分成为m（m≥0）个B
的集合T1，T2，…，Tm，每个集合又都是树，此时结点T称为Ti的父结点，Ti称为T的子结点
（1≤i≤m）。
一个结点的子结点个数为该结点的C。
供选择的答案
A：
①有0个或1个②有0个或多个③有且只有1个④有1个或1个以上
B:
①互不相交②允许相交③允许叶结点相交④允许树枝结点相交
C：
①权②维数③次数（或度）④序
8.（）在一棵二叉树的二叉链表中，空指针域数等于非空指针域数加（）。
A．2B．1C．0D．-1
三、简答题
1．一棵度为2的树与一棵二叉树有何区别？
6.2知识点：
遍历二叉树和线索二叉树
一、填空题
1.二叉树有四种遍历方法：
________、__________、___________、___________。
2.若已知一棵二叉树的先序序列是BEFCGDH，中序序列是FEBGCHD，则它的后序序列必是。
3.二叉树的链式存储结构有：
、、、四种。
4.指向前驱或后继结点的指针称为，加上线索的二叉链表表示的二叉树叫，
5.对二叉树按某种遍历次序使其变为线索二叉树的过程叫。
6.在线索二叉树的结点中增加两个标志域LTag和RTag,若LTag=0,则lchild域指向；若LTag=1,则lchild域指向；若RTag=0,则rchild域指向；若RTag=1,则rchild域指向。
二、选择题
1.（）某二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树一定是（）。
A.空树或只有一个结点B.完全二叉树C.二叉排序树D.高度等于其结点数
2.（）二叉树是非线性数据结构，所以（）。
A.它不能用顺序存储结构存储B.它不能用链式存储结构存储
C.顺序存储结构和链式存储结构都能存储D.顺序存储结构和链式存储结构都不能使用
3.（）线索二叉树是一种（）结构
A.逻辑B.存储C.线性
4.在n个结点的线索二叉树中，线索的数目为（）。
A.n-1B.nC.n+1D.2n
三、判断题
1.（）在先序、中序和后序序列中，叶子结点出现的相对次序是相同的。
2.（）由一棵二叉树的先序序列和中序序列可以唯一确定这棵二叉树。
3.（）在一棵二叉树中，假定每个结点只有左孩子，没有右孩子，对它分别进行中序遍历和后序遍历，则具有相同的遍历结果。
4.（）对于一棵具有n个结点，其高度为h的二叉树，进行任一种次序遍历的时间复杂度为O（n）。
5.（）在一棵具有n个结点的线索化二叉树中，每个结点的指针域可能指向孩子结点，也可能作为线索，使之指向某一种遍历次序的前驱或后继结点。
6.（）若有一个叶子结点是二叉树中某个子树的先序遍历结果序列的最后一个结点，则它一定是该子树中序遍历结果序列的最后一个结点。
7.（）由一棵二叉树的先序序列和后序序列可以唯一确定这棵二叉树。
四、简答题
1.试写出如图所示的二叉树分别按先序、中序、后序遍历时得到的结点序列。
2.设如下图所示的二叉树B的存储结构为二叉链表，root为根指针，结点结构为：
（lchild,data,rchild）。
其中lchild，rchild分别为指向左右孩子的指针，data为字符型，root为根指针，试回答下列问题：
（1）对下列二叉树B，执行下列算法traversal（root），试指出其输出结果；
（2）假定二叉树B共有n个结点，试分析算法traversal（root）的时间复杂度。
3.若已知一棵二叉树的后序序列是FEGHDCB，中序序列是FEBGCHD，试画出这棵二叉树。
4.给定如图所示二叉树T，请画出与其对应的中序线索二叉树。
5.阅读下列算法，若有错，改正之。
BiTreeInSucc（BiTreeq）{
//已知q是指向中序线索二叉树上某个结点的指针，
//本函数返回指向*q的后继的指针。
r=q->rchild;
if（!
r->rtag）
while（!
r->rtag）r=r->rchild;
}
五、算法设计题
1.假定二叉树采用二叉链表存储结构存储，编写递归算法，计算二叉树中叶子结点的数目。
2.假定二叉树采用二叉链表存储结构存储，编写递归算法，求二叉树中以元素值为x的结点为根的子树的深度。
3．假定二叉树采用二叉链表存储结构存储，编写按层次顺序（同一层自左至右）遍历二叉树的算法。
4.假定二叉树采用二叉链表存储结构存储，设计一个算法计算一棵给定二叉树的结点总数。
5.编写算法判别给定二叉树是否为完全二叉树。
6.3知识点：
树和森林
一、填空题
1.树的孩子-兄弟表示法又称为二叉链表表示法，即以作树的存储结构。
2.森林是m（m≥0）棵____________的树的集合。
对树的每个结点而言，其子树的集合即为。
3.遍历树的方法：
一种是先根（次序）遍历树，即先访问树的，然后依次遍历根的每棵子树；另一种是后根（次序）遍历，即先依次遍历每棵子树，然后访问根结点。
4.当以二叉链表作为树的存储结构时，树的先根遍历和后根遍历可借用二叉树的和来实现。
5.森林的先序遍历与其转换成的二叉树的相同，森林的中序遍历与其转换成的二叉树的_____________相同。
6.设森林F中有4棵树，第1、2、3、4棵树的结点个数分别为n1、n2、n3、n4，当把森林F转换成一棵二叉树后，其根结点的左子树中有______个结点，根结点的右子树上有___________个结点。
7.若用孩子兄弟链存储结构来存储具有m个叶子结点、n个分支结点的树，则孩子兄弟链中有_______个左指针域为空的结点，有_________个右指针域为空的结点。
二、选择题
1.（）把一棵树转换为二叉树后，这棵二叉树的形态是（）。
A．唯一的B．有多种C．有多种，但根结点都没有右孩子D．有多种，但根结点都没有左孩子
2.（）下图所示的二叉树T2是由森林T1转换而来的二叉树，那么森林T1有（）个叶子结点。
A．4B．5C．6D．7
3.从供选择的答案中，选出应填入下面叙述内的最确切的解答，把相应编号写在答卷的对应栏内。
二叉树A。
在完全的二叉树中，若一个结点没有B，则它必定是叶结点。
每棵树都能惟一地转换成与它对应的二叉树。
由树转换成的二叉树里，一个结点N的左孩子是N在原树里对应结点的C，而N的右孩子是它在原树里对应结点的D。
供选择的答案
A：
①是特殊的树②不是树的特殊形式③是两棵树的总称④有是只有二个根结点的树形结构
B:
①左孩子结点②右孩子结点③左孩子结点或者没有右孩子结点④兄弟
C～D：
①最左孩子结点②最右孩子结点③最邻近的右兄弟
④最邻近的左兄弟⑤最左的兄弟⑥最右的兄弟
答案：
A=B=C=D＝
4.（）在下列存储形式中，（）不是树的存储形式。
A.双亲表示法B.孩子链表表示法C.孩子兄弟链表表示法D.顺序存储表示法
5.（）用双亲存储结构表示树，其优点之一是（）比较方便。
A.找指定结点的双亲结点B.找指定结点的孩子结点
C.找指定结点的兄弟结点D.判断某结点是不是叶子结点
6.（）在孩子链表存储结构中，其优点之一是（）比较方便。
A.判断两个指定结点是不是兄弟B.找指定结点的双亲
C.判断指定结点在第几层D.计算指定结点度数
7.（）如果用孩子兄弟链表来表示一颗具有n（n>1）个结点的树，则在该存储结构中（）
A.至多有n-1个非空的右指针域B.至少有两个空的右指针域
C.至少有两个非空的左指针域D.至多有n-1个空的右指针域
8.（）如果T1是由有序树T转换而来的二叉树，那么T中结点的后序遍历序列就是T1中结点的（）序列。
A.先序B.中序C.后序D.层次序
三、简答题
1.把如图所示的树转化成二叉树。
2.画出和下列二叉树相应的森林。
6.4知识点：
哈夫曼编码
一、填空题
1.假设有n个权值{w1，w2，…，wn}，试构造一棵有n个结点的二叉树，每个叶子结点带权为wi，则其中带权路径长度为WPL最小的二叉树称为或。
2.用5个权值{3,2,4,5,1}构造的哈夫曼（Huffman）树的带权路径长度是。
3.由于赫夫曼树中没有度为1的结点，则一颗有n个叶子结点的赫夫曼树共有个结点。
二、选择题
1.（）根据使用频率为5个字符设计的哈夫曼编码不可能是（）。
A．111，110，10，01，00B．000，001，010，011，1
C．100，11，10，1，0D．001，000，01，11，10
2.（）设有13个值，用它们组成一颗哈夫曼树，该哈夫曼树共有（）个结点。
A．13B．12C．26D．25
3.（）下述编码中哪一个不是前缀码（）。
A．（00，01，10，11）B．（0，1，00，11）
C．（0，10，110，111）D．（1，01，000，001）
3、判断题
（）1.哈夫曼树中不存在度为1的结点。
（）2.在哈夫曼树中，权值相同的叶子结点都在同一层。
（）3.在哈夫曼树中，权值较大的叶子结点一般离根结点较远。
（）4.在哈夫曼树中，当两个字符出现的频率相同时，其编码也相同。
四、简答题
1.假设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。
试为这8个字母设计哈夫曼编码。
使用0～7的二进制表示形式是另一种编码方案。
对于上述实例，比较两种方案的优缺点，哈夫曼编码的平均码长是等长编码的百分之几？
2.假定用于通信的电文仅由8个字母c1,c2,c3,c4,c5,c6,c7,c8组成,各字母在电文中出现的频率分别为（5,25,3,6,10,11,36,4）。
（1）试构造哈夫曼树；
（2）试为这8个字母设计不等长Huffman编码；（3）求其WPL值。
3.已知某电文中出现了6种不同的字母，它们的出现次数分别为：
A为6次，B为26次，C为36次，D为17次，E为3次，F为12次。
完成以下题目。
（1）请为这些字符设计哈夫曼编码；
（2）请用三位二进制数对这6各字母进行等长编码；
（3）哈夫曼编码的平均码长是等长编码的百分之几？
第6章树和二叉树
6.1知识点:
树和二叉树的基本概念
一、填空题
1.h-1+m（mh-1）/（m-1）2.数据元素分支结点的度叶子或终端结点非终端结点或分支结点树的度树的深度3.n-14.45.每个结点至多只有两颗子树（即二叉树中不存在度大于2的结点），并且二叉树的子树有左右之分，其次序不能任意颠倒6.满二叉树7.完全二叉树8.31329.910.5004991011.5212.2013.3114.n-2n0+115.2h-1h16.nlog2n+1
二、选择题
1.C2.A3.B4.A5.D6.D7.ABC＝1，1，38.A
三、简答题
1．度为2的树从形式上看与二叉树很相似，但它的子树是无序的，而二叉树是有序的。
即，在一般树中若某结点只有一个孩子，就无需区分其左右次序，而在二叉树中即使是一个孩子也有左右之分。
6.2知识点：
遍历二叉树和线索二叉树
一、填空题
1.先序遍历中序遍历后序遍历层次遍历2.FEGHDCB3.二叉链表、三叉链表、双亲链表、线索链表4.线索线索二叉树二叉树的线索化5.左孩子该结点的前驱结点右孩子该结点的后继结点
二、选择题
1.D2.C3.B4.C
三、判断题
1.√2.√3.√4.√5.√6.√7.×
四、简答题
1.DLR：
ABDFJGKCEHILM
LDR:
BFJDGKACHELIM
LRD：
JFKGDBHLMIECA
2.这是“先根再左再根再右”，比前序遍历多打印各结点一次，输出结果为：
ABCCEEBADFFDGG
3.
4.要遵循中序遍历的轨迹来画出每个前驱和后继。
中序遍历序列：
5540256028083354
5.r=q->rchild;应改为r=q；
while（!
r->rtag）r=r->rchild;应改为while（!
r->Ltag）r=r->Lchild;
五、算法设计题
1.思路：
输出叶子结点比较简单，用任何一种遍历递归算法，凡是左右指针均空者，则为叶子，将其打印出来。
法一：
核心部分为：
DLR（liuyu*root）/*中序遍历递归函数*/
{if（root!
=NULL）
{if（（root->lchild==NULL）&&（root->rchild==NULL））{sum++;printf（"%d\n",root->data）;}
DLR（root->lchild）;
DLR（root->rchild）;}
return（0）;}
法二：
intLeafCount_BiTree（BitreeT）//求二叉树中叶子结点的数目
{if（!
T）return0;//空树没有叶子
elseif（!
T->lchild&&!
T->rchild）return1;//叶子结点
elsereturnLeaf_Count（T->lchild）+Leaf_Count（T->rchild）;//左子树的叶子数加
上右子树的叶子数
}//LeafCount_BiTree
2.
intGet_Sub_Depth（BitreeT,intx）//求二叉树中以值为x的结点为根的子树深度
{
if（T->data==x）
{
printf（"%d\n",Get_Depth（T））;//找到了值为x的结点,求其深度
exit1;
}}
else
{
if（T->lchild）Get_Sub_Depth（T->lchild,x）;
if（T->rchild）Get_Sub_Depth（T->rchild,x）;//在左右子树中继续寻找
}}//Get_Sub_Depth
intGet_Depth（BitreeT）//求子树深度的递归算法
{
if（!
T）return0;
else
{m=Get_Depth（T->lchild）;
n=Get_Depth（T->rchild）;
return（m>n?
m:
n）+1;
}}//Get_Depth
3．voidLayerOrder（BitreeT）//层序遍历二叉树
{
InitQueue（Q）;//建立工作队列
EnQueue（Q,T）;
while（!
QueueEmpty（Q））
{DeQueue（Q,p）;
visit（p）;
if（p->lchild）EnQueue（Q,p->lchild）;
if（p->rchild）EnQueue（Q,p->rchild）;
}}//LayerOrder
4.intNodes（BTNode*T）
{
intnum1,num2;
if（T==NULL）return0;
elseif（T->lchild==NULL&&T->rchild==NULL）return1;
else{
num1=Nodes（T->lchild）;
num2=Nodes（T->rchild）;
returnnum1+num2+1;
}
}
5.intIsFull_Bitree（BitreeT）//判断二叉树是否完全二叉树,是则返回1,否则返回0
{InitQueue（Q）;
flag=0;
EnQueue（Q,T）;//建立工作队列
while（!
QueueEmpty（Q））
{
DeQueue（Q,p）;
if（!
p）flag=1;
elseif（flag）return0;
else{EnQueue（Q,p->lchild）;
EnQueue（Q,p->rchild）;//不管孩子是否为空,都入队列
}
}//while
return1;
}//IsFull_Bitree
分析:
该问题可以通过层序遍历的方法来解决.不管当前结点是否有左右孩子,都入队列.这样当树为完全二叉树时,遍历时得到是一个连续的不包含空指针的序列.反之,则序列中会含有空指针.
6.3知识点：
树和森林
一、填空题
1.二叉链表2.互不相交森林3.根结点先根后根4.先序遍历中序遍历5.先序遍历中序遍历6.n1-1n2+n3+n47.mn+1
二、选择题
1.C2.C3.ABCDE＝2，1，1，34.D5.A6.D7.B8.B
三、简答题
1.
2.画出和下列二叉树相应的森林。
答：
注意根右边的子树肯定是森林，而孩子结点的右子树均为兄弟。
6.4知识点：
哈夫曼编码
一、填空题
1.最优二叉树赫夫曼树2.333.2n-1
二、选择题
1.C2.D3.B
三、判断题
1.×2.×3.×4.×
四、简答题
1.先将概率放大100倍，以方便构造哈夫曼树。
w={7,19,2,6,32,3,21,10}，按哈夫曼规则：
【[（2,3），6],（7,10）】,……19,21,32
方案比较：
方案1的WPL＝2（0.19+0.32+0.21）+4（0.07+0.06+0.10）+5（0.02+0.03）=1.44+0.92+0.25=2.61
方案2的WPL＝3（0.19+0.32+0.21+0.07+0.06+0.10+0.02+0.03）=3
结论：
哈夫曼编码优于等长二进制编码
哈夫曼编码的平均码长与等长编码的平均码长之比为：
2.61/3=87%
2.
（1）
61
39
36
25
22
17
7
10
11
11
4
3
6
5
C3
C8
C5
C6
C1
C4
C2
C7
0
0
0
0
0
0
1
1
1
1
1
1
（2）
c1
c2
c3
c4
c5
C6
c7
c8
0110
10
0000
0111
001
010
11
0001
（3）WPL=4*5+2*25+4*3+4*6+3*10+3*11+2*36+4*4=257
3.1）哈夫曼编码为：
A：
0101B：
10C：
11D：
00E：
0100F：
011
（2）等长编码为：
A：
000B：
001C：
010D：
011E：
100F：
101
（3）哈夫曼编码的平均码长为WPL=230
等长编码的平均码长为WPL=（3+6+12+17+26+36）*3=300
哈夫曼编码的平均码长与等长编码的平均码长之比为：
230/300=77%
升级会员 