软件技术树与二叉树习题1

习题十 一、 单项选择题 1．如图10.20所示二叉树的后序遍历序列是（  ）。 图10.20  一棵二叉树 A.abdefgc    B.dbgfeac      C.dbfgeac      D.dgfebca 2.设高度为h的二叉树上只有度为0和度为2的结点,则此类二叉树中所包含的结点数至少为:(    ) A.  2h        B.2h-1        C.2h+1        D.h+1  3.如图 10.21所示的二叉树是由森林转换过来的,此森林中有(    )个叶子结点. A.  4        B.  5        C.  6          D.  7 图10.21一棵二叉树 4.一棵满二叉树有M个树叶,N个结点,深度为H, 则  (      ) A.  n=h+m  B.  h+m=2n  C.m=h-1        D .n=2h-1 5.设 n,m为一棵二叉树上的两个结点,在中序遍历时, n 在m前的条件是(    ) A  n在m的右方                        B. n是m的祖先 C.  n在m的左方                        D. n是m的子孙 6.根据使用频率,为5个字符设计的哈夫曼编码不可能是(    ) A.111,110,10,01,00                        B. 000,001,010,011,1 C.100,11,10,1,0                          D.001,000,01,11,1o 7.森林F对应的二叉树为B,它有个结点m,B的根为p,p的右子树结点个数为n,森林中第一颗树的结点个数是(    ) A.m-n                                    B.m-n-1 C.n+1                                    D.条件不足,无法确定 8.深度为6 的二叉树的结点数个数为(    ) A.32                  B.33              C.63              D.64 9.若一棵二叉树具有10个度为2的结点,5个度为1的结点,则度为0的结点个数是(    ) A.9                    B.11              C.15              D.无法确定 二、 判断题 1. 完全深度二叉树一定存在度为1的结点 2. 深度为K的二叉树中的结点总数最多为2K-1个 3. 二叉树的遍历结果不是唯一的. 4. 一个树的叶子结点,在前序遍历和后序遍历下,皆以相同的位置出现. 5. 对一棵二叉树进行层次遍历时,应借助一个栈. 6. 由一棵二叉树的先序序列和后序序列可以唯一确定它. 7. 完全二叉树种,若一个结点没有左孩子,则它必定是树叶. 8. 一棵树中的叶子数一定等于与其对应的二叉树的叶子数。 9. 完全二叉树的存储结构通常采用顺序存储结构. 10. 将一棵树转换成二叉树，根结点没有左子树. 11. 一棵哈夫曼数的带权路径长度等于其所有分支结点的权值之和. 12. 当一棵具有个叶子结点的二叉树的WPL值为最小时,称这棵二叉树为哈夫曼树,且其二叉数的形状必是唯一的. 13. 哈夫曼树是带权路径长度最短的树,路径上权值较大的结点离根较近. 3、填空题 1. 二叉树由______,_______,_______三个基本单元组成. 2. 具有256个结点的完全二叉树的深度为______. 3. 一棵有n个结点的满二叉树有______个度为一的结点,由_______个分支(非终端)和                            ______个叶子,满二叉树的深度为______. 4. 设有n个结点的完全二叉树顺序存放在向量A[1..n]中，其下标值最大的分支结点为______. 5. 已知二叉树有50个叶子结点，则该二叉树的点数至少为__________. 6. 如果结点A有3个兄弟,B是A 的双亲,则B的度为_________ 7. 含4个度为2的结点和5个叶子结点的二叉树,可有________个度为1的结点. 8. 在有n（n〉1）个结点的各棵树中，深度最小的那棵树的深度是_______,它共有_____个叶子结点和_______个非叶子结点;深度最大的那棵树的深度是________,它共有_________个叶子结点和__________个非叶子结点. 9. 二叉树的先序序列和中序序列相同的条件是_________. 10. .一个无序序列可以构造一棵_______树而变成一个有序序列,构造树的过程即为对无序序列进行排列的过程. 11. 若一个二叉树的叶子结点是某棵树的中序遍历序列中的最后一个结点,则它必是该子树的________序列中的最后一个结点. 12. 若n0 为哈夫曼树的叶子结点数，则该哈夫曼共有_______个结点. 13. 若数据WG={ 7, 9, 2, 6, 32, 3, 21, 10},则所建哈夫曼树的树高是_______,带权路径长度WPL为__________. 参考 一． 单项选择题参考答案 1．D  2.B  3.C  4.D  5.C  6.C  7.A  8.C  9.B  10.D  11.D  12.B  13.C  14.A 15.C  16.C  17.D                                                                                                                  二. 判断题参考答案 1. 错误  完全二叉树不一定存在度为1的节点 2．正确 3．错误  二叉树的每一种遍历结果都是唯一的 4．正确 5．错误 对一棵二叉树进行层遍历时，应借助一个队列 6．错误 7．正确 8．错误 9．正确 10．错误 将一棵树转换成二叉树，根节点没有右子树 11．错误 一棵哈夫曼树的带权路径长度等于其所有终端节电的带权路径长度之和 12．错误 13．正确 三．填空题参考答案 1．根节点 ；左子树；右子树 2．9 3．0；n/2；n/2+1；［１ｂｎ＋１ 4．ｎ/2 5．99 6.  4 7.  若于 8． [1bn]+1;[n/2];[n/2];n;1;n-1 9.  该二叉树无左子树 10  二叉排序 11 先序 12．ｎ0-1 13  6;261