• 原创美文
  • 经典文章
  • 情感美文
  • 伤感文章
  • 散文
  • 美文随笔
  • 感人文章
  • 人生哲理
  • 学生美文
  • 民族文化
  • 说说大全
  • 网名大全
  • 范文大全
  • 当前位置: 佩佩美文网 > 经典文章 > 正文

    [树和二叉树]习题[1]_

    时间:2019-09-15 08:35:53来源:佩佩美文网 本文已影响 佩佩美文网手机站
    -->

    一、选择题

    1.对于先序遍历和中序遍历结果相同的二叉树为( BF );对于先序遍历和后序遍历结果相同的二叉树为( B )

    A. 一般二叉树 B. 只有根结点的二叉树 C. 根结点无左孩子的二叉树

    D. 根结点无右孩子的二叉树 E. 所有结点只有左孩子的二叉树

    F. 所有结点只有右孩子的二叉树。

    2.下列关于哈夫曼树的叙述错误的是( D) 。

    A .哈夫曼树的根结点的权值等于所有叶结点的权值之和

    B .具有n 个叶结点的哈夫曼树共有2n-l 个结点

    C .哈夫曼树是带权外路径长度最短的二叉树

    D .哈夫曼树一个结点的度可以是0、1或2

    3.设T2是由树T 转换得到的二叉树,则T 中结点的后序序列是T2结点的( B ) 。

    A .先序序列 B .中序序列 C .后序序列 D .层次序列

    4.设有一个度为3的树,其叶结点数为n0,度为1的结点数为nl ,度为2的结点数为n2, 度为3的结点数为n3,则n0与nl ,n2,n3满足关系( B )。

    A . n0 =n2+1 B .n0=n2+2*n3+1 C .n0=n2+n3+1 D .n0= nl+n2+n3

    二、填空题

    1.一棵有124个叶结点的完全二叉树,最多有______248__个结点。

    在有n 个结点的哈夫曼树中,其叶子结点数为__2/N+1_______。

    2.若一棵二叉树具有12个度为2的结点,6个度为1的结点,则度为0的结点个数是_____13__。

    3.已知某二叉树的先序序列为ABDECF ,中序序列为DBEAFC 。则其后序序列为_____DEBFCA_____。

    4. 二叉树结点数n 与边数e 的关系为__N=E+1__________。

    5. 己知二叉排序树的先序序列,___能_____唯一确定该二叉排序树。

    6. 完全二叉树采用_顺序__存储结构,满足存储空间少,方便的查找任意结点的双亲与孩子。

    三、综合题

    1.设有n 个结点的二叉树,度为2的结点数为n 2, 度为l 的结点数为n 1,叶结点数为n 0,试分别写出哈夫曼树、完全二叉树和单枝二叉树n 1的取值。

    答案:哈夫曼树:0 在哈夫曼树中,只能有度为0或2 的结点是严格二叉树

    完全二叉树:当n 为奇数时,度为1的结点树为0

    当n 为偶数时,度为1的结点树为1

    单支二叉树:n1=n-1

    2.找出满足下列条件的二叉树:

    (1)先序和中序的访问序列相同;

    根节点没有左孩子的二叉树或者只有根结点

    (2)中序和后序的访问序列相同;

    只有左孩子的二叉树

    (3)先序和后序的访问序列相同;

    只有根节点的二叉树

    3.已知二叉树的中序遍历序列为DEBAFCG ,后序遍历序列为EDBFGCA ,试画出该二叉树。

    4. 可以生成下图所示的二叉排序树的关键字初始序列有几种?试写出其中的任意4种。

    分析过程:{8,4,?,?,?}2^3=6

    {8,9,4,?,?}2

    2+6=8

    5. 设al ,a2,a3是不同的关键字,且al

    6.以权值分别为3,4,7,9,20的a,b,c,d,e 五个元素作为叶结点构造二叉树,回答:

    (1)如何构造路径长度最短的二叉树,图示出一棵路径长度最短二叉树,并计算出路径长度

    分析过程:最短路径长度,所以为完全二叉树:(不考虑权值)

    (9+20)*3+(3+4+7)*2=115

    (2

    最短带权路径:3*4+4*4+7*3+9*2+20*1=87

    7.已知4个字符A,B,C,D 的哈夫曼编码分别是1,01,000,

    001。下列01串是由以上4个字母构成的一

    段文本的哈夫曼编码:[***********]1010011。请将上述01串还原为编码前的文本,以字符在文本中出现的次数为权值,求出这棵树的带权路径长度。

    1 001 000 01 1 01 1 01 001 1 01 001 1

    A D C B A B A B D A B D A

    A:5

    B:4

    C:1 D:3

    带权路径长度:1*3+3*3+4*2+5*1=25

    • [树和二叉树]习题[1]_ 相关文章: