二叉树习题课.ppt

《二叉树习题课.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、一、判断题二叉树中每个结点的两棵子树的高度差等于1。×二叉树中每个结点的两棵子树是有序的。√二叉树中每个结点有两棵非空子树或有两棵空子树。×二叉树中每个结点的关键字值大于其左非空子树（若存在的话）所有结点的关键字值，且小于其右非空子树（若存在的话）所有结点的关键字值。（应当是二叉搜索树的特点）×二叉树中所有结点个数是2k+1-1，其中k是树的高度。（应当是满二叉树的特点）×二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。×对于一棵非空二叉树，它的第i层上最多能有2i个结点。√8.用二叉链表法

2、存储包含n个结点的二叉树，结点的2n个指针区域中有n+1个为空指针。（用二叉链表存储包含n个结点的二叉树，结点共有2n个链域。二叉树中除根结点外，每一个结点有且仅有一个双亲，所以只有n-1个结点的链域存放指向非空子女结点的指针，还有n+1个空指针。）√具有12个结点的完全二叉树有5个度为2的结点。(对完全二叉树，叶子数＝[n/2]＝6；对一般二叉树，n2=n0-1=5)√（应当是完全二叉树的特点）证明：若设度为1的结点有n1个，总结点个数为n，总边数为e，则根据二叉树的定义:n=n0+n1+n2e=2n

3、2+n1=n-1因此:2n2+n1=n0+n1+n2-1n2=n0-1---------------------(1)对完全二叉树而言，0<=n1<=1则：n0+n2<=n<=n0+n2+1--------(2)根据（1）式和（2）式，得：2n0-1<=n<=2n0即：n/2<=n0<=(n+1)/2则：n0=[n/2]（向上取整）二、填空题一棵具有２５７个结点的完全二叉树，它的深度为。设一棵完全二叉树有700个结点，则共有个叶子结点。设一棵完全二叉树具有1000个结点，则此完全二叉树有个叶子结点，有个

4、度为2的结点，有个结点只有非空左子树，有个结点只有非空右子树。一棵含有n个结点的k叉树，可能达到的最大深度为，最小深度为。中序遍历的递归算法平均空间复杂度为。(递归最大嵌套层数，即栈的占用单元数。精确值应为树的深度k+1，包括叶子的空域也递归了一次)用5个权值{3,2,4,5,1}构造的哈夫曼（Huffman）树的带权路径长度是。一棵深度为6的满二叉树有个分支结点和叶子。3508646350049910n-11三、单项选择题1．不含任何结点的空树。（Ａ）是一棵树;（Ｂ）是一棵二叉树;（Ｃ）是一棵树也是一

5、棵二叉树;Ｄ）既不是树也不是二叉树2．二叉树是非线性数据结构，所以。（Ａ）它不能用顺序存储结构存储;（Ｂ）它不能用链式存储结构存储;（Ｃ）顺序存储结构和链式存储结构都能存储;（Ｄ）顺序存储结构和链式存储结构都不能使用3.具有n(n>0)个结点的完全二叉树的深度为。(Ａ)log2(n)(Ｂ)log2(n)(Ｃ)log2(n)+1(Ｄ)log2(n)+14．把一棵树转换为二叉树后，这棵二叉树的形态是。（Ａ）唯一的（Ｂ）有多种（Ｃ）有多种，但根结点都没有左孩子（Ｄ）有多种，但根结点都没有右孩子

6、完全二叉树的向量表示一般二叉树的向量表示顺序存储结构单支树链式存储结构由于一般二叉树必须仿照完全二叉树那样存储，可能会浪费很多存储空间，单支树就是一个极端情况。阅读分析题试写出如图所示的二叉树分别按先序、中序、后序遍历时得到的结点序列。前序序列ABECDFGHIJ中序序列EBCDAFHIGJ由前序先确定root，由中序确定root的左、右子树。然后由左子树的元素集合和右子树的集合对应前序遍历序列中的元素集合，可继续确定root的左右孩子。将他们分别作为新的root，不断递归，所有元素都将被唯一确定，问题

7、得解。ABECDFGJHI