简答题

  1. 二叉树由(1)，(2)，(3)三个基本单元组成。
    (1)根结点(2)左子树(3)右子树
  2. 树在计算机内的表示方式有(1)，(2)，(3)。
    (1)双亲链表表示法(2)孩子链表表示法(3)孩子兄弟表示法
  3. 在二叉树中，指针 p 所指结点为叶子结点的条件是______
    p->lchild==null && p->rchlid==null
  4. 二叉树中某一结点左子树的深度减去右子树的深度称为该结点的____。
    平衡因子
  5. 具有 256 个结点的完全二叉树的深度为______。
    9
  6. 深度为 k 的完全二叉树至少有____(1)____个结点，至多有____(2)____个结点。
    2^(k-1) 　　 2^k-1
  7. 假设根结点的层数为１，具有ｎ个结点的二叉树的最大高度是______
    n
  8. 在一棵二叉树中，度为零的结点的个数为 N0,度为 2 的结点的个数为 N2,则有 N0 =______
    N2+1
  9. 高度为 8 的完全二叉树至少有______个叶子结点。
    64
  10. 已知二叉树有 50 个叶子结点，则该二叉树的总结点数至少是______
    99
  11. 一个有 2001 个结点的完全二叉树的高度为______。
    11
  12. 8 层完全二叉树至少有______个结点，拥有 100 个结点的完全二叉树的最大层数为______
    (1) 128(第七层满，加第八层１个)　　(2) 7
  13. 含 4 个度为 2 的结点和 5 个叶子结点的二叉树，可有______个度为 1 的结点。
    0至多个。任意二叉树，度为１的结点个数没限制。只有完全二叉树，度为１的结点个数才至多为1。
  14. 已知二叉树前序为 ABDEGCF，中序为 DBGEACF，则后序一定是____
    DGEBFCA
  15. 现有按中序遍历二叉树的结果为 abc，问有(1)种不同的二叉树可以得到这一遍历结果，这些二叉树分别是_(2)。
    (1)5 （2）略
  16. 利用树的孩子兄弟表示法存储，可以将一棵树转换为______。
    二叉树
  17. 具有 n 个结点的满二叉树，其叶结点的个数是______。
    (n+1)/2
  18. 哈夫曼树是______。
    带权路径长度最小的二叉树，又称最优二叉树
  19. 若以{4，5，6，7，8}作为叶子结点的权值构造哈夫曼树，则其带权路径长度是______。
    69
  20. 有数据 WG={7，19，2，6，32，3，21，10}，则所建 Huffman 树的树高是(1)，带权路径长度 WPL为_(2)。
    (1)6　　 (2)261
  21. 有一份电文中共使用 6 个字符:a,b,c,d,e,f,它们的出现频率依次为 2,3,4,7,8,9，试构造一棵哈夫曼树，则其加权路径长度 WPL 为(1)，字符 c 的编码是(2)。
    (1)80 (2)001（不唯一）
  22. 设 n0 为哈夫曼树的叶子结点数目，则该哈夫曼树共有______个结点。
    2n0-1
  23. 从概念上讲，树，森林和二叉树是三种不同的数据结构，将树，森林转化为二叉树的基本目的是什么，并指出树和二叉树的主要区别。
    树的孩子兄弟链表表示法和二叉树二叉链表表示法，本质是一样的，只是解释不同，也就是说树（树是森林的特例，即森林中只有一棵树的特殊情况）可用二叉树唯一表示，并可使用二叉树的一些算法去解决树和森林中的问题。
    树和二叉树的区别有三：一是二叉树的度至多为2，树无此限制；二是二叉树有左右子树之分，即使在只有一个分枝的情况下， 也必须指出是左子树还是右子树，树无此限制；三是二叉树允许为空，树一般不允许为空（个别书上允许为空）。
  24. 请分析线性表、树的主要结构特点，以及相互的差异与关联。
    线性表属于约束最强的线性结构，在非空线性表中，只有一个“第一个”元素，也只有一个“最后一个”元素；除第一个元素外，每个元素有唯一前驱；除最后一个元素外，每个元素有唯一后继。树是一种层次结构，有且只有一个根结点，每个结点可以有多个子女，但只有一个双亲（根无双亲），从这个意义上说存在一（双亲）对多（子女）的关系。
  25. 求含有 n 个结点、采用顺序存储结构的完全二叉树中的序号最小的叶子结点的下标。要求写出简要步骤。
    根据完全二叉树的性质，最后一个结点（编号为n）的双亲结点的编号是[n/2](向下取整)，这是最后一个分枝结点，在它之后是第一个终端（叶子）结点，故序号最小的叶子结点的下标是[n/2](向下取整)+1。
  26. 设有正文 AADBAACACCDACACAAD,字符集为 A,B,C,D,设计一套二进制编码，使得上述正文的编码最短。
    字符A，B，C，D出现的次数为9,1,5,3。其哈夫曼编码如下A:1，B:000，C:01，D:001
    IT料理 27．设 T 是一棵二叉树，除叶子结点外，其它结点的度数皆为 2，若 T 中有 6 个叶结点，试问：
    （1）T 树的最大深度 Kmax=?最小可能深度 Kmin=?
    （2）T 树中共有多少非叶结点？
    (3) 若叶结点的权值分别为 1,2,3,4,5,6。请构造一棵哈曼夫树，并计算该哈曼夫树的带权路径长度wpl。
    （1）T树的最大深度Kmax=6（除根外，每层均是两个结点）
    T树的最小深度Kmin=4（具有6个叶子的完全二叉树是其中的一种形态）
    （2）非叶子结点数是5。（n2=n0-1）
    （3）哈夫曼树见下图，其带权路径长度wpl=51
    IT料理