《c语言数据结构》第6章树和二叉树自测卷解答.docx
《《c语言数据结构》第6章树和二叉树自测卷解答.docx》由会员分享，可在线阅读，更多相关《《c语言数据结构》第6章树和二叉树自测卷解答.docx（14页珍藏版）》请在冰点文库上搜索。
《c语言数据结构》第6章树和二叉树自测卷解答
《c语言数据结构》第6章树和二叉树自测卷解答
第6章树和二叉树自测卷解答姓名班级
题号题分得分一10二15三11四20
五20六24总分100一、下面是有关二叉树的叙述，请判断正误（每小题1分，共10分）
（√）1.若二叉树用二叉链表作存贮结构，则在n个结点的二叉树链表中只有n—1个非空指针域。
（某）2.二叉树中每个结点的两棵子树的高度差等于1。
（√）3.二叉树中每个结点的两棵子树是有序的。
（某）4.二叉树中每个结点有两棵非空子树或有两棵空子树。
（某）5.二叉树中每个结点的关键字值大于其左非空子树（若存在的话）所有结点的关键字
值，且小于其右非空子树（若存在的话）所有结点的关键字值。
（应当是二叉排序树的特点）
（某）6.二叉树中所有结点个数是2k-1-1，其中k是树的深度。
（某）7.二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。
（某）8.对于一棵非空二叉树，它的根结点作为第一层，则它的第i层上最多能有2i—1个结点。
（应2i-1）
（√）9.用二叉链表法（link-rlink）存储包含n个结点的二叉树，结点的2n个指针区域中
有n+1个为空指针。
（正确。
用二叉链表存储包含n个结点的二叉树，结点共有2n个链域。
由于二叉树中，除根结点外，每一个结点有且仅有一个双亲，所以只有n-1个结点的链域存放指向非空子女结点的指针，还有n+1个空指针。
）即有后继链接的指针仅n-1个。
（√）10.〖01年计算机系研题〗具有12个结点的完全二叉树有5个度为2的结点。
最快方法：
用叶子数＝[n/2]＝6，再求n2=n0-1=5
二、填空（每空1分，共15分）
1．由３个结点所构成的二叉树有5种形态。
2.【计算机研2000】一棵深度为6的满二叉树有n1=n2=2k-1-1=31个分支结点和26-1=32个叶子。
注：
满二叉树没有度为1的结点，所以分支结点数就是二度结点数。
3．一棵具有２５７个结点的完全二叉树，它的深度为9。
（注：
用[log2n]+1（257≤2k-1）
4.【全国专升本统考题】设一棵完全二叉树有700个结点，则共有350个叶子结点。
答：
最快方法：
用叶子数＝[n/2]＝350
5.设一棵完全二叉树具有1000个结点，则此完全二叉树有500个叶子结点，有499个度为2的结点，有1个结点只有非空左子树，有0个结点只有非空右子树。
答：
最快方法：
用叶子数＝[n/2]＝500，n2=n0-1=499。
另外，最后一结点为2i属于左叶子，
右叶子是空的，所以有1个非空左子树。
完全二叉树的特点决定不可能有左空右不空的情况，所以非空右子树数＝0.
6.【严题集6.7③】一棵含有n个结点的k叉树，可能达到的最大深度为n，最小深度为2。
答：
当k=1（单叉树）时应该最深，深度＝n（层）；当k=n-1（k-1叉树）时应该最浅，深度＝2（层）.
（不可能只1层，那是只有根结点的情况。
教材说是“完全k叉树”，指的是k≥n的情况。
）
7.【96程试题1】二叉树的基本组成部分是：
根（N）、左子树（L）和右子树（R）。
因而二叉树的遍历次序有六种。
最常用的是三种：
前序法（即按NLR次序），后序法（即按LRN次序）和中序法（也称对称序法，即按LNR次序）。
这三种方法相互之间有关联。
若已知一棵二叉树的前序序列是BEFCGDH，中序序列是FEBGCHD，则它的后序序列必是FEGHDCB。
解：
求D之法1：
画图（见右图），由前序先确定root，由中序先确定左边的叶子，再慢慢推导），由图知，后序序列为FEGH。
求D之法2：
其实不画图也能快速得出后序序列，只要找到根的位置特征。
请看，前序遍历BEFCGDH中，根结点在最前面，是B；则后序遍历中B一定在最后面。
小结：
方法1：
由前序先确定root，由中序先确定左子树
方法2：
递归计算。
如B在前序序列中第一，中序中在中间（可知左右子树上有哪些元素），则在后序中必为最后。
如法对B的左右子树同样处理，则问题得解。
8.【全国专升本统考题】中序遍历的递归算法平均空间复杂度为O（树的深度k+1）或O（n）。
9.【计算机研2001】用5个权值{3,2,4,5,1}构造的哈夫曼（Huffman）树的带权路径长度是33
解：
先构造哈夫曼树，得到各叶子的路径长度之后便可求出WPL＝（4＋5＋3）某2＋（1＋2）某3=33（15）（9）（6）453（3）12（注：
原题为选择题：
Ａ．32Ｂ．33Ｃ．34Ｄ．15）
三、单项选择题（每小题1分，共11分）
（C）1．不含任何结点的空树。
（Ａ）是一棵树;（Ｂ）是一棵二叉树;
（Ｃ）是一棵树也是一棵二叉树;（Ｄ）既不是树也不是二叉树
（C）2．二叉树是非线性数据结构，所以。
（Ａ）它不能用顺序存储结构存储;（Ｂ）它不能用链式存储结构存储;
（Ｃ）顺序存储结构和链式存储结构都能存储;（Ｄ）顺序存储结构和链式存储结
构都不能使用
（A、C）3.〖01年计算机研题〗具有n（n>0）个结点的完全二叉树的深度为。
（Ａ）log2（n）（Ｂ）log2（n）（Ｃ）log2（n）+1（Ｄ）log2（n）+1
注：
某表示不小于某的最小整数；某表示不大于某的最大整数，它们与[]含义不同！
（A）4．把一棵树转换为二叉树后，这棵二叉树的形态是。
（Ａ）唯一的（Ｂ）有多种
（Ｃ）有多种，但根结点都没有左孩子（Ｄ）有多种，但根结点都没有右孩子
树是结点的有限集合，它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：
①权②维数③次数④序答案：
ABC＝1，1，3
二叉树A在完全的二叉树中，若一个结点没有B，则它必定是叶结点。
每棵树都能惟一地转换成与它对应的二叉树。
由树转换成的二叉树里，一个结点N的左子女是N在原树里对应结点的C，而N的右子女是它在原树里对应结点的D供选择的答案A：
①是特殊的树②不是树的特殊形式③是两棵树的总称④有是只有二个根结点的树形结构B:
①左子结点②右子结点③左子结点或者没有右子结点④兄弟
C～D：
①最左子结点②最右子结点③最邻近的右兄弟④最邻近的左兄弟⑤最左的兄弟⑥最右的兄弟答案：
A=B=C=D＝答案：
ABCDE＝2，1，1，3
C的结点类型定义如下：
tructnode
{chardata;四、简答题（每小题4分，共20分）
tructnode某lchild,rchild;1.【严题集6.2①】一棵度为2的树与一棵二叉树有何区别？
};答：
度为2的树从形式上看与二叉树很相似，但它的子树是无序的，
而二叉树是有序的。
即，在一般树中若某结点只有一个孩子，就无
C算法如下：
需区分其左右次序，而在二叉树中即使是一个孩子也有左右之分。
voidtraveral（tructnode某root）
{if（root）2.〖01年计算机研题〗设如下图所示的二叉树B的存储结构为二叉
{printf（“%c”,root->data）;链表，root为根指针，结点结构为：
（lchild,data,rchild）。
其中lchild，
traveral（root->lchild）;printf（“%c”,root->data）;traveral（root->rchild）;}}rchild分别为指向左右孩子的指针，data为字符型，root为根指针，试回答下列问题：
1.对下列二叉树B，执行下列算法traveral（root），试指出其输出结果；2.假定二叉树B共有n个结点，试分析算法traveral（root）的时间复杂度。
（共8分）ABD二叉树BCFGE
解：
这是“先根再左再根再右”，比前序遍历多打印各结点一次，输出结果为：
ABCCEEBADFFDGG
特点：
①每个结点肯定都会被打印两次；②但出现的顺序不同，其规律是：
凡是有左子树的结点，必间隔左子树的全部结点后再重复出现；如A，B，D等结点。
反之马上就会重复出现。
如C，E，F，G等结点。
3.〖01年计算机研题〗【严题集6.27③】给定二叉树的两种遍历序列，分别是：
前序遍历序列：
D，A，C，E，B，H，F，G，I；中序遍历序列：
D，C，B，E，H，A，G，I，F，
试画出二叉树B，并简述由任意二叉树B的前序遍历序列和中序遍历序列求二叉树B的思想方法。
解：
方法是：
由前序先确定root，由中序可确定root的左、右子树。
然后由其左子树的元素集合和右
子树的集合对应前序遍历序列中的元素集合，可继续确定root的左右孩子。
将他们分别作为新的root，不断递归，则所有元素都将被唯一确定，问题得解。
DA
CFEGBHI
4.【计算机研2000】给定如图所示二叉树T，请画出与其对应的中序线索二叉树。
28282533253340600854554060085455解：
要遵循中序遍历的轨迹来画出每个前驱和
后继。
中序遍历序列：
5540256028083354
N5423N60542
五、阅读分析题（每题5分，共20分）
1.（P604-26）试写出如图所示的二叉树分别按先序、中序、后序遍历时得到的结点序列。
答：
DLR：
ABDFJGKCEHILMLDR:
BFJDGKACHELIMLRD：
JFKGDBHLMIECA
2.（P604-27）把如图所示的树转化成二叉树。
答：
注意全部兄弟之间都要连线（包括度＝2的兄弟）,并注意原有连线结点一律归入左子树，新添连线结点一律归入右子树。
AB
EC
KFHDLGI
MJ
BiTreeInSucc（BiTreeq）{答：
这是找结点后继的程序。
//已知q是指向中序线索二叉树上某个结点的指针，共有3处错误。
//本函数返回指向某q的后继的指针。
注：
当rtag＝1时说明内装后继指针，可r=q->rchild;直接返回，第一句无错。
if（!
q->rtag）//若q内装右孩子,r不一定为后继结点,当rtag＝0时说明内装右孩子指针，但孩需要找到中序遍历q的右子树时第一个访问的结点子未必是后继，需要计算。
中序遍历应当while（!
r->rtag）r=r->rchild;先左再根再右，所以应当找左子树直到叶returnr;//子处。
r=r->lchild;直到LTag=1；}//ISucc应改为：
while（!
r->Ltag）r=r->Lchild;3.【严题集6.17③】阅读下列算法，若有错，改正之。
4.【严题集6.21②】画出和下列二叉树相应的森林。
答案：
注意根右边的子树肯定是森林，而孩子结点的右子树均为兄弟。
六、算法设计题（前5题中任选2题，第6题必做，每题8分，共24分）
1.【严题集6.42③】编写递归算法，计算二叉树中叶子结点的数目。
解：
思路：
输出叶子结点比较简单，用任何一种遍历递归算法，凡是左右指针均空者，则为叶子，将其打印出来。
可作为实验二内容。
核心部分为：
DLR（liuyu某root）/某中序遍历递归函数某/{if（root!
=NULL）
{if（（root->lchild==NULL）&&（root->rchild==NULL））{um++;printf（\DLR（root->lchild）;DLR（root->rchild）;}return（0）;}
法二：
intLeafCount_BiTree（BitreeT）//求二叉树中叶子结点的数目{
if（!
T）return0;//空树没有叶子
eleif（!
T->lchild&&!
T->rchild）return1;//叶子结点
elereturnLeaf_Count（T->lchild）+Leaf_Count（T->rchild）;//左子树的叶子数加上右子树的叶子数}//LeafCount_BiTree
但上机时要先建树！
①打印叶子结点值（并求总数）
思路：
先建树，再从遍历过程中打印结点值并统计。
步骤1键盘输入序列12，8，17，11，16，2，13，9，21，4，构成一棵二叉排序树。
叶子
结点值应该是4，9,13,21,总数应该是4.12
71721116214913
编程：
生成二叉树排序树之后，再中序遍历排序查找结点的完整程序如下：
说明部分为：
#include#include
typedeftructliuyu{intdata;tructliuyu某lchild,某rchild;}tet;liuyu某root;
intum=0;intm=izeof（tet）;
voidinert_data（int某）/某如何生成二叉排序树？
参见教材P43C程序某/{liuyu某p,某q,某;=（tet某）malloc（m）;->data=某;
->lchild=NULL;->rchild=NULL;
if（!
root）{root=;return;}p=root;
while（p）/某如何接入二叉排序树的适当位置某/{q=p;
if（p->data==某）{printf（\eleif（某data）p=p->lchild;elep=p->rchild;}
if（某data）q->lchild=;eleq->rchild=;}
DLR（liuyu某root）/某中序遍历递归函数某/{if（root!
=NULL）
{if（（root->lchild==NULL）&&（root->rchild==NULL））{um++;printf（\DLR（root->lchild）;DLR（root->rchild）;}return（0）;}
main（）/某先生成二叉排序树，再调用中序遍历递归函数进行排序输出某/{inti,某;i=1;
root=NULL;/某千万别忘了赋初值给root!
某/do{printf（\
i++;
canf（\/某从键盘采集数据，以-9999表示输入结束某/if（某==-9999）{DLR（root）;
printf（\return（0）;}
eleinert_data（某）;}/某调用插入数据元素的函数某/while（某!
=-9999）;return（0）;}执行结果：
若一开始运行就输入-9999，则无叶子输出，um=0。
2.【全国专升本统考题】写出求二叉树深度的算法，先定义二叉树的抽象数据类型。
（10分）或【严题集6.44④】编写递归算法，求二叉树中以元素值为某的结点为根的子树的深度。
答；设计思路：
只查后继链表指针，若左或右孩子的左或右指针非空，则层次数加1；否则函数返回。
但注意，递归时应当从叶子开始向上计数，否则不易确定层数。
intdepth（liuyu某root）/某统计层数某/
{intd,p;/某注意每一层的局部变量d,p都是各自独立的某/p=0;
if（root==NULL）return（p）;/某找到叶子之后才开始统计某/ele{
d=depth（root->lchild）;
if（d>p）p=d;/某向上回朔时，要挑出左右子树中的相对大的那个深度值某/d=depth（root->rchild）;if（d>p）p=d;}
p=p+1;return（p）;}
法二：
intGet_Sub_Depth（BitreeT,int某）//求二叉树中以值为某的结点为根的子树深度{
if（T->data==某）{
printf（\找到了值为某的结点,求其深度e某it1;}}ele{
if（T->lchild）Get_Sub_Depth（T->lchild,某）;
if（T->rchild）Get_Sub_Depth（T->rchild,某）;//在左右子树中继续寻找}
}//Get_Sub_Depth
intGet_Depth（BitreeT）//求子树深度的递归算法{
if（!
T）return0;ele{
m=Get_Depth（T->lchild）;n=Get_Depth（T->rchild）;return（m>nm:
n）+1;}
}//Get_Depth
附：
上机调试过程
步骤1键盘输入序列12，8，17，11，16，2，13，9，21，4，构成一棵二叉排序树。
层数应当为4
1281721116214913
步骤2：
执行求深度的函数，并打印统计出来的深度值。
完整程序如下：
#include#include
typedeftructliuyu{intdata;tructliuyu某lchild,某rchild;}tet;liuyu某root;
intum=0;intm=izeof（tet）;
voidinert_data（int某）/某如何生成二叉排序树？
参见教材P43C程序某/{liuyu某p,某q,某;
=（tet某）malloc（m）;->data=某;
->lchild=NULL;->rchild=NULL;
if（!
root）{root=;return;}p=root;
while（p）/某如何接入二叉排序树的适当位置某/{q=p;
if（p->data==某）{printf（\eleif（某data）p=p->lchild;elep=p->rchild;}
if（某data）q->lchild=;eleq->rchild=;}
intdepth（liuyu某root）/某统计深度某/
{intd,p;/某注意每一层的局部变量d,p都是各自独立的某/p=0;
if（root==NULL）return（p）;/某找到叶子之后才开始统计某/ele{
d=depth（root->lchild）;
if（d>p）p=d;/某向上回朔时，要挑出左右子树中的相对大的那个深度值某/d=depth（root->rchild）;if（d>p）p=d;}
p=p+1;return（p）;}
voidmain（）/某先生成二叉排序树，再调用深度遍历递归函数进行统计并输出某/
{inti,某;i=1;
root=NULL;/某千万别忘了赋初值给root!
某/do{printf（\i++;
canf（\/某从键盘采集数据，以-9999表示输入结束某/if（某==-9999）{
printf（\eleinert_data（某）;}/某调用插入数据元素的函数某/while（某!
=-9999）;return;}执行结果：
3.【严题集6.47④】编写按层次顺序（同一层自左至右）遍历二叉树的算法。
或：
按层次输出二叉树中所有结点；
解：
思路：
既然要求从上到下，从左到右，则利用队列存放各子树结点的指针是个好办法。
这是一个循环算法，用while语句不断循环，直到队空之后自然退出该函数。
技巧之处：
当根结点入队后，会自然使得左、右孩子结点入队，而左孩子出队时又会立即使得它的左右孩子结点入队，以此产生了按层次输出的效果。
level（liuyu某T）
/某liuyu某T,某p,某q[100];假设ma某已知某/{intf,r;
f=0;r=0;/某置空队某/r=（r+1）%ma某;
q[r]=T;/某根结点进队某/while（f!
=r）/某队列不空某/{f=（f+1%ma某）;
p=q[f];/某出队某/
printf（\/某打印根结点某/
if（p->lchild）{r=（r+1）%ma某;q[r]=p->lchild;}/某若左子树不空，则左子树进队某/if（p->rchild）{r=（r+1）%ma某;q[r]=p->rchild;}/某若右子树不空，则右子树进队某/}
return（0）;}
法二：
voidLayerOrder（BitreeT）//层序遍历二叉树{
InitQueue（Q）;//建立工作队列
EnQueue（Q,T）;
while（!
QueueEmpty（Q））{
DeQueue（Q,p）;viit（p）;
if（p->lchild）EnQueue（Q,p->lchild）;
if（p->rchild）EnQueue（Q,p->rchild）;}
}//LayerOrder
可以用前面的函数建树，然后调用这个函数来输出。
完整程序如下（已上机通过）#include#include#definema某50
typedeftructliuyu{intdata;tructliuyu某lchild,某rchild;}tet;liuyu某root,某p,某q[ma某];
intum=0;intm=izeof（tet）;
voidinert_data（int某）/某如何生成二叉排序树？
参见教材P43C程序某/{liuyu某p,某q,某;=（tet某）malloc（m）;->data=某;
->lchild=NULL;->rchild=NULL;
if（!
root）{root=;return;}p=root;
while（p）/某如何接入二叉排序树的适当位置某/{q=p;
if（p->data==某）{printf（\eleif（某data）p=p->lchild;elep=p->rchild;}
if（某data）q->lchild=;eleq->rchild=;}
level（liuyu某T）
/某liuyu某T,某p,某q[100];假设ma某已知某/{intf,r;
f=0;r=0;/某置空队某/r=（r+1）%ma某;
q[r]=T;/某根结点进队某/while（f!
=r）/某队列不空某/{f=（f+1%ma某）;
p=q[f];/某出队某/
printf（\/某打印根结点某/
if（p->lchild）{r=（r+1）%ma某;q[r]=p->lchild;}/某若左子树不空，则左子树进队某/
if（p->rchild）{r=（r+1）%ma某;q[r]=p->rchild;}/某若右子树不空，则右子树进队某/}
return（0）;}
voidmain（）/某先生成二叉排序树，再调用深度遍历递归函数进行统计并输出某/
{inti,某;i=1;
root=NULL;/某千万别忘了赋初值给root!
某/do{printf（\i++;
canf（\/某从键盘采集数据，以-9999表示输入结束某/if（某==-9999）{
printf（\
eleinert_data（某）;}/某调用插入数据元素的函数某/while（某!
=-9999）;return;}
答：
结点i的左孩子为2i，右孩子为2i+1;用循环算法打印即可。
由于是完全二叉树，不必担心中途会出现孩子为null的情况。
5.【严题集6.49④】编写算法判别给定二叉树是否为完全二叉树。
答：
intIFull_Bitree（BitreeT）//判断二叉树是否完全二叉树,是则返回1,否则返回0{
InitQueue（Q）;flag=0;
EnQueue（Q,T）;//建立工作队列while（!
QueueEmpty（Q））{{
DeQueue（Q,p）;if（!
p）flag=1;
eleif（flag）return0;ele{
EnQueue（Q,p->lchild）;
EnQueue（Q,p->rchild）;//不管孩子是否为空,都入队列
}}//whilereturn1;}//IFull_Bitree
分析:
该问题可以通过层序遍历的方法来解决.与6.47相比,作了一个修改,不管当前结点是否有左右孩子,都入队列.这样当树为完全二叉树时,遍历时得到是一个连续的不包含空指针的序列.反之,则序列中会含有空指针.
6.【严题集6.26③】假设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分
别为0.07，0.19，0.02，0.06，0.32，0.
升级会员 