数据结构考研分类复习真题 第六章 答案 (四)[32]

．前缀码是一编码不是任何其它编码前缀的编码例如和就不是前缀码因为编码是编码的前缀仅从编码来看和 是前缀码但因历史的原因它不被称为前缀码而是把一编码不是另一编码前缀的编码称为前缀码

利用二叉树可以构造前缀码例如以ABCD为叶子可构成二叉树将左分枝解释为右分枝解释成从根结点到叶子结点的串就是叶子的前缀码用哈夫曼树可构造出最优二叉树使编码长度最短

．哈夫曼树只有度为的叶子结点和度为的分枝结点设数量分别为n和n则树的结点数n为n=n+n 另根据二叉树性质任意二叉树中度为的结点数n和度为的结点数n间的关系是n=n代入上式则n=n+n=n

．（）T树的最大深度Kmax=（除根外每层均是两个结点）

T树的最小深度Kmin=（具有个叶子的完全二叉树是其中的一种形态）

（）非叶子结点数是（n=n） （）哈夫曼树见下图其带权路径长度wpl=

．（）错误循环结束条件top=不能满足因为在top>情况下执行top:=top

()错误 （）错误 （）正确 （）结点的深度与其右孩子深度相同比左孩子深度少

[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []