第06章 树与二叉树B
- 格式:ppt
- 大小:1.56 MB
- 文档页数:38
第6章树和二叉树习题解答一、下面是有关二叉树的叙述,请判断正误(每小题1分,共10分)(√)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. 〖01年考研题〗具有12个结点的完全二叉树有5个度为2的结点。
最快方法:用叶子数=[n/2]=6,再求n2=n0-1=5二、填空(每空1分,共15分)1.由3个结点所构成的二叉树有5种形态。
2. 【计算机研2000】一棵深度为6的满二叉树有n1+n2=0+ n2= n0-1=31 个分支结点和26-1 =32个叶子。
注:满二叉树没有度为1的结点,所以分支结点数就是二度结点数。
3.一棵具有257个结点的完全二叉树,它的深度为9。
(注:用⎣ log2(n) ⎦+1= ⎣ 8.xx ⎦+1=94.【全国专升本统考题】设一棵完全二叉树有700个结点,则共有350个叶子结点。
第6章 树和二叉树(参考答案)6.1(1)根结点a6.2三个结点的树的形态: 三个结点的二叉树的形态:(1) (1) (2) (4) (5)6.3 设树的结点数是n ,则n=n0+n1+n2+……+nm+ (1)设树的分支数为B ,有n=B+1n=1n1+2n2+……+mnm+1 (2)由(1)和(2)有:n0=n2+2n3+……+(m-1)nm+16.4(1) k i-1 (i 为层数)(2) (n-2)/k+1(3) (n-1)*k+i+1(4) (n-1)%k !=0; 其右兄弟的编号 n+16.5(1)顺序存储结构注:#为空结点6.6(1) 前序 ABDGCEFH(2) 中序 DGBAECHF(3) 后序 GDBEHFCA6.7(1) 空二叉树或任何结点均无左子树的非空二叉树(2) 空二叉树或任何结点均无右子树的非空二叉树(3) 空二叉树或只有根结点的二叉树6.8int height(bitree bt)// bt是以二叉链表为存储结构的二叉树,本算法求二叉树bt的高度{ int bl,br; // 局部变量,分别表示二叉树左、右子树的高度if (bt==null) return(0);else { bl=height(bt->lchild);br=height(bt->rchild);return(bl>br? bl+1: br+1); // 左右子树高度的大者加1(根) }}// 算法结束6.9void preorder(cbt[],int n,int i);// cbt是以完全二叉树形式存储的n个结点的二叉树,i是数// 组下标,初始调用时为1。
本算法以非递归形式前序遍历该二叉树{ int i=1,s[],top=0; // s是栈,栈中元素是二叉树结点在cbt中的序号 // top是栈顶指针,栈空时top=0if (n<=0) { printf(“输入错误”);exit(0);}while (i<=n ||top>0){ while(i<=n){visit(cbt[i]); // 访问根结点if (2*i+1<=n) s[++top]=2*i+1; //若右子树非空,其编号进栈i=2*i;// 先序访问左子树}if (top>0) i=s[top--]; // 退栈,先序访问右子树} // END OF while (i<=n ||top>0)}// 算法结束//以下是非完全二叉树顺序存储时的递归遍历算法,“虚结点”用‘*’表示void preorder(bt[],int n,int i);// bt是以完全二叉树形式存储的一维数组,n是数组元素个数。
习题六树和二叉树一、单项选择题1.以下说法错误的是 ( )A.树形结构的特点是一个结点可以有多个直接前趋B.线性结构中的一个结点至多只有一个直接后继C.树形结构可以表达(组织)更复杂的数据D.树(及一切树形结构)是一种"分支层次"结构E.任何只含一个结点的集合是一棵树2.下列说法中正确的是 ( )A.任何一棵二叉树中至少有一个结点的度为2B.任何一棵二叉树中每个结点的度都为2C.任何一棵二叉树中的度肯定等于2D.任何一棵二叉树中的度可以小于23.讨论树、森林和二叉树的关系,目的是为了()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+M37.一棵完全二叉树上有1001个结点,其中叶子结点的个数是()A. 250 B. 500 C.254 D.505 E.以上答案都不对8. 设给定权值总数有n 个,其哈夫曼树的结点总数为( )A.不确定 B.2n C.2n+1 D.2n-19.二叉树的第I层上最多含有结点数为()A.2I B. 2I-1-1 C. 2I-1 D.2I -110.一棵二叉树高度为h,所有结点的度或为0,或为2,则这棵二叉树最少有( )结点A.2h B.2h-1 C.2h+1 D.h+111. 利用二叉链表存储树,则根结点的右指针是()。
A.指向最左孩子 B.指向最右孩子 C.空 D.非空12.已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结果为()。