数据结构与算法分析 C语言描述（第2版）Larry Nyhoff 二叉树习题课 课件.ppt

《数据结构与算法分析 C语言描述（第2版）Larry Nyhoff 二叉树习题课 课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

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

3、则：n0+n2<=n<=n0+n2+1--------(2)根据（1）式和（2）式，得：2n0-1<=n<=2n0即：n/2<=n0<=(n+1)/2则：n0=[n/2]（向上取整）二、填空题一棵具有２５７个结点的完全二叉树，它的深度为。设一棵完全二叉树有700个结点，则共有个叶子结点。设一棵完全二叉树具有1000个结点，则此完全二叉树有个叶子结点，有个度为2的结点，有个结点只有非空左子树，有个结点只有非空右子树。一棵含有n个结点的k叉树，可能达到的最大深度为，最小深度为。中序遍历的递归算法平均空间复杂度为。(递归最大嵌套层数，即栈的占用单元数。精确值应为树的深度k+1，包括叶

4、子的空域也递归了一次)用5个权值{3,2,4,5,1}构造的哈夫曼（Huffman）树的带权路径长度是。一棵深度为6的满二叉树有个分支结点和叶子。3508646350049910n-11三、单项选择题1．不含任何结点的空树。（Ａ）是一棵树;（Ｂ）是一棵二叉树;（Ｃ）是一棵树也是一棵二叉树;Ｄ）既不是树也不是二叉树2．二叉树是非线性数据结构，所以。（Ａ）它不能用顺序存储结构存储;（Ｂ）它不能用链式存储结构存储;（Ｃ）顺序存储结构和链式存储结构都能存储;（Ｄ）顺序存储结构和链式存储结构都不能使用3.具有n(n>0)个结点的完全二叉树的深度为。(Ａ)log2(n)(Ｂ)log2

5、(n)(Ｃ)log2(n)+1(Ｄ)log2(n)+14．把一棵树转换为二叉树后，这棵二叉树的形态是。（Ａ）唯一的（Ｂ）有多种（Ｃ）有多种，但根结点都没有左孩子（Ｄ）有多种，但根结点都没有右孩子完全二叉树的向量表示一般二叉树的向量表示顺序存储结构单支树链式存储结构由于一般二叉树必须仿照完全二叉树那样存储，可能会浪费很多存储空间，单支树就是一个极端情况。把如图所示的树转化成二叉树从供选择的答案中，选出最确切的解答，把相应编号写在答卷的对应栏内。树是结点的有限集合，它A根结点，记为T。其余的结点分成为m（m≥0）个B的集合T1，T2，…，Tm，每个集合又都是树，此时结点T

6、称为Ti的父结点，Ti称为T的子结点（1≤i≤m）。一个结点的子结点个数为该结点的C。供选择的答案A：①有0个或1个②有0个或多个③有且只有1个④有1个或1个以上B:①互不相交②允许相交③允许叶结点相交④允许树枝结点相交C：①权②维数③度④序阅读分析题试写出如图所示的二叉树分别按先序、中序、后序遍历时得到的结点序列。前序序列ABECDFGHIJ中序序列EBCDAFHIGJ由前序先确定root，由中序确定root的左、右子树。然后由左子树的元素集合和右子树的集合对应前序遍历序列中的元素集合，可继续确定root的左右孩子。将他们分别作为新的root，不断递归，所有元素都将被唯一确定

7、，问题得解。ABECDFGJHI假设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。试为这8个字母设计哈夫曼编码。使用0～7的二进制表示形式是另一种编码方案。对于上述实例，比较两种方案的优缺点。哈夫曼编码方案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使用0－7的二进制编码方案WPL＝3(0.19+0.