数据结构练习题--树(题)

《数据结构练习题--树(题)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第六章树一．名词解释：1树2。结点的度3。叶子4。分支点5。树的度6．父结点、子结点7兄弟8结点的层数9树的高度10二叉树11空二叉树12左孩子、右孩子13孩子数14满二叉树15完全二叉树16先根遍历17中根遍历18后根遍历19二叉树的遍历20判定树21哈夫曼树二、填空题1、树（及一切树形结构）是一种“________”结构。在树上，________结点没有直接前趋。对树上任一结点X来说，X是它的任一子树的根结点惟一的________。2、一棵树上的任何结点（不包括根本身）称为根的________。若B是A的子孙，则称A是B的________3、一般的，

2、二叉树有______二叉树、______的二叉树、只有______的二叉树、只有______的二叉树、同时有______的二叉树五种基本形态。4、二叉树第i(i>=1)层上至多有______个结点。5、深度为k(k>=1)的二叉树至多有______个结点。6、对任何二叉树，若度为2的节点数为n2，则叶子数n0=______。7、满二叉树上各层的节点数已达到了二叉树可以容纳的______。满二叉树也是______二叉树，但反之不然。8、具有n个结点的完全二叉树的深度为______。9、如果将一棵有n个结点的完全二叉树按层编号，则对任一编号为i(1<=i<=

3、n)的结点X有：（1）若i=1,则结点X是______；若i〉1,则X的双亲PARENT(X)的编号为______。（2）若2i>n，则结点X无______且无______；否则，X的左孩子LCHILD(X)的编号为______。（3）若2i+1>n，则结点X无______；否则，X的右孩子RCHILD(X)的编号为______。10.二叉树通常有______存储结构和______存储结构两类存储结构。11.每个二叉链表的访问只能从______结点的指针，该指针具有标识二叉链表的作用。12.对二叉链表的访问只能从______指针开始，若二叉树为空，则__

4、____=NULL.13.二叉链表中每个存储结点的每个指针域必须有一个值，这个值或者是____________的指针，或者是______。14.具有n个结点的二叉树中,一共有________个指针域,其中只有________个用来指向结点的左右孩子，其余的________个指针域为NULL。17．以下程序段采用先根遍历方法求二叉树的叶子数，请在横线处填充适当的语句。Voidcountleaf(bitreptrt,int*count)/*根指针为t，假定叶子数count的初值为0*/{if(t!=NULL){if((t->lchild==NULL)&&(t

5、->rchild==NULL))________;countleaf(t->lchild,&count);________}}18．一棵二叉树由根、左子树和右子树三部分组成，因此对二叉树的遍历也可相应地分解成________、________、________三项“子任务”。19．若以D、L、R分别表示二叉树的三项子任务，限定“先左后右”，这样可能的次序有：________、________、________三种，按这三种次序进行的遍历分别称为________、9________、________。20．树的主要遍历方法有________、_______

6、_、________等三种。24．若二叉树的一个叶子是某子树的中根遍历序列中的第一个结点，则它必是该子树的后根遍历序列中的________个结点。25．在________遍历二叉树的序列中，任何结点的子树上的所有结点，都是直接跟在该结点之后。26．具有n个结点的完全二叉树，若按层次从上到下、从左到右对其编，号（根结点为1号），则编号最大的分支结点序号是________，编号最小的分支结点序号是________，编号最大的叶子结点序号是________，编号最小的叶子结点序号是________。27．二叉树的先根遍历序列中，除根结点外，任一结点均处在其双亲

7、结点的________。28．先根遍历树和先根遍历与该树对应的二叉树，其结果________。29．树与二叉树之间最主要的差别是：二叉树中各结点的子树要区分为________和________，即使在结点只有一棵子树的情况下，也要明确指出该子树是________还是________。30．由________转换成二叉树时，其根结点的右子树总是空的。31．哈夫曼树是带权路径度________的树，通常权值较大的结点离根________。32．有m个叶子结点的哈夫曼树，其结点总数为________。33．一棵树的形状如图填空题33所示，它的根结点是_____

8、___，叶子结点是________，结点H的度是________，这棵树的度是_